Estrutura de dados e algoritmo adequados para triangulação 3D em Delaunay

Elaborei um código ruim para atingir a meta da triangulação 3D Delauney (pontos aleatórios no E3), mas o tempo gasto é enorme e quando cinco pontos são exatamente (ou quase devido ao erro de arredondamento) em uma esfera, meu código não consegue lidar com essa situação corretamente.

Uso a estrutura de dados básica, que é uma lista de tetraedros e uma lista de pontos e uma lista de relacionamento dos tetraedros com a vizinhança. O algoritmo é de inserção incremental.

Alguém pode me dizer que tipos de estruturas de dados e algoritmo devo preferir? A estrutura de dados quad-edge pode ser usada na situação? Quando leio artigos sobre esse tópico, acho que talvez essa estrutura de dados não seja adequada para aplicativos 3D (a rigor, não é adequada para aplicativos de coletores 3D? Só sei o que é coletores ontem, por favor me ajude ...). Dividir-conquistar é um algoritmo melhor? Obrigado!

Isso é implementado no qhull, que está disponível no scipy (python). Se você não puder usar essas implementações diretamente por algum motivo, as explicações das estruturas de dados nos documentos podem ser úteis.

http://www.qhull.org/

http://docs.scipy.org/doc/scipy/reference/generated/scipy.spatial.Delaunay.html#scipy.spatial.Delaunay

A estrutura de dados em 3D é pura algébrica.

O que você precisa é das seguintes matrizes:

• Vertex V$(\# \text{ of vertices}) \times 3$$x$$y$$z$

• Element to Vertex E2V$(\# \text{ of tetrahedra}) \times 4$V

• Face to Vertex F2V$(\# \text{ of faces}) \times 3$V

• Edge to Vertex F2V$(\# \text{ of edges}) \times 2$V

Os dois primeiros são a estrutura de dados necessária ; todos os outros vetores podem ser gerados a partir dos dois primeiros usando operações algébricas. Outras matrizes são notáveis Element to Edge, Face to Edge, Vertex to Element(os elementos que partilham um vértice), Face to Element(os elementos que partilham uma face), Edge to Face(as faces que partilham uma aresta), etc.

A implementação da triangulação 3D Delaunay não parece tão trivial quanto a outra resposta. Depende do seu software de interesse, posso atualizar minha resposta mais.