#include <math.h>
#include "gts.h"

Include dependency graph for cdt.c:

Data Structures
struct	_SFindClosest
Defines
#define	NEXT_CUT(edge, edge1, list)
Typedefs
typedef struct _SFindClosest	SFindClosest
Functions
static void	find_closest (gpointer key, gpointer value, gpointer user_data)
static GtsFace *	closest_face (GtsSurface s, GtsPoint p)
static GtsFace *	neighbor (GtsFace f, GtsEdge e, GtsSurface *surface)
static GtsEdge *	triangle_next_edge (GtsTriangle t, GtsPoint o, GtsPoint p, gboolean on_summit)
static void	triangle_barycenter (GtsTriangle t, GtsPoint b)
static GtsFace *	point_locate (GtsPoint o, GtsPoint p, GtsFace f, GtsSurface surface)
GtsFace *	gts_point_locate (GtsPoint p, GtsSurface surface, GtsFace *guess)
GtsConstraintClass *	gts_constraint_class (void)
static void	split_list (GtsListFace f, GtsListFace f1, GtsListFace f2, GtsPoint p1, GtsPoint p2, GSList last1, GSList *last2)
static void	swap_if_in_circle (GtsFace f1, GtsVertex v1, GtsVertex v2, GtsVertex v3, GtsEdge e1, GtsEdge e2, GtsEdge e3, GtsSurface surface)
GtsVertex *	gts_delaunay_add_vertex_to_face (GtsSurface surface, GtsVertex v, GtsFace *f)
GtsVertex *	gts_delaunay_add_vertex (GtsSurface surface, GtsVertex v, GtsFace *guess)
static gboolean	polygon_in_circle (GSList poly, GtsPoint p1, GtsPoint p2, GtsPoint p3)
static void	triangulate_polygon (GSList poly, GtsSurface surface, GtsFace *ref)
void	gts_delaunay_remove_vertex (GtsSurface surface, GtsVertex v)
static void	remove_triangles (GtsEdge e, GtsSurface s)
static GSList *	remove_intersected_edge (GtsSegment s, GtsEdge e, GtsFace f, GtsSurface surface, GSList left, GSList right)
static GSList *	remove_intersected_vertex (GtsSegment s, GtsVertex v, GtsSurface surface, GSList left, GSList right, GtsFace *ref)
GSList *	gts_delaunay_add_constraint (GtsSurface surface, GtsConstraint c)
static void	delaunay_check (GtsTriangle t, gpointer data)
GtsFace *	gts_delaunay_check (GtsSurface *surface)
void	gts_delaunay_remove_hull (GtsSurface *surface)
static void	gts_list_face_destroy (GtsObject *object)
static void	gts_list_face_class_init (GtsFaceClass *klass)
GtsFaceClass *	gts_list_face_class (void)

Define Documentation

#define NEXT_CUT	(	edge,
		edge1,
		list
	)

Value:

{ next = neighbor (f, edge, surface);\
                                      remove_triangles (e, surface);\
                                      if (!constraint && !e->triangles)\
                                        gts_object_destroy (GTS_OBJECT (e));\
                                      g_assert (next);\
                                      *list = g_slist_prepend (*list, edge1);\
                                      return g_slist_concat (constraint,\
                                        remove_intersected_edge (s, edge,\
                                               next, surface, left, right));\
                                    }

Definition at line 812 of file cdt.c.

Referenced by remove_intersected_edge().

Typedef Documentation

typedef struct _SFindClosest SFindClosest

Definition at line 82 of file cdt.c.

Function Documentation

static GtsFace* closest_face	(	GtsSurface *	s,
		GtsPoint *	p
	)		`[static]`

Definition at line 150 of file cdt.c.

References _SFindClosest::closest, _SFindClosest::dmin, _GtsSurface::faces, find_closest(), _SFindClosest::p, and _SFindClosest::stop.

Referenced by gts_point_locate().

Here is the call graph for this function:

static void delaunay_check	(	GtsTriangle *	t,
		gpointer *	data
	)		`[static]`

Definition at line 1048 of file cdt.c.

References GTS_FACE, GTS_POINT, gts_point_in_circle(), gts_triangle_vertices(), and gts_vertex_neighbors().

Referenced by gts_delaunay_check().

Here is the call graph for this function:

static void find_closest	(	gpointer	key,
		gpointer	value,
		gpointer	user_data
	)		`[static]`

Definition at line 130 of file cdt.c.

References _SFindClosest::closest, _SFindClosest::dmin, f, GTS_FACE, GTS_POINT, GTS_SEGMENT, GTS_TRIANGLE, gts_triangle_orientation(), _SFindClosest::p, _SFindClosest::stop, _GtsPoint::x, and _GtsPoint::y.

Referenced by closest_face().

Here is the call graph for this function:

GtsConstraintClass* gts_constraint_class ( void )

gts_constraint_class:

Returns: the GtsConstraintClass.

Definition at line 391 of file cdt.c.

References gts_edge_class(), GTS_OBJECT_CLASS, and gts_object_class_new().

Referenced by edge_inter_class(), toporouter_arc_class(), and toporouter_constraint_class().

Here is the call graph for this function:

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

gts_delaunay_add_constraint: : a GtsSurface. : a GtsConstraint.

Add constraint to the constrained Delaunay triangulation defined by .

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

Definition at line 973 of file cdt.c.

References FALSE, gts_allow_floating_edges, GTS_IS_CONSTRAINT, GTS_OBJECT, gts_object_destroy(), GTS_POINT, GTS_SEGMENT, gts_surface_write(), remove_intersected_vertex(), _GtsFace::surfaces, triangulate_polygon(), TRUE, _GtsSegment::v1, and _GtsSegment::v2.

Referenced by build_cdt().

Here is the call graph for this function:

GtsVertex* gts_delaunay_add_vertex	(	GtsSurface *	surface,
		GtsVertex *	v,
		GtsFace *	guess
	)

gts_delaunay_add_vertex: : a GtsSurface. : a GtsVertex. : NULL or a GtsFace belonging to to be used as an initial guess for point location.

Adds vertex to the Delaunay triangulation defined by . If is not contained in the convex hull bounding , is not added to the triangulation.

Returns: NULL is has been successfully added to or was already contained in , if is not contained in the convex hull bounding surface or a GtsVertex having the same x and y coordinates as .

Definition at line 642 of file cdt.c.

References f, gts_delaunay_add_vertex_to_face(), GTS_POINT, and gts_point_locate().

Referenced by build_cdt(), delaunay_create_from_vertices(), and gts_delaunay_refine().

Here is the call graph for this function:

GtsVertex* gts_delaunay_add_vertex_to_face	(	GtsSurface *	surface,
		GtsVertex *	v,
		GtsFace *	f
	)

gts_delaunay_add_vertex_to_face: : a GtsSurface. : a GtsVertex. : a GtsFace belonging to .

Adds vertex to the face of the Delaunay triangulation defined by .

Returns: NULL is has been successfully added to or was already contained in or a GtsVertex having the same x and y coordinates as .

Definition at line 524 of file cdt.c.

References _GtsSurface::edge_class, _GtsSurface::face_class, GTS_EDGE, gts_edge_new(), gts_face_new(), GTS_IS_EDGE, GTS_IS_LIST_FACE, GTS_LIST_FACE, GTS_OBJECT, gts_object_attributes(), GTS_POINT, gts_point_orientation(), gts_surface_add_face(), gts_surface_remove_face(), GTS_TRIANGLE, gts_triangle_vertices_edges(), gts_vertices_are_connected(), swap_if_in_circle(), x, and y.

Referenced by gts_delaunay_add_vertex(), and split_encroached().

Here is the call graph for this function:

GtsFace* gts_delaunay_check ( GtsSurface * surface )

gts_delaunay_check: : a GtsSurface.

Returns: NULL if the planar projection of is a Delaunay triangulation (unconstrained), a GtsFace violating the Delaunay property otherwise.

Definition at line 1084 of file cdt.c.

References delaunay_check(), FALSE, and gts_surface_foreach_face().

Here is the call graph for this function:

void gts_delaunay_remove_hull ( GtsSurface * surface )

gts_delaunay_remove_hull: : a GtsSurface.

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

Definition at line 1105 of file cdt.c.

References _GtsTriangle::e1, _GtsTriangle::e2, _GtsTriangle::e3, FALSE, gts_allow_floating_edges, gts_edge_is_boundary(), GTS_FACE, GTS_IS_CONSTRAINT, GTS_OBJECT, gts_object_destroy(), gts_surface_boundary(), gts_surface_remove_face(), GTS_TRIANGLE, _GtsEdge::triangles, and TRUE.

Here is the call graph for this function:

void gts_delaunay_remove_vertex	(	GtsSurface *	surface,
		GtsVertex *	v
	)

gts_delaunay_remove_vertex: : a GtsSurface. : a GtsVertex.

Removes from the Delaunay triangulation defined by and restores the Delaunay property. Vertex must not be used by any constrained edge otherwise the triangulation is not guaranteed to be Delaunay.

Definition at line 782 of file cdt.c.

References gts_face_has_parent_surface(), GTS_IS_FACE, gts_surface_remove_face(), gts_vertex_fan_oriented(), gts_vertex_triangles(), and triangulate_polygon().

Referenced by gts_delaunay_refine().

Here is the call graph for this function:

GtsFaceClass* gts_list_face_class ( void )

Definition at line 1156 of file cdt.c.

References gts_face_class(), gts_list_face_class_init(), GTS_OBJECT_CLASS, and gts_object_class_new().

Referenced by gts_list_face_destroy().

Here is the call graph for this function:

static void gts_list_face_class_init ( GtsFaceClass * klass ) [static]

Definition at line 1151 of file cdt.c.

References gts_list_face_destroy(), and GTS_OBJECT_CLASS.

Referenced by gts_list_face_class().

Here is the call graph for this function:

static void gts_list_face_destroy ( GtsObject * object ) [static]

Definition at line 1143 of file cdt.c.

References GTS_LIST_FACE, gts_list_face_class(), and GTS_OBJECT_CLASS.

Referenced by gts_list_face_class_init().

Here is the call graph for this function:

GtsFace* gts_point_locate	(	GtsPoint *	p,
		GtsSurface *	surface,
		GtsFace *	guess
	)

gts_point_locate: : a GtsPoint. : a GtsSurface. : NULL or a face of close to .

Locates the face of the planar projection of containing . The planar projection of 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 .

If a good is given the point location can be significantly faster.

Returns: a GtsFace of containing or NULL if is not contained within the boundary of .

Definition at line 357 of file cdt.c.

References closest_face(), fr, gts_face_has_parent_surface(), GTS_OBJECT, GTS_OBJECT_CLASS, gts_object_destroy(), gts_object_new(), GTS_POINT, gts_point_class(), GTS_TRIANGLE, gts_triangle_orientation(), point_locate(), and triangle_barycenter().

Referenced by cluster_find(), and gts_delaunay_add_vertex().

Here is the call graph for this function:

static GtsFace* neighbor	(	GtsFace *	f,
		GtsEdge *	e,
		GtsSurface *	surface
	)		`[static]`

Definition at line 168 of file cdt.c.

References GTS_FACE, gts_face_has_parent_surface(), GTS_IS_FACE, GTS_TRIANGLE, and _GtsEdge::triangles.

Referenced by edge_fan_list(), find_neighbor_backward(), find_neighbor_forward(), gts_gnode_move_cost(), point_locate(), remove_intersected_vertex(), and swap_if_in_circle().

Here is the call graph for this function:

static GtsFace* point_locate	(	GtsPoint *	o,
		GtsPoint *	p,
		GtsFace *	f,
		GtsSurface *	surface
	)		`[static]`

Definition at line 257 of file cdt.c.

References f, GTS_POINT, gts_point_orientation(), GTS_SEGMENT, GTS_TRIANGLE, gts_triangle_vertices_edges(), neighbor(), triangle_barycenter(), and triangle_next_edge().

Referenced by gts_point_locate().

Here is the call graph for this function:

static gboolean polygon_in_circle	(	GSList *	poly,
		GtsPoint *	p1,
		GtsPoint *	p2,
		GtsPoint *	p3
	)		`[static]`

Definition at line 656 of file cdt.c.

References FALSE, GTS_POINT, gts_point_in_circle(), GTS_VERTEX, TRUE, _GtsSegment::v1, and _GtsSegment::v2.

Referenced by triangulate_polygon().

Here is the call graph for this function:

static GSList* remove_intersected_edge	(	GtsSegment *	s,
		GtsEdge *	e,
		GtsFace *	f,
		GtsSurface *	surface,
		GSList **	left,
		GSList **	right
	)		`[static]`

Definition at line 837 of file cdt.c.

References GTS_IS_CONSTRAINT, GTS_OBJECT, gts_object_destroy(), GTS_POINT, gts_point_orientation(), GTS_TRIANGLE, gts_triangle_vertices_edges(), NEXT_CUT, remove_triangles(), _GtsEdge::triangles, _GtsSegment::v1, and _GtsSegment::v2.

Referenced by remove_intersected_vertex().

Here is the call graph for this function:

static GSList* remove_intersected_vertex	(	GtsSegment *	s,
		GtsVertex *	v,
		GtsSurface *	surface,
		GSList **	left,
		GSList **	right,
		GtsFace **	ref
	)		`[static]`

Definition at line 896 of file cdt.c.

References FALSE, gts_allow_floating_faces, GTS_FACE, gts_face_has_parent_surface(), GTS_IS_FACE, GTS_POINT, gts_point_orientation(), gts_surface_remove_face(), gts_triangle_edge_opposite(), gts_triangle_vertices(), gts_triangle_vertices_edges(), gts_vertex_triangles(), neighbor(), remove_intersected_edge(), TRUE, and _GtsSegment::v2.

Referenced by gts_delaunay_add_constraint().

Here is the call graph for this function:

static void remove_triangles	(	GtsEdge *	e,
		GtsSurface *	s
	)		`[static]`

Definition at line 823 of file cdt.c.

References gts_face_has_parent_surface(), GTS_IS_FACE, gts_surface_remove_face(), and _GtsEdge::triangles.

Referenced by remove_intersected_edge().

Here is the call graph for this function:

static void split_list	(	GtsListFace *	f,
		GtsListFace *	f1,
		GtsListFace *	f2,
		GtsPoint *	p1,
		GtsPoint *	p2,
		GSList **	last1,
		GSList **	last2
	)		`[static]`

Definition at line 412 of file cdt.c.

References gts_point_orientation(), and _GtsListFace::points.

Referenced by swap_if_in_circle().

Here is the call graph for this function:

static void swap_if_in_circle	(	GtsFace *	f1,
		GtsVertex *	v1,
		GtsVertex *	v2,
		GtsVertex *	v3,
		GtsEdge *	e1,
		GtsEdge *	e2,
		GtsEdge *	e3,
		GtsSurface *	surface
	)		`[static]`