Polygon triangulação com buracos

Question

Eu estou procurando um algoritmo ou biblioteca (melhor) para quebrar um polígono em triângulos. Eu estarei usando estes triângulos em um aplicativo Direct3D. Quais são as melhores opções disponíveis?

Aqui está o que eu encontrei até agora:

1. notas de Ben Discoe
2. FIST: Rápido de força industrial Triangulação de polígonos
3. Eu sei que CGAL fornece triangulação, mas não tenho certeza se ele suporta buracos.

Eu realmente aprecio algumas opiniões de pessoas com experiência prévia nesta área.

Edit:. Este é um polígono 2D

Answer 1

biblioteca Triângulo de Jonathan Shewchuk é fenomenal; Eu usei-o para automatizar triangulação no passado. Você pode pedir-lhe para tentar evitar triângulos pequenos / estreitas, etc., de modo que você venha com "boas" triangulações em vez de apenas qualquer triangulação.

Answer 2

Para dar-lhe mais algumas opções de bibliotecas lá fora:

Polyboolean. Eu nunca tentei este, mas parece promissor: http: //www.complex-a5. ru / polyboolean / index.html

General Polygon Clipper. Este funciona muito bem na prática e faz triangulação, bem como buracos de recorte e buracos: http://www.cs.man.ac.uk/~toby/alan/software/

A minha recomendação pessoal: Use o tesselation da GLU (Utility biblioteca OpenGL). O código é rocha sólida, mais rápido do que a GPC e gera menos triângulos. Você não precisa de um OpenGL-Handle inicializado ou nada parecido com isso para usar o lib.

Se você não gosta da idéia de incluir libs sistema OpenGL em um aplicativo DirectX existe uma solução bem: Basta baixar o código de implementação de referência SGI OpenGL e levante a triangulador dele. Ele só usa os nomes OpenGL-typedef e uma mão cheia de enums. É isso aí. Você pode extrair o código e fazer um stand alone lib em uma ou duas horas.

---

Em geral, meu conselho seria usar algo que alreay obras e não começar a escrever o seu próprio triangulação.

É tentador para rolar seus próprios se você leu sobre a orelha-grampeamento ou algoritmo-line varredura, mas o fato é que os algoritmos de geometria computacional são incríveis difícil escrever de uma forma que eles trabalham estável, não bater e sempre retorno um resultado significativo. erros de arredondamento numérico irá acumular e matá-lo no final.

Eu escrevi um algoritmo de triangulação em C para a empresa que eu trabalho com. Obtendo o trabalho algoritmo núcleo levou dois dias. Fazê-lo funcionar com todos os tipos de entradas degeneradas levou mais dois anos (eu não estava trabalhando em tempo integral sobre ele, mas confia em mim - eu passei mais tempo com ele do que eu deveria ter).

Answer 3

CGAL tem a ferramenta que você precisa: Constrained Triangulações

Você pode simplesmente fornecer limites de seu polígono (incuding os limites dos buracos) como restrições (o melhor seria que você inserir todos os vértices, e especifique as restrições como pares de Vertex_handles).

Você pode então marcar os triângulos da triangulação por qualquer algoritmo de passagem: começar com um incidente de triângulo para o vértice infinito e tag-lo como sendo de fora, e cada vez que você cruza uma restrição, mude para o tag oposto (no interior se foram previamente marcar os triângulos como estranho, fora se você estivesse marcação triângulos como insider antes).

Answer 4

Eu descobri a biblioteca poly2tri ser exatamente o que eu precisava para triangulação. Ela produz uma malha muito mais limpo do que outras bibliotecas que eu tentei (incluindo libtess), e ele faz buracos de apoio também. Tem sido convertido a um grupo de idiomas. A licença é New BSD , para que você possa usá-lo em qualquer projeto.

biblioteca Poly2tri no Google Code

Answer 5

Você pode adicionar os buracos de forma relativamente fácil a si mesmo. Basicamente triangular para o casco convexo dos pontos de entrada, como por CGAL, e, em seguida, eliminar qualquer triângulo cujos mentiras incentro dentro de qualquer um dos polígonos furo (ou fora de qualquer dos limites externos). Ao lidar com muitos buracos em um grande conjunto de dados, técnicas de mascaramento pode ser usado para significativamente acelerar este processo.

editar: Uma extensão comum desta técnica é a triângulos fracos de plantas daninhas sobre o casco, em que o lado maior ou menor ângulo interno for superior a um determinado valor. Isto irá formar um casco melhor côncava.

Answer 6

Tente libtess2

https://code.google.com/p/libtess2/downloads/list

baseado no tesselator SGI GLU original (com licenciamento liberal). Resolve alguns problemas de gerenciamento de memória em torno de lotes de pequenas mallocs.

Answer 7

Este é um problema comum em análise de elementos finitos. É chamado de "geração de malha automático". Google encontrou neste site com links para fonte comercial e aberto Programas. Eles geralmente presumem algum tipo de representação CAD da geometria para começar.

Answer 8

Outra opção (com uma licença muito flexível) é a porta do algoritmo de VTK:

vtkDelaunay2D

Este algoritmo funciona razoavelmente bem. Usá-lo diretamente é possível, mas requer links para VTK, que podem ter mais sobrecarga do que você quer (embora tenha muitas outras características interessantes, bem).

Ele suporta restrições (furos / fronteiras / etc), bem como a triangulação uma superfície que não é, necessariamente, no plano XY. Ele também suporta algumas características que eu não tenha visto em outros lugares (veja as notas sobre os valores alfa).

Answer 9

Eu tenho implementado um 3D polígono triangulador em C # usando o método de recorte orelha. É fácil de usar, suporta buracos, é numericamente robusta e suportes aribtrary (não auto-interseção) convexo / polígonos não convexos.