From f693aeec68fa7c72781bb6d9f0b76e363d96e794 Mon Sep 17 00:00:00 2001 From: Emden Gansner Date: Thu, 1 Mar 2012 13:31:42 -0500 Subject: [PATCH] Fix finally, it is hoped, the potential infinite loop in routespl. When recovering unused space from the boxes, we try to find the smallest and largest x values of the spline in the box and reduce the box to that size. This is done by subdividing the spline into small pieces and using the end points. If the box is small in height, it is possible none of the points will lie in the box. To handle this, if any box is still unbounded, the spline is divided into smaller pieces and we try again. Alas, some times the path planner just fails, with the spline not passing through some boxes. In this case, the loop will never stop. So we now do some reasonable number of passes (initially, 15). If this isn't enough, we use the shortest path polyline to bound the boxes. This will allow the layout to finish. The bad spline will be emitted, but this should be obvious and, in any case, will help with debugging. --- lib/common/routespl.c | 120 +++++++++++++++++++++++++++--------------- 1 file changed, 77 insertions(+), 43 deletions(-) diff --git a/lib/common/routespl.c b/lib/common/routespl.c index 5b171bf12..055bddd9e 100644 --- a/lib/common/routespl.c +++ b/lib/common/routespl.c @@ -324,6 +324,51 @@ void routesplinesterm() nedges, nboxes, elapsed_sec()); } +static void +limitBoxes (boxf* boxes, int boxn, pointf *pps, int pn, int delta) +{ + int bi, si, splinepi; + double t; + pointf sp[4]; + int num_div = delta * boxn; + + for (splinepi = 0; splinepi + 3 < pn; splinepi += 3) { + for (si = 0; si <= num_div; si++) { + t = si / (double)num_div; + sp[0] = pps[splinepi]; + sp[1] = pps[splinepi + 1]; + sp[2] = pps[splinepi + 2]; + sp[3] = pps[splinepi + 3]; + sp[0].x = sp[0].x + t * (sp[1].x - sp[0].x); + sp[0].y = sp[0].y + t * (sp[1].y - sp[0].y); + sp[1].x = sp[1].x + t * (sp[2].x - sp[1].x); + sp[1].y = sp[1].y + t * (sp[2].y - sp[1].y); + sp[2].x = sp[2].x + t * (sp[3].x - sp[2].x); + sp[2].y = sp[2].y + t * (sp[3].y - sp[2].y); + sp[0].x = sp[0].x + t * (sp[1].x - sp[0].x); + sp[0].y = sp[0].y + t * (sp[1].y - sp[0].y); + sp[1].x = sp[1].x + t * (sp[2].x - sp[1].x); + sp[1].y = sp[1].y + t * (sp[2].y - sp[1].y); + sp[0].x = sp[0].x + t * (sp[1].x - sp[0].x); + sp[0].y = sp[0].y + t * (sp[1].y - sp[0].y); + for (bi = 0; bi < boxn; bi++) { +/* this tested ok on 64bit machines, but on 32bit we need this FUDGE + * or graphs/directed/records.gv fails */ +#define FUDGE .0001 + if (sp[0].y <= boxes[bi].UR.y+FUDGE && sp[0].y >= boxes[bi].LL.y-FUDGE) { + if (boxes[bi].LL.x > sp[0].x) + boxes[bi].LL.x = sp[0].x; + if (boxes[bi].UR.x < sp[0].x) + boxes[bi].UR.x = sp[0].x; + } + } + } + } +} + +#define INIT_DELTA 10 +#define LOOP_TRIES 15 /* number of times to try to limiting boxes to regain space, using smaller divisions */ + static pointf *_routesplines(path * pp, int *npoints, int polyline) { Ppoly_t poly; @@ -332,14 +377,13 @@ static pointf *_routesplines(path * pp, int *npoints, int polyline) Ppoint_t eps[2]; Pvector_t evs[2]; int edgei, prev, next; - pointf sp[4]; - int pi, bi, si; - double t; + int pi, bi; boxf *boxes; int boxn; edge_t* realedge; int flip; - int delta = 10; + int loopcnt, delta = INIT_DELTA; + boolean unbounded; nedges++; nboxes += pp->nbox; @@ -529,61 +573,51 @@ static pointf *_routesplines(path * pp, int *npoints, int polyline) #endif } if (mkspacep(spl.pn)) - longjmp (jbuf, 1); + longjmp (jbuf, 1); /* Bailout if no memory left */ + for (bi = 0; bi < boxn; bi++) { boxes[bi].LL.x = INT_MAX; boxes[bi].UR.x = INT_MIN; } + unbounded = TRUE; for (splinepi = 0; splinepi < spl.pn; splinepi++) { ps[splinepi] = spl.ps[splinepi]; } -REDO: - for (splinepi = 0; splinepi + 3 < spl.pn; splinepi += 3) { - int num_div = delta * boxn; - for (si = 0; si <= num_div; si++) { - t = si / (double)num_div; - sp[0] = ps[splinepi]; - sp[1] = ps[splinepi + 1]; - sp[2] = ps[splinepi + 2]; - sp[3] = ps[splinepi + 3]; - sp[0].x = sp[0].x + t * (sp[1].x - sp[0].x); - sp[0].y = sp[0].y + t * (sp[1].y - sp[0].y); - sp[1].x = sp[1].x + t * (sp[2].x - sp[1].x); - sp[1].y = sp[1].y + t * (sp[2].y - sp[1].y); - sp[2].x = sp[2].x + t * (sp[3].x - sp[2].x); - sp[2].y = sp[2].y + t * (sp[3].y - sp[2].y); - sp[0].x = sp[0].x + t * (sp[1].x - sp[0].x); - sp[0].y = sp[0].y + t * (sp[1].y - sp[0].y); - sp[1].x = sp[1].x + t * (sp[2].x - sp[1].x); - sp[1].y = sp[1].y + t * (sp[2].y - sp[1].y); - sp[0].x = sp[0].x + t * (sp[1].x - sp[0].x); - sp[0].y = sp[0].y + t * (sp[1].y - sp[0].y); - for (bi = 0; bi < boxn; bi++) { -/* this tested ok on 64bit machines, but on 32bit we need this FUDGE - * or graphs/directed/records.gv fails */ -#define FUDGE .0001 - if (sp[0].y <= boxes[bi].UR.y+FUDGE && sp[0].y >= boxes[bi].LL.y-FUDGE) { - if (boxes[bi].LL.x > sp[0].x) - boxes[bi].LL.x = sp[0].x; - if (boxes[bi].UR.x < sp[0].x) - boxes[bi].UR.x = sp[0].x; - } - } - } - } + + for (loopcnt = 0; unbounded && (loopcnt < LOOP_TRIES); loopcnt++) { + limitBoxes (boxes, boxn, ps, spl.pn, delta); + /* The following check is necessary because if a box is not very * high, it is possible that the sampling above might miss it. * Therefore, we make the sample finer until all boxes have * valid values. cf. bug 456. Would making sp[] pointfs help? */ - for (bi = 0; bi < boxn; bi++) { + for (bi = 0; bi < boxn; bi++) { /* these fp equality tests are used only to detect if the * values have been changed since initialization - ok */ - if ((boxes[bi].LL.x == INT_MAX) || (boxes[bi].UR.x == INT_MIN)) { - delta *= 2; - goto REDO; + if ((boxes[bi].LL.x == INT_MAX) || (boxes[bi].UR.x == INT_MIN)) { + delta *= 2; /* try again with a finer interval */ + if (delta > INT_MAX/boxn) /* in limitBoxes, boxn*delta must fit in an int, so give up */ + loopcnt = LOOP_TRIES; + break; + } } + if (bi == boxn) + unbounded = FALSE; + } + if (unbounded) { + /* Either an extremely short, even degenerate, box, or some failure with the path + * planner causing the spline to miss some boxes. In any case, use the shortest path + * to bound the boxes. This will probably mean a bad edge, but we avoid an infinite + * loop and we can see the bad edge, and even use the showboxes scaffolding. + */ + Ppolyline_t polyspl; + agerr(AGWARN, "Unable to reclaim box space in spline routing. Something is probably seriously wrong.\n"); + make_polyline (pl, &polyspl); + limitBoxes (boxes, boxn, polyspl.ps, polyspl.pn, INIT_DELTA); + free (polyspl.ps); } + *npoints = spl.pn; #ifdef DEBUG -- 2.40.0