GTS Library Reference Manual |
---|
#include <gts.h> #define GTS_CONSTRAINT_CLASS (klass) #define GTS_CONSTRAINT (obj) #define GTS_IS_CONSTRAINT (obj) struct GtsConstraintClass; struct GtsConstraint; GtsConstraintClass* gts_constraint_class (void); GtsFace* gts_point_locate (GtsPoint *p, GtsSurface *surface, GtsFace *guess); GtsVertex* gts_delaunay_add_vertex (GtsSurface *surface, GtsVertex *v, GtsFace *guess); GtsVertex* gts_delaunay_add_vertex_to_face (GtsSurface *surface, GtsVertex *v, GtsFace *f); void gts_delaunay_remove_vertex (GtsSurface *surface, GtsVertex *v);GSList * gts_delaunay_add_constraint (GtsSurface *surface, GtsConstraint *c); GtsFace* gts_delaunay_check (GtsSurface *surface); void gts_delaunay_remove_hull (GtsSurface *surface);guint gts_delaunay_conform (GtsSurface *surface,gint steiner_max, GtsEncroachFunc encroaches,gpointer data);guint gts_delaunay_refine (GtsSurface *surface,gint steiner_max, GtsEncroachFunc encroaches,gpointer encroach_data, GtsKeyFunc cost,gpointer cost_data);
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.
#define GTS_CONSTRAINT_CLASS(klass)
Casts klass to GtsConstraintClass.
klass : | a descendant of GtsConstraintClass. |
#define GTS_CONSTRAINT(obj)
Casts obj to GtsConstraint.
obj : | a descendant of GtsConstraint. |
#define GTS_IS_CONSTRAINT(obj)
Evaluates to TRUE if obj is a GtsConstraint, FALSE otherwise.
obj : | a pointer to test. |
GtsConstraintClass* gts_constraint_class (void);
Returns : | the GtsConstraintClass. |
GtsFace* gts_point_locate (GtsPoint *p, GtsSurface *surface, GtsFace *guess);
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.
p : | a GtsPoint. |
surface : | a GtsSurface. |
guess : | NULL or a face of surface close to p. |
Returns : | a GtsFace of surface containing p or NULL if p is not contained within the boundary of surface. |
GtsVertex* gts_delaunay_add_vertex (GtsSurface *surface, GtsVertex *v, GtsFace *guess);
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.
surface : | a GtsSurface. |
v : | a GtsVertex. |
guess : | 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. |
GtsVertex* gts_delaunay_add_vertex_to_face (GtsSurface *surface, GtsVertex *v, GtsFace *f);
Adds vertex v to the face f of the Delaunay triangulation defined by surface.
surface : | a GtsSurface. |
v : | a GtsVertex. |
f : | a GtsFace belonging to surface. |
Returns : | NULL is v has been successfully added to surface or was already contained in surface or a GtsVertex having the same x and y coordinates as v. |
void gts_delaunay_remove_vertex (GtsSurface *surface, GtsVertex *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.
surface : | a GtsSurface. |
v : | a GtsVertex. |
GSList * gts_delaunay_add_constraint (GtsSurface *surface, GtsConstraint *c);
Add constraint c to the constrained Delaunay triangulation defined by surface.
surface : | a GtsSurface. |
c : | |
Returns : | a list of GtsConstraint conflicting (i.e. intersecting) with c which were removed from surface (NULL if there was none). |
GtsFace* gts_delaunay_check (GtsSurface *surface);
surface : | a GtsSurface. |
Returns : | NULL if the planar projection of surface is a Delaunay triangulation (unconstrained), a GtsFace violating the Delaunay property otherwise. |
void gts_delaunay_remove_hull (GtsSurface *surface);
Removes all the edges of the boundary of surface which are not constraints.
surface : | a GtsSurface. |
guint gts_delaunay_conform (GtsSurface *surface,gint steiner_max, GtsEncroachFunc encroaches,gpointer data);
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. |
steiner_max : | maximum number of Steiner points. |
encroaches : | |
data : | user-data to pass to encroaches. |
Returns : | 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. |
guint gts_delaunay_refine (GtsSurface *surface,gint steiner_max, GtsEncroachFunc encroaches,gpointer encroach_data, GtsKeyFunc cost,gpointer cost_data);
An implementation of the refinement algorithm described in Ruppert (1995) and Shewchuk (1996).
surface : | a GtsSurface describing a conforming Delaunay triangulation. |
steiner_max : | maximum number of Steiner points. |
encroaches : | |
encroach_data : | user-data to pass to encroaches. |
cost : | a GtsKeyFunc used to sort the faces during refinement. |
cost_data : | user-data to pass to cost. |
Returns : | the number of unrefined faces of surface left. Should be zero if steiner_max is set to a negative value. |
<<< Isosurfaces from 3D functions | Differential geometry operators >>> |