Graphviz  2.41.20170921.2350
routespl.c
Go to the documentation of this file.
1 /* $Id$ $Revision$ */
2 /* vim:set shiftwidth=4 ts=8: */
3 
4 /*************************************************************************
5  * Copyright (c) 2011 AT&T Intellectual Property
6  * All rights reserved. This program and the accompanying materials
7  * are made available under the terms of the Eclipse Public License v1.0
8  * which accompanies this distribution, and is available at
9  * http://www.eclipse.org/legal/epl-v10.html
10  *
11  * Contributors: See CVS logs. Details at http://www.graphviz.org/
12  *************************************************************************/
13 
14 #include "config.h"
15 
16 #include "render.h"
17 #include "pathplan.h"
18 #include <setjmp.h>
19 
20 #ifdef UNUSED
21 static box *bs = NULL;
22 static int bn;
23 static int maxbn = 0;
24 #define BINC 300
25 #endif
26 
27 #define PINC 300
28 
29 #ifdef NOTNOW
30 static edge_t *origedge;
31 #endif
32 
33 static int nedges, nboxes; /* total no. of edges and boxes used in routing */
34 
35 static int routeinit;
36 /* static data used across multiple edges */
37 static pointf *ps; /* final spline points */
38 static int maxpn; /* size of ps[] */
39 static Ppoint_t *polypoints; /* vertices of polygon defined by boxes */
40 static int polypointn; /* size of polypoints[] */
41 static Pedge_t *edges; /* polygon edges passed to Proutespline */
42 static int edgen; /* size of edges[] */
43 
44 static int checkpath(int, boxf*, path*);
45 static int mkspacep(int size);
46 static void printpath(path * pp);
47 #ifdef DEBUG
48 static void printboxes(int boxn, boxf* boxes)
49 {
50  pointf ll, ur;
51  int bi;
52  char buf[BUFSIZ];
53  int newcnt = Show_cnt + boxn;
54 
55  Show_boxes = ALLOC(newcnt+2,Show_boxes,char*);
56  for (bi = 0; bi < boxn; bi++) {
57  ll = boxes[bi].LL, ur = boxes[bi].UR;
58  sprintf(buf, "%d %d %d %d pathbox", (int)ll.x, (int)ll.y, (int)ur.x, (int)ur.y);
59  Show_boxes[bi+1+Show_cnt] = strdup (buf);
60  }
61  Show_cnt = newcnt;
63 }
64 
65 #if DEBUG > 1
66 static void psprintpolypts(Ppoint_t * p, int sz)
67 {
68  int i;
69 
70  fprintf(stderr, "%%!\n");
71  fprintf(stderr, "%% constraint poly\n");
72  fprintf(stderr, "newpath\n");
73  for (i = 0; i < sz; i++)
74  fprintf(stderr, "%f %f %s\n", p[i].x, p[i].y,
75  (i == 0 ? "moveto" : "lineto"));
76  fprintf(stderr, "closepath stroke\n");
77 }
78 static void psprintpoint(point p)
79 {
80  fprintf(stderr, "gsave\n");
81  fprintf(stderr,
82  "newpath %d %d moveto %d %d 2 0 360 arc closepath fill stroke\n",
83  p.x, p.y, p.x, p.y);
84  fprintf(stderr, "/Times-Roman findfont 4 scalefont setfont\n");
85  fprintf(stderr, "%d %d moveto (\\(%d,%d\\)) show\n", p.x + 5, p.y + 5,
86  p.x, p.y);
87  fprintf(stderr, "grestore\n");
88 }
89 static void psprintpointf(pointf p)
90 {
91  fprintf(stderr, "gsave\n");
92  fprintf(stderr,
93  "newpath %.5g %.5g moveto %.5g %.5g 2 0 360 arc closepath fill stroke\n",
94  p.x, p.y, p.x, p.y);
95  fprintf(stderr, "/Times-Roman findfont 4 scalefont setfont\n");
96  fprintf(stderr, "%.5g %.5g moveto (\\(%.5g,%.5g\\)) show\n", p.x + 5, p.y + 5,
97  p.x, p.y);
98  fprintf(stderr, "grestore\n");
99 }
100 #endif
101 
102 static void psprintspline(Ppolyline_t spl)
103 {
104  char buf[BUFSIZ];
105  int newcnt = Show_cnt + spl.pn + 4;
106  int li, i;
107 
108  Show_boxes = ALLOC(newcnt+2,Show_boxes,char*);
109  li = Show_cnt+1;
110  Show_boxes[li++] = strdup ("%%!");
111  Show_boxes[li++] = strdup ("%% spline");
112  Show_boxes[li++] = strdup ("gsave 1 0 0 setrgbcolor newpath");
113  for (i = 0; i < spl.pn; i++) {
114  sprintf(buf, "%f %f %s", spl.ps[i].x, spl.ps[i].y,
115  (i == 0) ? "moveto" : ((i % 3 == 0) ? "curveto" : ""));
116  Show_boxes[li++] = strdup (buf);
117  }
118  Show_boxes[li++] = strdup ("stroke grestore");
119  Show_cnt = newcnt;
120  Show_boxes[Show_cnt+1] = NULL;
121 }
122 
123 static void psprintline(Ppolyline_t pl)
124 {
125  char buf[BUFSIZ];
126  int newcnt = Show_cnt + pl.pn + 4;
127  int i, li;
128 
129  Show_boxes = ALLOC(newcnt+2,Show_boxes,char*);
130  li = Show_cnt+1;
131  Show_boxes[li++] = strdup ("%%!");
132  Show_boxes[li++] = strdup ("%% line");
133  Show_boxes[li++] = strdup ("gsave 0 0 1 setrgbcolor newpath");
134  for (i = 0; i < pl.pn; i++) {
135  sprintf(buf, "%f %f %s", pl.ps[i].x, pl.ps[i].y,
136  (i == 0 ? "moveto" : "lineto"));
137  Show_boxes[li++] = strdup (buf);
138  }
139  Show_boxes[li++] = strdup ("stroke grestore");
140  Show_cnt = newcnt;
141  Show_boxes[Show_cnt+1] = NULL;
142 }
143 
144 static void psprintpoly(Ppoly_t p)
145 {
146  char buf[BUFSIZ];
147  int newcnt = Show_cnt + p.pn + 3;
148  point tl, hd;
149  int bi, li;
150  char* pfx;
151 
152  Show_boxes = ALLOC(newcnt+2,Show_boxes,char*);
153  li = Show_cnt+1;
154  Show_boxes[li++] = strdup ("%% poly list");
155  Show_boxes[li++] = strdup ("gsave 0 1 0 setrgbcolor");
156  for (bi = 0; bi < p.pn; bi++) {
157  tl.x = (int)p.ps[bi].x;
158  tl.y = (int)p.ps[bi].y;
159  hd.x = (int)p.ps[(bi+1) % p.pn].x;
160  hd.y = (int)p.ps[(bi+1) % p.pn].y;
161  if ((tl.x == hd.x) && (tl.y == hd.y)) pfx = "%%";
162  else pfx ="";
163  sprintf(buf, "%s%d %d %d %d makevec", pfx, tl.x, tl.y, hd.x, hd.y);
164  Show_boxes[li++] = strdup (buf);
165  }
166  Show_boxes[li++] = strdup ("grestore");
167 
168  Show_cnt = newcnt;
169  Show_boxes[Show_cnt+1] = NULL;
170 }
171 
172 static void psprintboxes(int boxn, boxf* boxes)
173 {
174  char buf[BUFSIZ];
175  int newcnt = Show_cnt + 5*boxn + 3;
176  pointf ll, ur;
177  int bi, li;
178 
179  Show_boxes = ALLOC(newcnt+2,Show_boxes,char*);
180  li = Show_cnt+1;
181  Show_boxes[li++] = strdup ("%% box list");
182  Show_boxes[li++] = strdup ("gsave 0 1 0 setrgbcolor");
183  for (bi = 0; bi < boxn; bi++) {
184  ll = boxes[bi].LL, ur = boxes[bi].UR;
185  sprintf(buf, "newpath\n%d %d moveto", (int)ll.x, (int)ll.y);
186  Show_boxes[li++] = strdup (buf);
187  sprintf(buf, "%d %d lineto", (int)ll.x, (int)ur.y);
188  Show_boxes[li++] = strdup (buf);
189  sprintf(buf, "%d %d lineto", (int)ur.x, (int)ur.y);
190  Show_boxes[li++] = strdup (buf);
191  sprintf(buf, "%d %d lineto", (int)ur.x, (int)ll.y);
192  Show_boxes[li++] = strdup (buf);
193  Show_boxes[li++] = strdup ("closepath stroke");
194  }
195  Show_boxes[li++] = strdup ("grestore");
196 
197  Show_cnt = newcnt;
198  Show_boxes[Show_cnt+1] = NULL;
199 }
200 
201 static void psprintinit (int begin)
202 {
203  int newcnt = Show_cnt + 1;
204 
205  Show_boxes = ALLOC(newcnt+2,Show_boxes,char*);
206  if (begin)
207  Show_boxes[1+Show_cnt] = strdup ("dbgstart");
208  else
209  Show_boxes[1+Show_cnt] = strdup ("grestore");
210  Show_cnt = newcnt;
211  Show_boxes[Show_cnt+1] = NULL;
212 }
213 
214 static int debugleveln(edge_t* realedge, int i)
215 {
216  return (GD_showboxes(agraphof(aghead(realedge))) == i ||
217  GD_showboxes(agraphof(agtail(realedge))) == i ||
218  ED_showboxes(realedge) == i ||
219  ND_showboxes(aghead(realedge)) == i ||
220  ND_showboxes(agtail(realedge)) == i);
221 }
222 #endif /* DEBUG */
223 
224 
225 
226 /* simpleSplineRoute:
227  * Given a simple (ccw) polygon, route an edge from tp to hp.
228  */
229 pointf*
230 simpleSplineRoute (pointf tp, pointf hp, Ppoly_t poly, int* n_spl_pts,
231  int polyline)
232 {
233  Ppolyline_t pl, spl;
234  Ppoint_t eps[2];
235  Pvector_t evs[2];
236  int i;
237 
238  eps[0].x = tp.x;
239  eps[0].y = tp.y;
240  eps[1].x = hp.x;
241  eps[1].y = hp.y;
242  if (Pshortestpath(&poly, eps, &pl) < 0)
243  return NULL;
244 
245  if (polyline)
246  make_polyline (pl, &spl);
247  else {
248  if (poly.pn > edgen) {
249  edges = ALLOC(poly.pn, edges, Pedge_t);
250  edgen = poly.pn;
251  }
252  for (i = 0; i < poly.pn; i++) {
253  edges[i].a = poly.ps[i];
254  edges[i].b = poly.ps[(i + 1) % poly.pn];
255  }
256 #if 0
257  if (pp->start.constrained) {
258  evs[0].x = cos(pp->start.theta);
259  evs[0].y = sin(pp->start.theta);
260  } else
261 #endif
262  evs[0].x = evs[0].y = 0;
263 #if 0
264  if (pp->end.constrained) {
265  evs[1].x = -cos(pp->end.theta);
266  evs[1].y = -sin(pp->end.theta);
267  } else
268 #endif
269  evs[1].x = evs[1].y = 0;
270  if (Proutespline(edges, poly.pn, pl, evs, &spl) < 0)
271  return NULL;
272  }
273 
274  if (mkspacep(spl.pn))
275  return NULL;
276  for (i = 0; i < spl.pn; i++) {
277  ps[i] = spl.ps[i];
278  }
279  *n_spl_pts = spl.pn;
280  return ps;
281 }
282 
283 /* routesplinesinit:
284  * Data initialized once until matching call to routeplineterm
285  * Allows recursive calls to dot
286  */
287 int
289 {
290  if (++routeinit > 1) return 0;
291  if (!(ps = N_GNEW(PINC, pointf))) {
292  agerr(AGERR, "routesplinesinit: cannot allocate ps\n");
293  return 1;
294  }
295  maxpn = PINC;
296 #ifdef DEBUG
297  if (Show_boxes) {
298  int i;
299  for (i = 0; Show_boxes[i]; i++)
300  free (Show_boxes[i]);
301  free (Show_boxes);
302  Show_boxes = NULL;
303  Show_cnt = 0;
304  }
305 #endif
306  nedges = 0;
307  nboxes = 0;
308  if (Verbose)
309  start_timer();
310  return 0;
311 }
312 
314 {
315  if (--routeinit > 0) return;
316  free(ps);
317 #ifdef UNUSED
318  free(bs), bs = NULL /*, maxbn = bn = 0 */ ;
319 #endif
320  if (Verbose)
321  fprintf(stderr,
322  "routesplines: %d edges, %d boxes %.2f sec\n",
323  nedges, nboxes, elapsed_sec());
324 }
325 
326 static void
327 limitBoxes (boxf* boxes, int boxn, pointf *pps, int pn, int delta)
328 {
329  int bi, si, splinepi;
330  double t;
331  pointf sp[4];
332  int num_div = delta * boxn;
333 
334  for (splinepi = 0; splinepi + 3 < pn; splinepi += 3) {
335  for (si = 0; si <= num_div; si++) {
336  t = si / (double)num_div;
337  sp[0] = pps[splinepi];
338  sp[1] = pps[splinepi + 1];
339  sp[2] = pps[splinepi + 2];
340  sp[3] = pps[splinepi + 3];
341  sp[0].x = sp[0].x + t * (sp[1].x - sp[0].x);
342  sp[0].y = sp[0].y + t * (sp[1].y - sp[0].y);
343  sp[1].x = sp[1].x + t * (sp[2].x - sp[1].x);
344  sp[1].y = sp[1].y + t * (sp[2].y - sp[1].y);
345  sp[2].x = sp[2].x + t * (sp[3].x - sp[2].x);
346  sp[2].y = sp[2].y + t * (sp[3].y - sp[2].y);
347  sp[0].x = sp[0].x + t * (sp[1].x - sp[0].x);
348  sp[0].y = sp[0].y + t * (sp[1].y - sp[0].y);
349  sp[1].x = sp[1].x + t * (sp[2].x - sp[1].x);
350  sp[1].y = sp[1].y + t * (sp[2].y - sp[1].y);
351  sp[0].x = sp[0].x + t * (sp[1].x - sp[0].x);
352  sp[0].y = sp[0].y + t * (sp[1].y - sp[0].y);
353  for (bi = 0; bi < boxn; bi++) {
354 /* this tested ok on 64bit machines, but on 32bit we need this FUDGE
355  * or graphs/directed/records.gv fails */
356 #define FUDGE .0001
357  if (sp[0].y <= boxes[bi].UR.y+FUDGE && sp[0].y >= boxes[bi].LL.y-FUDGE) {
358  if (boxes[bi].LL.x > sp[0].x)
359  boxes[bi].LL.x = sp[0].x;
360  if (boxes[bi].UR.x < sp[0].x)
361  boxes[bi].UR.x = sp[0].x;
362  }
363  }
364  }
365  }
366 }
367 
368 #define INIT_DELTA 10
369 #define LOOP_TRIES 15 /* number of times to try to limiting boxes to regain space, using smaller divisions */
370 
371 /* routesplines:
372  * Route a path using the path info in pp. This includes start and end points
373  * plus a collection of contiguous boxes contain the terminal points. The boxes
374  * are converted into a containing polygon. A shortest path is constructed within
375  * the polygon from between the terminal points. If polyline is true, this path
376  * is converted to a spline representation. Otherwise, we call the path planner to
377  * convert the polyline into a smooth spline staying within the polygon. In both
378  * cases, the function returns an array of the computed control points. The number
379  * of these points is given in npoints.
380  *
381  * Note that the returned points are stored in a single array, so the points must be
382  * used before another call to this function.
383  *
384  * During cleanup, the function determines the x-extent of the spline in the box, so
385  * the box can be shrunk to the minimum width. The extra space can then be used by other
386  * edges.
387  *
388  * If a catastrophic error, return NULL.
389  */
390 static pointf *_routesplines(path * pp, int *npoints, int polyline)
391 {
392  Ppoly_t poly;
393  Ppolyline_t pl, spl;
394  int splinepi;
395  Ppoint_t eps[2];
396  Pvector_t evs[2];
397  int edgei, prev, next;
398  int pi, bi;
399  boxf *boxes;
400  int boxn;
401  edge_t* realedge;
402  int flip;
403  int loopcnt, delta = INIT_DELTA;
404  boolean unbounded;
405 
406  nedges++;
407  nboxes += pp->nbox;
408 
409  for (realedge = (edge_t *) pp->data;
410 #ifdef NOTNOW
411  origedge = realedge;
412 #endif
413  realedge && ED_edge_type(realedge) != NORMAL;
414  realedge = ED_to_orig(realedge));
415  if (!realedge) {
416  agerr(AGERR, "in routesplines, cannot find NORMAL edge\n");
417  return NULL;
418  }
419 
420  boxes = pp->boxes;
421  boxn = pp->nbox;
422 
423  if (checkpath(boxn, boxes, pp))
424  return NULL;
425 
426 #ifdef DEBUG
427  if (debugleveln(realedge, 1))
428  printboxes(boxn, boxes);
429  if (debugleveln(realedge, 3)) {
430  psprintinit(1);
431  psprintboxes(boxn, boxes);
432  }
433 #endif
434 
435  if (boxn * 8 > polypointn) {
436  polypoints = ALLOC(boxn * 8, polypoints, Ppoint_t);
437  polypointn = boxn * 8;
438  }
439 
440  if ((boxn > 1) && (boxes[0].LL.y > boxes[1].LL.y)) {
441  flip = 1;
442  for (bi = 0; bi < boxn; bi++) {
443  double v = boxes[bi].UR.y;
444  boxes[bi].UR.y = -1*boxes[bi].LL.y;
445  boxes[bi].LL.y = -v;
446  }
447  }
448  else flip = 0;
449 
450  if (agtail(realedge) != aghead(realedge)) {
451  /* I assume that the path goes either down only or
452  up - right - down */
453  for (bi = 0, pi = 0; bi < boxn; bi++) {
454  next = prev = 0;
455  if (bi > 0)
456  prev = (boxes[bi].LL.y > boxes[bi - 1].LL.y) ? -1 : 1;
457  if (bi < boxn - 1)
458  next = (boxes[bi + 1].LL.y > boxes[bi].LL.y) ? 1 : -1;
459  if (prev != next) {
460  if (next == -1 || prev == 1) {
461  polypoints[pi].x = boxes[bi].LL.x;
462  polypoints[pi++].y = boxes[bi].UR.y;
463  polypoints[pi].x = boxes[bi].LL.x;
464  polypoints[pi++].y = boxes[bi].LL.y;
465  } else {
466  polypoints[pi].x = boxes[bi].UR.x;
467  polypoints[pi++].y = boxes[bi].LL.y;
468  polypoints[pi].x = boxes[bi].UR.x;
469  polypoints[pi++].y = boxes[bi].UR.y;
470  }
471  }
472  else if (prev == 0) { /* single box */
473  polypoints[pi].x = boxes[bi].LL.x;
474  polypoints[pi++].y = boxes[bi].UR.y;
475  polypoints[pi].x = boxes[bi].LL.x;
476  polypoints[pi++].y = boxes[bi].LL.y;
477  }
478  else {
479  if (!(prev == -1 && next == -1)) {
480  agerr(AGERR, "in routesplines, illegal values of prev %d and next %d, line %d\n", prev, next, __LINE__);
481  return NULL;
482  }
483  }
484  }
485  for (bi = boxn - 1; bi >= 0; bi--) {
486  next = prev = 0;
487  if (bi < boxn - 1)
488  prev = (boxes[bi].LL.y > boxes[bi + 1].LL.y) ? -1 : 1;
489  if (bi > 0)
490  next = (boxes[bi - 1].LL.y > boxes[bi].LL.y) ? 1 : -1;
491  if (prev != next) {
492  if (next == -1 || prev == 1 ) {
493  polypoints[pi].x = boxes[bi].LL.x;
494  polypoints[pi++].y = boxes[bi].UR.y;
495  polypoints[pi].x = boxes[bi].LL.x;
496  polypoints[pi++].y = boxes[bi].LL.y;
497  } else {
498  polypoints[pi].x = boxes[bi].UR.x;
499  polypoints[pi++].y = boxes[bi].LL.y;
500  polypoints[pi].x = boxes[bi].UR.x;
501  polypoints[pi++].y = boxes[bi].UR.y;
502  }
503  }
504  else if (prev == 0) { /* single box */
505  polypoints[pi].x = boxes[bi].UR.x;
506  polypoints[pi++].y = boxes[bi].LL.y;
507  polypoints[pi].x = boxes[bi].UR.x;
508  polypoints[pi++].y = boxes[bi].UR.y;
509  }
510  else {
511  if (!(prev == -1 && next == -1)) {
512  /* it went badly, e.g. degenerate box in boxlist */
513  agerr(AGERR, "in routesplines, illegal values of prev %d and next %d, line %d\n", prev, next, __LINE__);
514  return NULL; /* for correctness sake, it's best to just stop */
515  }
516  polypoints[pi].x = boxes[bi].UR.x;
517  polypoints[pi++].y = boxes[bi].LL.y;
518  polypoints[pi].x = boxes[bi].UR.x;
519  polypoints[pi++].y = boxes[bi].UR.y;
520  polypoints[pi].x = boxes[bi].LL.x;
521  polypoints[pi++].y = boxes[bi].UR.y;
522  polypoints[pi].x = boxes[bi].LL.x;
523  polypoints[pi++].y = boxes[bi].LL.y;
524  }
525  }
526  }
527  else {
528  agerr(AGERR, "in routesplines, edge is a loop at %s\n", agnameof(aghead(realedge)));
529  return NULL;
530  }
531 
532  if (flip) {
533  int i;
534  for (bi = 0; bi < boxn; bi++) {
535  double v = boxes[bi].UR.y;
536  boxes[bi].UR.y = -1*boxes[bi].LL.y;
537  boxes[bi].LL.y = -v;
538  }
539  for (i = 0; i < pi; i++)
540  polypoints[i].y *= -1;
541  }
542 
543  for (bi = 0; bi < boxn; bi++)
544  boxes[bi].LL.x = INT_MAX, boxes[bi].UR.x = INT_MIN;
545  poly.ps = polypoints, poly.pn = pi;
546  eps[0].x = pp->start.p.x, eps[0].y = pp->start.p.y;
547  eps[1].x = pp->end.p.x, eps[1].y = pp->end.p.y;
548  if (Pshortestpath(&poly, eps, &pl) < 0) {
549  agerr(AGERR, "in routesplines, Pshortestpath failed\n");
550  return NULL;
551  }
552 #ifdef DEBUG
553  if (debugleveln(realedge, 3)) {
554  psprintpoly(poly);
555  psprintline(pl);
556  }
557 #endif
558 
559  if (polyline) {
560  make_polyline (pl, &spl);
561  }
562  else {
563  if (poly.pn > edgen) {
564  edges = ALLOC(poly.pn, edges, Pedge_t);
565  edgen = poly.pn;
566  }
567  for (edgei = 0; edgei < poly.pn; edgei++) {
568  edges[edgei].a = polypoints[edgei];
569  edges[edgei].b = polypoints[(edgei + 1) % poly.pn];
570  }
571  if (pp->start.constrained) {
572  evs[0].x = cos(pp->start.theta);
573  evs[0].y = sin(pp->start.theta);
574  } else
575  evs[0].x = evs[0].y = 0;
576  if (pp->end.constrained) {
577  evs[1].x = -cos(pp->end.theta);
578  evs[1].y = -sin(pp->end.theta);
579  } else
580  evs[1].x = evs[1].y = 0;
581 
582  if (Proutespline(edges, poly.pn, pl, evs, &spl) < 0) {
583  agerr(AGERR, "in routesplines, Proutespline failed\n");
584  return NULL;
585  }
586 #ifdef DEBUG
587  if (debugleveln(realedge, 3)) {
588  psprintspline(spl);
589  psprintinit(0);
590  }
591 #endif
592  }
593  if (mkspacep(spl.pn))
594  return NULL; /* Bailout if no memory left */
595 
596  for (bi = 0; bi < boxn; bi++) {
597  boxes[bi].LL.x = INT_MAX;
598  boxes[bi].UR.x = INT_MIN;
599  }
600  unbounded = TRUE;
601  for (splinepi = 0; splinepi < spl.pn; splinepi++) {
602  ps[splinepi] = spl.ps[splinepi];
603  }
604 
605  for (loopcnt = 0; unbounded && (loopcnt < LOOP_TRIES); loopcnt++) {
606  limitBoxes (boxes, boxn, ps, spl.pn, delta);
607 
608  /* The following check is necessary because if a box is not very
609  * high, it is possible that the sampling above might miss it.
610  * Therefore, we make the sample finer until all boxes have
611  * valid values. cf. bug 456. Would making sp[] pointfs help?
612  */
613  for (bi = 0; bi < boxn; bi++) {
614  /* these fp equality tests are used only to detect if the
615  * values have been changed since initialization - ok */
616  if ((boxes[bi].LL.x == INT_MAX) || (boxes[bi].UR.x == INT_MIN)) {
617  delta *= 2; /* try again with a finer interval */
618  if (delta > INT_MAX/boxn) /* in limitBoxes, boxn*delta must fit in an int, so give up */
619  loopcnt = LOOP_TRIES;
620  break;
621  }
622  }
623  if (bi == boxn)
624  unbounded = FALSE;
625  }
626  if (unbounded) {
627  /* Either an extremely short, even degenerate, box, or some failure with the path
628  * planner causing the spline to miss some boxes. In any case, use the shortest path
629  * to bound the boxes. This will probably mean a bad edge, but we avoid an infinite
630  * loop and we can see the bad edge, and even use the showboxes scaffolding.
631  */
632  Ppolyline_t polyspl;
633  agerr(AGWARN, "Unable to reclaim box space in spline routing for edge \"%s\" -> \"%s\". Something is probably seriously wrong.\n", agnameof(agtail(realedge)), agnameof(aghead(realedge)));
634  make_polyline (pl, &polyspl);
635  limitBoxes (boxes, boxn, polyspl.ps, polyspl.pn, INIT_DELTA);
636  free (polyspl.ps);
637  }
638 
639  *npoints = spl.pn;
640 
641 #ifdef DEBUG
642  if (GD_showboxes(agraphof(aghead(realedge))) == 2 ||
643  GD_showboxes(agraphof(agtail(realedge))) == 2 ||
644  ED_showboxes(realedge) == 2 ||
645  ND_showboxes(aghead(realedge)) == 2 ||
646  ND_showboxes(agtail(realedge)) == 2)
647  printboxes(boxn, boxes);
648 #endif
649 
650  return ps;
651 }
652 
653 pointf *routesplines(path * pp, int *npoints)
654 {
655  return _routesplines (pp, npoints, 0);
656 }
657 
658 pointf *routepolylines(path * pp, int *npoints)
659 {
660  return _routesplines (pp, npoints, 1);
661 }
662 
663 static int overlap(int i0, int i1, int j0, int j1)
664 {
665  /* i'll bet there's an elegant way to do this */
666  if (i1 <= j0)
667  return 0;
668  if (i0 >= j1)
669  return 0;
670  if ((j0 <= i0) && (i0 <= j1))
671  return (j1 - i0);
672  if ((j0 <= i1) && (i1 <= j1))
673  return (i1 - j0);
674  return MIN(i1 - i0, j1 - j0);
675 }
676 
677 
678 /*
679  * repairs minor errors in the boxpath, such as boxes not joining
680  * or slightly intersecting. it's sort of the equivalent of the
681  * audit process in the 5E control program - if you've given up on
682  * fixing all the bugs, at least try to engineer around them!
683  * in postmodern CS, we could call this "self-healing code."
684  *
685  * Return 1 on failure; 0 on success.
686  */
687 static int checkpath(int boxn, boxf* boxes, path* thepath)
688 {
689  boxf *ba, *bb;
690  int bi, i, errs, l, r, d, u;
691  int xoverlap, yoverlap;
692 
693 #ifndef DONTFIXPATH
694  /* remove degenerate boxes. */
695  i = 0;
696  for (bi = 0; bi < boxn; bi++) {
697  if (ABS(boxes[bi].LL.y - boxes[bi].UR.y) < .01)
698  continue;
699  if (ABS(boxes[bi].LL.x - boxes[bi].UR.x) < .01)
700  continue;
701  if (i != bi)
702  boxes[i] = boxes[bi];
703  i++;
704  }
705  boxn = i;
706 #endif /* DONTFIXPATH */
707 
708  ba = &boxes[0];
709  if (ba->LL.x > ba->UR.x || ba->LL.y > ba->UR.y) {
710  agerr(AGERR, "in checkpath, box 0 has LL coord > UR coord\n");
711  printpath(thepath);
712  return 1;
713  }
714  for (bi = 0; bi < boxn - 1; bi++) {
715  ba = &boxes[bi], bb = &boxes[bi + 1];
716  if (bb->LL.x > bb->UR.x || bb->LL.y > bb->UR.y) {
717  agerr(AGERR, "in checkpath, box %d has LL coord > UR coord\n",
718  bi + 1);
719  printpath(thepath);
720  return 1;
721  }
722  l = (ba->UR.x < bb->LL.x) ? 1 : 0;
723  r = (ba->LL.x > bb->UR.x) ? 1 : 0;
724  d = (ba->UR.y < bb->LL.y) ? 1 : 0;
725  u = (ba->LL.y > bb->UR.y) ? 1 : 0;
726  errs = l + r + d + u;
727  if (errs > 0 && Verbose) {
728  fprintf(stderr, "in checkpath, boxes %d and %d don't touch\n",
729  bi, bi + 1);
730  printpath(thepath);
731  }
732 #ifndef DONTFIXPATH
733  if (errs > 0) {
734  int xy;
735 
736  if (l == 1)
737  xy = ba->UR.x, ba->UR.x = bb->LL.x, bb->LL.x = xy, l = 0;
738  else if (r == 1)
739  xy = ba->LL.x, ba->LL.x = bb->UR.x, bb->UR.x = xy, r = 0;
740  else if (d == 1)
741  xy = ba->UR.y, ba->UR.y = bb->LL.y, bb->LL.y = xy, d = 0;
742  else if (u == 1)
743  xy = ba->LL.y, ba->LL.y = bb->UR.y, bb->UR.y = xy, u = 0;
744  for (i = 0; i < errs - 1; i++) {
745  if (l == 1)
746  xy = (ba->UR.x + bb->LL.x) / 2.0 + 0.5, ba->UR.x =
747  bb->LL.x = xy, l = 0;
748  else if (r == 1)
749  xy = (ba->LL.x + bb->UR.x) / 2.0 + 0.5, ba->LL.x =
750  bb->UR.x = xy, r = 0;
751  else if (d == 1)
752  xy = (ba->UR.y + bb->LL.y) / 2.0 + 0.5, ba->UR.y =
753  bb->LL.y = xy, d = 0;
754  else if (u == 1)
755  xy = (ba->LL.y + bb->UR.y) / 2.0 + 0.5, ba->LL.y =
756  bb->UR.y = xy, u = 0;
757  }
758  }
759 #else
760  abort();
761 #endif
762 #ifndef DONTFIXPATH
763  /* check for overlapping boxes */
764  xoverlap = overlap(ba->LL.x, ba->UR.x, bb->LL.x, bb->UR.x);
765  yoverlap = overlap(ba->LL.y, ba->UR.y, bb->LL.y, bb->UR.y);
766  if (xoverlap && yoverlap) {
767  if (xoverlap < yoverlap) {
768  if (ba->UR.x - ba->LL.x > bb->UR.x - bb->LL.x) {
769  /* take space from ba */
770  if (ba->UR.x < bb->UR.x)
771  ba->UR.x = bb->LL.x;
772  else
773  ba->LL.x = bb->UR.x;
774  } else {
775  /* take space from bb */
776  if (ba->UR.x < bb->UR.x)
777  bb->LL.x = ba->UR.x;
778  else
779  bb->UR.x = ba->LL.x;
780  }
781  } else { /* symmetric for y coords */
782  if (ba->UR.y - ba->LL.y > bb->UR.y - bb->LL.y) {
783  /* take space from ba */
784  if (ba->UR.y < bb->UR.y)
785  ba->UR.y = bb->LL.y;
786  else
787  ba->LL.y = bb->UR.y;
788  } else {
789  /* take space from bb */
790  if (ba->UR.y < bb->UR.y)
791  bb->LL.y = ba->UR.y;
792  else
793  bb->UR.y = ba->LL.y;
794  }
795  }
796  }
797  }
798 #endif /* DONTFIXPATH */
799 
800  if (thepath->start.p.x < boxes[0].LL.x
801  || thepath->start.p.x > boxes[0].UR.x
802  || thepath->start.p.y < boxes[0].LL.y
803  || thepath->start.p.y > boxes[0].UR.y) {
804  if (Verbose) {
805  fprintf(stderr, "in checkpath, start port not in first box\n");
806  printpath(thepath);
807  }
808 #ifndef DONTFIXPATH
809  if (thepath->start.p.x < boxes[0].LL.x)
810  thepath->start.p.x = boxes[0].LL.x;
811  if (thepath->start.p.x > boxes[0].UR.x)
812  thepath->start.p.x = boxes[0].UR.x;
813  if (thepath->start.p.y < boxes[0].LL.y)
814  thepath->start.p.y = boxes[0].LL.y;
815  if (thepath->start.p.y > boxes[0].UR.y)
816  thepath->start.p.y = boxes[0].UR.y;
817 #else
818  abort();
819 #endif
820  }
821  if (thepath->end.p.x < boxes[boxn - 1].LL.x
822  || thepath->end.p.x > boxes[boxn - 1].UR.x
823  || thepath->end.p.y < boxes[boxn - 1].LL.y
824  || thepath->end.p.y > boxes[boxn - 1].UR.y) {
825  if (Verbose) {
826  fprintf(stderr, "in checkpath, end port not in last box\n");
827  printpath(thepath);
828  }
829 #ifndef DONTFIXPATH
830  if (thepath->end.p.x < boxes[boxn - 1].LL.x)
831  thepath->end.p.x = boxes[boxn - 1].LL.x;
832  if (thepath->end.p.x > boxes[boxn - 1].UR.x)
833  thepath->end.p.x = boxes[boxn - 1].UR.x;
834  if (thepath->end.p.y < boxes[boxn - 1].LL.y)
835  thepath->end.p.y = boxes[boxn - 1].LL.y;
836  if (thepath->end.p.y > boxes[boxn - 1].UR.y)
837  thepath->end.p.y = boxes[boxn - 1].UR.y;
838 #else
839  abort();
840 #endif
841  }
842  return 0;
843 }
844 
845 static int mkspacep(int size)
846 {
847  if (size > maxpn) {
848  int newmax = maxpn + (size / PINC + 1) * PINC;
849  ps = RALLOC(newmax, ps, pointf);
850  if (!ps) {
851  agerr(AGERR, "cannot re-allocate ps\n");
852  return 1;
853  }
854  maxpn = newmax;
855  }
856  return 0;
857 }
858 
859 static void printpath(path * pp)
860 {
861  int bi;
862 
863 #ifdef NOTNOW
864  fprintf(stderr, "edge %d from %s to %s\n", nedges,
865  realedge->tail->name, realedge->head->name);
866  if (ED_count(origedge) > 1)
867  fprintf(stderr, " (it's part of a concentrator edge)\n");
868 #endif
869  fprintf(stderr, "%d boxes:\n", pp->nbox);
870  for (bi = 0; bi < pp->nbox; bi++)
871  fprintf(stderr, "%d (%.5g, %.5g), (%.5g, %.5g)\n", bi,
872  pp->boxes[bi].LL.x, pp->boxes[bi].LL.y,
873  pp->boxes[bi].UR.x, pp->boxes[bi].UR.y);
874  fprintf(stderr, "start port: (%.5g, %.5g), tangent angle: %.5g, %s\n",
875  pp->start.p.x, pp->start.p.y, pp->start.theta,
876  pp->start.constrained ? "constrained" : "not constrained");
877  fprintf(stderr, "end port: (%.5g, %.5g), tangent angle: %.5g, %s\n",
878  pp->end.p.x, pp->end.p.y, pp->end.theta,
879  pp->end.constrained ? "constrained" : "not constrained");
880 }
881 
882 static pointf get_centroid(Agraph_t *g)
883 {
884  int cnt = 0;
885  static pointf sum = {0.0, 0.0};
886  static Agraph_t *save;
887  Agnode_t *n;
888 
889  sum.x = (GD_bb(g).LL.x + GD_bb(g).UR.x) / 2.0;
890  sum.y = (GD_bb(g).LL.y + GD_bb(g).UR.y) / 2.0;
891  return sum;
892 
893  if (save == g) return sum;
894  save = g;
895  for (n = agfstnode(g); n; n = agnxtnode(g,n)) {
896  sum.x += ND_pos(n)[0];
897  sum.y += ND_pos(n)[1];
898  cnt++;
899  }
900  sum.x = sum.x / cnt;
901  sum.y = sum.y / cnt;
902  return sum;
903 }
904 
905 static void bend(pointf spl[4], pointf centroid)
906 {
907  pointf midpt,a;
908  double r;
909  double dist,dx,dy;
910 
911  midpt.x = (spl[0].x + spl[3].x)/2.0;
912  midpt.y = (spl[0].y + spl[3].y)/2.0;
913  dx = (spl[3].x - spl[0].x);
914  dy = (spl[3].y - spl[0].y);
915  dist = sqrt(dx*dx + dy*dy);
916  r = dist/5.0;
917  {
918  double vX = centroid.x - midpt.x;
919  double vY = centroid.y - midpt.y;
920  double magV = sqrt(vX*vX + vY*vY);
921  if (magV == 0) return; /* if midpoint == centroid, don't divide by zero */
922  a.x = midpt.x - vX / magV * r; /* + would be closest point */
923  a.y = midpt.y - vY / magV * r;
924  }
925  /* this can be improved */
926  spl[1].x = spl[2].x = a.x;
927  spl[1].y = spl[2].y = a.y;
928 }
929 
930 /* makeStraightEdge:
931  *
932  * FIX: handle ports on boundary?
933  */
934 #define MAX_EDGE 20
935 void
936 makeStraightEdge(graph_t * g, edge_t * e, int et, splineInfo* sinfo)
937 {
938  edge_t *e0;
939  edge_t** edges;
941  int i, e_cnt;
942 
943  e_cnt = 1;
944  e0 = e;
945  while ((e0 != ED_to_virt(e0)) && (e0 = ED_to_virt(e0))) e_cnt++;
946 
947  if (e_cnt <= MAX_EDGE)
948  edges = elist;
949  else
950  edges = N_NEW(e_cnt,edge_t*);
951  e0 = e;
952  for (i = 0; i < e_cnt; i++) {
953  edges[i] = e0;
954  e0 = ED_to_virt(e0);
955  }
956  makeStraightEdges (g, edges, e_cnt, et, sinfo);
957  if (e_cnt > MAX_EDGE) free (edges);
958 
959 }
960 
961 void
962 makeStraightEdges(graph_t * g, edge_t** edges, int e_cnt, int et, splineInfo* sinfo)
963 {
964  pointf dumb[4];
965  node_t *n;
966  node_t *head;
967  int curved = (et == ET_CURVED);
968  pointf perp;
969  pointf del;
970  edge_t *e0;
971  edge_t *e;
972  int i, j, xstep, dx;
973  double l_perp;
974  pointf dumber[4];
975  pointf p, q;
976 
977  e = edges[0];
978  n = agtail(e);
979  head = aghead(e);
980  p = dumb[1] = dumb[0] = add_pointf(ND_coord(n), ED_tail_port(e).p);
981  q = dumb[2] = dumb[3] = add_pointf(ND_coord(head), ED_head_port(e).p);
982  if ((e_cnt == 1) || Concentrate) {
983  if (curved) bend(dumb,get_centroid(g));
984  clip_and_install(e, aghead(e), dumb, 4, sinfo);
985  addEdgeLabels(g, e, p, q);
986  return;
987  }
988 
989  e0 = e;
990  if (APPROXEQPT(dumb[0], dumb[3], MILLIPOINT)) {
991  /* degenerate case */
992  dumb[1] = dumb[0];
993  dumb[2] = dumb[3];
994  del.x = 0;
995  del.y = 0;
996  }
997  else {
998  perp.x = dumb[0].y - dumb[3].y;
999  perp.y = dumb[3].x - dumb[0].x;
1000  l_perp = LEN(perp.x, perp.y);
1001  xstep = GD_nodesep(g->root);
1002  dx = xstep * (e_cnt - 1) / 2;
1003  dumb[1].x = dumb[0].x + (dx * perp.x) / l_perp;
1004  dumb[1].y = dumb[0].y + (dx * perp.y) / l_perp;
1005  dumb[2].x = dumb[3].x + (dx * perp.x) / l_perp;
1006  dumb[2].y = dumb[3].y + (dx * perp.y) / l_perp;
1007  del.x = -xstep * perp.x / l_perp;
1008  del.y = -xstep * perp.y / l_perp;
1009  }
1010 
1011  for (i = 0; i < e_cnt; i++) {
1012  e0 = edges[i];
1013  if (aghead(e0) == head) {
1014  p = dumb[0];
1015  q = dumb[3];
1016  for (j = 0; j < 4; j++) {
1017  dumber[j] = dumb[j];
1018  }
1019  } else {
1020  p = dumb[3];
1021  q = dumb[0];
1022  for (j = 0; j < 4; j++) {
1023  dumber[3 - j] = dumb[j];
1024  }
1025  }
1026  if (et == ET_PLINE) {
1027  Ppoint_t pts[4];
1028  Ppolyline_t spl, line;
1029 
1030  line.pn = 4;
1031  line.ps = pts;
1032  for (j=0; j < 4; j++) {
1033  pts[j] = dumber[j];
1034  }
1035  make_polyline (line, &spl);
1036  clip_and_install(e0, aghead(e0), spl.ps, spl.pn, sinfo);
1037  }
1038  else
1039  clip_and_install(e0, aghead(e0), dumber, 4, sinfo);
1040 
1041  addEdgeLabels(g, e0, p, q);
1042  dumb[1].x += del.x;
1043  dumb[1].y += del.y;
1044  dumb[2].x += del.x;
1045  dumb[2].y += del.y;
1046  }
1047 }
void * data
Definition: types.h:105
port start
Definition: types.h:101
Definition: cgraph.h:388
pointf * routesplines(path *, int *)
Definition: routespl.c:653
#define RALLOC(size, ptr, type)
Definition: memory.h:42
#define ABS(a)
Definition: arith.h:45
#define PINC
Definition: routespl.c:27
void start_timer(void)
Definition: timing.c:45
#define N_NEW(n, t)
Definition: memory.h:36
int pn
Definition: pathgeom.h:36
#define MAX_EDGE
Definition: routespl.c:934
#define FUDGE
#define head
Definition: dthdr.h:19
#define LOOP_TRIES
Definition: routespl.c:369
#define MIN(a, b)
Definition: arith.h:35
pointf * routepolylines(path *pp, int *npoints)
Definition: routespl.c:658
#define ALLOC(size, ptr, type)
Definition: memory.h:41
#define ED_head_port(e)
Definition: types.h:591
double x
Definition: pathgeom.h:27
int Proutespline(Pedge_t *barriers, int n_barriers, Ppolyline_t input_route, Pvector_t endpoint_slopes[2], Ppolyline_t *output_route)
Definition: geom.h:28
#define ED_to_orig(e)
Definition: types.h:601
void makeStraightEdges(graph_t *g, edge_t **edges, int e_cnt, int et, splineInfo *sinfo)
Definition: routespl.c:962
void make_polyline(Ppolyline_t line, Ppolyline_t *sline)
Definition: util.c:82
void clip_and_install(edge_t *fe, node_t *hn, pointf *ps, int pn, splineInfo *info)
Definition: splines.c:241
#define GD_showboxes(g)
Definition: types.h:410
#define ND_pos(n)
Definition: types.h:526
#define APPROXEQPT(p, q, tol)
Definition: geom.h:78
int agerr(agerrlevel_t level, const char *fmt,...)
Definition: agerror.c:141
pointf * simpleSplineRoute(pointf, pointf, Ppoly_t, int *, int)
Definition: routespl.c:230
Ppoint_t b
Definition: pathgeom.h:42
boolean constrained
Definition: types.h:74
int x
Definition: geom.h:26
boxf * boxes
Definition: types.h:104
Definition: cgraph.h:388
int routesplinesinit(void)
Definition: routespl.c:288
CGRAPH_API Agraph_t * agraphof(void *obj)
Definition: obj.c:185
CGRAPH_API Agnode_t * agtail(Agedge_t *e)
Definition: edge.c:525
void addEdgeLabels(graph_t *g, edge_t *e, pointf rp, pointf rq)
Definition: splines.c:1355
#define ED_showboxes(e)
Definition: types.h:597
#define INIT_DELTA
Definition: routespl.c:368
#define ED_tail_port(e)
Definition: types.h:600
CGRAPH_API Agnode_t * agnxtnode(Agraph_t *g, Agnode_t *n)
Definition: node.c:45
Definition: types.h:261
int
Definition: grammar.c:1264
CGRAPH_API Agnode_t * aghead(Agedge_t *e)
Definition: edge.c:533
void routesplinesterm(void)
Definition: routespl.c:313
#define LEN(a, b)
Definition: geom.h:57
double y
Definition: geom.h:28
#define ET_PLINE
Definition: const.h:273
CGRAPH_API char * agnameof(void *)
Definition: id.c:143
#define ED_count(e)
Definition: types.h:583
#define overlap(pb, qb)
Definition: constraint.c:549
#define ND_showboxes(n)
Definition: types.h:536
struct elist elist
CGRAPH_API Agnode_t * agfstnode(Agraph_t *g)
Definition: node.c:38
double theta
Definition: types.h:69
Ppoint_t * ps
Definition: pathgeom.h:35
if(aagss+aagstacksize-1<=aagssp)
Definition: grammar.c:1332
#define ET_CURVED
Definition: const.h:272
#define ED_to_virt(e)
Definition: types.h:602
EXTERN unsigned char Concentrate
Definition: globals.h:76
#define NULL
Definition: logic.h:39
EXTERN int Show_cnt
Definition: globals.h:73
#define INT_MIN
Definition: arith.h:56
Definition: geom.h:26
double elapsed_sec(void)
Definition: timing.c:50
double x
Definition: geom.h:28
#define ND_coord(n)
Definition: types.h:496
EXTERN unsigned char Verbose
Definition: globals.h:64
pointf p
Definition: types.h:68
int Pshortestpath(Ppoly_t *boundary, Ppoint_t endpoints[2], Ppolyline_t *output_route)
Ppoint_t a
Definition: pathgeom.h:42
pointf LL
Definition: geom.h:35
Definition: types.h:100
void makeStraightEdge(graph_t *g, edge_t *e, int edgetype, splineInfo *info)
Definition: routespl.c:936
EXTERN char ** Show_boxes
Definition: globals.h:74
#define MILLIPOINT
Definition: geom.h:81
#define GD_bb(g)
Definition: types.h:357
Definition: pathgeom.h:26
#define GD_nodesep(g)
Definition: types.h:402
double y
Definition: pathgeom.h:27
Agraph_t * root
Definition: cgraph.h:247
double dist(Site *s, Site *t)
Definition: site.c:41
#define NORMAL
Definition: const.h:27
int y
Definition: geom.h:26
int nbox
Definition: types.h:103
#define ED_edge_type(e)
Definition: types.h:585
port end
Definition: types.h:102
pointf UR
Definition: geom.h:35
Definition: geom.h:35
#define N_GNEW(n, t)
Definition: agxbuf.c:20
#define FALSE
Definition: cgraph.h:35
Definition: geom.h:33
#define INT_MAX
Definition: arith.h:52
#define TRUE
Definition: cgraph.h:38