Categories
Fade2D Examples

Constraint Edges – Example3

When you triangulate just the vertices of a polygon, it is not guaranteed that its edges are edges of the resulting Delaunay triagulation. But you can enforce edges in a triangulation as demonstrated in the below example where constraint edges are inserted into a 2D triangulation. Similarly you can insert breaklines into 2.5D triangle meshes, see Breaklines, ISO Contours and the Cookie Cutter.

Create a Delaunay triangulation

// * 1 *   Generate some input points
std::vector<Point2> vInputPoints;
vInputPoints.push_back(Point2(-100,-100));
vInputPoints.push_back(Point2(+100,+100));
vInputPoints.push_back(Point2(-50,-70));
vInputPoints.push_back(Point2(-50,-30));
vInputPoints.push_back(Point2(50,70));
vInputPoints.push_back(Point2(50,30));

// * 2 *   Triangulate the points and show
Fade_2D dt;
dt.insert(vInputPoints);
dt.show("example3_noConstraints.ps",true);
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 draws the result, see the right image.

Insert a Constraint Edge

Next we modify the Delaunay triangulation from above: Assume that we want to establish an edge from the bottom left to the top right: For this purpose we prepare a vector containing one or more Segment2 objects. Then we call createConstraint().

std::vector<Segment2> vSegments;
vSegments.push_back(Segment2(vInputPoints[0],vInputPoints[1]));
ConstraintGraph2* pCG;
pCG=dt.createConstraint(vSegments,CIS_CONSTRAINED_DELAUNAY);

The above createConstraint() command inserts the constraint edge without subdivision. More precisely two cases exist that would enforce subdivision: When the constraint edge hits an existing vertex or when it intersects another constraint edge.

Constrained Delaunay triangulation with Constraint Edge
Constrained Delaunay

“This example uses CIS_CONSTRAINED_DELAUNAY. You will notice that there are also other constraint insertion strategies. However, these are deprecated in favor of newer techniques and are only included in the API for backward compatibility.

Conforming Edges

Triangles next to long Constraint Edges can have a bad shape as shown in the above image. Thus conforming triangulations are often more desirable:

std::vector<Segment2> vSegments;
vSegments.push_back(Segment2(vInputPoints[0],vInputPoints[1]));
ConstraintGraph2* pCG;
pCG=dt.createConstraint(vSegments,CIS_CONSTRAINED_DELAUNAY);
double minLen(0.1);
pCG->makeDelaunay(minLen);

The makeDelaunay(double minLen) method in the above code makes it possible. It subdivides the constraint-edges recursively until the adjacent triangles satisfy the empty-circle condition. It’s minLen parameter prevents excessive subdivision in narrow settings.

Did you read this article because you want to triangulate a polygon? Don’t stop reading, the next article introduces the Zone concept, which is useful for this purpose.

That’s all you need to know about constraint edges. But more options exist in 2.5D, you might also want to look at Breaklines, ISO Contours and the Cookie Cutter.

Now that you know how to create constraint graphs you are ready to use 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);
dt.applyConstraintsAndZones();
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?

Hi,
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 *