Constraint Edges – Example3

Constraint Edges (Breaklines)

When you triangulate the vertices of a polygon then its edges are not always automatically edges of the resulting Delaunay triangulation. But you can enforce them as Constraint Edges (sometimes called ‘Breaklines’). This is demonstrated for 2D here but works also for 2.5D TINs, see 2.5D Terrain Triangulation. Creating a Constrained Delaunay triangulation is easy, see examples_2D/example3.cpp (contained in the download), the code is described now:

Constrained Delaunay Triangulation

Constrained Delaunay Triangulation

Create a Delaunay triangulation

A simple Delaunay triangulation without constraint edges is created:

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


Code for Constraint Edge (‘Breakline’) insertion

Let’s enforce an edge from the lower left to the upper right corner. For this purpose prepare a vector containing one or more Segment2 objects. Then call Fade_2D::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);
CIS_CONSTRAINED_DELAUNAY is the recommended constraint-insertion-strategy. It 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.

Triangles near constraint edges are often bad shaped i.e., they have undesirable interior angles. Thus conforming triangulations are often more desirable, read further.

Constrained Delaunay

Constrained Delaunay


Code for Conforming Delaunay Edges

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 method ConstraintGraph2::makeDelaunay(double minLen) can be used to subdivide the constraint edges recursively in order to achieve better (Delaunay-) triangles. Thereby the minLen parameter can be used to avoid excessive subdivision in narrow settings. Edges smaller than minLen are not further subdivided.
Conforming Delaunay

Conforming Delaunay


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!

4 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?

  2. Reply Samu

    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!

    • Reply Bernhard Kornberger

      Hi,

      I’m sorry, removing constraints is not supported but it’s on the wishlist now. In case you need it for a commercial project please let me know so that I can put priority into this task.

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