41static void printboxes(
size_t boxn,
boxf *boxes) {
44 for (
size_t bi = 0; bi < boxn; bi++) {
45 ll = boxes[bi].
LL, ur = boxes[bi].
UR;
47 agxbprint(&buf,
"%.0f %.0f %.0f %.0f pathbox", ll.
x, ll.
y, ur.
x, ur.
y);
56 for (
size_t i = 0; i < spl.
pn; i++) {
59 i == 0 ?
"moveto" : (i % 3 == 0 ?
"curveto" :
""));
69 for (
size_t i = 0; i < pl.
pn; i++) {
72 i == 0 ?
"moveto" :
"lineto");
78static void psprintpoly(
Ppoly_t p) {
83 for (
size_t bi = 0; bi < p.
pn; bi++) {
86 if (fabs(tail.x -
head.x) < 1 && fabs(tail.y -
head.y) < 1)
91 agxbprint(&buf,
"%s%.0f %.0f %.0f %.0f makevec", pfx, tail.x, tail.y,
98static void psprintboxes(
size_t boxn,
boxf *boxes) {
103 for (
size_t bi = 0; bi < boxn; bi++) {
104 ll = boxes[bi].
LL, ur = boxes[bi].
UR;
106 agxbprint(&buf,
"newpath\n%.0f %.0f moveto", ll.
x, ll.
y);
119static void psprintinit(
int begin) {
126static bool debugleveln(
edge_t *realedge,
int i) {
152 for (
size_t i = 0; i <
poly.pn; i++) {
153 edges[i].
a =
poly.ps[i];
163 pointf *ps = calloc(spl.
pn,
sizeof(ps[0]));
168 for (
size_t i = 0; i < spl.
pn; i++) {
201 const double num_div =
delta * (double)boxn;
203 for (
size_t splinepi = 0; splinepi + 3 < pn; splinepi += 3) {
204 for (
double si = 0; si <= num_div; si++) {
206 sp[0] = pps[splinepi];
207 sp[1] = pps[splinepi + 1];
208 sp[2] = pps[splinepi + 2];
209 sp[3] = pps[splinepi + 3];
210 sp[0].
x += t * (sp[1].
x - sp[0].
x);
211 sp[0].
y += t * (sp[1].
y - sp[0].
y);
212 sp[1].
x += t * (sp[2].
x - sp[1].
x);
213 sp[1].
y += t * (sp[2].
y - sp[1].
y);
214 sp[2].
x += t * (sp[3].
x - sp[2].
x);
215 sp[2].
y += t * (sp[3].
y - sp[2].
y);
216 sp[0].
x += t * (sp[1].
x - sp[0].
x);
217 sp[0].
y += t * (sp[1].
y - sp[0].
y);
218 sp[1].
x += t * (sp[2].
x - sp[1].
x);
219 sp[1].
y += t * (sp[2].
y - sp[1].
y);
220 sp[0].
x += t * (sp[1].
x - sp[0].
x);
221 sp[0].
y += t * (sp[1].
y - sp[0].
y);
222 for (
size_t bi = 0; bi < boxn; bi++) {
226 if (sp[0].y <= boxes[bi].UR.y +
FUDGE &&
228 boxes[bi].
LL.
x = fmin(boxes[bi].LL.x, sp[0].
x);
229 boxes[bi].
UR.
x = fmax(boxes[bi].UR.x, sp[0].
x);
275 agerrorf(
"in routesplines, cannot find NORMAL edge\n");
280 const size_t boxn = pp->
nbox;
286 if (debugleveln(realedge, 1))
287 printboxes(boxn, boxes);
288 if (debugleveln(realedge, 3)) {
290 psprintboxes(boxn, boxes);
297 if (boxn > 1 && boxes[0].LL.y > boxes[1].
LL.
y) {
299 for (
size_t bi = 0; bi < boxn; bi++) {
300 double v = boxes[bi].
UR.
y;
301 boxes[bi].
UR.
y = -1 * boxes[bi].
LL.
y;
312 for (bi = 0, pi = 0; bi < boxn; bi++) {
315 prev = boxes[bi].
LL.
y > boxes[bi - 1].
LL.
y ? -1 : 1;
317 next = boxes[bi + 1].
LL.
y > boxes[bi].
LL.
y ? 1 : -1;
319 if (next == -1 ||
prev == 1) {
320 polypoints[pi].
x = boxes[bi].
LL.
x;
321 polypoints[pi++].
y = boxes[bi].
UR.
y;
322 polypoints[pi].
x = boxes[bi].
LL.
x;
323 polypoints[pi++].
y = boxes[bi].
LL.
y;
325 polypoints[pi].
x = boxes[bi].
UR.
x;
326 polypoints[pi++].
y = boxes[bi].
LL.
y;
327 polypoints[pi].
x = boxes[bi].
UR.
x;
328 polypoints[pi++].
y = boxes[bi].
UR.
y;
330 }
else if (
prev == 0) {
331 polypoints[pi].
x = boxes[bi].
LL.
x;
332 polypoints[pi++].
y = boxes[bi].
UR.
y;
333 polypoints[pi].
x = boxes[bi].
LL.
x;
334 polypoints[pi++].
y = boxes[bi].
LL.
y;
336 if (!(
prev == -1 && next == -1)) {
338 agerrorf(
"in routesplines, illegal values of prev %d and next %d, "
340 prev, next, __LINE__);
345 for (bi = boxn - 1; bi !=
SIZE_MAX; bi--) {
348 prev = boxes[bi].
LL.
y > boxes[bi + 1].
LL.
y ? -1 : 1;
350 next = boxes[bi - 1].
LL.
y > boxes[bi].
LL.
y ? 1 : -1;
352 if (next == -1 ||
prev == 1) {
353 polypoints[pi].
x = boxes[bi].
LL.
x;
354 polypoints[pi++].
y = boxes[bi].
UR.
y;
355 polypoints[pi].
x = boxes[bi].
LL.
x;
356 polypoints[pi++].
y = boxes[bi].
LL.
y;
358 polypoints[pi].
x = boxes[bi].
UR.
x;
359 polypoints[pi++].
y = boxes[bi].
LL.
y;
360 polypoints[pi].
x = boxes[bi].
UR.
x;
361 polypoints[pi++].
y = boxes[bi].
UR.
y;
363 }
else if (
prev == 0) {
364 polypoints[pi].
x = boxes[bi].
UR.
x;
365 polypoints[pi++].
y = boxes[bi].
LL.
y;
366 polypoints[pi].
x = boxes[bi].
UR.
x;
367 polypoints[pi++].
y = boxes[bi].
UR.
y;
369 if (!(
prev == -1 && next == -1)) {
372 agerrorf(
"in routesplines, illegal values of prev %d and next %d, "
374 prev, next, __LINE__);
377 polypoints[pi].
x = boxes[bi].
UR.
x;
378 polypoints[pi++].
y = boxes[bi].
LL.
y;
379 polypoints[pi].
x = boxes[bi].
UR.
x;
380 polypoints[pi++].
y = boxes[bi].
UR.
y;
381 polypoints[pi].
x = boxes[bi].
LL.
x;
382 polypoints[pi++].
y = boxes[bi].
UR.
y;
383 polypoints[pi].
x = boxes[bi].
LL.
x;
384 polypoints[pi++].
y = boxes[bi].
LL.
y;
389 agerrorf(
"in routesplines, edge is a loop at %s\n",
395 for (
size_t bi = 0; bi < boxn; bi++) {
396 double v = boxes[bi].
UR.
y;
397 boxes[bi].
UR.
y = -1 * boxes[bi].
LL.
y;
400 for (
size_t i = 0; i < pi; i++)
401 polypoints[i].y *= -1;
404 static const double INITIAL_LLX = DBL_MAX;
405 static const double INITIAL_URX = -DBL_MAX;
406 for (
size_t bi = 0; bi < boxn; bi++) {
407 boxes[bi].
LL.
x = INITIAL_LLX;
408 boxes[bi].
UR.
x = INITIAL_URX;
415 agerrorf(
"in routesplines, Pshortestpath failed\n");
419 if (debugleveln(realedge, 3)) {
429 for (
size_t edgei = 0; edgei <
poly.pn; edgei++) {
430 edges[edgei].
a = polypoints[edgei];
431 edges[edgei].
b = polypoints[(edgei + 1) %
poly.pn];
446 agerrorf(
"in routesplines, Proutespline failed\n");
451 if (debugleveln(realedge, 3)) {
457 pointf *ps = calloc(spl.
pn,
sizeof(ps[0]));
465 for (
size_t splinepi = 0; splinepi < spl.
pn; splinepi++) {
466 ps[splinepi] = spl.
ps[splinepi];
471 bool is_horizontal = spl.
pn > 0;
472 for (
size_t i = 0; i < spl.
pn; ++i) {
473 if (fabs(ps[0].y - ps[i].y) >
FUDGE) {
474 is_horizontal =
false;
479 GV_INFO(
"spline [%.03f, %.03f] -- [%.03f, %.03f] is horizontal;"
480 " will be trivially bounded",
481 ps[0].x, ps[0].y, ps[spl.
pn - 1].
x, ps[spl.
pn - 1].
y);
485 bool is_vertical = spl.
pn > 0;
486 for (
size_t i = 0; i < spl.
pn; ++i) {
487 if (fabs(ps[0].x - ps[i].x) >
FUDGE) {
493 GV_INFO(
"spline [%.03f, %.03f] -- [%.03f, %.03f] is vertical;"
494 " will be trivially bounded",
495 ps[0].x, ps[0].y, ps[spl.
pn - 1].
x, ps[spl.
pn - 1].
y);
500 if (is_horizontal || is_vertical) {
501 for (
size_t i = 0; i < boxn; ++i) {
502 boxes[i].
LL.
x = ps[0].
x;
503 boxes[i].
UR.
x = ps[0].
x;
511 for (loopcnt = 0; unbounded && loopcnt <
LOOP_TRIES; loopcnt++) {
520 for (bi = 0; bi < boxn; bi++) {
540 agwarningf(
"Unable to reclaim box space in spline routing for edge \"%s\" "
541 "-> \"%s\". Something is probably seriously wrong.\n",
554 printboxes(boxn, boxes);
569static double overlap(
double i0,
double i1,
double j0,
double j1) {
576 if (i0 <= j0 && i1 >= j1)
579 if (j0 <= i0 && j1 >= i1)
582 if (j0 <= i0 && i0 <= j1)
584 assert(j0 <= i1 && i1 <= j1);
599 int errs, l, r, d, u;
603 for (
size_t bi = 0; bi < boxn; bi++) {
604 if (fabs(boxes[bi].LL.y - boxes[bi].
UR.
y) < .01)
606 if (fabs(boxes[bi].LL.x - boxes[bi].
UR.
x) < .01)
608 boxes[i] = boxes[bi];
614 agerrorf(
"in checkpath, all bounding boxes are below threshold\n");
621 agerrorf(
"in checkpath, box 0 has LL coord > UR coord\n");
625 for (
size_t bi = 0; bi + 1 < boxn; bi++) {
626 ba = &boxes[bi], bb = &boxes[bi + 1];
627 if (bb->LL.x > bb->UR.x || bb->LL.y > bb->UR.y) {
633 l = ba->
UR.
x < bb->LL.x ? 1 : 0;
634 r = ba->
LL.
x > bb->UR.x ? 1 : 0;
635 d = ba->
UR.
y < bb->LL.y ? 1 : 0;
636 u = ba->
LL.
y > bb->UR.y ? 1 : 0;
637 errs = l + r + d + u;
649 xy = ba->
UR.
x, ba->
UR.
x = bb->LL.x, bb->LL.x = xy, l = 0;
651 xy = ba->
LL.
x, ba->
LL.
x = bb->UR.x, bb->UR.x = xy, r = 0;
653 xy = ba->
UR.
y, ba->
UR.
y = bb->LL.y, bb->LL.y = xy, d = 0;
655 xy = ba->
LL.
y, ba->
LL.
y = bb->UR.y, bb->UR.y = xy, u = 0;
656 for (
int j = 0; j < errs - 1; j++) {
658 xy = (ba->
UR.
x + bb->LL.x) / 2.0 + 0.5, ba->
UR.
x = bb->LL.x = xy,
661 xy = (ba->
LL.
x + bb->UR.x) / 2.0 + 0.5, ba->
LL.
x = bb->UR.x = xy,
664 xy = (ba->
UR.
y + bb->LL.y) / 2.0 + 0.5, ba->
UR.
y = bb->LL.y = xy,
667 xy = (ba->
LL.
y + bb->UR.y) / 2.0 + 0.5, ba->
LL.
y = bb->UR.y = xy,
672 double xoverlap =
overlap(ba->
LL.
x, ba->
UR.
x, bb->LL.x, bb->UR.x);
673 double yoverlap =
overlap(ba->
LL.
y, ba->
UR.
y, bb->LL.y, bb->UR.y);
674 if (xoverlap > 0 && yoverlap > 0) {
675 if (xoverlap < yoverlap) {
676 if (ba->
UR.
x - ba->
LL.
x > bb->UR.x - bb->LL.x) {
678 if (ba->
UR.
x < bb->UR.x)
684 if (ba->
UR.
x < bb->UR.x)
690 if (ba->
UR.
y - ba->
LL.
y > bb->UR.y - bb->LL.y) {
692 if (ba->
UR.
y < bb->UR.y)
698 if (ba->
UR.
y < bb->UR.y)
716 if (thepath->
end.
p.
x < boxes[boxn - 1].
LL.
x ||
717 thepath->
end.
p.
x > boxes[boxn - 1].
UR.
x ||
718 thepath->
end.
p.
y < boxes[boxn - 1].
LL.
y ||
719 thepath->
end.
p.
y > boxes[boxn - 1].
UR.
y) {
720 thepath->
end.
p.
x = fmax(thepath->
end.
p.
x, boxes[boxn - 1].
LL.
x);
721 thepath->
end.
p.
x = fmin(thepath->
end.
p.
x, boxes[boxn - 1].
UR.
x);
722 thepath->
end.
p.
y = fmax(thepath->
end.
p.
y, boxes[boxn - 1].
LL.
y);
723 thepath->
end.
p.
y = fmin(thepath->
end.
p.
y, boxes[boxn - 1].
UR.
y);
730 for (
size_t bi = 0; bi < pp->
nbox; bi++)
731 fprintf(stderr,
"%" PRISIZE_T " (%.5g, %.5g), (%.5g, %.5g)\n", bi,
734 fprintf(stderr,
"start port: (%.5g, %.5g), tangent angle: %.5g, %s\n",
737 fprintf(stderr,
"end port: (%.5g, %.5g), tangent angle: %.5g, %s\n",
752static void nodes_delete(nodes_t *pvec) {
759typedef LIST(nodes_t *) cycles_t;
761static bool cycle_contains_edge(nodes_t *cycle,
edge_t *
edge) {
765 const size_t cycle_len =
LIST_SIZE(cycle);
767 for (
size_t i = 0; i < cycle_len; ++i) {
768 const node_t *c_start =
LIST_GET(cycle, i == 0 ? cycle_len - 1 : i - 1);
771 if (c_start == start && c_end == end)
779 const size_t cycle_len =
LIST_SIZE(cycle);
782 bool all_items_match;
784 for (
size_t c = 0; c <
LIST_SIZE(cycles); ++c) {
785 nodes_t *cur_cycle =
LIST_GET(cycles, c);
786 const size_t cur_cycle_len =
LIST_SIZE(cur_cycle);
789 if (cur_cycle_len == cycle_len) {
790 all_items_match =
true;
791 for (i = 0; i < cur_cycle_len; ++i) {
794 all_items_match =
false;
814 nodes_t *cycle =
gv_alloc(
sizeof(nodes_t));
823 dfs(g, n, visited, end, cycles);
836 cycles_t alloced_cycles = {.dtor = nodes_delete};
842 nodes_t *cycle =
gv_alloc(
sizeof(nodes_t));
847 dfs(g, n, cycle, n, &cycles);
856 nodes_t *shortest =
NULL;
858 for (
size_t c = 0; c <
LIST_SIZE(cycles); ++c) {
859 nodes_t *cycle =
LIST_GET(cycles, c);
862 if (cycle_len < min_size)
866 if (cycle_contains_edge(cycle,
edge)) {
888 for (
size_t idx = 0; idx <
LIST_SIZE(cycle); ++idx) {
904 const double dist =
DIST(spl[3], spl[0]);
905 const double r =
dist / 5.0;
906 const double vX = centroid.
x - midpt.
x;
907 const double vY = centroid.
y - midpt.
y;
908 const double magV = hypot(vX, vY);
913 const pointf a = {.
x = midpt.
x - vX / magV * r,
914 .y = midpt.
y - vY / magV * r};
930 for (
size_t i = 0; i < e_cnt; i++) {
934 assert(e_cnt <= INT_MAX);
965 pointf perp = {.
x = dumb[0].
y - dumb[3].
y, .y = dumb[3].
x - dumb[0].
x};
968 assert(e_cnt - 1 <= INT_MAX);
969 int dx = xstep * (int)(e_cnt - 1) / 2;
970 dumb[1].
x = dumb[0].
x +
dx *
perp.
x / l_perp;
971 dumb[1].
y = dumb[0].
y +
dx *
perp.
y / l_perp;
972 dumb[2].
x = dumb[3].
x +
dx *
perp.
x / l_perp;
973 dumb[2].
y = dumb[3].
y +
dx *
perp.
y / l_perp;
978 for (
size_t i = 0; i < e_cnt; i++) {
979 edge_t *e0 = edge_list[i];
982 for (
size_t j = 0; j < 4; j++) {
986 for (
size_t j = 0; j < 4; j++) {
987 dumber[3 - j] = dumb[j];
991 Ppoint_t pts[] = {dumber[0], dumber[1], dumber[2], dumber[3]};
Dynamically expanding string buffers.
static int agxbprint(agxbuf *xb, const char *fmt,...)
Printf-style output to an agxbuf.
static char * agxbdisown(agxbuf *xb)
Memory allocation wrappers that exit on failure.
static char * gv_strdup(const char *original)
static void * gv_calloc(size_t nmemb, size_t size)
static void * gv_alloc(size_t size)
helpers for verbose/debug printing
static void del(Dict_t *d, Dtlink_t **set, Agedge_t *e)
static double dist(int dim, double *x, double *y)
#define APPROXEQPT(p, q, tol)
geometric functions (e.g. on points and boxes)
static WUR pointf perp(pointf p)
static WUR pointf mid_pointf(pointf p, pointf q)
static WUR pointf add_pointf(pointf p, pointf q)
static int cnt(Dict_t *d, Dtlink_t **set)
Agedge_t * agfstout(Agraph_t *g, Agnode_t *n)
Agedge_t * agnxtout(Agraph_t *g, Agedge_t *e)
void agwarningf(const char *fmt,...)
void agerrorf(const char *fmt,...)
Agnode_t * agnxtnode(Agraph_t *g, Agnode_t *n)
Agnode_t * agfstnode(Agraph_t *g)
Agraph_t * agraphof(void *obj)
char * agnameof(void *)
returns a string descriptor for the object.
Arithmetic helper functions.
static bool is_exactly_equal(double a, double b)
are two values precisely the same?
type-generic dynamically expanding list
#define LIST_APPEND(list,...)
#define LIST_COPY(list_type, src)
#define LIST_DROP_BACK(list)
#define LIST_CONTAINS(list, needle)
#define LIST_IS_EMPTY(list)
#define LIST_GET(list, index)
arithmetic overflow helpers
static bool fdiv_overflow(double n, double d, double *res)
finds and smooths shortest paths
void make_polyline(Ppolyline_t line, Ppolyline_t *sline)
int Proutespline(Pedge_t *barriers, size_t n_barriers, Ppolyline_t input_route, Pvector_t endpoint_slopes[2], Ppolyline_t *output_route)
int Pshortestpath(Ppoly_t *boundary, Ppoint_t endpoints[2], Ppolyline_t *output_route)
void clip_and_install(edge_t *fe, node_t *hn, pointf *ps, size_t pn, splineInfo *info)
void addEdgeLabels(edge_t *e)
static bool is_cycle_unique(cycles_t *cycles, nodes_t *cycle)
static void printpath(path *pp)
static pointf get_centroid(Agraph_t *g)
static void dfs(graph_t *g, node_t *search, nodes_t *visited, node_t *end, cycles_t *cycles)
static int nedges
total no. of edges used in routing
pointf * simpleSplineRoute(pointf tp, pointf hp, Ppoly_t poly, size_t *n_spl_pts, int polyline)
Given a simple (ccw) polygon, route an edge from tp to hp.
static nodes_t * find_shortest_cycle_with_edge(cycles_t *cycles, edge_t *edge, size_t min_size)
static cycles_t find_all_cycles(graph_t *g)
static size_t nboxes
total no. of boxes used in routing
static void limitBoxes(boxf *boxes, size_t boxn, const pointf *pps, size_t pn, double delta)
static int checkpath(size_t, boxf *, path *)
static pointf get_cycle_centroid(graph_t *g, edge_t *edge)
static double overlap(double i0, double i1, double j0, double j1)
void routesplinesterm(void)
void makeStraightEdges(graph_t *g, edge_t **edge_list, size_t e_cnt, int et, splineInfo *sinfo)
void makeStraightEdge(graph_t *g, edge_t *e, int et, splineInfo *sinfo)
void routesplinesinit(void)
pointf * routesplines(path *pp, size_t *npoints)
pointf * routepolylines(path *pp, size_t *npoints)
static pointf * routesplines_(path *pp, size_t *npoints, int polyline)
Agraph_t * root
subgraphs - ancestors
size_t nbox
number of subdivisions