#pragma prototyped
/*
* Copyright (c) AT&T Corp. 1994, 1995.
* This code is licensed by AT&T Corp. For the
* terms and conditions of the license, see
* http://www.research.att.com/orgs/ssr/book/reuse
*/
#include "dot.h"
#include "pathplan.h"
/* some of the following must be dispensible, see constants.h */
#ifndef INT_MAX
#define INT_MAX MAXINT
#define INT_MIN (-INT_MAX-1)
#endif
static box *bs = NULL;
#ifdef UNUSED
static int bn;
static int maxbn = 0;
#endif
#define BINC 300
static point *ps = NULL;
static int pn;
static int maxpn = 0;
#define PINC 300
static box *boxes;
static int boxn;
static box minbbox;
static edge_t *origedge, *realedge;
static path *thepath;
static int nedges, nboxes, nsplines;
static Ppoint_t *polypoints;
static int polypointn, polysz;
static Pedge_t *edges;
static int edgen;
static void checkpath (void);
static void mkspacep (int size);
static void printpath (path* pp);
static void printpsboxes (void);
#if DEBUG
static void printpspath (void);
#endif
static void append(path *path, int bi, point p0, point p1);
static point mkpt(int x, int y) {
point rv;
rv.x = x; rv.y = y;
return rv;
}
static int pteq(point p, point q) {
return ((p.x == q.x) && (p.y == q.y));
}
void routesplinesinit (void)
{
if (!(bs = N_GNEW (BINC,box))) {
agerr(AGERR, "cannot allocate bs\n");
abort ();
}
#ifdef UNUSED
maxbn = BINC;
#endif
if (!(ps = N_GNEW (PINC,point))) {
agerr(AGERR, "cannot allocate ps\n");
abort ();
}
maxpn = PINC;
minbbox.LL.x = minbbox.LL.y = INT_MAX;
minbbox.UR.x = minbbox.UR.y = INT_MIN;
Show_boxes = FALSE;
if (Verbose) start_timer();
}
void routesplinesterm (void)
{
free (ps), ps = NULL, maxpn = pn = 0;
free (bs), bs = NULL /*, maxbn = bn = 0 */;
if (Verbose)
fprintf (stderr, "routesplines: %d edges, %d boxes, %d splines %.2f sec\n",
nedges, nboxes, nsplines,elapsed_sec());
}
point *routesplines (path* pp, int* npoints)
{
Ppoly_t poly;
Ppolyline_t pl, spl;
int splinepi;
Ppoint_t eps[2];
Pvector_t evs[2];
int edgei, prev, next;
point sp[4];
int pi, bi, si;
double t;
nedges++;
nboxes += pp->nbox;
for (realedge = origedge = (edge_t *) pp->data;
realedge && ED_edge_type(realedge) != NORMAL; realedge = ED_to_orig(realedge))
;
if (!realedge) {
agerr(AGERR, "in routesplines, cannot find NORMAL edge\n");
abort ();
}
thepath = pp;
boxes = pp->boxes;
boxn = pp->nbox;
checkpath ();
if (GD_showboxes(realedge->head->graph) == 1 ||
GD_showboxes(realedge->tail->graph) == 1 ||
ED_showboxes(realedge) == 1 ||
ND_showboxes(realedge->head) == 1||
ND_showboxes(realedge->tail) == 1)
printpsboxes ();
if (boxn * 8 > polypointn) {
polypoints = ALLOC (boxn*8, polypoints, Ppoint_t);
polypointn = pp->nbox * 8;
}
if (realedge->tail != realedge->head) {
/* I assume that the path goes either down only or
up - right - down */
for (bi = 0, pi = 0; bi < boxn; bi++) {
next = prev = 0;
if (bi > 0)
prev = (boxes[bi].LL.y > boxes[bi - 1].LL.y) ? -1 : 1;
if (bi < boxn - 1)
next = (boxes[bi + 1].LL.y > boxes[bi].LL.y) ? 1 : -1;
if (prev != next) {
if (next == -1 || prev == 1) {
polypoints[pi].x = boxes[bi].LL.x;
polypoints[pi++].y = boxes[bi].UR.y;
polypoints[pi].x = boxes[bi].LL.x;
polypoints[pi++].y = boxes[bi].LL.y;
} else {
polypoints[pi].x = boxes[bi].UR.x;
polypoints[pi++].y = boxes[bi].LL.y;
polypoints[pi].x = boxes[bi].UR.x;
polypoints[pi++].y = boxes[bi].UR.y;
}
} else {
if (!(prev == -1 && next == -1))
abort ();
}
}
for (bi = boxn - 1; bi >= 0; bi--) {
next = prev = 0;
if (bi < boxn - 1)
prev = (boxes[bi].LL.y > boxes[bi + 1].LL.y) ? -1 : 1;
if (bi > 0)
next = (boxes[bi - 1].LL.y > boxes[bi].LL.y) ? 1 : -1;
if (prev != next) {
if (next == -1 || prev == 1) {
polypoints[pi].x = boxes[bi].LL.x;
polypoints[pi++].y = boxes[bi].UR.y;
polypoints[pi].x = boxes[bi].LL.x;
polypoints[pi++].y = boxes[bi].LL.y;
} else {
polypoints[pi].x = boxes[bi].UR.x;
polypoints[pi++].y = boxes[bi].LL.y;
polypoints[pi].x = boxes[bi].UR.x;
polypoints[pi++].y = boxes[bi].UR.y;
}
} else {
if (!(prev == -1 && next == -1)) {
/* it went badly, e.g. degenerate box in boxlist */
*npoints = 0;
abort (); /* for correctness sake, it's best to just stop */
return ps; /* could also be reported as a lost edge (no spline) */
}
polypoints[pi].x = boxes[bi].UR.x;
polypoints[pi++].y = boxes[bi].LL.y;
polypoints[pi].x = boxes[bi].UR.x;
polypoints[pi++].y = boxes[bi].UR.y;
polypoints[pi].x = boxes[bi].LL.x;
polypoints[pi++].y = boxes[bi].UR.y;
polypoints[pi].x = boxes[bi].LL.x;
polypoints[pi++].y = boxes[bi].LL.y;
}
}
}
else {
/* new, more generalized approach for self-edges. We do not
assume any monotonicity about the box path, only that it
is simply connected. We build up the constraint poly by
walking the box path from one end to the other and back
in the recursive function append(). A better approach to all
of this might be to dispense with the box paths altogether
and just compute the constraint poly directly, but this
needs to be done as part of a more thorough overhaul. */
point p0, p1;
box b0,b1;
b0 = pp->boxes[0]; b1 = pp->boxes[1];
/* determine 'starting' segment (side of b0) for box path search */
if (b0.UR.x == b1.LL.x) {p0 = b0.LL; p1 = mkpt(b0.LL.x,b0.UR.y);}
else if (b0.LL.y == b1.UR.y) {p0 = mkpt(b0.LL.x,b0.UR.y); p1 = b0.UR;}
else if (b0.LL.x == b1.UR.x) {p0 = b0.UR; p1 = mkpt(b0.UR.x,b0.LL.y);}
else if (b0.UR.y == b1.LL.y) {p0 = mkpt(b0.UR.x,b0.LL.y); p1 = b0.LL;}
else abort();
polysz = 0;
append(pp,0,p0,p1);
pi = polysz;
}
for (bi = 0; bi < boxn; bi++)
boxes[bi].LL.x = INT_MAX, boxes[bi].UR.x = INT_MIN;
poly.ps = polypoints, poly.pn = pi;
eps[0].x = pp->start.p.x, eps[0].y = pp->start.p.y;
eps[1].x = pp->end.p.x, eps[1].y = pp->end.p.y;
if (Pshortestpath (&poly, eps, &pl) == -1)
abort ();
if (poly.pn > edgen) {
edges = ALLOC (poly.pn, edges, Pedge_t);
edgen = poly.pn;
}
for (edgei = 0; edgei < poly.pn; edgei++) {
edges[edgei].a = polypoints[edgei];
edges[edgei].b = polypoints[(edgei + 1) % poly.pn];
}
if (pp->start.constrained) {
evs[0].x = cos (pp->start.theta);
evs[0].y = sin (pp->start.theta);
} else
evs[0].x = evs[0].y = 0;
if (pp->end.constrained) {
evs[1].x = -cos (pp->end.theta);
evs[1].y = -sin (pp->end.theta);
} else
evs[1].x = evs[1].y = 0;
if (Proutespline (edges, poly.pn, pl, evs, &spl) == -1)
abort ();
mkspacep (spl.pn);
for (bi = 0; bi <= boxn; bi++)
boxes[bi].LL.x = minbbox.LL.x, boxes[bi].UR.x = minbbox.UR.x;
for (splinepi = 0; splinepi < spl.pn; splinepi++) {
ps[splinepi].x = spl.ps[splinepi].x;
ps[splinepi].y = spl.ps[splinepi].y;
}
for (splinepi = 0; splinepi + 3 < spl.pn; splinepi += 3) {
for (si = 0; si <= 10 * boxn; si++) {
t = si / (10.0 * boxn);
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++) {
if (sp[0].y <= boxes[bi].UR.y && sp[0].y >= boxes[bi].LL.y) {
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;
}
}
}
}
*npoints = spl.pn;
if (GD_showboxes(realedge->head->graph) == 2 ||
GD_showboxes(realedge->tail->graph) == 2 ||
ED_showboxes(realedge) == 2 ||
ND_showboxes(realedge->head) == 2||
ND_showboxes(realedge->tail) == 2)
printpsboxes ();
return ps;
}
static void checkpath (void)
{
box *ba, *bb;
int bi, i, errs, l, r, d, u;
#ifndef DONTFIXPATH
/* remove degenerate boxes. */
i = 0;
for (bi = 0; bi < boxn; bi++) {
if (boxes[bi].LL.y == boxes[bi].UR.y) continue;
if (i != bi) boxes[i] = boxes[bi];
i++;
}
boxn = i;
#endif /* DONTFIXPATH */
ba = &boxes[0];
if (ba->LL.x > ba->UR.x || ba->LL.y > ba->UR.y) {
agerr(AGERR, "in checkpath, box 0 has LL coord > UR coord\n");
printpath (thepath);
abort ();
}
for (bi = 0; bi < boxn - 1; bi++) {
ba = &boxes[bi], bb = &boxes[bi + 1];
if (bb->LL.x > bb->UR.x || bb->LL.y > bb->UR.y) {
agerr(AGERR, "in checkpath, box %d has LL coord > UR coord\n", bi + 1);
printpath (thepath);
abort ();
}
l = (ba->UR.x < bb->LL.x) ? 1 : 0;
r = (ba->LL.x > bb->UR.x) ? 1 : 0;
d = (ba->UR.y < bb->LL.y) ? 1 : 0;
u = (ba->LL.y > bb->UR.y) ? 1 : 0;
errs = l + r + d + u;
if (errs > 0 && Verbose) {
fprintf (stderr, "in checkpath, boxes %d and %d don't touch\n", bi, bi + 1);
printpath (thepath);
}
#ifndef DONTFIXPATH
if (errs > 0) {
int xy;
if (l == 1)
xy = ba->UR.x, ba->UR.x = bb->LL.x, bb->LL.x = xy, l = 0;
else if (r == 1)
xy = ba->LL.x, ba->LL.x = bb->UR.x, bb->UR.x = xy, r = 0;
else if (d == 1)
xy = ba->UR.y, ba->UR.y = bb->LL.y, bb->LL.y = xy, d = 0;
else if (u == 1)
xy = ba->LL.y, ba->LL.y = bb->UR.y, bb->UR.y = xy, u = 0;
for (i = 0; i < errs - 1; i++) {
if (l == 1)
xy = (ba->UR.x + bb->LL.x) / 2.0 + 0.5, ba->UR.x = bb->LL.x = xy, l = 0;
else if (r == 1)
xy = (ba->LL.x + bb->UR.x) / 2.0 + 0.5, ba->LL.x = bb->UR.x = xy, r = 0;
else if (d == 1)
xy = (ba->UR.y + bb->LL.y) / 2.0 + 0.5, ba->UR.y = bb->LL.y = xy, d = 0;
else if (u == 1)
xy = (ba->LL.y + bb->UR.y) / 2.0 + 0.5, ba->LL.y = bb->UR.y = xy, u = 0;
}
}
#else
abort ();
#endif
}
if (thepath->start.p.x < boxes[0].LL.x || thepath->start.p.x > boxes[0].UR.x ||
thepath->start.p.y < boxes[0].LL.y || thepath->start.p.y > boxes[0].UR.y) {
if (Verbose) {
fprintf (stderr, "in checkpath, start port not in first box\n");
printpath (thepath);
}
#ifndef DONTFIXPATH
if (thepath->start.p.x < boxes[0].LL.x)
thepath->start.p.x = boxes[0].LL.x;
if (thepath->start.p.x > boxes[0].UR.x)
thepath->start.p.x = boxes[0].UR.x;
if (thepath->start.p.y < boxes[0].LL.y)
thepath->start.p.y = boxes[0].LL.y;
if (thepath->start.p.y > boxes[0].UR.y)
thepath->start.p.y = boxes[0].UR.y;
#else
abort ();
#endif
}
if (thepath->end.p.x < boxes[boxn - 1].LL.x || thepath->end.p.x > boxes[boxn - 1].UR.x ||
thepath->end.p.y < boxes[boxn - 1].LL.y || thepath->end.p.y > boxes[boxn - 1].UR.y) {
if (Verbose) {
fprintf (stderr, "in checkpath, end port not in last box\n");
printpath (thepath);
}
#ifndef DONTFIXPATH
if (thepath->end.p.x < boxes[boxn - 1].LL.x)
thepath->end.p.x = boxes[boxn - 1].LL.x;
if (thepath->end.p.x > boxes[boxn - 1].UR.x)
thepath->end.p.x = boxes[boxn - 1].UR.x;
if (thepath->end.p.y < boxes[boxn - 1].LL.y)
thepath->end.p.y = boxes[boxn - 1].LL.y;
if (thepath->end.p.y > boxes[boxn - 1].UR.y)
thepath->end.p.y = boxes[boxn - 1].UR.y;
#else
abort ();
#endif
}
}
static void mkspacep (int size)
{
if (pn + size > maxpn) {
int newmax = maxpn + (size / PINC + 1) * PINC;
ps = RALLOC (newmax, ps, point);
maxpn = newmax;
}
}
static void printpath (path* pp)
{
int bi;
fprintf (stderr, "edge %d from %s to %s\n", nedges, realedge->tail->name, realedge->head->name);
if (ED_count(origedge) > 1)
fprintf (stderr, " (it's part of a concentrator edge)\n");
fprintf (stderr, "%d boxes:\n", pp->nbox);
for (bi = 0; bi < pp->nbox; bi++)
fprintf (stderr, "%d (%d, %d), (%d, %d)\n", bi, pp->boxes[bi].LL.x, pp->boxes[bi].LL.y,
pp->boxes[bi].UR.x, pp->boxes[bi].UR.y);
fprintf (stderr, "start port: (%d, %d), tangent angle: %.3f, %s\n",
pp->start.p.x, pp->start.p.y, pp->start.theta,
pp->start.constrained ? "constrained" : "not constrained");
fprintf (stderr, "end port: (%d, %d), tangent angle: %.3f, %s\n",
pp->end.p.x, pp->end.p.y, pp->end.theta,
pp->end.constrained ? "constrained" : "not constrained");
}
static void printpsboxes (void)
{
point ll, ur;
int bi;
Show_boxes = TRUE;
for (bi = 0; bi < boxn; bi++) {
ll = boxes[bi].LL, ur = boxes[bi].UR;
fprintf (stderr, "%d %d %d %d pathbox\n", ll.x, ll.y, ur.x, ur.y);
}
}
#if DEBUG
static void printpspath (void)
{
int i;
fprintf(stderr,"%% constraint poly \n");
fprintf(stderr,"newpath %f %f moveto ",polypoints[0].x,polypoints[0].y);
for (i = 1; i < polysz; i++)
fprintf(stderr," %f %f lineto ",polypoints[i].x,polypoints[i].y);
fprintf(stderr,"closepath stroke\n");
}
#endif
/* new code to create poly from box list */
/* given that we entered the box b on segment p0,p1
(p0==p1 allowed) then add successive points to the constraint poly
*/
#define BOXLEFT 0
#define BOXTOP 1
#define BOXRIGHT 2
#define BOXBOTTOM 3
static box B;
static int sideofB(point p, box B)
{
if (p.x == B.LL.x) return BOXLEFT;
if (p.y == B.UR.y) return BOXTOP;
if (p.x == B.UR.x) return BOXRIGHT;
if (p.y == B.LL.y) return BOXBOTTOM;
abort();
return 0;
}
static void appendpt(point p)
{
polypoints[polysz].x = p.x;
polypoints[polysz].y = p.y;
polysz++;
}
static int cmpf(const void *pp0, const void *pp1)
{
point p0,p1;
int s0,s1;
p0 = *(point*)pp0;
p1 = *(point*)pp1;
s0 = sideofB(p0,B);
s1 = sideofB(p1,B);
if (s0 != s1) return s1 - s0;
switch (s0) {
case BOXLEFT: return p1.y - p0.y;
case BOXTOP: return p1.x - p0.x;
case BOXRIGHT:return p0.y - p1.y;
case BOXBOTTOM:return p0.x - p1.x;
default: abort();
}
return 0; /* not reached */
}
void
append(path *path, int bi, point p0, point p1)
{
point v[8]; /* worse case 4 corners + 2 segs * 2 points each */
point w[8];
box b = path->boxes[bi];
box bb;
int i,i0,npw,delta;
point q0,q1,r;
/* v = 4 corners of b, p0 and p1 */
pn = 0;
v[pn++] = b.LL;
v[pn++] = mkpt(b.UR.x,b.LL.y);
v[pn++] = b.UR;
v[pn++] = mkpt(b.LL.x,b.UR.y);
v[pn++] = p0;
v[pn++] = p1;
if (bi + 1 < path->nbox) {
bb = path->boxes[bi+1];
/* determine points q0,q1 where b and bb touch and append to v */
if (b.UR.x == bb.LL.x) {
q0.x = q1.x = b.UR.x;
q0.y = MIN(b.UR.y,bb.UR.y);
q1.y = MAX(b.LL.y,bb.LL.y);
}
else if (b.LL.x == bb.UR.x) {
q0.x = q1.x = b.LL.x;
q0.y = MIN(b.UR.y,bb.UR.y);
q1.y = MAX(b.LL.y,bb.LL.y);
}
else if (b.UR.y == bb.LL.y) {
q0.y = q1.y = b.UR.y;
q0.x = MIN(b.UR.x,bb.UR.x);
q1.x = MAX(b.LL.x,bb.LL.x);
}
else if (b.LL.y == bb.UR.y) {
q0.y = q1.y = b.LL.y;
q0.x = MIN(b.UR.x,bb.UR.x);
q1.x = MAX(b.LL.x,bb.LL.x);
}
else abort();
v[pn++] = q0;
v[pn++] = q1;
}
/* sort v so that the cyclic order is p0, all other points, p1 */
B = b;
qsort(v,pn,sizeof(v[0]),cmpf);
/* eliminate duplicates and record i0 = index of p0 in w */
w[0] = v[0]; npw = 1; i0 = -1;
for (i = 0; i < pn; i++) {
if (pteq(w[npw-1],p0)) i0 = npw-1;
if (!pteq(v[i],w[npw-1])) w[npw++] = v[i];
}
i = i0;
if (bi == 0) appendpt(p0);
if (pteq(p1,w[(i0+1)%npw])) delta = -1;
else if (pteq(p1,w[(i0-1+npw)%npw])) delta = 1;
else abort();
do {
i = (i + delta + npw) % npw; /* go to the next point in order */
r = w[i]; /* call it r */
/* append r to current poly, except p0 and p1 are special cases */
if ((bi == 0) || (!pteq(r,p0) && !pteq(r,p1))) appendpt(r);
if (pteq(r,p1)) break;
if (bi + 1 < path->nbox) { /* recur when we hit the next box */
if (pteq(r,q0)) {
append(path,bi+1,q0,q1);
appendpt(q1); /* assumes q1 != p0 and p1 */
i+=delta; /* skip q1 */
}
else if (pteq(r,q1)) {
append(path,bi+1,q1,q0);
appendpt(q0);
i+=delta;
}
}
} while (i != i0);
}
|
