Estructura de datos y algoritmo adecuados para la triangulación 3D de Delaunay

He elaborado un código pobre para lograr el objetivo de la triangulación 3D Delauney (puntos aleatorios en E3), pero el tiempo es enorme, y cuando cinco puntos son exactamente (o casi debido al error de redondeo) en una esfera, mi código no puede manejar esta situación correctamente.

Utilizo la estructura de datos básica que es una lista de tetraedros y una lista de puntos y una lista de relación de tetraedros con su vecindario. El algoritmo es la inserción incremental.

¿Alguien puede decirme qué tipo de estructuras de datos y algoritmo debería preferir? ¿Se puede utilizar la estructura de datos de cuatro filos en la situación? Cuando leo documentos sobre este tema, encuentro que tal vez esta estructura de datos no es adecuada para la aplicación 3D (estrictamente hablando, ¿no es adecuada para la aplicación múltiple 3D? Solo sé lo que fue múltiple ayer, por favor ayúdenme ...). ¿Es dividir-conquistar un mejor algoritmo? ¡Gracias!

Esto se implementa en qhull, que está disponible desde scipy (python). Si no puede usar estas implementaciones directamente por alguna razón, las explicaciones de las estructuras de datos en los documentos pueden ser útiles.

http://www.qhull.org/

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

La estructura de datos en 3D es puramente algebraica.

Lo que necesita tener son las siguientes matrices:

• 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

Los dos primeros son la estructura de datos necesaria , todos los demás arreglos se pueden generar a partir de los dos primeros mediante operaciones algebraicas. Otras matrices notables son Element to Edge, Face to Edge, Vertex to Element(los elementos que comparten un vértice), Face to Element(los elementos que comparten una cara), Edge to Face(las caras que comparten un borde), etc.

La implementación de la triangulación 3D Delaunay no suena tan trivial como dice la otra respuesta. Depende de su software de interés, puedo actualizar mi respuesta más.