Алгоритмы триангуляции полигонов

9

Мне было трудно найти алгоритм или опубликовать статьи о триангуляции самопересекающегося многоугольника (также многоугольника со структурой дырок).

Может, кто-нибудь поможет мне найти опубликованную статью / алгоритм, пожалуйста?

PS: кто-то пометит этот вопрос соответствующим образом, пожалуйста, мне не хватает очков репутации, чтобы сделать это.

ds.algorithms reference-request cg.comp-geom Прашант Чолачагудда
источник
5
Возможно, ваш акцент делается на самопересекающихся аспектах ваших полигонов? Большинство алгоритмов (таких, как предлагает Суреш) предполагают простой многоугольник. Сначала вам нужно будет вычислить точки пересечения при самопересечении, например, с помощью развертки плоскости. Тогда вы можете применить алгоритм Зайделя.
Джозеф О'Рурк

Ответы:

7

Рассматривали ли вы алгоритм Зайделя ?

Суреш Венкат
источник
Алгоритм Зайделя, хотя и очень быстрый, нуждается в модификации для обработки самопересечений. Это не невозможно, но не сразу очевидно.
Simon F
1

Я думаю, что вы можете посмотреть на http://sigbjorn.vik.name/projects/Triangulation.pdf, который был первым результатом Google для "самопересекающегося алгоритма триангуляции многоугольника". Сначала он обсудит алгоритм Сайдела и его реализацию, а затем обобщит его. в «5.2 Пересечения» говорится о самопересекающихся многоугольниках.

Saeed
источник