27static int triangle_is_hole(
void *
triangle,
void *ignored) {
31 GtsEdge *e1, *e2, *e3;
32 GtsVertex *v1, *v2, *v3;
34 gts_triangle_vertices_edges(t,
NULL, &v1, &v2, &v3, &e1, &e2, &e3);
36 if ((GTS_IS_CONSTRAINT(e1) && GTS_SEGMENT(e1)->v1 != v1) ||
37 (GTS_IS_CONSTRAINT(e2) && GTS_SEGMENT(e2)->v1 != v2) ||
38 (GTS_IS_CONSTRAINT(e3) && GTS_SEGMENT(e3)->v1 != v3))
44static unsigned delaunay_remove_holes(GtsSurface *surface) {
45 return gts_surface_foreach_face_remove(surface, triangle_is_hole,
NULL);
59static GVertex *downcast(GtsVertex *base) {
60 return (GVertex *)((
char *)base - offsetof(GVertex, v));
64static GtsVertex *upcast(GVertex *derived) {
69 GtsVertexClass parent_class;
72static GtsVertexClass *g_vertex_class(
void) {
73 static GVertexClass *klass =
NULL;
76 GtsObjectClassInfo vertex_info = {
78 .object_size =
sizeof(GVertex),
79 .class_size =
sizeof(GVertexClass),
81 klass = gts_object_class_new(GTS_OBJECT_CLASS(gts_vertex_class()),
85 return &klass->parent_class;
94 GtsFaceClass parent_class;
97static GtsFaceClass *g_face_class(
void) {
98 static GFaceClass *klass =
NULL;
101 GtsObjectClassInfo face_info = {
103 .object_size =
sizeof(GFace),
104 .class_size =
sizeof(GFaceClass),
106 klass = gts_object_class_new(GTS_OBJECT_CLASS(gts_face_class()),
110 return &klass->parent_class;
117destroy (GtsVertex* v)
123 GSList * next = i->next;
124 gts_object_destroy (i->data);
127 g_assert (v->segments ==
NULL);
128 gts_object_destroy(GTS_OBJECT(v));
143tri(
double *x,
double *y,
int npt,
int *segs,
int nsegs,
int sepArr)
147 GVertex **vertices =
gv_calloc(npt,
sizeof(GVertex *));
148 GtsEdge **edges =
gv_calloc(nsegs,
sizeof(GtsEdge *));
150 GtsVertex *v1, *v2, *v3;
152 GtsVertexClass *vcl = g_vertex_class();
153 GtsEdgeClass *ecl = GTS_EDGE_CLASS (gts_constraint_class ());
156 for (i = 0; i < npt; i++) {
157 GVertex *p = downcast(gts_vertex_new(vcl, x[i], y[i], 0));
163 for (i = 0; i < npt; i++) {
164 GVertex *p = downcast(gts_vertex_new(vcl, x[2*i], x[2*i+1], 0));
174 for (i = 0; i < nsegs; i++) {
175 edges[i] = gts_edge_new(ecl,
176 upcast(vertices[segs[2 * i]]),
177 upcast(vertices[segs[2 * i + 1]]));
180 for (i = 0; i < npt; i++)
181 list = g_slist_prepend(list, vertices[i]);
182 t = gts_triangle_enclosing(gts_triangle_class(), list, 100.);
185 gts_triangle_vertices(t, &v1, &v2, &v3);
187 surface = gts_surface_new(gts_surface_class(), g_face_class(),
188 gts_edge_class(), gts_vertex_class());
189 gts_surface_add_face(surface, gts_face_new(gts_face_class(),
190 t->e1, t->e2, t->e3));
192 for (i = 0; i < npt; i++) {
193 GtsVertex *v4 = upcast(vertices[i]);
194 GtsVertex *v = gts_delaunay_add_vertex(surface, v4,
NULL);
200 gts_vertex_replace(v4, v);
204 for (i = 0; i < nsegs; i++) {
205 gts_delaunay_add_constraint(surface,GTS_CONSTRAINT(edges[i]));
209 gts_allow_floating_vertices = TRUE;
210 gts_allow_floating_edges = TRUE;
214 gts_allow_floating_edges = FALSE;
215 gts_allow_floating_vertices = FALSE;
218 delaunay_remove_holes(surface);
230static int cnt_edge(
void *
edge,
void *stats) {
231 GtsSegment *e =
edge;
236 sp->delaunay[downcast(e->v1)->idx].
nedges++;
237 sp->delaunay[downcast(e->v2)->idx].nedges++;
244edgeStats (GtsSurface*
s, estats* sp)
246 gts_surface_foreach_edge(
s, cnt_edge, sp);
250 GtsSegment *e =
edge;
253 int source = downcast(e->v1)->idx;
254 int dest = downcast(e->v2)->idx;
256 delaunay[source].
edges[delaunay[source].
nedges++] = dest;
257 delaunay[dest].
edges[delaunay[dest].
nedges++] = source;
263 GtsSurface*
s =
tri(x, y, n,
NULL, 0, 1);
271 for (i = 0; i < n; i++) {
277 stats.delaunay = delaunay;
278 edgeStats (
s, &stats);
282 for (i = 0; i < n; i++) {
283 delaunay[i].
edges = edges;
284 edges += delaunay[i].
nedges;
285 delaunay[i].
edges[0] = i;
288 gts_surface_foreach_edge(
s,
add_edge, delaunay);
290 gts_object_destroy (GTS_OBJECT (
s));
301 GtsSegment *e =
edge;
304 int source = downcast(e->v1)->idx;
305 int dest = downcast(e->v2)->idx;
307 es->
edges[2 * es->n] = source;
308 es->edges[2 * es->n + 1] = dest;
314static int vcmp(
const void *x,
const void *y,
void *values) {
317 const double *_vals = values;
318 double va = _vals[*a];
319 double vb = _vals[*b];
321 if (va < vb)
return -1;
322 if (va > vb)
return 1;
338int *
delaunay_tri(
double *x,
double *y,
int n,
int* pnedges)
340 GtsSurface*
s =
tri(x, y, n,
NULL, 0, 1);
349 stats.delaunay =
NULL;
350 edgeStats (
s, &stats);
351 *pnedges =
nedges = stats.n;
357 gts_surface_foreach_edge(
s,
addEdge, &state);
367 for (i = 0; i < n; i++)
370 gv_sort(vs, n,
sizeof(
int), vcmp, x[0] == x[1] ? y : x);
373 for (i = 1; i < n; i++) {
383 gts_object_destroy (GTS_OBJECT (
s));
388static int cntFace(
void *face,
void *
data) {
409static int addNeighbor(
void *face,
void *ni) {
413 es->neigh[es->nneigh] = f->idx;
419static int addFace(
void *face,
void *state) {
423 int i, myid = f->idx;
424 int* ip = es->faces + 3*myid;
425 int* neigh = es->neigh + 3*myid;
427 GtsVertex *v1, *v2, *v3;
429 gts_triangle_vertices (&f->v.triangle, &v1, &v2, &v3);
430 *ip++ = downcast(v1)->idx;
431 *ip++ = downcast(v2)->idx;
432 *ip++ = downcast(v3)->idx;
436 gts_face_foreach_neighbor((GtsFace*)f, 0, addNeighbor, &ni);
437 for (i = ni.nneigh; i < 3; i++)
443static int addTri(
void *face,
void *state) {
448 int* ip = es->faces + 3*myid;
449 GtsVertex *v1, *v2, *v3;
451 gts_triangle_vertices (&f->v.triangle, &v1, &v2, &v3);
452 *ip++ = downcast(v1)->idx;
453 *ip++ = downcast(v2)->idx;
454 *ip++ = downcast(v3)->idx;
467mkSurface (
double *x,
double *y,
int n,
int* segs,
int nsegs)
469 GtsSurface*
s =
tri(x, y, n, segs, nsegs, 1);
479 stats.delaunay =
NULL;
480 edgeStats (
s, &stats);
482 segs =
gv_calloc(2 * nsegs,
sizeof(
int));
486 gts_surface_foreach_edge(
s,
addEdge, &state);
488 gts_surface_foreach_face(
s, cntFace, &nfaces);
490 int *faces =
gv_calloc(3 * nfaces,
sizeof(
int));
491 int *neigh =
gv_calloc(3 * nfaces,
sizeof(
int));
495 gts_surface_foreach_face(
s, addFace, &statf);
503 gts_object_destroy (GTS_OBJECT (
s));
522 if (n <= 2)
return NULL;
527 gts_surface_foreach_face(
s, cntFace, &nfaces);
528 statf.faces =
gv_calloc(3 * nfaces,
sizeof(
int));
529 gts_surface_foreach_face(
s,
addTri, &statf);
531 gts_object_destroy (GTS_OBJECT (
s));
546static char*
err =
"Graphviz built without any triangulation library\n";
575mkSurface (
double *x,
double *y,
int n,
int* segs,
int nsegs)
598 for (i = 1; i <
graph[source].nedges; i++) {
599 if (
graph[source].edges[i] == dest) {
609 double dist_ij, dist_ik, dist_jk, x_i, y_i, x_j, y_j;
610 int j, k, neighbor_j, neighbor_k;
616 delaunay[0].
edges = edges;
618 delaunay[0].
edges[0] = 0;
619 delaunay[0].
edges[1] = 1;
620 delaunay[1].
edges = edges + 2;
623 delaunay[1].
edges[0] = 1;
624 delaunay[1].
edges[1] = 0;
630 delaunay[0].
edges = edges;
632 delaunay[0].
edges[0] = 0;
639 for (i = 0; i < n; i++) {
642 for (j = 1; j < delaunay[i].
nedges;) {
643 neighbor_j = delaunay[i].
edges[j];
646 dist_ij = (x_j - x_i) * (x_j - x_i) + (y_j - y_i) * (y_j - y_i);
649 bool removed =
false;
650 for (k = 1; k < delaunay[i].
nedges && !removed; k++) {
651 neighbor_k = delaunay[i].
edges[k];
652 dist_ik = (x[neighbor_k] - x_i) * (x[neighbor_k] - x_i) +
653 (y[neighbor_k] - y_i) * (y[neighbor_k] - y_i);
654 if (dist_ik < dist_ij) {
655 dist_jk = (x[neighbor_k] - x_j) * (x[neighbor_k] - x_j) +
656 (y[neighbor_k] - y_j) * (y[neighbor_k] - y_j);
657 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