Триангуляция многоугольника, соответствующего свойству Делоне

Я хочу триангулировать многоугольник (без самопересечения, но с дырками, и многоугольник тоже может быть вогнутым). В этом вопросе (например): Делоне триангулирует двумерный многоугольник с отверстиями предлагается ограниченная триангуляция Делоне. Что меня интересовало: это лучший способ сделать это или это как «кувалдой расколоть орех»? Альтернативой может быть использование алгоритма для создания «нормальной» триангуляции (например, разделение многоугольника на y-монотонные части и триангуляция этих частей) и последующее переворачивание ребер. Но похоже, что (почти) никто не принимает это решение. Есть ли причина? Каковы плюсы и минусы одного из этих решений? (многоугольники могут иметь произвольный размер)


polygon delaunay triangulation
person Infinity    schedule 08.04.2015    source источник
comment
Все, что вам нужно, это EarClipping, перейдите по этой ссылке.   -  person abenci    schedule 09.04.2015
comment
Спасибо. Но я думал, что сложность отсечения ушей O(n^2)? Извините, я немного запутался, как лучше всего решить мою проблему.   -  person Infinity    schedule 09.04.2015
comment
И после обрезки ушей я просто легализую края, чтобы они соответствовали свойству Делоне?   -  person Infinity    schedule 09.04.2015
comment
Отсечение ушей может триангулировать любой многоугольник с любым количеством отверстий, единственное требование состоит в том, чтобы многоугольники не перекрывались. Нет причин использовать Делоне, если в качестве входных данных у вас есть только контуры.   -  person abenci    schedule 10.04.2015

Ответы (2)


arrow_upward
1
arrow_downward

Есть несколько причин предпочесть (ограниченные) триангуляции Делоне другим подходам:

  1. В R^2 можно доказать, что такая триангуляция является «лучшим» способом триангуляции заданной геометрии — в результате получается триангуляция, максимизирующая минимальный угол. Это равносильно получению треугольников оптимального качества без каких-либо «худых» элементов.

  2. Формирование триангуляции Делоне эффективно (т.е. O(n*log(n)) в R^2).

  3. Алгоритмы триангуляции Делоне на практике надежны и эффективны. Существует ряд очень качественных реализаций, таких как Triangle и CGAL.

  4. Триангуляции Делоне обобщаются на многомерные задачи (например, тетраэдры в R^3 и общие симплексы в R^d).

  5. Триангуляции Делоне индуцируют ортогональный двойственный комплекс (то есть диаграмму Вороного). Это может быть важно для некоторых классов численных методов.

В зависимости от того, чего именно вы хотите достичь, вы можете найти один или несколько из этих критериев убедительными. Другие варианты, такие как отсечение ушей или триангуляция монотонных плит, могут быть конкурентоспособными в некоторых областях, но, IMO, не демонстрируют такой же общей производительности.

person Darren Engwirda    schedule 09.04.2015

arrow_upward
0
arrow_downward

Вы можете попробовать альфа-формы. Он определяется как триангуляция Делоне без ребер, превышающих альфа.

person Gigamegs    schedule 08.04.2015
comment
Не могли бы вы объяснить мне, как я могу реализовать это с помощью альфа-форм? Я подумал, что альфа-формы хороши, если у меня есть облако точек и я хочу получить форму этих точек. Но в моем случае у меня есть точки (вершины многоугольника) и ребра. Таким образом, я подумал, что должен использовать Constrained Delaunay или алгоритм для триангуляции многоугольника и последующего легализации ребер. А для произвольного полигона не сложно найти нужную альфу? (Некоторые ребра многоугольника могут быть довольно короткими, другие — более длинными) - person Infinity; 08.04.2015
comment
@Infinity: Может быть, вы можете удалить ребра внутри отверстий и аппроксимировать? - person Gigamegs; 09.04.2015
comment
Вы имеете в виду использование альфа-форм для удаления краев? Но как бы вы начали получать первую триангуляцию? Использование триангуляции Делоне с ограничениями? - person Infinity; 09.04.2015