26static int triangle_is_hole(
void *
triangle,
void *ignored) {
30 GtsEdge *e1, *e2, *e3;
31 GtsVertex *v1, *v2, *v3;
33 gts_triangle_vertices_edges(t,
NULL, &v1, &v2, &v3, &e1, &e2, &e3);
35 if ((GTS_IS_CONSTRAINT(e1) && GTS_SEGMENT(e1)->v1 != v1) ||
36 (GTS_IS_CONSTRAINT(e2) && GTS_SEGMENT(e2)->v1 != v2) ||
37 (GTS_IS_CONSTRAINT(e3) && GTS_SEGMENT(e3)->v1 != v3))
43static unsigned delaunay_remove_holes(GtsSurface *surface) {
44 return gts_surface_foreach_face_remove(surface, triangle_is_hole,
NULL);
58 GtsVertexClass parent_class;
61static GtsVertexClass *g_vertex_class(
void) {
62 static GVertexClass *klass =
NULL;
65 GtsObjectClassInfo vertex_info = {
67 .object_size =
sizeof(GVertex),
68 .class_size =
sizeof(GVertexClass),
70 klass = gts_object_class_new(GTS_OBJECT_CLASS(gts_vertex_class()),
74 return &klass->parent_class;
83 GtsFaceClass parent_class;
86static GtsFaceClass *g_face_class(
void) {
87 static GFaceClass *klass =
NULL;
90 GtsObjectClassInfo face_info = {
92 .object_size =
sizeof(GFace),
93 .class_size =
sizeof(GFaceClass),
95 klass = gts_object_class_new(GTS_OBJECT_CLASS(gts_face_class()),
99 return &klass->parent_class;
106destroy (GtsVertex* v)
112 GSList * next = i->next;
113 gts_object_destroy (i->data);
116 g_assert (v->segments ==
NULL);
117 gts_object_destroy(GTS_OBJECT(v));
132tri(
double *x,
double *y,
int npt,
int *segs,
int nsegs,
int sepArr)
136 GVertex **vertices =
gv_calloc(npt,
sizeof(GVertex *));
137 GtsEdge **edges =
gv_calloc(nsegs,
sizeof(GtsEdge *));
139 GtsVertex *v1, *v2, *v3;
141 GtsVertexClass *vcl = g_vertex_class();
142 GtsEdgeClass *ecl = GTS_EDGE_CLASS (gts_constraint_class ());
145 for (i = 0; i < npt; i++) {
146 GVertex *p = (GVertex *) gts_vertex_new(vcl, x[i], y[i], 0);
152 for (i = 0; i < npt; i++) {
153 GVertex *p = (GVertex *) gts_vertex_new(vcl, x[2*i], x[2*i+1], 0);
163 for (i = 0; i < nsegs; i++) {
164 edges[i] = gts_edge_new(ecl,
165 (GtsVertex *)vertices[segs[2 * i]],
166 (GtsVertex *)vertices[segs[2 * i + 1]]);
169 for (i = 0; i < npt; i++)
170 list = g_slist_prepend(list, vertices[i]);
171 t = gts_triangle_enclosing(gts_triangle_class(), list, 100.);
174 gts_triangle_vertices(t, &v1, &v2, &v3);
176 surface = gts_surface_new(gts_surface_class(), g_face_class(),
177 gts_edge_class(), gts_vertex_class());
178 gts_surface_add_face(surface, gts_face_new(gts_face_class(),
179 t->e1, t->e2, t->e3));
181 for (i = 0; i < npt; i++) {
182 GtsVertex *v4 = (GtsVertex *)vertices[i];
183 GtsVertex *v = gts_delaunay_add_vertex(surface, v4,
NULL);
189 gts_vertex_replace(v4, v);
193 for (i = 0; i < nsegs; i++) {
194 gts_delaunay_add_constraint(surface,GTS_CONSTRAINT(edges[i]));
198 gts_allow_floating_vertices = TRUE;
199 gts_allow_floating_edges = TRUE;
203 gts_allow_floating_edges = FALSE;
204 gts_allow_floating_vertices = FALSE;
207 delaunay_remove_holes(surface);
219static int cnt_edge(
void *
edge,
void *stats) {
220 GtsSegment *e =
edge;
225 sp->delaunay[((GVertex*)e->v1)->idx].
nedges++;
226 sp->delaunay[((GVertex*)e->v2)->idx].nedges++;
233edgeStats (GtsSurface*
s, estats* sp)
235 gts_surface_foreach_edge(
s, cnt_edge, sp);
239 GtsSegment *e =
edge;
242 int source = ((GVertex*)e->v1)->idx;
243 int dest = ((GVertex*)e->v2)->idx;
245 delaunay[source].
edges[delaunay[source].
nedges++] = dest;
246 delaunay[dest].
edges[delaunay[dest].
nedges++] = source;
252 GtsSurface*
s =
tri(x, y, n,
NULL, 0, 1);
260 for (i = 0; i < n; i++) {
266 stats.delaunay = delaunay;
267 edgeStats (
s, &stats);
271 for (i = 0; i < n; i++) {
272 delaunay[i].
edges = edges;
273 edges += delaunay[i].
nedges;
274 delaunay[i].
edges[0] = i;
277 gts_surface_foreach_edge(
s,
add_edge, delaunay);
279 gts_object_destroy (GTS_OBJECT (
s));
290 GtsSegment *e =
edge;
293 int source = ((GVertex*)e->v1)->idx;
294 int dest = ((GVertex*)e->v2)->idx;
296 es->
edges[2 * es->n] = source;
297 es->edges[2 * es->n + 1] = dest;
303static int vcmp(
const void *x,
const void *y,
void *values) {
306 const double *_vals = values;
307 double va = _vals[*a];
308 double vb = _vals[*b];
310 if (va < vb)
return -1;
311 if (va > vb)
return 1;
327int *
delaunay_tri(
double *x,
double *y,
int n,
int* pnedges)
329 GtsSurface*
s =
tri(x, y, n,
NULL, 0, 1);
338 stats.delaunay =
NULL;
339 edgeStats (
s, &stats);
340 *pnedges =
nedges = stats.n;
346 gts_surface_foreach_edge(
s,
addEdge, &state);
356 for (i = 0; i < n; i++)
359 gv_sort(vs, n,
sizeof(
int), vcmp, x[0] == x[1] ? y : x);
362 for (i = 1; i < n; i++) {
372 gts_object_destroy (GTS_OBJECT (
s));
377static int cntFace(
void *face,
void *
data) {
398static int addNeighbor(
void *face,
void *ni) {
402 es->neigh[es->nneigh] = f->idx;
408static int addFace(
void *face,
void *state) {
412 int i, myid = f->idx;
413 int* ip = es->faces + 3*myid;
414 int* neigh = es->neigh + 3*myid;
416 GtsVertex *v1, *v2, *v3;
418 gts_triangle_vertices (&f->v.triangle, &v1, &v2, &v3);
419 *ip++ = ((GVertex*)v1)->idx;
420 *ip++ = ((GVertex*)v2)->idx;
421 *ip++ = ((GVertex*)v3)->idx;
425 gts_face_foreach_neighbor((GtsFace*)f, 0, addNeighbor, &ni);
426 for (i = ni.nneigh; i < 3; i++)
432static int addTri(
void *face,
void *state) {
437 int* ip = es->faces + 3*myid;
438 GtsVertex *v1, *v2, *v3;
440 gts_triangle_vertices (&f->v.triangle, &v1, &v2, &v3);
441 *ip++ = ((GVertex*)v1)->idx;
442 *ip++ = ((GVertex*)v2)->idx;
443 *ip++ = ((GVertex*)v3)->idx;
456mkSurface (
double *x,
double *y,
int n,
int* segs,
int nsegs)
458 GtsSurface*
s =
tri(x, y, n, segs, nsegs, 1);
468 stats.delaunay =
NULL;
469 edgeStats (
s, &stats);
471 segs =
gv_calloc(2 * nsegs,
sizeof(
int));
475 gts_surface_foreach_edge(
s,
addEdge, &state);
477 gts_surface_foreach_face(
s, cntFace, &nfaces);
479 int *faces =
gv_calloc(3 * nfaces,
sizeof(
int));
480 int *neigh =
gv_calloc(3 * nfaces,
sizeof(
int));
484 gts_surface_foreach_face(
s, addFace, &statf);
492 gts_object_destroy (GTS_OBJECT (
s));
511 if (n <= 2)
return NULL;
516 gts_surface_foreach_face(
s, cntFace, &nfaces);
517 statf.faces =
gv_calloc(3 * nfaces,
sizeof(
int));
518 gts_surface_foreach_face(
s,
addTri, &statf);
520 gts_object_destroy (GTS_OBJECT (
s));
535static char*
err =
"Graphviz built without any triangulation library\n";
564mkSurface (
double *x,
double *y,
int n,
int* segs,
int nsegs)
587 for (i = 1; i <
graph[source].nedges; i++) {
588 if (
graph[source].edges[i] == dest) {
598 double dist_ij, dist_ik, dist_jk, x_i, y_i, x_j, y_j;
599 int j, k, neighbor_j, neighbor_k;
605 delaunay[0].
edges = edges;
607 delaunay[0].
edges[0] = 0;
608 delaunay[0].
edges[1] = 1;
609 delaunay[1].
edges = edges + 2;
612 delaunay[1].
edges[0] = 1;
613 delaunay[1].
edges[1] = 0;
619 delaunay[0].
edges = edges;
621 delaunay[0].
edges[0] = 0;
628 for (i = 0; i < n; i++) {
631 for (j = 1; j < delaunay[i].
nedges;) {
632 neighbor_j = delaunay[i].
edges[j];
635 dist_ij = (x_j - x_i) * (x_j - x_i) + (y_j - y_i) * (y_j - y_i);
638 bool removed =
false;
639 for (k = 1; k < delaunay[i].
nedges && !removed; k++) {
640 neighbor_k = delaunay[i].
edges[k];
641 dist_ik = (x[neighbor_k] - x_i) * (x[neighbor_k] - x_i) +
642 (y[neighbor_k] - y_i) * (y[neighbor_k] - y_i);
643 if (dist_ik < dist_ij) {
644 dist_jk = (x[neighbor_k] - x_j) * (x[neighbor_k] - x_j) +
645 (y[neighbor_k] - y_j) * (y[neighbor_k] - y_j);
646 if (dist_jk < dist_ij) {
Memory allocation wrappers that exit on failure.
static void * gv_calloc(size_t nmemb, size_t size)
static void * gv_alloc(size_t size)
abstract graph C library, Cgraph API
int * get_triangles(double *x, int n, int *tris)
void freeGraph(v_data *graph)
v_data * UG_graph(double *x, double *y, int n)
void freeGraphData(vtx_data *graph)
static v_data * delaunay_triangulation(double *x, double *y, int n)
surface_t * mkSurface(double *x, double *y, int n, int *segs, int nsegs)
static void remove_edge(v_data *graph, int source, int dest)
int * delaunay_tri(double *x, double *y, int n, int *nedges)
void freeSurface(surface_t *s)
void add_edge(edgelist *list, Agedge_t *e)
void agerrorf(const char *fmt,...)
Agraph_t * graph(char *name)
static void addEdge(edge_t *de, edge_t *e)
static tri * addTri(int i, int j, tri *oldp)
static int nedges
total no. of edges used in routing
qsort with carried along context
static void gv_sort(void *base, size_t nmemb, size_t size, int(*compar)(const void *, const void *, void *), void *arg)
qsort with an extra state parameter, ala qsort_r