pcb 4.1.1
An interactive printed circuit board layout editor.

cdt.c File Reference

#include <math.h>
#include "gts.h"
Include dependency graph for cdt.c:

Go to the source code of this file.

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 GtsFaceclosest_face (GtsSurface *s, GtsPoint *p)
static GtsFaceneighbor (GtsFace *f, GtsEdge *e, GtsSurface *surface)
static GtsEdgetriangle_next_edge (GtsTriangle *t, GtsPoint *o, GtsPoint *p, gboolean *on_summit)
static void triangle_barycenter (GtsTriangle *t, GtsPoint *b)
static GtsFacepoint_locate (GtsPoint *o, GtsPoint *p, GtsFace *f, GtsSurface *surface)
GtsFacegts_point_locate (GtsPoint *p, GtsSurface *surface, GtsFace *guess)
GtsConstraintClassgts_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)
GtsVertexgts_delaunay_add_vertex_to_face (GtsSurface *surface, GtsVertex *v, GtsFace *f)
GtsVertexgts_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)
GtsFacegts_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)
GtsFaceClassgts_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]
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]
static GSList* remove_intersected_vertex ( GtsSegment s,
GtsVertex v,
GtsSurface surface,
GSList **  left,
GSList **  right,
GtsFace **  ref 
) [static]
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 triangle_barycenter ( GtsTriangle t,
GtsPoint b 
) [static]

Definition at line 246 of file cdt.c.

References _GtsTriangle::e1, GTS_POINT, GTS_SEGMENT, gts_triangle_vertex, _GtsPoint::x, and _GtsPoint::y.

Referenced by gts_point_locate(), and point_locate().

static GtsEdge* triangle_next_edge ( GtsTriangle t,
GtsPoint o,
GtsPoint p,
gboolean *  on_summit 
) [static]

Definition at line 191 of file cdt.c.

References FALSE, GTS_POINT, gts_point_orientation(), gts_triangle_vertices_edges(), and TRUE.

Referenced by point_locate().

Here is the call graph for this function:

static void triangulate_polygon ( GSList *  poly,
GtsSurface surface,
GtsFace ref 
) [static]