cgal_constrained_delaunay_2 - Constrained Delaunay triangulation
A 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] = cgal_constrained_delaunay_2(x,y,C); clf(); coord = cgal_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 cgal_cdt2_delete(ptr,"ptr");
cgal_delaunay_2 , cgal_delaunay_3 , cgal_delaunay_n ,
For more details see CGAL Manual.
This function uses the Triangulation_2 package of CGAL, which is under QPL license. See License Terms