40static void printboxes(
size_t boxn,
boxf *boxes) {
43 for (
size_t bi = 0; bi < boxn; bi++) {
44 ll = boxes[bi].
LL, ur = boxes[bi].
UR;
46 agxbprint(&buf,
"%.0f %.0f %.0f %.0f pathbox", ll.
x, ll.
y, ur.
x, ur.
y);
52static void psprintpolypts(
Ppoint_t * p,
int sz)
56 fprintf(stderr,
"%%!\n");
57 fprintf(stderr,
"%% constraint poly\n");
58 fprintf(stderr,
"newpath\n");
59 for (i = 0; i < sz; i++)
60 fprintf(stderr,
"%f %f %s\n", p[i].x, p[i].y, i == 0 ?
"moveto" :
"lineto");
61 fprintf(stderr,
"closepath stroke\n");
63static void psprintpoint(
point p)
65 fprintf(stderr,
"gsave\n");
67 "newpath %d %d moveto %d %d 2 0 360 arc closepath fill stroke\n",
69 fprintf(stderr,
"/Times-Roman findfont 4 scalefont setfont\n");
70 fprintf(stderr,
"%d %d moveto (\\(%d,%d\\)) show\n", p.
x + 5, p.
y + 5,
72 fprintf(stderr,
"grestore\n");
74static void psprintpointf(
pointf p)
76 fprintf(stderr,
"gsave\n");
78 "newpath %.5g %.5g moveto %.5g %.5g 2 0 360 arc closepath fill stroke\n",
80 fprintf(stderr,
"/Times-Roman findfont 4 scalefont setfont\n");
81 fprintf(stderr,
"%.5g %.5g moveto (\\(%.5g,%.5g\\)) show\n", p.
x + 5, p.
y + 5,
83 fprintf(stderr,
"grestore\n");
92 for (
size_t i = 0; i < spl.
pn; i++) {
95 i == 0 ?
"moveto" : (i % 3 == 0 ?
"curveto" :
""));
106 for (
size_t i = 0; i < pl.
pn; i++) {
109 i == 0 ?
"moveto" :
"lineto");
115static void psprintpoly(
Ppoly_t p)
121 for (
size_t bi = 0; bi < p.
pn; bi++) {
124 if (fabs(tail.x -
head.x) < 1 && fabs(tail.y -
head.y) < 1) pfx =
"%%";
127 agxbprint(&buf,
"%s%.0f %.0f %.0f %.0f makevec", pfx, tail.x, tail.y,
head.x,
134static void psprintboxes(
size_t boxn,
boxf *boxes) {
139 for (
size_t bi = 0; bi < boxn; bi++) {
140 ll = boxes[bi].
LL, ur = boxes[bi].
UR;
142 agxbprint(&buf,
"newpath\n%.0f %.0f moveto", ll.
x, ll.
y);
155static void psprintinit (
int begin)
163static bool debugleveln(
edge_t* realedge,
int i)
192 for (
size_t i = 0; i <
poly.pn; i++) {
193 edges[i].
a =
poly.ps[i];
196 evs[0].
x = evs[0].
y = 0;
197 evs[1].
x = evs[1].
y = 0;
210 for (
size_t i = 0; i < spl.
pn; i++) {
245 const double num_div =
delta * (double)boxn;
247 for (
size_t splinepi = 0; splinepi + 3 < pn; splinepi += 3) {
248 for (
double si = 0; si <= num_div; si++) {
250 sp[0] = pps[splinepi];
251 sp[1] = pps[splinepi + 1];
252 sp[2] = pps[splinepi + 2];
253 sp[3] = pps[splinepi + 3];
254 sp[0].
x += t * (sp[1].
x - sp[0].
x);
255 sp[0].
y += t * (sp[1].
y - sp[0].
y);
256 sp[1].
x += t * (sp[2].
x - sp[1].
x);
257 sp[1].
y += t * (sp[2].
y - sp[1].
y);
258 sp[2].
x += t * (sp[3].
x - sp[2].
x);
259 sp[2].
y += t * (sp[3].
y - sp[2].
y);
260 sp[0].
x += t * (sp[1].
x - sp[0].
x);
261 sp[0].
y += t * (sp[1].
y - sp[0].
y);
262 sp[1].
x += t * (sp[2].
x - sp[1].
x);
263 sp[1].
y += t * (sp[2].
y - sp[1].
y);
264 sp[0].
x += t * (sp[1].
x - sp[0].
x);
265 sp[0].
y += t * (sp[1].
y - sp[0].
y);
266 for (
size_t bi = 0; bi < boxn; bi++) {
270 if (sp[0].y <= boxes[bi].UR.y+
FUDGE && sp[0].
y >= boxes[bi].
LL.
y-
FUDGE) {
271 boxes[bi].
LL.
x = fmin(boxes[bi].LL.x, sp[0].
x);
272 boxes[bi].
UR.
x = fmax(boxes[bi].UR.x, sp[0].
x);
313 for (realedge = pp->
data;
317 agerrorf(
"in routesplines, cannot find NORMAL edge\n");
322 const size_t boxn = pp->
nbox;
328 if (debugleveln(realedge, 1))
329 printboxes(boxn, boxes);
330 if (debugleveln(realedge, 3)) {
332 psprintboxes(boxn, boxes);
339 if (boxn > 1 && boxes[0].LL.y > boxes[1].
LL.
y) {
341 for (
size_t bi = 0; bi < boxn; bi++) {
342 double v = boxes[bi].
UR.
y;
343 boxes[bi].
UR.
y = -1*boxes[bi].
LL.
y;
354 for (bi = 0, pi = 0; bi < boxn; bi++) {
357 prev = boxes[bi].
LL.
y > boxes[bi - 1].
LL.
y ? -1 : 1;
359 next = boxes[bi + 1].
LL.
y > boxes[bi].
LL.
y ? 1 : -1;
361 if (next == -1 ||
prev == 1) {
362 polypoints[pi].
x = boxes[bi].
LL.
x;
363 polypoints[pi++].
y = boxes[bi].
UR.
y;
364 polypoints[pi].
x = boxes[bi].
LL.
x;
365 polypoints[pi++].
y = boxes[bi].
LL.
y;
367 polypoints[pi].
x = boxes[bi].
UR.
x;
368 polypoints[pi++].
y = boxes[bi].
LL.
y;
369 polypoints[pi].
x = boxes[bi].
UR.
x;
370 polypoints[pi++].
y = boxes[bi].
UR.
y;
373 else if (
prev == 0) {
374 polypoints[pi].
x = boxes[bi].
LL.
x;
375 polypoints[pi++].
y = boxes[bi].
UR.
y;
376 polypoints[pi].
x = boxes[bi].
LL.
x;
377 polypoints[pi++].
y = boxes[bi].
LL.
y;
380 if (!(
prev == -1 && next == -1)) {
382 agerrorf(
"in routesplines, illegal values of prev %d and next %d, line %d\n",
prev, next, __LINE__);
387 for (bi = boxn - 1; bi !=
SIZE_MAX; bi--) {
390 prev = boxes[bi].
LL.
y > boxes[bi + 1].
LL.
y ? -1 : 1;
392 next = boxes[bi - 1].
LL.
y > boxes[bi].
LL.
y ? 1 : -1;
394 if (next == -1 ||
prev == 1 ) {
395 polypoints[pi].
x = boxes[bi].
LL.
x;
396 polypoints[pi++].
y = boxes[bi].
UR.
y;
397 polypoints[pi].
x = boxes[bi].
LL.
x;
398 polypoints[pi++].
y = boxes[bi].
LL.
y;
400 polypoints[pi].
x = boxes[bi].
UR.
x;
401 polypoints[pi++].
y = boxes[bi].
LL.
y;
402 polypoints[pi].
x = boxes[bi].
UR.
x;
403 polypoints[pi++].
y = boxes[bi].
UR.
y;
406 else if (
prev == 0) {
407 polypoints[pi].
x = boxes[bi].
UR.
x;
408 polypoints[pi++].
y = boxes[bi].
LL.
y;
409 polypoints[pi].
x = boxes[bi].
UR.
x;
410 polypoints[pi++].
y = boxes[bi].
UR.
y;
413 if (!(
prev == -1 && next == -1)) {
416 agerrorf(
"in routesplines, illegal values of prev %d and next %d, line %d\n",
prev, next, __LINE__);
419 polypoints[pi].
x = boxes[bi].
UR.
x;
420 polypoints[pi++].
y = boxes[bi].
LL.
y;
421 polypoints[pi].
x = boxes[bi].
UR.
x;
422 polypoints[pi++].
y = boxes[bi].
UR.
y;
423 polypoints[pi].
x = boxes[bi].
LL.
x;
424 polypoints[pi++].
y = boxes[bi].
UR.
y;
425 polypoints[pi].
x = boxes[bi].
LL.
x;
426 polypoints[pi++].
y = boxes[bi].
LL.
y;
437 for (
size_t bi = 0; bi < boxn; bi++) {
438 double v = boxes[bi].
UR.
y;
439 boxes[bi].
UR.
y = -1*boxes[bi].
LL.
y;
442 for (
size_t i = 0; i < pi; i++)
443 polypoints[i].y *= -1;
446 static const double INITIAL_LLX = DBL_MAX;
447 static const double INITIAL_URX = -DBL_MAX;
448 for (
size_t bi = 0; bi < boxn; bi++) {
449 boxes[bi].
LL.
x = INITIAL_LLX;
450 boxes[bi].
UR.
x = INITIAL_URX;
457 agerrorf(
"in routesplines, Pshortestpath failed\n");
461 if (debugleveln(realedge, 3)) {
472 for (
size_t edgei = 0; edgei <
poly.pn; edgei++) {
473 edges[edgei].
a = polypoints[edgei];
474 edges[edgei].
b = polypoints[(edgei + 1) %
poly.pn];
480 evs[0].
x = evs[0].
y = 0;
485 evs[1].
x = evs[1].
y = 0;
490 agerrorf(
"in routesplines, Proutespline failed\n");
495 if (debugleveln(realedge, 3)) {
509 for (
size_t splinepi = 0; splinepi < spl.
pn; splinepi++) {
510 ps[splinepi] = spl.
ps[splinepi];
515 bool is_horizontal = spl.
pn > 0;
516 for (
size_t i = 0; i < spl.
pn; ++i) {
518 is_horizontal =
false;
523 GV_INFO(
"spline [%.03f, %.03f] -- [%.03f, %.03f] is horizontal;"
524 " will be trivially bounded",
ps[0].x,
ps[0].y,
ps[spl.
pn - 1].x,
529 bool is_vertical = spl.
pn > 0;
530 for (
size_t i = 0; i < spl.
pn; ++i) {
537 GV_INFO(
"spline [%.03f, %.03f] -- [%.03f, %.03f] is vertical;"
538 " will be trivially bounded",
ps[0].x,
ps[0].y,
ps[spl.
pn - 1].x,
544 if (is_horizontal || is_vertical) {
545 for (
size_t i = 0; i < boxn; ++i) {
546 boxes[i].
LL.
x =
ps[0].x;
547 boxes[i].
UR.
x =
ps[0].x;
555 for (loopcnt = 0; unbounded && loopcnt <
LOOP_TRIES; loopcnt++) {
564 for (bi = 0; bi < boxn; bi++) {
596 printboxes(boxn, boxes);
611static double overlap(
double i0,
double i1,
double j0,
double j1) {
618 if (i0 <= j0 && i1 >= j1)
621 if (j0 <= i0 && j1 >= i1)
624 if (j0 <= i0 && i0 <= j1)
626 assert(j0 <= i1 && i1 <= j1);
642 int errs, l, r, d, u;
646 for (
size_t bi = 0; bi < boxn; bi++) {
647 if (fabs(boxes[bi].LL.y - boxes[bi].
UR.
y) < .01)
649 if (fabs(boxes[bi].LL.x - boxes[bi].
UR.
x) < .01)
651 boxes[i] = boxes[bi];
658 agerrorf(
"in checkpath, box 0 has LL coord > UR coord\n");
662 for (
size_t bi = 0; bi + 1 < boxn; bi++) {
663 ba = &boxes[bi], bb = &boxes[bi + 1];
664 if (bb->LL.x > bb->UR.x || bb->LL.y > bb->UR.y) {
670 l = ba->
UR.
x < bb->LL.x ? 1 : 0;
671 r = ba->
LL.
x > bb->UR.x ? 1 : 0;
672 d = ba->
UR.
y < bb->LL.y ? 1 : 0;
673 u = ba->
LL.
y > bb->UR.y ? 1 : 0;
674 errs = l + r + d + u;
677 " don't touch\n", bi, bi + 1);
684 xy = ba->
UR.
x, ba->
UR.
x = bb->LL.x, bb->LL.x = xy, l = 0;
686 xy = ba->
LL.
x, ba->
LL.
x = bb->UR.x, bb->UR.x = xy, r = 0;
688 xy = ba->
UR.
y, ba->
UR.
y = bb->LL.y, bb->LL.y = xy, d = 0;
690 xy = ba->
LL.
y, ba->
LL.
y = bb->UR.y, bb->UR.y = xy, u = 0;
691 for (
int j = 0; j < errs - 1; j++) {
693 xy = (ba->
UR.
x + bb->LL.x) / 2.0 + 0.5, ba->
UR.
x =
694 bb->LL.x = xy, l = 0;
696 xy = (ba->
LL.
x + bb->UR.x) / 2.0 + 0.5, ba->
LL.
x =
697 bb->UR.x = xy, r = 0;
699 xy = (ba->
UR.
y + bb->LL.y) / 2.0 + 0.5, ba->
UR.
y =
700 bb->LL.y = xy, d = 0;
702 xy = (ba->
LL.
y + bb->UR.y) / 2.0 + 0.5, ba->
LL.
y =
703 bb->UR.y = xy, u = 0;
707 double xoverlap =
overlap(ba->
LL.
x, ba->
UR.
x, bb->LL.x, bb->UR.x);
708 double yoverlap =
overlap(ba->
LL.
y, ba->
UR.
y, bb->LL.y, bb->UR.y);
709 if (xoverlap > 0 && yoverlap > 0) {
710 if (xoverlap < yoverlap) {
711 if (ba->
UR.
x - ba->
LL.
x > bb->UR.x - bb->LL.x) {
713 if (ba->
UR.
x < bb->UR.x)
719 if (ba->
UR.
x < bb->UR.x)
725 if (ba->
UR.
y - ba->
LL.
y > bb->UR.y - bb->LL.y) {
727 if (ba->
UR.
y < bb->UR.y)
733 if (ba->
UR.
y < bb->UR.y)
751 if (thepath->
end.
p.
x < boxes[boxn - 1].
LL.
x
752 || thepath->
end.
p.
x > boxes[boxn - 1].
UR.
x
753 || thepath->
end.
p.
y < boxes[boxn - 1].
LL.
y
754 || thepath->
end.
p.
y > boxes[boxn - 1].
UR.
y) {
755 thepath->
end.
p.
x = fmax(thepath->
end.
p.
x, boxes[boxn - 1].
LL.
x);
756 thepath->
end.
p.
x = fmin(thepath->
end.
p.
x, boxes[boxn - 1].
UR.
x);
757 thepath->
end.
p.
y = fmax(thepath->
end.
p.
y, boxes[boxn - 1].
LL.
y);
758 thepath->
end.
p.
y = fmin(thepath->
end.
p.
y, boxes[boxn - 1].
UR.
y);
766 for (
size_t bi = 0; bi < pp->
nbox; bi++)
767 fprintf(stderr,
"%" PRISIZE_T " (%.5g, %.5g), (%.5g, %.5g)\n", bi,
770 fprintf(stderr,
"start port: (%.5g, %.5g), tangent angle: %.5g, %s\n",
773 fprintf(stderr,
"end port: (%.5g, %.5g), tangent angle: %.5g, %s\n",
802 const size_t cycle_len = nodes_size(cycle);
804 for (
size_t i=0; i < cycle_len; ++i) {
805 const node_t *c_start = nodes_get(cycle, i == 0 ? cycle_len - 1 : i - 1);
806 const node_t *c_end = nodes_get(cycle, i);
808 if (c_start == start && c_end == end)
819 const size_t cycle_len = nodes_size(cycle);
822 bool all_items_match;
824 for (
size_t c = 0; c < cycles_size(cycles); ++c) {
825 nodes_t *cur_cycle = cycles_get(cycles, c);
826 const size_t cur_cycle_len = nodes_size(cur_cycle);
829 if (cur_cycle_len == cycle_len) {
830 all_items_match =
true;
831 for (i=0; i < cur_cycle_len; ++i) {
832 node_t *cur_cycle_item = nodes_get(cur_cycle, i);
833 if (!nodes_contains(cycle, cur_cycle_item,
eq)) {
834 all_items_match =
false;
851 if (nodes_contains(visited, search,
eq)) {
854 nodes_t *cycle =
gv_alloc(
sizeof(nodes_t));
855 *cycle = nodes_copy(visited);
856 cycles_append(cycles, cycle);
860 nodes_append(visited, search);
863 dfs(g, n, visited, end, cycles);
865 if (!nodes_is_empty(visited)) {
866 (void)nodes_pop_back(visited);
876 cycles_t alloced_cycles = {0};
877 cycles_t cycles = {0};
880 nodes_t *cycle =
gv_alloc(
sizeof(nodes_t));
882 cycles_append(&alloced_cycles, cycle);
884 dfs(g, n, cycle, n, &cycles);
887 cycles_free(&alloced_cycles);
893 nodes_t *shortest =
NULL;
895 for (
size_t c = 0; c < cycles_size(cycles); ++c) {
896 nodes_t *cycle = cycles_get(cycles, c);
897 size_t cycle_len = nodes_size(cycle);
899 if (cycle_len < min_size)
902 if (shortest ==
NULL || nodes_size(shortest) > cycle_len) {
921 cycles_free(&cycles);
926 for (
size_t idx = 0; idx < nodes_size(cycle); ++idx) {
927 node_t *n = nodes_get(cycle, idx);
933 cycles_free(&cycles);
949 double vX = centroid.
x - midpt.
x;
950 double vY = centroid.
y - midpt.
y;
951 double magV = hypot(vX, vY);
952 if (magV == 0)
return;
953 a.
x = midpt.
x - vX / magV * r;
954 a.
y = midpt.
y - vY / magV * r;
957 spl[1].
x = spl[2].
x = a.
x;
958 spl[1].
y = spl[2].
y = a.
y;
973 for (
size_t i = 0; i < e_cnt; i++) {
977 assert(e_cnt <= INT_MAX);
1009 .
x = dumb[0].
y - dumb[3].
y,
1010 .y = dumb[3].
x - dumb[0].
x
1014 assert(e_cnt - 1 <= INT_MAX);
1015 int dx = xstep * (int)(e_cnt - 1) / 2;
1016 dumb[1].
x = dumb[0].
x +
dx *
perp.
x / l_perp;
1017 dumb[1].
y = dumb[0].
y +
dx *
perp.
y / l_perp;
1018 dumb[2].
x = dumb[3].
x +
dx *
perp.
x / l_perp;
1019 dumb[2].
y = dumb[3].
y +
dx *
perp.
y / l_perp;
1024 for (
size_t i = 0; i < e_cnt; i++) {
1025 edge_t *e0 = edge_list[i];
1028 for (
size_t j = 0; j < 4; j++) {
1029 dumber[j] = dumb[j];
1032 for (
size_t j = 0; j < 4; j++) {
1033 dumber[3 - j] = dumb[j];
1037 Ppoint_t pts[] = {dumber[0], dumber[1], dumber[2], dumber[3]};
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 pointf mid_pointf(pointf p, pointf q)
static pointf add_pointf(pointf p, pointf q)
static pointf perp(pointf p)
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?
#define DEFINE_LIST_WITH_DTOR(name, type, dtor)
#define DEFINE_LIST(name, type)
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)
int routesplinesinit(void)
static int nedges
total no. of edges used in routing
static void nodes_delete(nodes_t *pvec)
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 bool eq(const node_t *a, const node_t *b)
static bool cycle_contains_edge(nodes_t *cycle, edge_t *edge)
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)
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