Description
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.
The functions gts_delaunay_conform() and gts_delaunay_refine() can be used to build Delaunay conforming constrained triangulations and to refine them.
Details
GTS_CONSTRAINT_CLASS()
#define GTS_CONSTRAINT_CLASS(klass) |
Casts klass to GtsConstraintClass.
GTS_CONSTRAINT()
#define GTS_CONSTRAINT(obj) |
Casts obj to GtsConstraint.
GTS_IS_CONSTRAINT()
#define GTS_IS_CONSTRAINT(obj) |
Evaluates to TRUE if obj is a GtsConstraint, FALSE otherwise.
struct GtsConstraintClass
struct GtsConstraintClass; |
The constraint class derived from GtsEdgeClass.
struct GtsConstraint
The constraint object derived from GtsEdge.
gts_point_locate ()
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.
gts_delaunay_add_vertex ()
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.
gts_delaunay_add_vertex_to_face ()
Adds vertex v to the face f of the Delaunay triangulation defined
by surface.
gts_delaunay_remove_vertex ()
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.
gts_delaunay_add_constraint ()
Add constraint c to the constrained Delaunay triangulation defined by
surface.
gts_delaunay_remove_hull ()
void gts_delaunay_remove_hull (GtsSurface *surface); |
Removes all the edges of the boundary of surface which are not
constraints.
gts_delaunay_conform ()
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.
gts_delaunay_refine ()
An implementation of the refinement algorithm described in Ruppert
(1995) and Shewchuk (1996).