Categories

# Constraint Edges – Example3

When you triangulate the vertices of a polygon, its edges are not always contained in the Delaunay triangulation. But you can insert the edges as constraint edges. This is shown for 2D below. Similarly we can insert breaklines into 2.5D triangle meshes, see 2.5D Terrain Triangulation.

## Create a Delaunay triangulation

This code creates an initial Delaunay triangulation without constraint edges.

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

## Insert an Edge

Now let’s change the pure Delaunay triangulation from above. For example we 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);```

Always use the recommended constraint insertion strategy `CIS_CONSTRAINED_DELAUNAY`. It inserts a constraint edge without subdivision. More precisely only two cases enforce subdivision: When the constraint edge hits an existing vertex or when it intersects another constraint edge.

## Conforming Edges

Triangles next to long constraint edges can have a bad shape. 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 method subdivides the constraint-edges recursively until the adjacent triangles satisfy the empty-circle condition. Thereby the `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 also useful for this purpose.

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

## 4 replies on “Constraint Edges – Example3”

Boyansays:

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?

Samusays:

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.