Delaunay triangulation

0
votes

I read this http://en.wikipedia.org/w/index.php?title=Delaunay_triangulation&oldid=626189710 article on wikipedia but I can't make quite sense of it. In case of 2 dimensional euclidean space (I think I) understand what it is about.

My problem starts when it comes to higher dimensions. As I interpret what I read, in 3d this is not a triangulation (of a 2D surface) but rather a tetrahedron-ization (of the 3D convex hull), is this correct?

And the Delaunay triangulation of a 2D surface in 3D would be the set of those triangles of those tetrahedrons that lie on the surface?

If so, is there an easier or more efficient algorithm when I'm only interested in the surface triangles?

1
algorithmmathcomputational-geometrytriangulation
They call it tetrahedrization. I am not sure that the Delaunay triangulation of a surface is something defined, because you are lacking the surface definition. You can indeed use the convex hull of the point cloud, but it will not pass through all given points. You may have a look at 3D alpha-shapes. doc.cgal.org/latest/Alpha_shapes_3/index.html – Yves Daoust
In higher dimensions you are looking at a simplex. – Nuclearman

1 Answers

0
votes

You are correct but you can use any triangulation. A dt has special properties also in 2d and 3d. Its not so complicated start with simple algorithm like the bowyer-watson. You need also a super triangle. In fact Cgal uses a bowyer-watson.