2D Delaunay Triangulation Examples in C++

Constraint Edges – Example3

When you perform a triangulation using only the vertices of a polygon, there’s no guarantee that the resulting Delaunay triangulation will contain the original polygon’s edges. However, don’t worry; you can enforce edges in a triangulation. In the example below, we demonstrate the insertion of constraint edges into a 2D triangulation. Similarly, you can insert breaklines into 2.5D triangle meshes, as discussed in our article on Breaklines, ISO Contours and the Cookie Cutter.

Create a Delaunay triangulation

// * 1 *   Generate some input points
std::vector<Point2> vInputPoints;

// * 2 *   Triangulate the points and show
Fade_2D dt;
Delaunay Triangulation of 6 points without Constraint Edges

The above code creates a simple Delaunay triangulation of 6 input points but without Constraint Edges. After that, it generates the image, displayed on the right side, in Postscript format.

Insert a Constraint Edge

Next, we modify the Delaunay triangulation from the previous example. Suppose we want to create an edge from the bottom left to the top right of the triangulation. To accomplish this, we prepare one or more Segment2 objects, which we store in an std::vector. We then use this vector as an argument when calling createConstraint().

std::vector<Segment2> vSegments;
ConstraintGraph2* pCG;

The createConstraint() command mentioned above inserts the constraint edge without subdivision. To clarify, there are two cases in which subdivision is enforced: when the constraint edge intersects an existing vertex or when it intersects another constraint edge.

Constrained Delaunay triangulation with Constraint Edge
Constrained Delaunay Triangulation

“In this example, we use CIS_CONSTRAINED_DELAUNAY as the constraint insertion strategy. You may notice that there are other strategies available; however, these are deprecated in favor of newer techniques and are kept in the API for backward compatibility.

Subdividing Constraint Edges

Triangles next to long Constraint Edges can have poor aspect ratios, as shown in the result image of the previous example. Subdividing the Constraint Edges results in improved adjacent triangles:

std::vector<Segment2> vSegments;
ConstraintGraph2* pCG;
double minLen(0.1);

The makeDelaunay(double minLen) method in the above code facilitates this process. It recursively subdivides the constraint edges until the adjacent triangles meet the empty-circle condition. Thereby, the minLen parameter prevents excessive subdivision in narrow geometric scenarios.

Did you come across this article while looking for information on polygon triangulation? Keep going! The next article introduces the Zone concept, a valuable tool for achieving precisely that.

That covers the essentials of constraint edges. But in the domain of 2.5D, there are more options to explore. You might also find value in exploring articles like Breaklines, ISO Contours and the Cookie Cutter.

Now that you’ve become proficient in creating constraint graphs, you’re well-prepared to venture into the world of polygonal zones.

4 replies on “Constraint Edges – Example3”

Dear Dr. Kornberger,

If there is a random polygon. How I can triangulate it?
Just insert all points into a object of Fade_2D or do I need to add all boundaries as Segment2 and apply
ConstraintGraph2* pCG = dt.createConstraint(vSegments, CIS_CONSTRAINED_DELAUNAY);
In both ways I didn’t get a proper result. Looking forward to your help!

Dear Boyan,

When you insert just the points you will get the Delaunay triangulation of the points. But the edges of your polygon are not necessarily part of the Delaunay triangulation. You must enforce these edges with createConstraint. But a Constrained Delaunay triangulation is always convex, this is why you see additional triangles when you triangulate a non-convex polygon. If you want to extract only the triangles inside the polygon you must create an INSIDE ZONE. See the next example (example4.cpp). Does that answer your question?

Can I somehow delete an already created constraint segment? If so, how?
So far, all I could do was create an entirely new triangulation, and add the edited constraints there.
Thanks in advance!

Leave a Reply

Your email address will not be published. Required fields are marked *