Graphviz 16.1.3~dev.20261121.1645
Loading...
Searching...
No Matches
routespl.c
Go to the documentation of this file.
1
3/*************************************************************************
4 * Copyright (c) 2011 AT&T Intellectual Property
5 * All rights reserved. This program and the accompanying materials
6 * are made available under the terms of the Eclipse Public License v2.0
7 * which accompanies this distribution, and is available at
8 * https://www.eclipse.org/org/documents/epl-2.0/EPL-2.0.html
9 *
10 * Contributors: Details at https://graphviz.org
11 *************************************************************************/
12
13#include "config.h"
14#include <assert.h>
15#include <common/geomprocs.h>
16#include <common/render.h>
17#include <float.h>
18#include <limits.h>
19#include <math.h>
20#include <pathplan/pathplan.h>
21#include <stdbool.h>
22#include <stdint.h>
23#include <stdlib.h>
24#include <string.h>
25#include <util/agxbuf.h>
26#include <util/alloc.h>
27#include <util/debug.h>
28#include <util/gv_math.h>
29#include <util/list.h>
30#include <util/overflow.h>
31#include <util/prisize_t.h>
32
33static int nedges;
34static size_t nboxes;
35
36static int routeinit;
37
38static int checkpath(size_t, boxf *, path *);
39static void printpath(path *pp);
40#ifdef DEBUG
41static void printboxes(size_t boxn, boxf *boxes) {
42 pointf ll, ur;
43
44 for (size_t bi = 0; bi < boxn; bi++) {
45 ll = boxes[bi].LL, ur = boxes[bi].UR;
46 agxbuf buf = {0};
47 agxbprint(&buf, "%.0f %.0f %.0f %.0f pathbox", ll.x, ll.y, ur.x, ur.y);
49 }
50}
51
52static void psprintspline(Ppolyline_t spl) {
54 LIST_APPEND(&Show_boxes, gv_strdup("%% spline"));
55 LIST_APPEND(&Show_boxes, gv_strdup("gsave 1 0 0 setrgbcolor newpath"));
56 for (size_t i = 0; i < spl.pn; i++) {
57 agxbuf buf = {0};
58 agxbprint(&buf, "%f %f %s", spl.ps[i].x, spl.ps[i].y,
59 i == 0 ? "moveto" : (i % 3 == 0 ? "curveto" : ""));
61 }
62 LIST_APPEND(&Show_boxes, gv_strdup("stroke grestore"));
63}
64
65static void psprintline(Ppolyline_t pl) {
67 LIST_APPEND(&Show_boxes, gv_strdup("%% line"));
68 LIST_APPEND(&Show_boxes, gv_strdup("gsave 0 0 1 setrgbcolor newpath"));
69 for (size_t i = 0; i < pl.pn; i++) {
70 agxbuf buf = {0};
71 agxbprint(&buf, "%f %f %s", pl.ps[i].x, pl.ps[i].y,
72 i == 0 ? "moveto" : "lineto");
74 }
75 LIST_APPEND(&Show_boxes, gv_strdup("stroke grestore"));
76}
77
78static void psprintpoly(Ppoly_t p) {
79 char *pfx;
80
81 LIST_APPEND(&Show_boxes, gv_strdup("%% poly list"));
82 LIST_APPEND(&Show_boxes, gv_strdup("gsave 0 1 0 setrgbcolor"));
83 for (size_t bi = 0; bi < p.pn; bi++) {
84 const pointf tail = p.ps[bi];
85 const pointf head = p.ps[(bi + 1) % p.pn];
86 if (fabs(tail.x - head.x) < 1 && fabs(tail.y - head.y) < 1)
87 pfx = "%%";
88 else
89 pfx = "";
90 agxbuf buf = {0};
91 agxbprint(&buf, "%s%.0f %.0f %.0f %.0f makevec", pfx, tail.x, tail.y,
92 head.x, head.y);
94 }
95 LIST_APPEND(&Show_boxes, gv_strdup("grestore"));
96}
97
98static void psprintboxes(size_t boxn, boxf *boxes) {
99 pointf ll, ur;
100
101 LIST_APPEND(&Show_boxes, gv_strdup("%% box list"));
102 LIST_APPEND(&Show_boxes, gv_strdup("gsave 0 1 0 setrgbcolor"));
103 for (size_t bi = 0; bi < boxn; bi++) {
104 ll = boxes[bi].LL, ur = boxes[bi].UR;
105 agxbuf buf = {0};
106 agxbprint(&buf, "newpath\n%.0f %.0f moveto", ll.x, ll.y);
108 agxbprint(&buf, "%.0f %.0f lineto", ll.x, ur.y);
110 agxbprint(&buf, "%.0f %.0f lineto", ur.x, ur.y);
112 agxbprint(&buf, "%.0f %.0f lineto", ur.x, ll.y);
114 LIST_APPEND(&Show_boxes, gv_strdup("closepath stroke"));
115 }
116 LIST_APPEND(&Show_boxes, gv_strdup("grestore"));
117}
118
119static void psprintinit(int begin) {
120 if (begin)
121 LIST_APPEND(&Show_boxes, gv_strdup("dbgstart"));
122 else
123 LIST_APPEND(&Show_boxes, gv_strdup("grestore"));
124}
125
126static bool debugleveln(edge_t *realedge, int i) {
127 return GD_showboxes(agraphof(aghead(realedge))) == i ||
128 GD_showboxes(agraphof(agtail(realedge))) == i ||
129 ED_showboxes(realedge) == i || ND_showboxes(aghead(realedge)) == i ||
130 ND_showboxes(agtail(realedge)) == i;
131}
132#endif /* DEBUG */
133
135pointf *simpleSplineRoute(pointf tp, pointf hp, Ppoly_t poly, size_t *n_spl_pts,
136 int polyline) {
137 Ppolyline_t pl, spl;
138 Ppoint_t eps[2];
139
140 eps[0].x = tp.x;
141 eps[0].y = tp.y;
142 eps[1].x = hp.x;
143 eps[1].y = hp.y;
144 if (Pshortestpath(&poly, eps, &pl) < 0)
145 return NULL;
146
147 if (polyline)
148 make_polyline(pl, &spl);
149 else {
150 // polygon edges passed to Proutespline
151 Pedge_t *edges = gv_calloc(poly.pn, sizeof(Pedge_t));
152 for (size_t i = 0; i < poly.pn; i++) {
153 edges[i].a = poly.ps[i];
154 edges[i].b = poly.ps[(i + 1) % poly.pn];
155 }
156 if (Proutespline(edges, poly.pn, pl, (Pvector_t[2]){0}, &spl) < 0) {
157 free(edges);
158 return NULL;
159 }
160 free(edges);
161 }
162
163 pointf *ps = calloc(spl.pn, sizeof(ps[0]));
164 if (ps == NULL) {
165 agerrorf("cannot allocate ps\n");
166 return NULL;
167 }
168 for (size_t i = 0; i < spl.pn; i++) {
169 ps[i] = spl.ps[i];
170 }
171 *n_spl_pts = spl.pn;
172 return ps;
173}
174
179 if (++routeinit > 1)
180 return;
181#ifdef DEBUG
183#endif
184 nedges = 0;
185 nboxes = 0;
186 if (Verbose)
187 start_timer();
188}
189
191 if (--routeinit > 0)
192 return;
193 GV_DEBUG("routesplines: %d edges, %" PRISIZE_T " boxes %.2f sec", nedges,
195}
196
197static void limitBoxes(boxf *boxes, size_t boxn, const pointf *pps, size_t pn,
198 double delta) {
199 double t;
200 pointf sp[4];
201 const double num_div = delta * (double)boxn;
202
203 for (size_t splinepi = 0; splinepi + 3 < pn; splinepi += 3) {
204 for (double si = 0; si <= num_div; si++) {
205 t = si / num_div;
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++) {
223/* this tested ok on 64bit machines, but on 32bit we need this FUDGE
224 * or graphs/directed/records.gv fails */
225#define FUDGE .0001
226 if (sp[0].y <= boxes[bi].UR.y + FUDGE &&
227 sp[0].y >= boxes[bi].LL.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);
230 }
231 }
232 }
233 }
234}
235
236#define INIT_DELTA 10
237#define LOOP_TRIES \
238 15 /* number of times to try to limiting boxes to regain space, using \
239 smaller divisions */
240
256static pointf *routesplines_(path *pp, size_t *npoints, int polyline) {
258 Ppolyline_t pl, spl;
259 Ppoint_t eps[2];
260 int prev, next;
261 boxf *boxes;
262 edge_t *realedge;
263 bool flip;
264 int loopcnt;
265 bool unbounded;
266
267 *npoints = 0;
268 nedges++;
269 nboxes += pp->nbox;
270
271 for (realedge = pp->data; realedge && ED_edge_type(realedge) != NORMAL;
272 realedge = ED_to_orig(realedge))
273 ;
274 if (!realedge) {
275 agerrorf("in routesplines, cannot find NORMAL edge\n");
276 return NULL;
277 }
278
279 boxes = pp->boxes;
280 const size_t boxn = pp->nbox;
281
282 if (checkpath(boxn, boxes, pp))
283 return NULL;
284
285#ifdef DEBUG
286 if (debugleveln(realedge, 1))
287 printboxes(boxn, boxes);
288 if (debugleveln(realedge, 3)) {
289 psprintinit(1);
290 psprintboxes(boxn, boxes);
291 }
292#endif
293
294 // vertices of polygon defined by boxes
295 Ppoint_t *polypoints = gv_calloc(boxn * 8, sizeof(Ppoint_t));
296
297 if (boxn > 1 && boxes[0].LL.y > boxes[1].LL.y) {
298 flip = true;
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;
302 boxes[bi].LL.y = -v;
303 }
304 } else
305 flip = false;
306
307 size_t pi;
308 if (agtail(realedge) != aghead(realedge)) {
309 /* I assume that the path goes either down only or
310 up - right - down */
311 size_t bi;
312 for (bi = 0, pi = 0; bi < boxn; bi++) {
313 next = prev = 0;
314 if (bi > 0)
315 prev = boxes[bi].LL.y > boxes[bi - 1].LL.y ? -1 : 1;
316 if (bi + 1 < boxn)
317 next = boxes[bi + 1].LL.y > boxes[bi].LL.y ? 1 : -1;
318 if (prev != next) {
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;
324 } else {
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;
329 }
330 } else if (prev == 0) { /* single box */
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;
335 } else {
336 if (!(prev == -1 && next == -1)) {
337 free(polypoints);
338 agerrorf("in routesplines, illegal values of prev %d and next %d, "
339 "line %d\n",
340 prev, next, __LINE__);
341 return NULL;
342 }
343 }
344 }
345 for (bi = boxn - 1; bi != SIZE_MAX; bi--) {
346 next = prev = 0;
347 if (bi + 1 < boxn)
348 prev = boxes[bi].LL.y > boxes[bi + 1].LL.y ? -1 : 1;
349 if (bi > 0)
350 next = boxes[bi - 1].LL.y > boxes[bi].LL.y ? 1 : -1;
351 if (prev != next) {
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;
357 } else {
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;
362 }
363 } else if (prev == 0) { /* single box */
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;
368 } else {
369 if (!(prev == -1 && next == -1)) {
370 /* it went badly, e.g. degenerate box in boxlist */
371 free(polypoints);
372 agerrorf("in routesplines, illegal values of prev %d and next %d, "
373 "line %d\n",
374 prev, next, __LINE__);
375 return NULL; /* for correctness sake, it's best to just stop */
376 }
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;
385 }
386 }
387 } else {
388 free(polypoints);
389 agerrorf("in routesplines, edge is a loop at %s\n",
390 agnameof(aghead(realedge)));
391 return NULL;
392 }
393
394 if (flip) {
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;
398 boxes[bi].LL.y = -v;
399 }
400 for (size_t i = 0; i < pi; i++)
401 polypoints[i].y *= -1;
402 }
403
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;
409 }
410 poly.ps = polypoints, poly.pn = pi;
411 eps[0].x = pp->start.p.x, eps[0].y = pp->start.p.y;
412 eps[1].x = pp->end.p.x, eps[1].y = pp->end.p.y;
413 if (Pshortestpath(&poly, eps, &pl) < 0) {
414 free(polypoints);
415 agerrorf("in routesplines, Pshortestpath failed\n");
416 return NULL;
417 }
418#ifdef DEBUG
419 if (debugleveln(realedge, 3)) {
420 psprintpoly(poly);
421 psprintline(pl);
422 }
423#endif
424
425 if (polyline) {
426 make_polyline(pl, &spl);
427 } else {
428 Pedge_t *edges = gv_calloc(poly.pn, sizeof(Pedge_t));
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];
432 }
433 Pvector_t evs[2] = {0};
434 if (pp->start.constrained) {
435 evs[0].x = cos(pp->start.theta);
436 evs[0].y = sin(pp->start.theta);
437 }
438 if (pp->end.constrained) {
439 evs[1].x = -cos(pp->end.theta);
440 evs[1].y = -sin(pp->end.theta);
441 }
442
443 if (Proutespline(edges, poly.pn, pl, evs, &spl) < 0) {
444 free(edges);
445 free(polypoints);
446 agerrorf("in routesplines, Proutespline failed\n");
447 return NULL;
448 }
449 free(edges);
450#ifdef DEBUG
451 if (debugleveln(realedge, 3)) {
452 psprintspline(spl);
453 psprintinit(0);
454 }
455#endif
456 }
457 pointf *ps = calloc(spl.pn, sizeof(ps[0]));
458 if (ps == NULL) {
459 free(polypoints);
460 agerrorf("cannot allocate ps\n");
461 return NULL; /* Bailout if no memory left */
462 }
463
464 unbounded = true;
465 for (size_t splinepi = 0; splinepi < spl.pn; splinepi++) {
466 ps[splinepi] = spl.ps[splinepi];
467 }
468
469 {
470 // does the spline go straight left/right?
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;
475 break;
476 }
477 }
478 if (is_horizontal) {
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);
482 }
483
484 // does the spline go straight up/down?
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) {
488 is_vertical = false;
489 break;
490 }
491 }
492 if (is_vertical) {
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);
496 }
497
498 // if the spline is horizontal or vertical, the `limitBoxes` loop will not
499 // converge, but we know the expected outcome trivially
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;
504 }
505 unbounded = false;
506 }
507 }
508
509 double delta = INIT_DELTA;
510
511 for (loopcnt = 0; unbounded && loopcnt < LOOP_TRIES; loopcnt++) {
512 limitBoxes(boxes, boxn, ps, spl.pn, delta);
513
514 /* The following check is necessary because if a box is not very
515 * high, it is possible that the sampling above might miss it.
516 * Therefore, we make the sample finer until all boxes have
517 * valid values. cf. bug 456.
518 */
519 size_t bi;
520 for (bi = 0; bi < boxn; bi++) {
521 /* these fp equality tests are used only to detect if the
522 * values have been changed since initialization - ok */
523 if (is_exactly_equal(boxes[bi].LL.x, INITIAL_LLX) ||
524 is_exactly_equal(boxes[bi].UR.x, INITIAL_URX)) {
525 delta *= 2; /* try again with a finer interval */
526 break;
527 }
528 }
529 if (bi == boxn)
530 unbounded = false;
531 }
532 if (unbounded) {
533 /* Either an extremely short, even degenerate, box, or some failure with the
534 * path planner causing the spline to miss some boxes. In any case, use the
535 * shortest path to bound the boxes. This will probably mean a bad edge, but
536 * we avoid an infinite loop and we can see the bad edge, and even use the
537 * showboxes scaffolding.
538 */
539 Ppolyline_t polyspl;
540 agwarningf("Unable to reclaim box space in spline routing for edge \"%s\" "
541 "-> \"%s\". Something is probably seriously wrong.\n",
542 agnameof(agtail(realedge)), agnameof(aghead(realedge)));
543 make_polyline(pl, &polyspl);
544 limitBoxes(boxes, boxn, polyspl.ps, polyspl.pn, INIT_DELTA);
545 }
546
547 *npoints = spl.pn;
548
549#ifdef DEBUG
550 if (GD_showboxes(agraphof(aghead(realedge))) == 2 ||
551 GD_showboxes(agraphof(agtail(realedge))) == 2 ||
552 ED_showboxes(realedge) == 2 || ND_showboxes(aghead(realedge)) == 2 ||
553 ND_showboxes(agtail(realedge)) == 2)
554 printboxes(boxn, boxes);
555#endif
556
557 free(polypoints);
558 return ps;
559}
561pointf *routesplines(path *pp, size_t *npoints) {
562 return routesplines_(pp, npoints, 0);
563}
565pointf *routepolylines(path *pp, size_t *npoints) {
566 return routesplines_(pp, npoints, 1);
567}
569static double overlap(double i0, double i1, double j0, double j1) {
570 if (i1 <= j0)
571 return 0;
572 if (i0 >= j1)
573 return 0;
574
575 // does the first interval subsume the second?
576 if (i0 <= j0 && i1 >= j1)
577 return i1 - i0;
578 // does the second interval subsume the first?
579 if (j0 <= i0 && j1 >= i1)
580 return j1 - j0;
581
582 if (j0 <= i0 && i0 <= j1)
583 return j1 - i0;
584 assert(j0 <= i1 && i1 <= j1);
585 return i1 - j0;
586}
587
588/*
589 * repairs minor errors in the boxpath, such as boxes not joining
590 * or slightly intersecting. it's sort of the equivalent of the
591 * audit process in the 5E control program - if you've given up on
592 * fixing all the bugs, at least try to engineer around them!
593 * in postmodern CS, we could call this "self-healing code."
594 *
595 * Return 1 on failure; 0 on success.
596 */
597static int checkpath(size_t boxn, boxf *boxes, path *thepath) {
598 boxf *ba, *bb;
599 int errs, l, r, d, u;
600
601 /* remove degenerate boxes. */
602 size_t i = 0;
603 for (size_t bi = 0; bi < boxn; bi++) {
604 if (fabs(boxes[bi].LL.y - boxes[bi].UR.y) < .01)
605 continue;
606 if (fabs(boxes[bi].LL.x - boxes[bi].UR.x) < .01)
607 continue;
608 boxes[i] = boxes[bi];
609 i++;
610 }
611 boxn = i;
612
613 if (boxn == 0) {
614 agerrorf("in checkpath, all bounding boxes are below threshold\n");
615 printpath(thepath);
616 return 1;
617 }
618
619 ba = &boxes[0];
620 if (ba->LL.x > ba->UR.x || ba->LL.y > ba->UR.y) {
621 agerrorf("in checkpath, box 0 has LL coord > UR coord\n");
622 printpath(thepath);
623 return 1;
624 }
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) {
628 agerrorf("in checkpath, box %" PRISIZE_T " has LL coord > UR coord\n",
629 bi + 1);
630 printpath(thepath);
631 return 1;
632 }
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;
638 if (errs > 0 && Verbose) {
639 fprintf(stderr,
640 "in checkpath, boxes %" PRISIZE_T " and %" PRISIZE_T
641 " don't touch\n",
642 bi, bi + 1);
643 printpath(thepath);
644 }
645 if (errs > 0) {
646 double xy;
647
648 if (l == 1)
649 xy = ba->UR.x, ba->UR.x = bb->LL.x, bb->LL.x = xy, l = 0;
650 else if (r == 1)
651 xy = ba->LL.x, ba->LL.x = bb->UR.x, bb->UR.x = xy, r = 0;
652 else if (d == 1)
653 xy = ba->UR.y, ba->UR.y = bb->LL.y, bb->LL.y = xy, d = 0;
654 else if (u == 1)
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++) {
657 if (l == 1)
658 xy = (ba->UR.x + bb->LL.x) / 2.0 + 0.5, ba->UR.x = bb->LL.x = xy,
659 l = 0;
660 else if (r == 1)
661 xy = (ba->LL.x + bb->UR.x) / 2.0 + 0.5, ba->LL.x = bb->UR.x = xy,
662 r = 0;
663 else if (d == 1)
664 xy = (ba->UR.y + bb->LL.y) / 2.0 + 0.5, ba->UR.y = bb->LL.y = xy,
665 d = 0;
666 else if (u == 1)
667 xy = (ba->LL.y + bb->UR.y) / 2.0 + 0.5, ba->LL.y = bb->UR.y = xy,
668 u = 0;
669 }
670 }
671 /* check for overlapping boxes */
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) {
677 /* take space from ba */
678 if (ba->UR.x < bb->UR.x)
679 ba->UR.x = bb->LL.x;
680 else
681 ba->LL.x = bb->UR.x;
682 } else {
683 /* take space from bb */
684 if (ba->UR.x < bb->UR.x)
685 bb->LL.x = ba->UR.x;
686 else
687 bb->UR.x = ba->LL.x;
688 }
689 } else { /* symmetric for y coords */
690 if (ba->UR.y - ba->LL.y > bb->UR.y - bb->LL.y) {
691 /* take space from ba */
692 if (ba->UR.y < bb->UR.y)
693 ba->UR.y = bb->LL.y;
694 else
695 ba->LL.y = bb->UR.y;
696 } else {
697 /* take space from bb */
698 if (ba->UR.y < bb->UR.y)
699 bb->LL.y = ba->UR.y;
700 else
701 bb->UR.y = ba->LL.y;
702 }
703 }
704 }
705 }
706
707 if (thepath->start.p.x < boxes[0].LL.x ||
708 thepath->start.p.x > boxes[0].UR.x ||
709 thepath->start.p.y < boxes[0].LL.y ||
710 thepath->start.p.y > boxes[0].UR.y) {
711 thepath->start.p.x = fmax(thepath->start.p.x, boxes[0].LL.x);
712 thepath->start.p.x = fmin(thepath->start.p.x, boxes[0].UR.x);
713 thepath->start.p.y = fmax(thepath->start.p.y, boxes[0].LL.y);
714 thepath->start.p.y = fmin(thepath->start.p.y, boxes[0].UR.y);
715 }
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);
724 }
725 return 0;
726}
728static void printpath(path *pp) {
729 fprintf(stderr, "%" PRISIZE_T " boxes:\n", pp->nbox);
730 for (size_t bi = 0; bi < pp->nbox; bi++)
731 fprintf(stderr, "%" PRISIZE_T " (%.5g, %.5g), (%.5g, %.5g)\n", bi,
732 pp->boxes[bi].LL.x, pp->boxes[bi].LL.y, pp->boxes[bi].UR.x,
733 pp->boxes[bi].UR.y);
734 fprintf(stderr, "start port: (%.5g, %.5g), tangent angle: %.5g, %s\n",
735 pp->start.p.x, pp->start.p.y, pp->start.theta,
736 pp->start.constrained ? "constrained" : "not constrained");
737 fprintf(stderr, "end port: (%.5g, %.5g), tangent angle: %.5g, %s\n",
738 pp->end.p.x, pp->end.p.y, pp->end.theta,
739 pp->end.constrained ? "constrained" : "not constrained");
740}
742static pointf get_centroid(Agraph_t *g) {
743 pointf sum = {0.0, 0.0};
744
745 sum.x = (GD_bb(g).LL.x + GD_bb(g).UR.x) / 2.0;
746 sum.y = (GD_bb(g).LL.y + GD_bb(g).UR.y) / 2.0;
747 return sum;
748}
750typedef LIST(node_t *) nodes_t;
751
752static void nodes_delete(nodes_t *pvec) {
753 if (pvec != NULL) {
754 LIST_FREE(pvec);
755 }
756 free(pvec);
757}
759typedef LIST(nodes_t *) cycles_t;
760
761static bool cycle_contains_edge(nodes_t *cycle, edge_t *edge) {
762 node_t *start = agtail(edge);
763 node_t *end = aghead(edge);
764
765 const size_t cycle_len = LIST_SIZE(cycle);
766
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);
769 const node_t *c_end = LIST_GET(cycle, i);
770
771 if (c_start == start && c_end == end)
772 return true;
773 }
774
775 return false;
776}
778static bool is_cycle_unique(cycles_t *cycles, nodes_t *cycle) {
779 const size_t cycle_len = LIST_SIZE(cycle);
780 size_t i; // node counter
781
782 bool all_items_match;
783
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);
787
788 // if all the items match in equal length cycles then we're not unique
789 if (cur_cycle_len == cycle_len) {
790 all_items_match = true;
791 for (i = 0; i < cur_cycle_len; ++i) {
792 node_t *cur_cycle_item = LIST_GET(cur_cycle, i);
793 if (!LIST_CONTAINS(cycle, cur_cycle_item)) {
794 all_items_match = false;
795 break;
796 }
797 }
798 if (all_items_match)
799 return false;
800 }
801 }
802
803 return true;
804}
806static void dfs(graph_t *g, node_t *search, nodes_t *visited, node_t *end,
807 cycles_t *cycles) {
808 edge_t *e;
809 node_t *n;
810
811 if (LIST_CONTAINS(visited, search)) {
812 if (search == end) {
813 if (is_cycle_unique(cycles, visited)) {
814 nodes_t *cycle = gv_alloc(sizeof(nodes_t));
815 *cycle = LIST_COPY(nodes_t, visited);
816 LIST_APPEND(cycles, cycle);
817 }
818 }
819 } else {
820 LIST_APPEND(visited, search);
821 for (e = agfstout(g, search); e; e = agnxtout(g, e)) {
822 n = aghead(e);
823 dfs(g, n, visited, end, cycles);
824 }
825 if (!LIST_IS_EMPTY(visited)) {
826 LIST_DROP_BACK(visited);
827 }
828 }
829}
830
831// Returns a vec of vec of nodes (aka a vector of cycles)
832static cycles_t find_all_cycles(graph_t *g) {
833 node_t *n;
834
835 // vector of vectors of nodes -- AKA cycles to delete
836 cycles_t alloced_cycles = {.dtor = nodes_delete};
837 cycles_t cycles = {
838 .dtor =
839 nodes_delete}; // vector of vectors of nodes AKA a vector of cycles
840
841 for (n = agfstnode(g); n; n = agnxtnode(g, n)) {
842 nodes_t *cycle = gv_alloc(sizeof(nodes_t));
843 // keep track of all items we allocate to clean up at the end of this
844 // function
845 LIST_APPEND(&alloced_cycles, cycle);
846
847 dfs(g, n, cycle, n, &cycles);
848 }
849
850 LIST_FREE(&alloced_cycles); // cycles contains copied vecs
851 return cycles;
852}
854static nodes_t *find_shortest_cycle_with_edge(cycles_t *cycles, edge_t *edge,
855 size_t min_size) {
856 nodes_t *shortest = NULL;
857
858 for (size_t c = 0; c < LIST_SIZE(cycles); ++c) {
859 nodes_t *cycle = LIST_GET(cycles, c);
860 size_t cycle_len = LIST_SIZE(cycle);
861
862 if (cycle_len < min_size)
863 continue;
864
865 if (shortest == NULL || LIST_SIZE(shortest) > cycle_len) {
866 if (cycle_contains_edge(cycle, edge)) {
867 shortest = cycle;
868 }
869 }
870 }
871 return shortest;
872}
875 cycles_t cycles = find_all_cycles(g);
876
877 // find the center of the shortest cycle containing this edge
878 // cycles of length 2 do their own thing, we want 3 or
879 nodes_t *cycle = find_shortest_cycle_with_edge(&cycles, edge, 3);
880 pointf sum = {0.0, 0.0};
881
882 if (cycle == NULL) {
883 LIST_FREE(&cycles);
884 return get_centroid(g);
885 }
886
887 double cnt = 0;
888 for (size_t idx = 0; idx < LIST_SIZE(cycle); ++idx) {
889 node_t *n = LIST_GET(cycle, idx);
890 sum.x += ND_coord(n).x;
891 sum.y += ND_coord(n).y;
892 cnt++;
893 }
894
895 LIST_FREE(&cycles);
896
897 sum.x /= cnt;
898 sum.y /= cnt;
899 return sum;
900}
902static void bend(pointf spl[4], pointf centroid) {
903 const pointf midpt = mid_pointf(spl[0], spl[3]);
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);
909 // avoid out of range division results
910 if (fdiv_overflow(vX, magV, &(double){0}) ||
911 fdiv_overflow(vY, magV, &(double){0}))
912 return;
913 const pointf a = {.x = midpt.x - vX / magV * r,
914 .y = midpt.y - vY / magV * r}; // + would be closest point
915 /* this can be improved */
916 spl[1] = spl[2] = a;
917}
918
919// FIX: handle ports on boundary?
920void makeStraightEdge(graph_t *g, edge_t *e, int et, splineInfo *sinfo) {
921 edge_t *e0;
922
923 size_t e_cnt = 1;
924 e0 = e;
925 while (e0 != ED_to_virt(e0) && (e0 = ED_to_virt(e0)))
926 e_cnt++;
927
928 edge_t **edge_list = gv_calloc(e_cnt, sizeof(edge_t *));
929 e0 = e;
930 for (size_t i = 0; i < e_cnt; i++) {
931 edge_list[i] = e0;
932 e0 = ED_to_virt(e0);
933 }
934 assert(e_cnt <= INT_MAX);
935 makeStraightEdges(g, edge_list, e_cnt, et, sinfo);
936 free(edge_list);
937}
939void makeStraightEdges(graph_t *g, edge_t **edge_list, size_t e_cnt, int et,
940 splineInfo *sinfo) {
941 pointf dumb[4];
942 bool curved = et == EDGETYPE_CURVED;
943 pointf del;
944
945 edge_t *e = edge_list[0];
946 node_t *n = agtail(e);
947 node_t *head = aghead(e);
948 dumb[1] = dumb[0] = add_pointf(ND_coord(n), ED_tail_port(e).p);
949 dumb[2] = dumb[3] = add_pointf(ND_coord(head), ED_head_port(e).p);
950 if (e_cnt == 1 || Concentrate) {
951 if (curved)
952 bend(dumb, get_cycle_centroid(g, edge_list[0]));
953 clip_and_install(e, aghead(e), dumb, 4, sinfo);
954 addEdgeLabels(e);
955 return;
956 }
957
958 if (APPROXEQPT(dumb[0], dumb[3], MILLIPOINT)) {
959 /* degenerate case */
960 dumb[1] = dumb[0];
961 dumb[2] = dumb[3];
962 del.x = 0;
963 del.y = 0;
964 } else {
965 pointf perp = {.x = dumb[0].y - dumb[3].y, .y = dumb[3].x - dumb[0].x};
966 double l_perp = hypot(perp.x, perp.y);
967 int xstep = GD_nodesep(g->root);
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;
974 del.x = -xstep * perp.x / l_perp;
975 del.y = -xstep * perp.y / l_perp;
976 }
977
978 for (size_t i = 0; i < e_cnt; i++) {
979 edge_t *e0 = edge_list[i];
980 pointf dumber[4];
981 if (aghead(e0) == head) {
982 for (size_t j = 0; j < 4; j++) {
983 dumber[j] = dumb[j];
984 }
985 } else {
986 for (size_t j = 0; j < 4; j++) {
987 dumber[3 - j] = dumb[j];
988 }
989 }
990 if (et == EDGETYPE_PLINE) {
991 Ppoint_t pts[] = {dumber[0], dumber[1], dumber[2], dumber[3]};
992 Ppolyline_t spl, line = {.pn = 4, .ps = pts};
993 make_polyline(line, &spl);
994 clip_and_install(e0, aghead(e0), spl.ps, spl.pn, sinfo);
995 } else
996 clip_and_install(e0, aghead(e0), dumber, 4, sinfo);
997
998 addEdgeLabels(e0);
999 dumb[1] = add_pointf(dumb[1], del);
1000 dumb[2] = add_pointf(dumb[2], del);
1001 }
1002}
Dynamically expanding string buffers.
static int agxbprint(agxbuf *xb, const char *fmt,...)
Printf-style output to an agxbuf.
Definition agxbuf.h:252
static char * agxbdisown(agxbuf *xb)
Definition agxbuf.h:345
Memory allocation wrappers that exit on failure.
static char * gv_strdup(const char *original)
Definition alloc.h:101
static void * gv_calloc(size_t nmemb, size_t size)
Definition alloc.h:26
static void * gv_alloc(size_t size)
Definition alloc.h:47
#define NORMAL
Definition const.h:24
#define EDGETYPE_CURVED
Definition const.h:236
#define EDGETYPE_PLINE
Definition const.h:237
helpers for verbose/debug printing
#define GV_DEBUG(...)
Definition debug.h:40
#define GV_INFO(...)
Definition debug.h:15
static splineInfo sinfo
Definition dotsplines.c:125
static float dx
Definition draw.c:42
#define head
Definition dthdr.h:15
static void del(Dict_t *d, Dtlink_t **set, Agedge_t *e)
Definition edge.c:149
static double dist(int dim, double *x, double *y)
#define MILLIPOINT
Definition geom.h:74
#define APPROXEQPT(p, q, tol)
Definition geom.h:71
#define DIST(p, q)
Definition geom.h:56
geometric functions (e.g. on points and boxes)
static WUR pointf perp(pointf p)
Definition geomprocs.h:140
static WUR pointf mid_pointf(pointf p, pointf q)
Definition geomprocs.h:104
static WUR pointf add_pointf(pointf p, pointf q)
Definition geomprocs.h:88
show_boxes_t Show_boxes
Definition globals.c:23
bool Concentrate
Definition globals.h:62
static bool Verbose
Definition gml2gv.c:26
void free(void *)
edge
Definition gmlparse.y:246
#define SIZE_MAX
Definition gmlscan.c:347
node NULL
Definition grammar.y:181
static int cnt(Dict_t *d, Dtlink_t **set)
Definition graph.c:204
#define ED_to_orig(e)
Definition types.h:598
#define ED_showboxes(e)
Definition types.h:594
Agedge_t * agfstout(Agraph_t *g, Agnode_t *n)
Definition edge.c:28
#define agtail(e)
Definition cgraph.h:982
#define ED_edge_type(e)
Definition types.h:582
#define aghead(e)
Definition cgraph.h:983
Agedge_t * agnxtout(Agraph_t *g, Agedge_t *e)
Definition edge.c:42
#define ED_head_port(e)
Definition types.h:588
#define ED_tail_port(e)
Definition types.h:597
#define ED_to_virt(e)
Definition types.h:599
void agwarningf(const char *fmt,...)
Definition agerror.c:175
void agerrorf(const char *fmt,...)
Definition agerror.c:167
#define GD_bb(g)
Definition types.h:354
#define GD_showboxes(g)
Definition types.h:401
#define GD_nodesep(g)
Definition types.h:394
Agnode_t * agnxtnode(Agraph_t *g, Agnode_t *n)
Definition node.c:50
Agnode_t * agfstnode(Agraph_t *g)
Definition node.c:43
#define ND_showboxes(n)
Definition types.h:530
#define ND_coord(n)
Definition types.h:490
Agraph_t * agraphof(void *obj)
Definition obj.c:187
char * agnameof(void *)
returns a string descriptor for the object.
Definition id.c:145
Arithmetic helper functions.
static bool is_exactly_equal(double a, double b)
are two values precisely the same?
Definition gv_math.h:49
$2 prev
Definition htmlparse.y:291
type-generic dynamically expanding list
#define LIST_APPEND(list,...)
Definition list.h:151
#define LIST(type)
Definition list.h:66
#define LIST_COPY(list_type, src)
Definition list.h:356
#define LIST_SIZE(list)
Definition list.h:92
#define LIST_DROP_BACK(list)
Definition list.h:483
#define LIST_FREE(list)
Definition list.h:413
#define LIST_CONTAINS(list, needle)
Definition list.h:340
#define LIST_IS_EMPTY(list)
Definition list.h:102
#define LIST_GET(list, index)
Definition list.h:197
#define delta
Definition maze.c:138
arithmetic overflow helpers
static bool fdiv_overflow(double n, double d, double *res)
Definition overflow.h:142
finds and smooths shortest paths
void make_polyline(Ppolyline_t line, Ppolyline_t *sline)
Definition util.c:44
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)
Definition shortest.c:84
#define PRISIZE_T
Definition prisize_t.h:25
void clip_and_install(edge_t *fe, node_t *hn, pointf *ps, size_t pn, splineInfo *info)
Definition splines.c:221
void addEdgeLabels(edge_t *e)
Definition splines.c:1248
static bool is_cycle_unique(cycles_t *cycles, nodes_t *cycle)
Definition routespl.c:777
#define INIT_DELTA
Definition routespl.c:236
static void printpath(path *pp)
Definition routespl.c:727
static int routeinit
Definition routespl.c:36
static pointf get_centroid(Agraph_t *g)
Definition routespl.c:741
static void dfs(graph_t *g, node_t *search, nodes_t *visited, node_t *end, cycles_t *cycles)
Definition routespl.c:805
static int nedges
total no. of edges used in routing
Definition routespl.c:33
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.
Definition routespl.c:135
static nodes_t * find_shortest_cycle_with_edge(cycles_t *cycles, edge_t *edge, size_t min_size)
Definition routespl.c:853
static cycles_t find_all_cycles(graph_t *g)
Definition routespl.c:831
#define LOOP_TRIES
Definition routespl.c:237
static size_t nboxes
total no. of boxes used in routing
Definition routespl.c:34
static void limitBoxes(boxf *boxes, size_t boxn, const pointf *pps, size_t pn, double delta)
Definition routespl.c:197
static int checkpath(size_t, boxf *, path *)
Definition routespl.c:596
static pointf get_cycle_centroid(graph_t *g, edge_t *edge)
Definition routespl.c:873
static double overlap(double i0, double i1, double j0, double j1)
Definition routespl.c:568
#define FUDGE
void routesplinesterm(void)
Definition routespl.c:190
void makeStraightEdges(graph_t *g, edge_t **edge_list, size_t e_cnt, int et, splineInfo *sinfo)
Definition routespl.c:938
void makeStraightEdge(graph_t *g, edge_t *e, int et, splineInfo *sinfo)
Definition routespl.c:919
void routesplinesinit(void)
Definition routespl.c:178
pointf * routesplines(path *pp, size_t *npoints)
Definition routespl.c:560
pointf * routepolylines(path *pp, size_t *npoints)
Definition routespl.c:564
static pointf * routesplines_(path *pp, size_t *npoints, int polyline)
Definition routespl.c:255
graph or subgraph
Definition cgraph.h:424
Agraph_t * root
subgraphs - ancestors
Definition cgraph.h:433
Ppoint_t b
Definition pathgeom.h:53
Ppoint_t a
Definition pathgeom.h:53
size_t pn
Definition pathgeom.h:47
Ppoint_t * ps
Definition pathgeom.h:46
double x
Definition pathgeom.h:38
double y
Definition pathgeom.h:38
Definition geom.h:41
pointf UR
Definition geom.h:41
pointf LL
Definition geom.h:41
Definition types.h:81
port start
Definition types.h:82
boxf * boxes
Definition types.h:85
port end
Definition types.h:83
size_t nbox
number of subdivisions
Definition types.h:84
void * data
Definition types.h:86
double x
Definition geom.h:29
double y
Definition geom.h:29
pointf p
Definition types.h:49
double theta
Definition types.h:50
bool constrained
Definition types.h:55
bend
Definition structures.h:33
struct poly_s poly
double elapsed_sec(void)
Definition timing.c:23
void start_timer(void)
Definition timing.c:21