# 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:

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

dt.insert(vInputPoints);
dt.show("example3_noConstraints.ps");
``` 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,vInputPoints));
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

## Code for Conforming Delaunay Edges

```std::vector<Segment2> vSegments;
vSegments.push_back(Segment2(vInputPoints,vInputPoints));
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

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.

1. 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!

• 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. 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.
• 