Example3 – Constraint Edges
When you triangulate a polygon and you use only its vertices then its edges are not necessarily contained in the resulting triangulation. To enforce the shape’s edges in the triangulation you must insert them as Constraint Edges. It’s easy, see the code below.
Create a simple Delaunay triangulation
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");
Inserting constraint edges
And now assume that we want to enforce an edge from the lower left to the upper right corner. There are two different insertion strategies:
- CIS_CONSTRAINED_DELAUNAY 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. Be aware that intersection points may require rounding because the exact intersection coordinates of two segments do not necessarily exist as IEEE754 double precision floating point numbers.
- CIS_CONFORMING_DELAUNAY subdivides a constraint edge such that it appears naturally as part of the Delaunay triangulation where every triangle keeps its empty circle property. This insertion strategy creates more (but better shaped) triangles. Be careful: Narrow geometric settings may enforce many tiny triangles and even prevent complete insertion when subsegments get too small.
Code for Constrained Delaunay
We prepare a vector of one or more constraint segments and call createConstraint() using the constraint insertion strategy CIS_CONSTRAINED_DELAUNAY. Then we call applyConstraintAndZones() to establish the constraint graph in the triangulation. Note: Subsequent changes in the triangulation may make the constraints disappear and for efficiency reasons Fade does not automatically re-establish them. You must call applyConstraintsAndZones() again at the time you need the constraints in your triangulation.
std::vector<Segment2> vSegments; vSegments.push_back(Segment2(vInputPoints,vInputPoints)); ConstraintGraph2* pCG; pCG=dt.createConstraint(vSegments,CIS_CONSTRAINED_DELAUNAY); dt.applyConstraintsAndZones();
Code for Conforming Delaunay
The same again, but with the constraint insertion strategy CIS_CONFORMING_DELAUNAY:
std::vector<Segment2> vSegments; vSegments.push_back(Segment2(vInputPoints,vInputPoints)); ConstraintGraph2* pCG; pCG=dt.createConstraint(vSegments,CIS_CONFORMING_DELAUNAY); dt.applyConstraintsAndZones();
Now that you know how to create constraint graphs you are ready use polygonal zones.