When you triangulate the vertices of a polygon, the edges of the polygon are not necessarily automatically edges of the Delaunay triangulation. But you can insert the edges as constraint edges (sometimes called ‘breaklines’). This is demonstrated for 2D below and in later examples you will see that it works also for 2.5D triangle meshes, see 2.5D Terrain Triangulation.
Create a Delaunay triangulation
A very simple Delaunay triangulation without constraint edges is created:
// * 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);
Insert an Edge (‘Breakline’)
Now we want to change the pure Delaunay triangulation from above by inserting an edge from bottom left to top right. For this purpose we prepare a vector containing one or more
Segment2 objects and call
std::vector<Segment2> vSegments; vSegments.push_back(Segment2(vInputPoints,vInputPoints)); ConstraintGraph2* pCG; pCG=dt.createConstraint(vSegments,CIS_CONSTRAINED_DELAUNAY);
The used and only recommended constraint-insertion-strategy is
CIS_CONSTRAINED_DELAUNAY. It inserts a constraint edge without subdivision. More precisely subdivision takes place in only the two cases where it can’t be avoided: When the constraint edge hits an existing vertex or when it intersects another constraint edge.
Conforming Delaunay Edges
Triangles next to long constraint edges can have a bad shape i.e., extremely large and small interior angles. Thus conforming triangulations are often more desirable:
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);
makeDelaunay(double minLen) method method is used to subdivide the constraint-edges recursively until the adjacent triangles satisfy the empty-circle condition. The
minLen parameter is thought to prevent 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.