Constrained Delaunay triangulation and the triangulation of a polygon
A plain Delaunay triangulation (ADR 0029) knows only points: it puts its edges where the empty-circle rule says, wherever the real world has a ridge, a ditch, a bank or a parcel boundary. A terrain model needs break lines, edges that must be part of the triangulation, and the triangles must still be as good as the constraints allow. The same machine gives the triangles inside a polygon: constrain its rings and keep what lies inside. That is what rendering, area decomposition and a mesh of a boundary need. Both are made by Triangulation (ADR 0037): FromPointsAndLines and FromPolygon, and Triangulate for a polygon as a flat list of triangles.
German version: 0038-constrained-delaunay-und-polygon-triangulierung.de.md
Consequences
Placement: the static methods
Triangulation.FromPointsAndLinesandTriangulation.FromPolygon, and the extension methodShapes.Triangulate(IPolygon2D), inSpatialNET.Extensions, namespaceSpatialNET. The result is theTriangulationof ADR 0037, withIsConstrainedandConstrainedEdgesto tell the constraints. For the package validation and the API tracking this is an addition only (ADR 0028).API:
static Triangulation FromPointsAndLines(IGeometry2D points, IGeometry2D lines, IGeometryFactory? factory = null, double? gridSize = null) static Triangulation FromPolygon(IPolygon2D polygon, IGeometryFactory? factory = null, double? gridSize = null) static IReadOnlyList<IPolygon2D> Triangulate(this IPolygon2D polygon, IGeometryFactory? factory = null, double? gridSize = null)The
linesare polylines (every segment is kept) or polygons (every edge of every ring is kept); points and multipoints add their vertices as points only. The vertices of the lines are vertices of the triangulation, so a break line needs no extra points.factoryandgridSizematter only if constraints cross (below).What is kept. Every segment of the constraints is a chain of edges of the triangulation. A constraint that passes exactly through a vertex is split there (the vertex is on the line, so the line is kept as two edges). Constraints may touch each other, share end points and overlap collinearly, and a constraint may be given twice; they collapse to the same edges. The triangulation tiles the convex hull of all vertices, and every edge that is not a constraint is locally Delaunay (checked in the tests for every triangle).
Crossing constraints are noded. Two constraints that cross in a point that is the end of neither cannot both be edges. Then all constraints are first noded like the lines of an overlay (
Union, ADR 0005): the crossing becomes a vertex, and all constraints are rounded to the grid (gridSize, as for the overlays), which can move their vertices by up to half of it. This is the same rule as everywhere else in the library, and it is applied only if a crossing exists: without one the constraints are used exactly as they are, with no rounding. Crossings are detected exactly (the orientation test of ADR 0005, over a spatial index of the segments), so the noding is never skipped by rounding. A factory is needed only for the noding (InvalidOperationExceptionif there is none);gridSizethat is not finite or not greater than 0 is anArgumentOutOfRangeException.Algorithm (internal). The Delaunay triangulation of all vertices (ADR 0029) is made first. Each constraint is then inserted by Sloan's edge flipping (1993): the edges that the segment crosses are found by walking along it, and flipped one by one (a flip is possible only if the quadrilateral is convex, otherwise the edge waits) until the segment is an edge. A last pass flips every edge that is not a constraint and not locally Delaunay until none is left (Lawson flipping; a triangulation that contains the constraints ends in the constrained Delaunay triangulation). Every decision uses the exact predicates
Orient2DandInCircle(ADR 0029), so the result is a valid triangulation for any input, and a constraint is never lost to rounding. Constraints are remembered by their vertex pair, so a flip, which renumbers the half-edges, cannot confuse them. Points that lie on a common circle allow several constrained Delaunay triangulations, as in ADR 0029.FromPolygontriangulates the polygon with its rings as constraints and keeps the triangles inside. A valid polygon (a first ring with holes inside it, all vertices different, no ring touching or crossing another or itself; collinear vertices may leave no ear) takes the fast path described under Speed, which gives the same triangles; every other input takes the general path below. The inside is decided from the outside of the hull by the even-odd rule: a triangle next to the hull is outside unless the hull edge is a ring, and crossing a ring toggles inside and outside. So holes are left out, and an invalid polygon (rings that cross or touch) is read the wayMakeValidreads it (ADR 0020); a bow tie gives its two triangles. A polygon without holes and withnvertices hasn − 2triangles, every hole adds two (no vertex is added: this is a triangulation of the polygon's own vertices, not a mesh with added points). Every edge of a ring is an edge of a triangle (IsConstrained), and the triangles that lie at the border have −1 as their neighbour there. A polygon with fewer than three different vertices or only collinear ones has no triangles.TriangulateisFromPolygon(...).ToPolygons(...): the triangles as a flat list of polygons likeDelaunayTriangles, but in the order of their ids.Z. The vertices carry the Z of the points they come from; a vertex that is a vertex of a line and a point takes the Z of the first that has one (the points first). The vertices created by noding have Z interpolated by the overlay (ADR 0015). So a break line with Z fixes the height along it, and
InterpolateZon the line is the linear interpolation along its edges (a test).Exceptions (ADR 0012):
ArgumentNullExceptionfornull,NotSupportedExceptionfor an unknown geometry kind,ArgumentOutOfRangeExceptionfor a badgridSize,InvalidOperationExceptionwithout a factory when constraints cross. Too few or collinear vertices give an empty triangulation, no exception.Speed. One-shot measurements (
--quick-voronoi, Release build). A break line through 100 of the points costs about as much as the triangulation of the points itself:Case N SpatialNET (ms) NTS (ms) FromPointsandFromPointsAndLineswith a line of 100 points10,000 7 and 14 – the same 100,000 80 and 131 – FromPolygonvsPolygonTriangulator, a smooth ring (a real boundary)1,000 1.9 0.6 the same 10,000 21 16 the same 100,000 427 1,234 the same, the Delaunay triangulation of the ring's vertices alone (not made by FromPolygonany more)100,000 9,605 61,712 FromPolygonvsPolygonTriangulator, a jagged star-shaped ring10,000 89 46 the same 100,000 6,520 3,621 For a polygon the first step decides, and a valid polygon does not take it. The vertices of a boundary lie on a curve, and the Delaunay triangulation of points on a curve is expensive for every algorithm: it consists of long thin triangles and the edge flips run far (9.6 s for 100,000 vertices of a smooth ring, and 62 s for the NTS builder on the same points). So
FromPolygondoes not build it for a valid polygon: it clips ears (the one with the smallest circumcircle first, so the triangles are already close to Delaunay; holes are joined to the outer ring by bridges) and then makes the edges Delaunay by the same exact flips as above, with the ring edges fixed, which ends in the same constrained Delaunay triangulation. The smooth ring of 100,000 vertices drops from 9.8 s to 0.4 s, faster than the NTSPolygonTriangulator(1.2 s), which also clips ears. What is left of the time is the check of the input and the ears. The jagged ring, whose long edges make every spatial query return thousands of candidates, is dominated by the check that no two edges cross or touch (the same check the general path needs for crossings), and is not faster than before; NTS is faster there.Tests (ADR 0008):
[Covers]tests. A forced diagonal; random constraints between random points, which have to flip a lot (every constraint is covered by constrained edges and every constrained edge lies on a constraint; counter-clockwise triangles; the area is the hull's; every unconstrained interior edge is locally Delaunay by the exactInCircle); a long break line through many points; a constraint through a vertex; crossing, overlapping and repeated constraints; a polygon aslines; polygons (a square, a U, with a hole, a bow tie, collinear) and random star-shaped polygons with and without a hole (the count of triangles isn − 2or+ 2per hole, the area is the polygon's, every centroid lies inside, every ring edge is an edge) with the NTSPolygonTriangulatoras an oracle for the count and the area; random polygons with up to nine holes, in either direction, on both paths (ear clipping with flips, and all vertices with the rings forced in): the same triangles, since without points on a common circle the constrained Delaunay triangulation is unique; polygons the fast path cannot take (a hole or a vertex touching a ring, nested holes) that the general path still triangulates; a polygon with 3,000 vertices; argument errors.Playground and documentation: descriptors for
ConstrainedDelaunay(points and break lines) andTriangulate(a polygon) with examples (ADR 0011). The concept page "triangulation, Voronoi and terrain", a snippet each for break lines and polygons, glossary entries.Not now: conforming and quality triangulations that add points (Steiner points, a minimum angle; NTS has a conforming builder), a triangulation of a polygon with additional points inside it (
FromPointsAndLineswith the polygon aslinestriangulates the whole convex hull and keeps the triangles outside the polygon; the caller can drop them), removing and inserting constraints after the fact.
Considered Options
- Ear clipping for polygons as the only method (rejected: its triangles are not Delaunay, it cannot take break lines or interior points, and the robust versions need as much machinery as the constrained triangulation, which also gives the triangles for terrain; it is used as the first step of the valid-polygon path, where the flips then make the triangles Delaunay)
- A conforming Delaunay triangulation that splits the constraints until they are Delaunay edges (rejected: it adds vertices that are not in the input, so the vertices of a triangulation are no longer the points of the user; constraints as edges keep them)
- Noding every time (rejected: it would round the vertices of every polygon to a grid although they do not cross; it is done only when needed)
- An error when constraints cross (rejected: break lines and drawn rings do cross, and the overlay noding that the library has everywhere else is the answer)
- Shewchuk's Triangle or another native library (rejected: the library has no dependencies, ADR 0001, and the exact predicates it needs already exist)
- Inserting the constraints before the points, as a sweep (rejected: inserting into the finished Delaunay triangulation is simple, local, and reuses it; the cost is shown above)
- Deciding the inside of a polygon by testing the centroid of every triangle (rejected: a thin triangle's centroid can be off by rounding, while the flood fill over constraints is combinatorial and exact)
- Keeping the constraints as flags of half-edges (rejected: flips renumber half-edges; vertex pairs are stable)