Constraint Edges – Example3

Constraint Edges

When you triangulate the vertices of a polygon then its edges are not necessarily contained in the resulting Delaunay triangulation. But you can enforce Constraint Edges and the result is a Constrained Delaunay Triangulation then. It’s easy, see example3.cpp (contained in the download), the code is described below.

Constrained Delaunay Triangulation

Constrained Delaunay Triangulation


Create a Delaunay triangulation

To start, we create and draw a simple Delaunay triangulation without constraint edges:

	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));

	Fade_2D dt;
	dt.insert(vInputPoints);
	dt.show("example3_noConstraints.ps");
Delaunay Triangulation without Constraint Edges

Delaunay Triangulation without Constraint Edges


Constrained Delaunay: Insert Constraint Edges

And now assume that we want to enforce an edge from the lower left to the upper right corner. There are two different insertion strategies:

  • CIS_CONSTRAINED_DELAUNAY inserts a constraint edge without subdivision. More precisely subdivision takes place in only two cases: When the constraint edge hits an existing vertex or when it intersects another constraint edge. This is the recommended way to insert constraint edges.
Constrained Delaunay

Constrained Delaunay


  • CIS_CONFORMING_DELAUNAY subdivides a constraint edge such that it appears naturally as part of the Delaunay triangulation where every triangle keeps its empty circle property. This insertion strategy creates more (but better shaped) triangles. Be careful: Narrow geometric settings may enforce many tiny triangles and even prevent complete insertion when subsegments get too small.
Conforming Delaunay

Conforming Delaunay


Be aware that exact intersection points may simply not exist as double precision floating point coordinates and thus rounding can be involved.

Code for Constrained Delaunay

We prepare a vector of one or more constraint segments and call createConstraint() using the constraint insertion strategy CIS_CONSTRAINED_DELAUNAY.

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

Code for Conforming Delaunay

The same again, but with the constraint insertion strategy CIS_CONFORMING_DELAUNAY. Only for the constraint insertion strategy CIS_CONFORMING_DELAUNAY we need to call applyConstraintsAndZones() to establish the constraint graph in the triangulation. Subsequent changes in the triangulation may make the conforming constraints disappear and for efficiency reasons Fade does not automatically re-establish them. You must call applyConstraintsAndZones() again at the time you need the conforming constraints in your triangulation.

	std::vector<Segment2> vSegments;
	vSegments.push_back(Segment2(vInputPoints[0],vInputPoints[1]));
	ConstraintGraph2* pCG;
	pCG=dt.createConstraint(vSegments,CIS_CONFORMING_DELAUNAY);
	dt.applyConstraintsAndZones();
Have you read this article because you want to triangulate a polygon? Don’t stop reading: The next article introduces the zone concept that you also need for this purpose.

Now that you know how to create constraint graphs you are ready use polygonal zones.

Spread the word. Share this post!

2 Comments

  1. Reply Boyan

    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!

    • Reply Bernhard Kornberger

      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?

Leave A Reply

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

*

By continuing to use the site, you agree to the use of cookies. more information

The cookie settings on this website are set to "allow cookies" to give you the best browsing experience possible. If you continue to use this website without changing your cookie settings or you click "Accept" below then you are consenting to this.

Close