pcb 4.1.1
An interactive printed circuit board layout editor.

refine.c File Reference

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

Go to the source code of this file.

Defines

#define ALREADY_ENCROACHED(c)   (GTS_OBJECT (c)->reserved)
#define SQUARE_ROOT_TWO   1.41421356237309504880168872420969807856967187
#define DISTANCE_2D(v1, v2)
#define EHEAP_PAIR(f)   (GTS_OBJECT (f)->reserved)

Functions

gboolean gts_vertex_encroaches_edge (GtsVertex *v, GtsEdge *e)
GtsVertexgts_edge_is_encroached (GtsEdge *e, GtsSurface *s, GtsEncroachFunc encroaches, gpointer data)
static void vertex_encroaches (GtsVertex *v, GtsSurface *surface, GtsFifo *encroached, GtsEncroachFunc encroaches, gpointer data)
static void make_encroached_fifo (GtsEdge *e, gpointer *datas)
static GtsVertexsplit_edge (GtsEdge *e, GtsSurface *surface)
static gint split_encroached (GtsSurface *surface, GtsFifo *encroached, gint steiner_max, GtsEncroachFunc encroaches, gpointer data)
guint gts_delaunay_conform (GtsSurface *surface, gint steiner_max, GtsEncroachFunc encroaches, gpointer data)
static void heap_surface_add_face (GtsSurface *s, GtsFace *f)
static void heap_surface_remove_face (GtsSurface *s, GtsFace *f)
static void heap_surface_class_init (GtsSurfaceClass *klass)
static GtsObjectClassheap_surface_class_new (GtsObjectClass *parent_class)
static void make_face_heap (GtsFace *f, GtsEHeap *heap)
guint gts_delaunay_refine (GtsSurface *surface, gint steiner_max, GtsEncroachFunc encroaches, gpointer encroach_data, GtsKeyFunc cost, gpointer cost_data)

Define Documentation

#define ALREADY_ENCROACHED (   c)    (GTS_OBJECT (c)->reserved)

Definition at line 82 of file refine.c.

Referenced by make_encroached_fifo(), split_encroached(), and vertex_encroaches().

#define DISTANCE_2D (   v1,
  v2 
)
Value:
(sqrt ((GTS_POINT (v2)->x - GTS_POINT (v1)->x)*\
                                   (GTS_POINT (v2)->x - GTS_POINT (v1)->x) +\
                                   (GTS_POINT (v2)->y - GTS_POINT (v1)->y)*\
                                   (GTS_POINT (v2)->y - GTS_POINT (v1)->y)))

Definition at line 129 of file refine.c.

Referenced by split_edge().

#define EHEAP_PAIR (   f)    (GTS_OBJECT (f)->reserved)
#define SQUARE_ROOT_TWO   1.41421356237309504880168872420969807856967187

Definition at line 128 of file refine.c.

Referenced by split_edge().


Function Documentation

guint gts_delaunay_conform ( GtsSurface surface,
gint  steiner_max,
GtsEncroachFunc  encroaches,
gpointer  data 
)

gts_delaunay_conform: : a GtsSurface describing a constrained Delaunay triangulation. : maximum number of Steiner points. : a GtsEncroachFunc. : user-data to pass to .

Recursively split constraints of which are encroached by vertices of (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 , the resulting surface will be Delaunay conforming.

If 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.

Returns: the number of remaining encroached edges. If is set to a negative value and gts_vertex_encroaches_edge() is used for this should always be zero.

Definition at line 266 of file refine.c.

References gts_fifo_destroy(), gts_fifo_foreach(), gts_fifo_new(), gts_fifo_size(), gts_object_reset_reserved(), gts_surface_foreach_edge(), make_encroached_fifo(), and split_encroached().

Here is the call graph for this function:

guint gts_delaunay_refine ( GtsSurface surface,
gint  steiner_max,
GtsEncroachFunc  encroaches,
gpointer  encroach_data,
GtsKeyFunc  cost,
gpointer  cost_data 
)

gts_delaunay_refine: : a GtsSurface describing a conforming Delaunay triangulation. : maximum number of Steiner points. : a GtsEncroachFunc. : user-data to pass to . : a GtsKeyFunc used to sort the faces during refinement. : user-data to pass to .

An implementation of the refinement algorithm described in Ruppert (1995) and Shewchuk (1996).

Returns: the number of unrefined faces of left. Should be zero if is set to a negative value.

Definition at line 362 of file refine.c.

References c, EHEAP_PAIR, f, gts_delaunay_add_vertex(), gts_delaunay_remove_vertex(), gts_eheap_destroy(), gts_eheap_foreach(), gts_eheap_new(), gts_eheap_remove_top(), gts_eheap_size(), gts_fifo_destroy(), gts_fifo_foreach(), gts_fifo_is_empty(), gts_fifo_new(), GTS_OBJECT, gts_object_reset_reserved(), GTS_POINT_CLASS, gts_surface_foreach_face(), GTS_TRIANGLE, gts_triangle_circumcircle_center(), GTS_VERTEX, heap_surface_class_new(), make_face_heap(), split_encroached(), _GtsSurface::vertex_class, and vertex_encroaches().

Here is the call graph for this function:

GtsVertex* gts_edge_is_encroached ( GtsEdge e,
GtsSurface s,
GtsEncroachFunc  encroaches,
gpointer  data 
)

gts_edge_is_encroached: : a GtsEdge. : a GtsSurface describing a (constrained) Delaunay triangulation. : a GtsEncroachFunc. : user data to be passed to .

Returns: a GtsVertex belonging to and encroaching upon (as defined by ) or NULL if there is none.

Definition at line 57 of file refine.c.

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

Referenced by make_encroached_fifo(), and split_encroached().

Here is the call graph for this function:

gboolean gts_vertex_encroaches_edge ( GtsVertex v,
GtsEdge e 
)

gts_vertex_encroaches_edge: : a GtsVertex. : a GtsEdge.

Returns: TRUE if is strictly contained in the diametral circle of , FALSE otherwise.

Definition at line 31 of file refine.c.

References FALSE, GTS_POINT, GTS_SEGMENT, TRUE, _GtsPoint::x, and _GtsPoint::y.

static void heap_surface_add_face ( GtsSurface s,
GtsFace f 
) [static]

Definition at line 297 of file refine.c.

References EHEAP_PAIR, gts_eheap_insert_with_key(), gts_eheap_key(), GTS_OBJECT, and GTS_SURFACE_CLASS.

Referenced by heap_surface_class_init().

Here is the call graph for this function:

static void heap_surface_class_init ( GtsSurfaceClass klass) [static]

Definition at line 322 of file refine.c.

References _GtsSurfaceClass::add_face, heap_surface_add_face(), heap_surface_remove_face(), and _GtsSurfaceClass::remove_face.

Referenced by heap_surface_class_new().

Here is the call graph for this function:

static GtsObjectClass* heap_surface_class_new ( GtsObjectClass parent_class) [static]

Definition at line 328 of file refine.c.

References _GtsObjectClassInfo::class_init_func, gts_object_class_new(), heap_surface_class_init(), and _GtsObjectClass::info.

Referenced by gts_delaunay_refine().

Here is the call graph for this function:

static void heap_surface_remove_face ( GtsSurface s,
GtsFace f 
) [static]

Definition at line 310 of file refine.c.

References EHEAP_PAIR, gts_eheap_remove(), GTS_OBJECT, and GTS_SURFACE_CLASS.

Referenced by heap_surface_class_init().

Here is the call graph for this function:

static void make_encroached_fifo ( GtsEdge e,
gpointer *  datas 
) [static]

Definition at line 114 of file refine.c.

References ALREADY_ENCROACHED, gts_edge_is_encroached(), gts_fifo_push(), GTS_IS_CONSTRAINT, and s.

Referenced by gts_delaunay_conform().

Here is the call graph for this function:

static void make_face_heap ( GtsFace f,
GtsEHeap heap 
) [static]

Definition at line 339 of file refine.c.

References EHEAP_PAIR, gts_eheap_insert_with_key(), and gts_eheap_key().

Referenced by gts_delaunay_refine().

Here is the call graph for this function:

static void vertex_encroaches ( GtsVertex v,
GtsSurface surface,
GtsFifo encroached,
GtsEncroachFunc  encroaches,
gpointer  data 
) [static]