Delaunay and constrained Delaunay triangulations

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.

GtsConstraintClass

typedef struct _GtsConstraintClass GtsConstraintClass;

The constraint class derived from GtsEdgeClass.

GtsConstraint

typedef struct _GtsConstraint 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.