# How does heavily constrained delaunay triangulation work?

In short: I'm trying to find an algorithm for performing a Delaunay triangulation of a heavily constrained polygon (for the purpose of pathfinding), with the understanding that most of the resulting triangles will be illegal (non-Delaunay) due to the constraints. Making the effort should still help reduce generation of long/thin triangles where possible.

I'm trying to understand how constrained Delaunay triangulation works, within the context of game maps where the available ground surface for navigation and pathing is defined by a polygon on a flat 2D plane. The polygon needs to be triangulated for use in pathfinding, such that moving from point A to point B passes through as few polygons as possible (so polygons need to be as large as possible).

I first looked into regular Delaunay triangulation, and there are multiple methods available, but they all assume a point cloud where the goal is to create ideal triangles without constraints.

Then I looked into constrained Delaunay triangulation, but there is very little available I could find beyond academic papers, and many of those simply perform a regular Delaunay triangulation, then cut triangles that intersect constraints and re-triangulate around them. This seems backwards and inefficient to me when literally ALL of the triangles I want to end up with will be constrained.

I saw a GDC video, where the Starcraft 2 devs talked about using constrained Delaunay triangulation, and you can kind of see it when you look at the pathing mesh in the Starcraft 2 editor (see below). However, very few of the generated triangles are legal, due to the number of constraints in the map layout. Still, I am assuming the Delaunay algorithm influenced the selection of points to triangulate, in order to get the best triangle coverage.

However, I can't find any further info on how this might work. How does one start with constraints, points connected by fixed lines, and then "fill in" the remaining lines to generate triangles that are a best-effort attempt to not be overly stretched or narrow?

Edit: Screenshot example from Starcraft 2 editor:

• I'd recommend walking us through the kinds of polygons you need to triangulate, and the constraints you need to honour, so we can help find effective solutions for that use case — whether constrained Delaunay triangulation is the best solution, or whether another algorithm could give better results for your case. Commented Jun 20, 2020 at 17:42
• As with Starcraft 2, this would be for map boundaries. Walls, cliffs, buildings, etc. The resulting triangles would be used with the funnel algorithm for pathing around within the map. Commented Jun 20, 2020 at 20:12
• So you're making a navmesh? Including that in your question can help you get good answers appropriate to that use. For questions of geometry, including representative images is almost always a good idea. Don't assume everyone who might have useful info to share has seen the same SC2 GDC video you saw. Commented Jun 20, 2020 at 20:31
• @Topicstarter, can you link the Starcraft 2 GDC talk on the matter into the question plz? Commented Jun 21, 2020 at 5:39
• Commented Jun 21, 2020 at 14:10

You're almost there. Once you have a delaunay triangulation of all the points (including constraint points) then:

foreach constraint edge:

1. Find all existing intersecting edges in the triangulation
2. 'Remove' these intersecting edges (see below)
3. Restore the delaunay triangulation

Regarding step 2), here is a description from Eric Nordeus that summarises this step:

"The idea here is that all possible triangulations for a set of points can be found by systematically swapping the diagonal in each convex quadrilateral formed by a pair of triangles. So we will test all possible arrangements and will always find a triangulation which includes the constrained edge."

The quadrilateral is formed from the 2 triangles that share the edge intersecting the constraint.

Get the 3 vertices for the triangle the intersecting edge is on and then get the 'opposite' edge of this edge (in the half edge data structure on the Habrador blog, the opposite edge has the same vertices, but they are swapped in order).

If these 4 points form a convex quad then you can flip the edge.

If the new flipped edge intersects the current constraint you push it back on the intersectingEdges list, otherwise you have a new edge that no longer intersects the constraint.

Here's a very simple diagram that hopefully helps illustrate the basic concept:

Here is some further reading, including better & more detailed descriptions on the above & some further experiments on constrained delaunay navmesh pathfinding by myself:

Eric Nordeus blog: constrained delaunay

Constrained Delaunay Navmesh someone posted on the Unity forums, complete with tutorial

My own blog post on using Constrained Delaunay Triangles as a navmesh including dynamic updating and pathfinding info

• BTW, if you try to constrain two intersecting edges, adding the second constraint will undo the first. In that case, you have to add a new vertex to the mesh at the intersection point, and then you can constrain the 4 sub-segments. (This case won't happen if you constrain a valid polygon, but it might if you constrain two overlapping polygons). Commented Jan 12, 2023 at 5:20