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

8

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!

mengxia
fonte
1
Bem-vindo ao SciComp. Sua pergunta parece legítima para este fórum. Talvez você possa trabalhar um pouco na clareza e formatação de sua postagem, o que aumentará as chances de obter uma resposta rápida e instrutiva.
Jan
Experimente o Voro ++: math.lbl.gov/voro++ Seu código está disponível gratuitamente (e modificável) e acredito que você pode obter a triangulação delaunay a partir dele. (Ou Zeo ++ maciejharanczyk.info/Zeopp para mais recursos).
Nick
@ Jan, desculpe pelo meu péssimo inglês, terminei este post com a ajuda do dicionário, obrigado pelo seu post!
mengxia

Respostas:

4

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

tosquiadeira
fonte
O link que você forneceu possui apenas exemplos 2d. A estrutura de dados 3D é significativamente mais difícil.
Shuhao Cao
Além disso, o link qhull que você forneceu não está vinculado à página de explicação da estrutura de dados. Pelo padrão stackexchange, essa é uma resposta típica de -1.
Shuhao Cao
Oi, @ShuhaoCao, você pode me dizer um melhor para implementar a triangulação 3D delaunay?
mengxia
@ Clipper, obrigado pelo seu post, vou ler os documentos.
mengxia
A parte importante está na seção de atributos: pontos, simplicidades, vizinhos, equações
meawoppl
0

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

O que você precisa é das seguintes matrizes:

  • Vertex V(# of vertices)×3xyz

  • Element to Vertex E2V(# of tetrahedra)×4V

  • Face to Vertex F2V(# of faces)×3V

  • Edge to Vertex F2V(# of edges)×2V

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.

Shuhao Cao
fonte
A partir de agora, você terá acesso a todas as informações necessárias para a obtenção do certificado de conclusão do ensino médio, além de um certificado de conclusão do ensino médio, além de certificado de conclusão do ensino médio. melhor maneira .. desculpe pelo meu pobre inglês.
mengxia
Que tipo de relacionamento de adjacência você quer dizer? Deseja encontrar todos os tetraedros vizinhos de um determinado tetraedro? Ou você deseja descobrir quais nós são vizinhos de um determinado nó?
Daniel Shapero
@mengxia Você tem essa matriz Face to Element? Se você tiver isso, os elementos vizinhos serão relativamente fáceis de encontrar.
Shuhao Cao
Oi, @ DanielShapero, obrigado por seu post. Quero encontrar o relacionamento do tetraedro
mengxia
Oi , @ ShuhaoCao , Eu terminei meu código e as matrizes que eu preferia eram V, E2V, E2f (elementos para enfrentar), E2N (elemento para seus neibors), mas não havia uma matriz de borda. O código é executado de forma ineficiente e memória caro. qual o uso da matriz de borda? se eu usar essa matriz, meu código aceleraria ou seria mais eficiente? Obrigado!
mengxia