From: Eelco de Lange Newsgroups: comp.graphics.algorithms Subject: Re: Delaunay on non-convex poligons Date: Tue, 27 May 1997 09:13:53 +0200 andres@sysnet.it wrote: > I want to triangulate some non convex regions giving a set of surface > points. > Am I sure that Delaunay triangulatiion will create the correct faces? No, that is not guaranteed. (It is though for convex polygons: an edge of the convex hull always being an edge of the Delaunay triangulation) An edge is only part of the Delaunay triangulation if an empty circle exists that has the two endpoints of the edge on its border and no points in its interior. > Which additional information I can add to be sure? You can add points that are on the edge to assure that the edge (well, the sub-edges) is part of the Delaunay triangulation. This is not trivial to do (you might get in a loop adding infinitely many points). For more information, see for instance the work done by Boissonnat and Geiger on 3D reconstruction: http://www.inria.fr/rapports/sophia/RR-1697.html Eelco de Lange -- Eelco de Lange Projet Prisme-INRIA email: Eelco.de_Lange@sophia.inria.fr Dept. AOII-MMS http://www.inria.fr/prisme/personnel/edelange/