When you triangulate just the vertices of a polygon, it is not guaranteed that its edges are edges of the Delaunay triagulation. But you can insert them as Constraint Edges as demonstrated for a 2D triangulation and one segment below. Similarly you can insert breaklines into 2.5D triangle meshes, see Breaklines, ISO Contours and the Cookie Cutter.
Create a Delaunay triangulation
// * 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);
The above code creates a simple Delaunay triangulation of 6 input points but without Constraint Edges. After that it draws the result.
Insert a Constraint Edge
Next we modify the Delaunay triangulation from above: Assume that we want to 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
std::vector<Segment2> vSegments; vSegments.push_back(Segment2(vInputPoints,vInputPoints)); ConstraintGraph2* pCG; pCG=dt.createConstraint(vSegments,CIS_CONSTRAINED_DELAUNAY);
We use the constraint insertion strategy
CIS_CONSTRAINED_DELAUNAY. It inserts our constraint edge without subdivision. More precisely two cases exist that would enforce subdivision: When the constraint edge hits an existing vertex or when it intersects another constraint edge.
“You will notice that there are also other constraint insertion strategies. However, these are deprecated in favor of better techniques and are only included in the interface for backward compatibility.“
Triangles next to long Constraint Edges can have a bad shape as shown in the above image. 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 in the above code makes it possible. It subdivides the constraint-edges recursively until the adjacent triangles satisfy the empty-circle condition. It’s
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.
That’s all you need to know about constraint edges. But more options exist in 2.5D, you might also want to look at Breaklines, ISO Contours and the Cookie Cutter.
Now that you know how to create constraint graphs you are ready to use polygonal zones.