8
$\begingroup$

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!

Improve this question
$\endgroup$
3
  • 1
    $\begingroup$ 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. $\endgroup$
    – Jan
    Jun 14, 2013 at 16:09
  • $\begingroup$ 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). $\endgroup$
    – Nick
    Jun 14, 2013 at 18:30
  • $\begingroup$ @Jan ,Sorry for my poor English, I finished these post with the help of dictionary, thanks for your post! $\endgroup$
    – mengxia
    Jun 15, 2013 at 5:10

2 Answers 2

Reset to default
4
$\begingroup$

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

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

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.

Improve this answer
$\endgroup$
6
  • $\begingroup$ 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. $\endgroup$
    – mengxia
    Jun 15, 2013 at 4:59
  • $\begingroup$ 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? $\endgroup$
    – Daniel Shapero
    Jun 15, 2013 at 12:43
  • $\begingroup$ @mengxia Have you got that Face to Element array? If you have that then the neighbor elements is relatively easy to find. $\endgroup$
    – Shuhao Cao
    Jun 15, 2013 at 19:08
  • $\begingroup$ HI,@DanielShapero ,thanks for your post,I want to find the relationship of the tetrahedron $\endgroup$
    – mengxia
    Jun 17, 2013 at 10:04
  • $\begingroup$ 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! $\endgroup$
    – mengxia
    Jun 24, 2013 at 14:58

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

Not the answer you're looking for? Browse other questions tagged or ask your own question.