Proper data-structure and algorithm for 3-D Delaunay triangulation

I have worked out some poor code to achieve the goal of 3D Delauney triangulation(random points in E3), but the time consuming is huge, and when five points are exactly (or nearly due to the round-off error) on one sphere, my code can not handle this situation properly.

I use the basic data-structure which is a list of tetrahedrons and a list of points and a list of relationship of tetrahedrons with their neighborhood. The algorithm is incremental insertion.

Can somebody tell me which kinds of data-structures and algorithm should i prefer to? Can quad-edge data-structure be used in the situation ? When I read papers about this topic,I find that maybe this data-structure is not suitable for 3D application(strictly speaking, not suitable for 3D manifold application?I just know what is manifold yesterday, Please help me...). Is divide-conquer a better algorithm? Thanks!

• Welcome to SciComp. Your question looks legit for this forum. Maybe, you can work a bit on clarity and formatting of your post, what will improve the chances of getting a quick and instructive answer. – Jan Jun 14 '13 at 16:09
• Give Voro++ a try: math.lbl.gov/voro++ Its code is freely available (and modifiable) and I believe you can get the delaunay triangulation from it. (Or Zeo++ maciejharanczyk.info/Zeopp for more features). – Nick Jun 14 '13 at 18:30
• @Jan ,Sorry for my poor English, I finished these post with the help of dictionary, thanks for your post! – mengxia Jun 15 '13 at 5:10

This is implemented in qhull which is available from scipy (python). If you cannot use these implementations directly for some reason, the explanations of the data structures in the docs might be helpful.

http://www.qhull.org/

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

• The link you provided only has 2d examples. 3d data structure is significantly more difficult. – Shuhao Cao Jun 14 '13 at 20:44
• Also the qhull link you provided doesn't link to the data structure explanation page. By stackexchange standard, this is a typical -1 answer. – Shuhao Cao Jun 14 '13 at 20:46
• Hi , @ShuhaoCao ,can you tell me a better to implement 3D delaunay triangulation? – mengxia Jun 15 '13 at 5:03
• @clipper ,thanks for your post ,I will read the docs. – mengxia Jun 15 '13 at 5:05
• The important part is in the attributes section: points, simplices, neighbors, equations – meawoppl Jun 17 '13 at 18:32

The data structure in 3D is pure algebraic.

What you need to have is the following arrays:

• Vertex V: the vertices' coordinates for the mesh, a $(\# \text{ of vertices}) \times 3$ array, with each column being $x$-, $y$- and $z$-coordinates, and the row index corresponds to the index of that vertex.

• Element to Vertex E2V: the tetrahedral element to the vertex numbering, a $(\# \text{ of tetrahedra}) \times 4$ array. Each row represents a tetrahedron, and each column on that row is the index vertex(row number of this specific index in V) of that tetrahedron.

• Face to Vertex F2V: triangle faces to the vertex numbering, with a $(\# \text{ of faces}) \times 3$ array. Each row represents a face, and each column on that row is the index vertex(row number of this specific index in V) of that face.

• Edge to Vertex F2V: edge to the vertex numbering, with a $(\# \text{ of edges}) \times 2$ array. Each row represents an edge, and each column on that row is the index vertex(row number of this specific index in V) of that edge.

First two are necessary data structure, all other array can be generated from the first two using algebraic operations. Other notable arrays are Element to Edge, Face to Edge, Vertex to Element(the elements sharing a vertex), Face to Element(the elements sharing a face), Edge to Face(the faces sharing an edge), etc.

The implementation of 3D Delaunay triangulation does not sound as trivial as the other answer said. Depends on your software of interest, I may update my answer more.

• Thanks for your post,the data structure I have used was almost the same with what you said above.I found it was difficult to determine the adjacent relationship of the tetrahedral .The algorithm I used was incremental insertion and this time i want to try a better way.. sorry for my poor English. – mengxia Jun 15 '13 at 4:59
• What kind of adjacency relationship do you mean? Do you want to be able to find all tetrahedra which are neighbors of a given tetrahedron? Or do you want to find which nodes are neighbors of a given node? – Daniel Shapero Jun 15 '13 at 12:43
• @mengxia Have you got that Face to Element array? If you have that then the neighbor elements is relatively easy to find. – Shuhao Cao Jun 15 '13 at 19:08
• HI,@DanielShapero ,thanks for your post,I want to find the relationship of the tetrahedron – mengxia Jun 17 '13 at 10:04
• Hi，@ShuhaoCao ，I have finished my code and the arrays i prefered were V,E2V,E2f(elements to face),E2N(element to their neibors),but there wasn't a edge array .the code runs inefficiently and memory costly .what the usage of the edge array? if I use this array ,would my code speed up or more efficient? Thanks! – mengxia Jun 24 '13 at 14:58