The functions described in this section are useful to build two-dimensional Delaunay and constrained Delaunay triangulations. Only the x and y coordinates of the points are taken into account.
The algorithm is fully dynamic (insertion and deletion) for Delaunay triangulation and semi-dynamic (insertion only of vertices and constraints) for constrained Delaunay triangulation.
The insertion part uses a very simple jump-and-walk location algorithm which can be used on any (even non-Delaunay) 2D triangulation as long as its boundary is convex.
Locates the face of the planar projection of surface containing
p. The planar projection of surface must define a connected set
of triangles without holes and bounded by a convex boundary. The
algorithm is randomized and performs in O(n^1/3) expected time
where n is the number of triangles of surface.
If a good guess is given the point location can be significantly faster.
Adds vertex v to the Delaunay triangulation defined by
surface. If v is not contained in the convex hull bounding
surface, v is not added to the triangulation.
NULL or a GtsFace belonging to surface to be used as an initial
guess for point location.
Returns :
NULL is v has been successfully added to surface or was
already contained in surface, v if v is not contained in the
convex hull bounding surface or a GtsVertex having the same x and
y coordinates as v.
Removes v from the Delaunay triangulation defined by surface and
restores the Delaunay property. Vertex v must not be used by any
constrained edge otherwise the triangulation is not guaranteed to
be Delaunay.
Recursively split constraints of surface which are encroached by
vertices of surface (see Shewchuk 96 for details). The split
constraints are destroyed and replaced by a set of new constraints
of the same class. If gts_vertex_encroaches_edge() is used for
encroaches, the resulting surface will be Delaunay conforming.
If steiner_max is positive or nul, the recursive splitting
procedure will stop when this maximum number of Steiner points is
reached. In that case the resulting surface will not necessarily be
Delaunay conforming.
surface :
a GtsSurface describing a constrained Delaunay triangulation.
the number of remaining encroached edges. If steiner_max
is set to a negative value and gts_vertex_encroaches_edge() is used
for encroaches this should always be zero.