Google

NAME="GENERATOR" CONTENT="Modular DocBook HTML Stylesheet Version 1.52">
GTS Library Reference Manual
<<< Previous PageHomeUpNext Page >>>

Delaunay and constrained Delaunay triangulations

Name

Delaunay and constrained Delaunay triangulations -- implementation of a dynamic Delaunay triangulation algorithm.

Synopsis


#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);

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.

klass :a descendant of GtsConstraintClass.

GTS_CONSTRAINT()

#define     GTS_CONSTRAINT(obj)

Casts obj to GtsConstraint.

obj :a descendant of GtsConstraint.

GTS_IS_CONSTRAINT()

#define     GTS_IS_CONSTRAINT(obj)

Evaluates to TRUE if obj is a GtsConstraint, FALSE otherwise.

obj :a pointer to test.

struct GtsConstraintClass

struct GtsConstraintClass;

The constraint class derived from GtsEdgeClass.

struct GtsConstraint

struct GtsConstraint;

The constraint object derived from GtsEdge.

gts_constraint_class ()

GtsConstraintClass* gts_constraint_class    (void);

Returns : the GtsConstraintClass.

gts_point_locate ()

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.

gts_delaunay_add_vertex ()

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.

gts_delaunay_add_vertex_to_face ()

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.

gts_delaunay_remove_vertex ()

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.

gts_delaunay_add_constraint ()

GSList*     gts_delaunay_add_constraint     (GtsSurface *surface,
                                             GtsConstraint *c);

Add constraint c to the constrained Delaunay triangulation defined by surface.

surface : a GtsSurface.
c : a GtsConstraint.
Returns : a list of GtsConstraint conflicting (i.e. intersecting) with c which were removed from surface (NULL if there was none).

gts_delaunay_check ()

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.

gts_delaunay_remove_hull ()

void        gts_delaunay_remove_hull        (GtsSurface *surface);

Removes all the edges of the boundary of surface which are not constraints.

surface : a GtsSurface.

gts_delaunay_conform ()

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 : a GtsEncroachFunc.
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.

gts_delaunay_refine ()

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 : a GtsEncroachFunc.
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.



<<< Previous PageHomeUpNext Page >>>
Isosurfaces from 3D functionsDifferential geometry operators