Constrained Delaunay triangulation
[tri [,ptr] ] = constrained_delaunay_2(x,y,C)
- cdt2_insert_constraints - cdt2_remove_constraints
- cdt2_insert_points - cdt2_remove_points
- cdt2_get_coordA constrained Delaunay triangulation is a triangulation with constrained edges which tries to be as much Delaunay as possible. Constrained edges are not necessarily Delaunay edges, therefore a constrained Delaunay triangulation is not a Delaunay triangulation. A constrained Delaunay is a triangulation whose faces do not necessarily fulfill the empty circle property but fulfill a weaker property called the constrained empty circle. To state this property, it is convenient to think of constrained edges as blocking the view. Then, a triangulation is constrained Delaunay if the circumscribing circle of any of its triangular faces includes in its interior no vertex that is visible from the interior of the triangle.
x = [5 1 6]; y = [2 6 6]; C=[8. 2. 7. 4.;6. 4.5 4. 5.;3. 6. 3. 7.;3. 4. 2. 3.;9. 4. 8. 7.]; [tri,ptr] = constrained_delaunay_2(x,y,C); clf(); coord = cdt2_get_coord(ptr); X=coord(:,1)'; Y=coord(:,2)'; [nbtri,nb] = size(tri); tri = [tri tri(:,1)]; for k = 1:nbtri plot2d(X(tri(k,:)),Y(tri(k,:)),style = 2); end [nbconstraints,nb] = size(C); for i = 1:nbconstraints plot2d([C(i,1) C(i,3)]',[C(i,2) C(i,4)]',style = 3); plot2d([C(i,1) C(i,3)]',[C(i,2) C(i,4)]',style = -5); end cdt2_delete(ptr,"ptr"); | ![]() | ![]() |
For more details see CGAL Manual.
This function uses the Triangulation_2 package of CGAL, which is under QPL license. See License Terms