Builds a delaunay triangulation using the divide-and-conquer algorithm. More...
Public Member Functions | |
| IMesh | Triangulate (IList< Vertex > points, Configuration config) |
| Form a Delaunay triangulation by the divide-and-conquer method. | |
| IMesh | Triangulate (IList< Vertex > points, Configuration config) |
| Triangulates a point set. | |
Public Attributes | |
| bool | UseDwyer = true |
Detailed Description
Builds a delaunay triangulation using the divide-and-conquer algorithm.
The divide-and-conquer bounding box
I originally implemented the divide-and-conquer and incremental Delaunay triangulations using the edge-based data structure presented by Guibas and Stolfi. Switching to a triangle-based data structure floatd the speed. However, I had to think of a few extra tricks to maintain the elegance of the original algorithms.
The "bounding box" used by my variant of the divide-and-conquer algorithm uses one triangle for each edge of the convex hull of the triangulation. These bounding triangles all share a common apical vertex, which is represented by NULL and which represents nothing. The bounding triangles are linked in a circular fan about this NULL vertex, and the edges on the convex hull of the triangulation appear opposite the NULL vertex. You might find it easiest to imagine that the NULL vertex is a point in 3D space behind the center of the triangulation, and that the bounding triangles form a sort of cone.
This bounding box makes it easy to represent degenerate cases. For instance, the triangulation of two vertices is a single edge. This edge is represented by two bounding box triangles, one on each "side" of the edge. These triangles are also linked together in a fan about the NULL vertex.
The bounding box also makes it easy to traverse the convex hull, as the divide-and-conquer algorithm needs to do.
Member Function Documentation
◆ Triangulate()
|
inline |
Form a Delaunay triangulation by the divide-and-conquer method.
- Returns
Sorts the vertices, calls a recursive procedure to triangulate them, and removes the bounding box, setting boundary markers as appropriate.
Implements TriangleNet.Meshing.ITriangulator.
The documentation for this class was generated from the following file:
- C:/Transhuman/S2/Assets/Plugins/TriangleNet/Scripts/Source/Meshing/Algorithm/Dwyer.cs
