0

Привожу текст пользователя sercxjo (https://ru.stackoverflow.com/a/167434/177188)

  1. Если число вершин <= 3 разбиение закончено
  2. Выбраем первую вершину как текущую (N)
  3. Если из неё нельзя провести диагональ внутри многоугольника к точке N+2, то теущей становится следующая и т.д. по кольцу. Думаю можно доказать что этот цикл не бесконечен.
  4. "Отрезаем" треугольник от многоугольника, вершин становится на одну меньше за счёт исключения вершины N+1.
  5. Переходим к пункту 1

Наверно удобно использовать связный список.

Определение проходит ли диагональ внутри многоугольника.

Заранее определим в каком направлении задан многоугольник - по или против часовой стрелки. Далее если треугольник N N+1 N+2 обходится в противоположном направлении, значит наша диагональ снаружи - не подходит. В противном случае возможен ещё вариант когда диагональ оказывается снаружи полностью или частично по вине других внутренних углов.

Для точек N+3 и N-1 нужно проверить, чтобы эти углы при этих вершинах были больше чем соответствующие углы отрезаемого треугольника. Т.е. вершина лежит по другую сторону от диагонали относительно вершины N+1, либо угол при вершине больше развёрнутого.

Для оставшихся сторон нужно проверить не пересекают ли они данную диагональ.

Определение направления обхода многоугольника

Проводим из одной вершины A1 вектора ко всем остальным A1->A2, A1->A3, ... A1->AN. Считаем сумму N-1 векторных произведений соседних векторов по порядку, нас интереует только координата z. Эта сумма по модулю равна удвоенной площади фигуры, а знак указывает направление обхода.

===========================================

Не понятны вот эти слова:

В противном случае возможен ещё вариант когда диагональ оказывается снаружи

Для точек N+3 и N-1 нужно проверить, чтобы эти углы при этих вершинах были больше чем соответствующие углы отрезаемого треугольника. Т.е. вершина лежит по другую сторону от диагонали относительно вершины N+1, либо угол при вершине больше развёрнутого.

Для оставшихся сторон нужно проверить не пересекают ли они данную диагональ.полностью или частично по вине других внутренних углов.

Т.к. эта проверка не выполняется, очень сложные фигуры обрабатываются не верно.

Объясните это, пожалуйста, другими словами.

18
  • Я проверяю треугольник (v,v+1,v+2). Мне нужно сложить углы (v) и (v+2) в этом треугольнике и сравнить с углами треугольника (v-1,v+1,v+3) соответственно (v-1) и (v+3)?
    – Keefred
    18 сен 2016 в 21:54
  • Имеется в виду ещё случай когда диагональ сначала идёт внутри, но пересекается другими сторонами завёрнутыми внутрь многоугольника. Нужно найти точку пересечения диагонали с каждой из сторон, кроме прилежащих к вершине-кандидату на отсекание и двух соседних и посмотреть принадлежит ли она отрезку, т.е пересекаются ли отрезки.
    – sercxjo
    18 сен 2016 в 21:58
  • 1
    проще наверно нарисовать
    – sercxjo
    18 сен 2016 в 22:00
  • Я предполагал такую проверку, но надеялся на другой метод, так как из процитированных слов понял то, что написал на 2 коммента выше. Так прибавиться много вычислений( Но видимо без этого никак. Вам, sercxjo, спасибо от души. Ваше объяснение лучше из того что видел) Простое такое, человеческое) Респект!
    – Keefred
    18 сен 2016 в 22:04
  • Не надо рисовать) Я видел эти фигуры, когда "диагональ сначала идёт внутри, но пересекается другими сторонами завёрнутыми внутрь многоугольника"
    – Keefred
    18 сен 2016 в 22:05

1 ответ 1

1

Если многоугольник выпуклый, то его триангуляция тривиальна.
Невыпуклые многоугольники отличаются от выпуклых всего лишь одним свойством - наличием углов, превышающих развёрнутый (180 градусов). Поскольку в треугольнике такой угол невозможен, проще всего связать с ним треугольную выемку. Для практических задач (расчёт площадей, моментов, центра тяжести и т.п.) доработка алгоритмов под возможность учёта выемок не выглядит сложной.

Важное свойство выемок - то, что они не пересекаются. И если "отрезать" выемки в порядке убывания "вогнутого" угла, то процесс представления невыпуклого многоугольника в виде выпуклого многоугольника и множества треугольных выемок проблем не вызывает.

Если требуется именно классическая триангуляция, то можно сформировать множество треугольников и множество выемок и для каждого треугольника рассчитывать пересечения с каждой выемкой. При наличии изменений - удалять исходный треугольник и дописывать результат в конец списка треугольников.

введите сюда описание изображения

Повторные циклы при этом не нужны, а функция вычитания треугольников несложна (у треугольника нет диагоналей) и пишется один раз.

8
  • И как это представление нам помогает построить триангуляцию? 7 фев 2018 в 22:54
  • @AnT Это помогает построить триангуляцию, использующую операции объединения и разности множеств (треугольников). Можно, конечно, доработать алгоритм под триангуляцию объединением (с треугольниками ситуация попроще), но для более общей задачи это обычно не требуется. 7 фев 2018 в 23:21
  • Но как именно? Хоть автор не говорит этого явно, но по-видимому ему нужна классическая триангуляция - построенная на исходных вершинах многоугольника. Как получить такую триангуляцию из "представления невыпуклого многоугольника в виде выпуклого многоугольника и множества треугольных выемок"? Да, впрочем, и любую триангуляцию... "Объединение и разность" каких множеств треугольников мы будем делать? 7 фев 2018 в 23:24
  • О какой именно паре "треугольник - выемка" идет речь? 7 фев 2018 в 23:39
  • @AnT Речь обо всех возможных парах классических треугольников и треугольных выемок. 7 фев 2018 в 23:43

Ваш ответ

Нажимая на кнопку «Отправить ответ», вы соглашаетесь с нашими условиями использования и подтверждаете, что прочитали и поняли наши политику конфиденциальности и нормы поведения.

Всё ещё ищете ответ? Посмотрите другие вопросы с метками или задайте свой вопрос.