Algoritmos para triangulação de polígonos

9

Foi difícil encontrar algoritmos ou publicar artigos sobre a triangulação de polígono com interseção automática (também polígono com estrutura de orifícios).

Alguém pode me orientar a encontrar artigos / algoritmos publicados, por favor?

PS: alguém marcar essa pergunta adequadamente, por favor, não tenho pontos de reputação suficientes para fazê-lo.

ds.algorithms reference-request cg.comp-geom Prashant Cholachagudda
fonte
5
Talvez sua ênfase esteja no aspecto de auto-interseção de seus polígonos? A maioria dos algoritmos (como sugerido por Suresh) assume um polígono simples. Primeiro você terá que calcular os pontos de interseção nas auto-travessias, via, por exemplo, uma varredura de avião. Então você pode aplicar o algoritmo de Seidel.
Joseph O'Rourke

Respostas:

7

Você já considerou o algoritmo de Seidel ?

Suresh Venkat
fonte
O algoritmo de Seidel, embora muito rápido, precisa de modificação para lidar com auto-interseções. Não é impossível, mas não é imediatamente óbvio.
Simon F
1

Eu acho que você pode olhar http://sigbjorn.vik.name/projects/Triangulation.pdf, que foi o primeiro resultado do google para "algoritmo de triangulação com polígonos auto-interceptáveis", primeiro ele discutirá sobre o algoritmo de Seidel e sua implementação e, em seguida, generalizará em "5.2 Intersecções" fala sobre polígonos que se interceptam.

Saeed
fonte