Search code examples
c++geometrytriangulationcgal

CGAL: Difference between normal and weighted 3D triangulation


For a set of 3D points, all of them specified by their cartesian coordinates, what is the main difference in CGAL between its 3D Delaunay triangulation and its weighted (as depicted here) or regular 3D triangulation?


Solution

  • As you know, given a set of points, there exist many triangulations defined over this set of points. The Delaunay triangulation is the one such that for each tetrahedron, the circumscribed sphere does not contain any other points but the vertices of the tetrahedron. It is unique if no more than 4 points are co-spherical. A regular triangulation uses the weight associated each point to define a similar emptiness criteria as described on this page using the power of a weighted point. In particular, in a regular triangulation, a point might be hidden (does not appear in the triangulation with an associated vertex), if it is not on the convex hull and if its weight is too small compared to its neighbors.