From b5e66c5e6adbe1f6d2adc9d5fe7ed26b66fb1bcc Mon Sep 17 00:00:00 2001 From: mjwybrow Date: Fri, 14 Jul 2006 05:30:15 +0000 Subject: [PATCH] * src/sp-conn-end-pair.cpp, src/connector-context.cpp, src/document.cpp, src/libavoid/*: Update libavoid with upstream fixes, optimisations and new features. --- ChangeLog | 8 +- src/connector-context.cpp | 4 +- src/document.cpp | 2 + src/libavoid/connector.cpp | 58 ++++++++- src/libavoid/connector.h | 6 + src/libavoid/geometry.cpp | 247 +++++++++++++++++++++++++++++++++++- src/libavoid/geometry.h | 33 +++++ src/libavoid/geomtypes.h | 16 ++- src/libavoid/graph.cpp | 2 + src/libavoid/graph.h | 5 +- src/libavoid/makepath.cpp | 193 +++++++++++++++++++++++++--- src/libavoid/router.cpp | 184 +++++++++++++++++++++------ src/libavoid/router.h | 8 +- src/libavoid/shape.cpp | 72 +++++++++-- src/libavoid/shape.h | 5 + src/libavoid/static.cpp | 4 +- src/libavoid/vertices.cpp | 10 +- src/libavoid/vertices.h | 1 + src/libavoid/visibility.cpp | 12 +- src/sp-conn-end-pair.cpp | 8 +- 20 files changed, 781 insertions(+), 97 deletions(-) diff --git a/ChangeLog b/ChangeLog index 3e7651fa1..615203404 100644 --- a/ChangeLog +++ b/ChangeLog @@ -1,4 +1,10 @@ -2006-07-13 Tim Dwyer +2006-07-13 Michael Wybrow + + * src/sp-conn-end-pair.cpp, src/connector-context.cpp, + src/document.cpp, src/libavoid/*: + Update libavoid with upstream fixes, optimisations and new features. + +2006-07-13 Tim Dwyer * src/libvpsc/*, src/graphlayout/graphlayout.cpp: diff --git a/src/connector-context.cpp b/src/connector-context.cpp index bb0c8e740..e38f8a627 100644 --- a/src/connector-context.cpp +++ b/src/connector-context.cpp @@ -794,8 +794,8 @@ spcc_connector_set_subsequent_point(SPConnectorContext *const cc, NR::Point cons SPDesktop *dt = cc->desktop; NR::Point o = dt->dt2doc(cc->p[0]); NR::Point d = dt->dt2doc(p); - Avoid::Point src = { o[NR::X], o[NR::Y] }; - Avoid::Point dst = { d[NR::X], d[NR::Y] }; + Avoid::Point src(o[NR::X], o[NR::Y]); + Avoid::Point dst(d[NR::X], d[NR::Y]); if (!cc->newConnRef) { Avoid::Router *router = sp_desktop_document(dt)->router; diff --git a/src/document.cpp b/src/document.cpp index 69f9128a8..534ad412d 100644 --- a/src/document.cpp +++ b/src/document.cpp @@ -91,6 +91,8 @@ SPDocument::SPDocument() { // Initialise instance of connector router. router = new Avoid::Router(); + // Don't use the Consolidate moves optimisation. + router->ConsolidateMoves = false; p = new SPDocumentPrivate(); diff --git a/src/libavoid/connector.cpp b/src/libavoid/connector.cpp index a9f144688..3526b3f15 100644 --- a/src/libavoid/connector.cpp +++ b/src/libavoid/connector.cpp @@ -46,6 +46,7 @@ ConnRef::ConnRef(Router *router, const unsigned int id) , _initialised(false) , _callback(NULL) , _connector(NULL) + , _hateCrossings(false) { // TODO: Store endpoints and details. _route.pn = 0; @@ -69,6 +70,7 @@ ConnRef::ConnRef(Router *router, const unsigned int id, , _initialised(false) , _callback(NULL) , _connector(NULL) + , _hateCrossings(false) { _route.pn = 0; _route.ps = NULL; @@ -121,7 +123,9 @@ void ConnRef::updateEndPoint(const unsigned int type, const Point& point) { assert((type == (unsigned int) VertID::src) || (type == (unsigned int) VertID::tar)); - //assert(IncludeEndpoints); + + // XXX: This was commented out. Is there a case where it isn't true? + assert(_router->IncludeEndpoints); if (!_initialised) { @@ -163,8 +167,11 @@ void ConnRef::updateEndPoint(const unsigned int type, const Point& point) altered = _dstVert; partner = _srcVert; } - - bool knownNew = false; + + // XXX: Seems to be faster to just remove the edges and recreate + bool isConn = true; + altered->removeFromGraph(isConn); + bool knownNew = true; vertexVisibility(altered, partner, knownNew, true); } @@ -182,6 +189,18 @@ void ConnRef::setEndPointId(const unsigned int type, const unsigned int id) } +unsigned int ConnRef::getSrcShapeId(void) +{ + return _srcId; +} + + +unsigned int ConnRef::getDstShapeId(void) +{ + return _dstId; +} + + void ConnRef::makeActive(void) { assert(!_active); @@ -249,6 +268,12 @@ void ConnRef::lateSetup(const Point& src, const Point& dst) } +unsigned int ConnRef::id(void) +{ + return _id; +} + + VertInf *ConnRef::src(void) { return _srcVert; @@ -355,8 +380,9 @@ int ConnRef::generatePath(Point p0, Point p1) tar = _dstVert; bool knownNew = true; - vertexVisibility(src, tar, knownNew); - vertexVisibility(tar, src, knownNew); + bool genContains = true; + vertexVisibility(src, tar, knownNew, genContains); + vertexVisibility(tar, src, knownNew, genContains); } bool *flag = &(_needs_reroute_flag); @@ -405,7 +431,9 @@ int ConnRef::generatePath(Point p0, Point p1) { _false_path = true; } - path[j--] = i->point; + path[j] = i->point; + path[j].id = i->id.objID; + j--; } path[0] = src->point; @@ -415,11 +443,29 @@ int ConnRef::generatePath(Point p0, Point p1) PolyLine& output_route = route(); output_route.pn = pathlen; output_route.ps = path; + + if ( !(_router->IncludeEndpoints) ) + { + assert(_initialised); + unInitialise(); + } return (int) result; } +void ConnRef::setHateCrossings(bool value) +{ + _hateCrossings = value; +} + + +bool ConnRef::doesHateCrossings(void) +{ + return _hateCrossings; +} + + //============================================================================ } diff --git a/src/libavoid/connector.h b/src/libavoid/connector.h index 0ec5890a1..a313e3bb4 100644 --- a/src/libavoid/connector.h +++ b/src/libavoid/connector.h @@ -51,9 +51,12 @@ class ConnRef void calcRouteDist(void); void updateEndPoint(const unsigned int type, const Point& point); void setEndPointId(const unsigned int type, const unsigned int id); + unsigned int getSrcShapeId(void); + unsigned int getDstShapeId(void); void makeActive(void); void makeInactive(void); void lateSetup(const Point& src, const Point& dst); + unsigned int id(void); VertInf *src(void); VertInf *dst(void); void removeFromGraph(void); @@ -64,6 +67,8 @@ class ConnRef int generatePath(Point p0, Point p1); void makePathInvalid(void); Router *router(void); + void setHateCrossings(bool value); + bool doesHateCrossings(void); friend void Router::attachedShapes(IntList &shapes, const unsigned int shapeId, const unsigned int type); @@ -87,6 +92,7 @@ class ConnRef bool _initialised; void (*_callback)(void *); void *_connector; + bool _hateCrossings; }; diff --git a/src/libavoid/geometry.cpp b/src/libavoid/geometry.cpp index 20f045231..8f58d4481 100644 --- a/src/libavoid/geometry.cpp +++ b/src/libavoid/geometry.cpp @@ -9,6 +9,10 @@ * and/or described in "Computational Geometry in C" (Second Edition), * Copyright (C) 1998 Joseph O'Rourke * -------------------------------------------------------------------- + * The segmentIntersectPoint function is based on code published and + * described in Franklin Antonio, Faster Line Segment Intersection, + * Graphics Gems III, p. 199-202, code: p. 500-501. + * -------------------------------------------------------------------- * * This library is free software; you can redistribute it and/or * modify it under the terms of the GNU Lesser General Public @@ -35,6 +39,38 @@ namespace Avoid { +Point::Point() +{ +} + + +Point::Point(const double xv, const double yv) + : x(xv) + , y(yv) +{ +} + + +bool Point::operator==(const Point& rhs) const +{ + if ((x == rhs.x) && (y == rhs.y)) + { + return true; + } + return false; +} + + +bool Point::operator!=(const Point& rhs) const +{ + if ((x != rhs.x) || (y != rhs.y)) + { + return true; + } + return false; +} + + // Returns true iff the point c lies on the closed segment ab. // // Based on the code of 'Between'. @@ -89,7 +125,7 @@ bool segmentIntersect(const Point& a, const Point& b, const Point& c, // and c and d are on opposite sides of the line ab. // // Note: this is safe even though the textbook warns about it - // since, unlike them, out vecDir is equivilent to 'AreaSign' + // since, unlike them, our vecDir is equivilent to 'AreaSign' // rather than 'Area2'. return (((ab_c * ab_d) < 0) && ((cd_a * cd_b) < 0)); } @@ -153,6 +189,55 @@ bool inValidRegion(bool IgnoreRegions, const Point& a0, const Point& a1, } +// Gives the side of a corner that a point lies on: +// 1 anticlockwise +// -1 clockwise +// e.g. /| +// /s2 -1 / |s1 +// / / | +// 1 |s1 -1 / 1 | -1 +// | / | +// |s0 s2/ |s0 +// +int cornerSide(const Point &c1, const Point &c2, const Point &c3, + const Point& p) +{ + int s123 = vecDir(c1, c2, c3); + int s12p = vecDir(c1, c2, p); + int s23p = vecDir(c2, c3, p); + + if (s12p == 0) + { + // Case of p being somewhere on c1-c2. + return s23p; + } + if (s23p == 0) + { + // Case of p being somewhere on c2-c3. + return s12p; + } + + if (s123 == 1) + { + if ((s12p == 1) && (s23p == 1)) + { + return 1; + } + return -1; + } + else if (s123 == -1) + { + if ((s12p == -1) && (s23p == -1)) + { + return -1; + } + return 1; + } + // Case of c3 being somewhere on c1-c2. + return s12p; +} + + // Returns the distance between points a and b. // double dist(const Point& a, const Point& b) @@ -163,13 +248,59 @@ double dist(const Point& a, const Point& b) return sqrt((xdiff * xdiff) + (ydiff * ydiff)); } +// Returns the total length of all line segments in the polygon +double totalLength(const Polygn& poly) +{ + double l = 0; + for (int i = 0; i < poly.pn-1; ++i) { + l += dist(poly.ps[i], poly.ps[i+1]); + } + return l; +} + +// Uses the dot-product rule to find the angle (radians) between ab and bc +double angle(const Point& a, const Point& b, const Point& c) +{ + double ux = b.x - a.x, + uy = b.y - a.y, + vx = c.x - b.x, + vy = c.y - b.y, + lu = sqrt(ux*ux+uy*uy), + lv = sqrt(vx*vx+vy*vy), + udotv = ux * vx + uy * vy, + costheta = udotv / (lu * lv); + return acos(costheta); +} + +// Returns true iff the point q is inside (or on the edge of) the +// polygon argpoly. +// +// This is a fast version that only works for convex shapes. The +// other version (inPolyGen) is more general. +// +bool inPoly(const Polygn& poly, const Point& q) +{ + int n = poly.pn; + Point *P = poly.ps; + for (int i = 0; i < n; i++) + { + // point index; i1 = i-1 mod n + int prev = (i + n - 1) % n; + if (vecDir(P[prev], P[i], q) == 1) + { + return false; + } + } + return true; +} + // Returns true iff the point q is inside (or on the edge of) the // polygon argpoly. // // Based on the code of 'InPoly'. // -bool inPoly(const Polygn& argpoly, const Point& q) +bool inPolyGen(const Polygn& argpoly, const Point& q) { // Numbers of right and left edge/ray crossings. int Rcross = 0; @@ -257,5 +388,117 @@ bool inPoly(const Polygn& argpoly, const Point& q) } + +// Line Segment Intersection +// Original code by Franklin Antonio +// +// The SAME_SIGNS macro assumes arithmetic where the exclusive-or +// operation will work on sign bits. This works for twos-complement, +// and most other machine arithmetic. +#define SAME_SIGNS( a, b ) \ + (((long) ((unsigned long) a ^ (unsigned long) b)) >= 0 ) +// +int segmentIntersectPoint(const Point& a1, const Point& a2, + const Point& b1, const Point& b2, double *x, double *y) +{ + + double Ax,Bx,Cx,Ay,By,Cy,d,e,f,num,offset; + double x1lo,x1hi,y1lo,y1hi; + + Ax = a2.x - a1.x; + Bx = b1.x - b2.x; + + // X bound box test: + if (Ax < 0) + { + x1lo = a2.x; + x1hi = a1.x; + } + else + { + x1hi = a2.x; + x1lo = a1.x; + } + if (Bx > 0) + { + if (x1hi < b2.x || b1.x < x1lo) return DONT_INTERSECT; + } + else + { + if (x1hi < b1.x || b2.x < x1lo) return DONT_INTERSECT; + } + + Ay = a2.y - a1.y; + By = b1.y - b2.y; + + // Y bound box test: + if (Ay < 0) + { + y1lo = a2.y; + y1hi = a1.y; + } + else + { + y1hi = a2.y; + y1lo = a1.y; + } + if (By > 0) + { + if (y1hi < b2.y || b1.y < y1lo) return DONT_INTERSECT; + } + else + { + if (y1hi < b1.y || b2.y < y1lo) return DONT_INTERSECT; + } + + + Cx = a1.x - b1.x; + Cy = a1.y - b1.y; + // alpha numerator: + d = By*Cx - Bx*Cy; + // Both denominator: + f = Ay*Bx - Ax*By; + // aplha tests: + if (f > 0) + { + if (d < 0 || d > f) return DONT_INTERSECT; + } + else + { + if (d > 0 || d < f) return DONT_INTERSECT; + } + + // beta numerator: + e = Ax*Cy - Ay*Cx; + // beta tests: + if (f > 0) + { + if (e < 0 || e > f) return DONT_INTERSECT; + } + else + { + if (e > 0 || e < f) return DONT_INTERSECT; + } + + // compute intersection coordinates: + + if (f == 0) return PARALLEL; + + // Numerator: + num = d*Ax; + // Round direction: + offset = SAME_SIGNS(num,f) ? f/2 : -f/2; + // Intersection X: + *x = a1.x + (num+offset) / f; + + num = d*Ay; + offset = SAME_SIGNS(num,f) ? f/2 : -f/2; + // Intersection Y: + *y = a1.y + (num+offset) / f; + + return DO_INTERSECT; +} + + } diff --git a/src/libavoid/geometry.h b/src/libavoid/geometry.h index 07bfd5d33..1422be050 100644 --- a/src/libavoid/geometry.h +++ b/src/libavoid/geometry.h @@ -9,6 +9,10 @@ * and/or described in "Computational Geometry in C" (Second Edition), * Copyright (C) 1998 Joseph O'Rourke * -------------------------------------------------------------------- + * The segmentIntersectPoint function is based on code published and + * described in Franklin Antonio, Faster Line Segment Intersection, + * Graphics Gems III, p. 199-202, code: p. 500-501. + * -------------------------------------------------------------------- * * This library is free software; you can redistribute it and/or * modify it under the terms of the GNU Lesser General Public @@ -36,11 +40,16 @@ namespace Avoid { extern double dist(const Point& a, const Point& b); +extern double totalLength(const Polygn& poly); +extern double angle(const Point& a, const Point& b, const Point& c); extern bool segmentIntersect(const Point& a, const Point& b, const Point& c, const Point& d); extern bool inPoly(const Polygn& poly, const Point& q); +extern bool inPolyGen(const Polygn& poly, const Point& q); extern bool inValidRegion(bool IgnoreRegions, const Point& a0, const Point& a1, const Point& a2, const Point& b); +extern int cornerSide(const Point &c1, const Point &c2, const Point &c3, + const Point& p); // Direction from vector. @@ -68,6 +77,30 @@ static inline int vecDir(const Point& a, const Point& b, const Point& c) return 0; } +// Finds the projection point of (a,b) onto (a,c) +static inline Point projection(const Point& a, const Point& b, const Point& c) +{ + double ux = c.x - a.x, + uy = c.y - a.y, + vx = b.x - a.x, + vy = b.y - a.y, + scalarProj = ux * vx + uy * vy; + scalarProj /= ux * ux + uy * uy; + Point p; + p.x = scalarProj * ux + a.x; + p.y = scalarProj * uy + a.y; + return p; +} + +// Line Segment Intersection +// Original code by Franklin Antonio +// +static const int DONT_INTERSECT = 0; +static const int DO_INTERSECT = 1; +static const int PARALLEL = 3; +extern int segmentIntersectPoint(const Point& a1, const Point& a2, + const Point& b1, const Point& b2, double *x, double *y); + } diff --git a/src/libavoid/geomtypes.h b/src/libavoid/geomtypes.h index 53f58af81..dd9d26f2f 100644 --- a/src/libavoid/geomtypes.h +++ b/src/libavoid/geomtypes.h @@ -29,11 +29,19 @@ namespace Avoid { -typedef struct +class Point { - double x; - double y; -} Point; + public: + Point(); + Point(const double xv, const double yv); + bool operator==(const Point& rhs) const; + bool operator!=(const Point& rhs) const; + + double x; + double y; + int id; + +}; typedef Point Vector; diff --git a/src/libavoid/graph.cpp b/src/libavoid/graph.cpp index c8f061f6a..1970212df 100644 --- a/src/libavoid/graph.cpp +++ b/src/libavoid/graph.cpp @@ -31,6 +31,8 @@ #include +using std::pair; + namespace Avoid { diff --git a/src/libavoid/graph.h b/src/libavoid/graph.h index 92451f205..c4de3df08 100644 --- a/src/libavoid/graph.h +++ b/src/libavoid/graph.h @@ -27,7 +27,6 @@ #include #include #include -using std::pair; #include "libavoid/vertices.h" namespace Avoid { @@ -55,8 +54,8 @@ class EdgeInf void addCycleBlocker(void); void addBlocker(int b); - pair ids(void); - pair points(void); + std::pair ids(void); + std::pair points(void); void db_print(void); void checkVis(void); VertInf *otherVert(VertInf *vert); diff --git a/src/libavoid/makepath.cpp b/src/libavoid/makepath.cpp index 5f3ef3ac6..746e530bc 100644 --- a/src/libavoid/makepath.cpp +++ b/src/libavoid/makepath.cpp @@ -37,10 +37,6 @@ namespace Avoid { -double segmt_penalty = 0; -double angle_penalty = 0; - - static double Dot(const Point& l, const Point& r) { return (l.x * r.x) + (l.y * r.y); @@ -57,8 +53,8 @@ static double CrossLength(const Point& l, const Point& r) // static double angleBetween(const Point& p1, const Point& p2, const Point& p3) { - Point v1 = { p1.x - p2.x, p1.y - p2.y }; - Point v2 = { p3.x - p2.x, p3.y - p2.y }; + Point v1(p1.x - p2.x, p1.y - p2.y); + Point v2(p3.x - p2.x, p3.y - p2.y); return fabs(atan2(CrossLength(v1, v2), Dot(v1, v2))); } @@ -69,13 +65,17 @@ static double angleBetween(const Point& p1, const Point& p2, const Point& p3) // possibly the previous point (inf1) [from inf1--inf2], return a // cost associated with this route. // -double cost(const double dist, VertInf *inf1, +double cost(ConnRef *lineRef, const double dist, VertInf *inf1, VertInf *inf2, VertInf *inf3) { double result = dist; + Router *router = inf2->_router; if (inf2->pathNext != NULL) { + double& angle_penalty = router->angle_penalty; + double& segmt_penalty = router->segmt_penalty; + // This is not the first segment, so there is a bend // between it and the last one in the existing path. if ((angle_penalty > 0) || (segmt_penalty > 0)) @@ -86,9 +86,14 @@ double cost(const double dist, VertInf *inf1, double rad = M_PI - angleBetween(p1, p2, p3); - // Make `rad' between 0--10 then take its log so small + // Make `xval' between 0--10 then take its log so small // angles are not penalised as much as large ones. - result += (angle_penalty * log((rad * 10 / M_PI) + 1)); + // + double xval = rad * 10 / M_PI; + double yval = xval * log10(xval + 1) / 10.5; + result += (angle_penalty * yval); + //printf("deg from straight: %g\tpenalty: %g\n", + // rad * 180 / M_PI, (angle_penalty * yval)); // Don't penalise as an extra segment if there is no turn. if (rad > 0.0005) @@ -96,9 +101,160 @@ double cost(const double dist, VertInf *inf1, result += segmt_penalty; } } - } + if (lineRef->doesHateCrossings() && (router->crossing_penalty > 0)) + { + Point& a1 = inf2->point; + Point& a2 = inf3->point; + + ConnRefList::iterator curr, finish = router->connRefs.end(); + for (curr = router->connRefs.begin(); curr != finish; ++curr) + { + ConnRef *connRef = *curr; + + if (connRef->id() == lineRef->id()) + { + continue; + } + Avoid::PolyLine& route2 = connRef->route(); + for (int j = 1; j < route2.pn; ++j) + { + Avoid::Point& b1 = route2.ps[j - 1]; + Avoid::Point& b2 = route2.ps[j]; + + if (((a1 == b1) && (a2 == b2)) || + ((a2 == b1) && (a1 == b2))) + { + // Route along same segment: no penalty. We detect + // crossovers when we see the segments diverge. + continue; + } + + if ((a2 == b2) || (a2 == b1) || (b2 == a1)) + { + // Each crossing that is at a vertex in the + // visibility graph gets noticed four times. + // We ignore three of these cases. + // This also catches the case of a shared path, + // but this is one that terminates at a common + // endpoint, so we don't care about it. + continue; + } + + if (a1 == b1) + { + if (j == 1) + { + // common source point. + continue; + } + Avoid::Point& b0 = route2.ps[j - 2]; + // The segments share an endpoint -- a1==b1. + if (a2 == b0) + { + // a2 is not a split, continue. + continue; + } + + // If here, then we know that a2 != b2 + // And a2 and its pair in b are a split. + assert(a2 != b2); + + if (inf2->pathNext == NULL) + { + continue; + } + Avoid::Point& a0 = inf1->point; + + if ((a0 == b0) || (a0 == b2)) + { + //printf("Shared path... "); + bool normal = (a0 == b0) ? true : false; + // Determine direction we have to look through + // the points of connector b. + int dir = normal ? -1 : 1; + + int traceJ = j - 1 + dir; + + int endCornerSide = Avoid::cornerSide( + a0, a1, a2, normal ? b2 : b0); + + + VertInf *traceInf1 = inf2->pathNext; + VertInf *traceInf2 = inf2; + VertInf *traceInf3 = inf3; + while (traceInf1 && + (traceJ >= 0) && (traceJ < route2.pn) && + (traceInf1->point == route2.ps[traceJ])) + { + traceInf3 = traceInf2; + traceInf2 = traceInf1; + traceInf1 = traceInf1->pathNext; + traceJ += dir; + } + + if (!traceInf1 || + (traceJ < 0) || (traceJ >= route2.pn)) + { + //printf("common source or destination.\n"); + // The connectors have a shared path, but it + // comes from a common source point. + // XXX: There might be a better way to + // check this by asking the connectors + // for the IDs of the attached shapes. + continue; + } + + int startCornerSide = Avoid::cornerSide( + traceInf1->point, traceInf2->point, + traceInf3->point, route2.ps[traceJ]); + + if (endCornerSide != startCornerSide) + { + //printf("crosses.\n"); + result += router->crossing_penalty; + } + else + { + //printf("doesn't cross.\n"); + } + } + else + { + // The connectors cross or touch at this point. + //printf("Cross or touch at point... "); + + int side1 = Avoid::cornerSide(a0, a1, a2, b0); + int side2 = Avoid::cornerSide(a0, a1, a2, b2); + + if (side1 != side2) + { + //printf("cross.\n"); + // The connectors cross at this point. + result += router->crossing_penalty; + } + else + { + //printf("touch.\n"); + // The connectors touch at this point. + } + } + continue; + } + + double xc, yc; + int intersectResult = Avoid::segmentIntersectPoint( + a1, a2, b1, b2, &xc, &yc); + + if (intersectResult == Avoid::DO_INTERSECT) + { + result += router->crossing_penalty; + } + } + } + } + return result; } @@ -110,7 +266,7 @@ double cost(const double dist, VertInf *inf1, // // Based on the code of 'matrixpfs'. // -static void dijkstraPath(VertInf *src, VertInf *tar) +static void dijkstraPath(ConnRef *lineRef, VertInf *src, VertInf *tar) { Router *router = src->_router; @@ -150,7 +306,7 @@ static void dijkstraPath(VertInf *src, VertInf *tar) { double kt_dist = (*edge)->getDist(); double priority = k->pathDist + - cost(kt_dist, k->pathNext, k, t); + cost(lineRef, kt_dist, k->pathNext, k, t); if ((kt_dist != 0) && (t->pathDist < -priority)) { @@ -232,7 +388,7 @@ bool operator>(const ANode &a, const ANode &b) // The aStar STL code is based on public domain code available on the // internet. // -static void aStarPath(VertInf *src, VertInf *tar) +static void aStarPath(ConnRef *lineRef, VertInf *src, VertInf *tar) { std::vector PENDING; // STL Vectors chosen because of rapid std::vector DONE; // insertions/deletions at back, @@ -316,7 +472,7 @@ static void aStarPath(VertInf *src, VertInf *tar) VertInf *prevInf = BestNode.inf->pathNext; - Node.g = BestNode.g + cost(edgeDist, prevInf, + Node.g = BestNode.g + cost(lineRef, edgeDist, prevInf, BestNode.inf, Node.inf); // Calculate the Heuristic. @@ -409,6 +565,9 @@ void makePath(ConnRef *lineRef, bool *flag) VertInf *src = lineRef->src(); VertInf *tar = lineRef->dst(); + // If the connector hates crossings then we want to examine direct paths: + bool examineDirectPath = lineRef->doesHateCrossings(); + // TODO: Could be more efficient here. EdgeInf *directEdge = EdgeInf::existingEdge(src, tar); if (!(router->IncludeEndpoints) && directVis(src, tar)) @@ -426,7 +585,7 @@ void makePath(ConnRef *lineRef, bool *flag) return; } else if (router->IncludeEndpoints && directEdge && - (directEdge->getDist() > 0)) + (directEdge->getDist() > 0) && !examineDirectPath) { tar->pathNext = src; directEdge->addConn(flag); @@ -446,11 +605,11 @@ void makePath(ConnRef *lineRef, bool *flag) if (router->UseAStarSearch) { - aStarPath(src, tar); + aStarPath(lineRef, src, tar); } else { - dijkstraPath(src, tar); + dijkstraPath(lineRef, src, tar); } #if 0 diff --git a/src/libavoid/router.cpp b/src/libavoid/router.cpp index 36514e24e..6570962a9 100644 --- a/src/libavoid/router.cpp +++ b/src/libavoid/router.cpp @@ -26,6 +26,7 @@ #include "libavoid/connector.h" #include "libavoid/polyutil.h" #include "libavoid/debug.h" +#include "libavoid/region.h" #include "math.h" //#define ORTHOGONAL_ROUTING @@ -33,8 +34,34 @@ namespace Avoid { +static const unsigned int infoAdd = 1; +static const unsigned int infoDel = 2; +static const unsigned int infoMov = 3; + + +class MoveInfo { + public: + MoveInfo(ShapeRef *s, Polygn *p, bool fM) + : shape(s) + , newPoly(copyPoly(*p)) + , firstMove(fM) + { } + ~MoveInfo() + { + freePoly(newPoly); + } + ShapeRef *shape; + Polygn newPoly; + bool firstMove; +}; + + + Router::Router() : PartialTime(false) + , segmt_penalty(0) + , angle_penalty(0) + , crossing_penalty(200) // Algorithm options: , UseAStarSearch(true) , IgnoreRegions(true) @@ -42,7 +69,7 @@ Router::Router() , IncludeEndpoints(true) , UseLeesAlgorithm(false) , InvisibilityGrph(true) - , ConsolidateMoves(false) + , ConsolidateMoves(true) , PartialFeedback(false) // Instrumentation: , st_checked_edges(0) @@ -118,31 +145,94 @@ void Router::delShape(ShapeRef *shape) void Router::moveShape(ShapeRef *shape, Polygn *newPoly, const bool first_move) { - unsigned int pid = shape->id(); - bool notPartialTime = !(PartialFeedback && PartialTime); + // Sanely cope with the case where the user requests moving the same + // shape multiple times before rerouting connectors. + bool alreadyThere = false; + unsigned int id = shape->id(); + MoveInfoList::iterator finish = moveList.end(); + for (MoveInfoList::iterator it = moveList.begin(); it != finish; ++it) + { + if ((*it)->shape->id() == id) + { + fprintf(stderr, + "warning: multiple moves requested for shape %d.\n", + (int) id); + // Just update the MoveInfo with the second polygon, but + // leave the firstMove setting alone. + (*it)->newPoly = copyPoly(*newPoly); + alreadyThere = true; + } + } - // o Remove entries related to this shape's vertices - shape->removeFromGraph(); - - if (SelectiveReroute && (notPartialTime || first_move)) + if (!alreadyThere) { - markConnectors(shape); + MoveInfo *moveInfo = new MoveInfo(shape, newPoly, first_move); + moveList.push_back(moveInfo); } - adjustContainsWithDel(pid); - + if (!ConsolidateMoves) + { + processMoves(); + } +} + + +void Router::processMoves(void) +{ + if (moveList.empty()) + { + return; + } + + MoveInfoList::iterator curr; + MoveInfoList::iterator finish = moveList.end(); + for (curr = moveList.begin(); curr != finish; ++curr) + { + MoveInfo *moveInf = *curr; + ShapeRef *shape = moveInf->shape; + Polygn *newPoly = &(moveInf->newPoly); + bool first_move = moveInf->firstMove; + + unsigned int pid = shape->id(); + bool notPartialTime = !(PartialFeedback && PartialTime); + + // o Remove entries related to this shape's vertices + shape->removeFromGraph(); + + if (SelectiveReroute && (notPartialTime || first_move)) + { + markConnectors(shape); + } + + adjustContainsWithDel(pid); + #ifdef ORTHOGONAL_ROUTING - Region::removeShape(shape); + Region::removeShape(shape); #endif - shape->setNewPoly(*newPoly); + shape->setNewPoly(*newPoly); + + adjustContainsWithAdd(*newPoly, pid); - adjustContainsWithAdd(*newPoly, pid); + // Ignore this shape for visibility. + // XXX: We don't really need to do this if we're not using Partial + // Feedback. Without this the blocked edges still route + // around the shape until it leaves the connector. + shape->makeInactive(); + + } - // o Check all edges that were blocked by this shape. if (InvisibilityGrph) { - checkAllBlockedEdges(pid); + for (curr = moveList.begin(); curr != finish; ++curr) + { + MoveInfo *moveInf = *curr; + ShapeRef *shape = moveInf->shape; + unsigned int pid = shape->id(); + + // o Check all edges that were blocked by this shape. + checkAllBlockedEdges(pid); + } } else { @@ -150,31 +240,46 @@ void Router::moveShape(ShapeRef *shape, Polygn *newPoly, const bool first_move) checkAllMissingEdges(); } + while ( ! moveList.empty() ) + { + MoveInfo *moveInf = moveList.front(); + ShapeRef *shape = moveInf->shape; + Polygn *newPoly = &(moveInf->newPoly); + + unsigned int pid = shape->id(); + bool notPartialTime = !(PartialFeedback && PartialTime); + + // Restore this shape for visibility. + shape->makeActive(); + #ifdef ORTHOGONAL_ROUTING - Region::addShape(shape); + Region::addShape(shape); #endif - // o Check all visibility edges to see if this one shape - // blocks them. - if (notPartialTime) - { - newBlockingShape(newPoly, pid); - } + // o Check all visibility edges to see if this one shape + // blocks them. + if (notPartialTime) + { + newBlockingShape(newPoly, pid); + } - // o Calculate visibility for the new vertices. - if (UseLeesAlgorithm) - { - shapeVisSweep(shape); - } - else - { - shapeVis(shape); + // o Calculate visibility for the new vertices. + if (UseLeesAlgorithm) + { + shapeVisSweep(shape); + } + else + { + shapeVis(shape); + } + + moveList.pop_front(); + delete moveInf; } callbackAllInvalidConnectors(); } - //---------------------------------------------------------------------------- // XXX: attachedShapes and attachedConns both need to be rewritten @@ -248,10 +353,10 @@ void Router::newBlockingShape(Polygn *poly, int pid) if (tmp->getDist() != 0) { - pair ids(tmp->ids()); + std::pair ids(tmp->ids()); VertID eID1 = ids.first; VertID eID2 = ids.second; - pair points(tmp->points()); + std::pair points(tmp->points()); Point e1 = points.first; Point e2 = points.second; bool blocked = false; @@ -426,6 +531,11 @@ void Router::markConnectors(ShapeRef *shape) // Ignore uninitialised connectors. continue; } + else if (conn->_needs_reroute_flag) + { + // Already marked, so skip. + continue; + } Point start = conn->_route.ps[0]; Point end = conn->_route.ps[conn->_route.pn - 1]; @@ -478,9 +588,9 @@ void Router::markConnectors(ShapeRef *shape) else { // Need to do rotation - Point n_p2 = { p2.x - p1.x, p2.y - p1.y }; - Point n_start = { start.x - p1.x, start.y - p1.y }; - Point n_end = { end.x - p1.x, end.y - p1.y }; + Point n_p2(p2.x - p1.x, p2.y - p1.y); + Point n_start(start.x - p1.x, start.y - p1.y); + Point n_end(end.x - p1.x, end.y - p1.y); //printf("n_p2: (%.1f, %.1f)\n", n_p2.x, n_p2.y); //printf("n_start: (%.1f, %.1f)\n", n_start.x, n_start.y); //printf("n_end: (%.1f, %.1f)\n", n_end.x, n_end.y); @@ -488,7 +598,7 @@ void Router::markConnectors(ShapeRef *shape) double theta = 0 - atan2(n_p2.y, n_p2.x); //printf("theta = %.2f\n", theta * (180 / PI)); - Point r_p1 = {0, 0}; + Point r_p1(0, 0); Point r_p2 = n_p2; start = n_start; end = n_end; diff --git a/src/libavoid/router.h b/src/libavoid/router.h index 4d25b53d4..a331527d5 100644 --- a/src/libavoid/router.h +++ b/src/libavoid/router.h @@ -41,7 +41,8 @@ namespace Avoid { class ConnRef; typedef std::list ConnRefList; typedef std::list IntList; -typedef std::pair MoveInfo; +class MoveInfo; +typedef std::list MoveInfoList; static const unsigned int runningTo = 1; @@ -63,6 +64,8 @@ class Router { bool PartialTime; double segmt_penalty; double angle_penalty; + double crossing_penalty; + bool UseAStarSearch; bool IgnoreRegions; @@ -84,6 +87,7 @@ class Router { void delShape(ShapeRef *shape); void moveShape(ShapeRef *shape, Polygn *newPoly, const bool first_move = false); + void processMoves(void); void attachedConns(IntList &conns, const unsigned int shapeId, const unsigned int type); @@ -100,6 +104,8 @@ class Router { void adjustContainsWithAdd(const Polygn& poly, const int p_shape); void adjustContainsWithDel(const int p_shape); void callbackAllInvalidConnectors(void); + + MoveInfoList moveList; }; } diff --git a/src/libavoid/shape.cpp b/src/libavoid/shape.cpp index 84f0312ee..2b241b728 100644 --- a/src/libavoid/shape.cpp +++ b/src/libavoid/shape.cpp @@ -37,6 +37,7 @@ ShapeRef::ShapeRef(Router *router, unsigned int id, Polygn& ply) , _id(id) , _poly(copyPoly(ply)) , _active(false) + , _inMoveList(false) , _firstVert(NULL) , _lastVert(NULL) { @@ -60,18 +61,15 @@ ShapeRef::ShapeRef(Router *router, unsigned int id, Polygn& ply) //node->lstPrev = last; //last->lstNext = node; } - _router->vertices.addVertex(node); last = node; i++; - // Increase total vertices count ++; } _lastVert = node; _lastVert->shNext = _firstVert; _firstVert->shPrev = _lastVert; - // Increase total shape count ++; makeActive(); } @@ -80,23 +78,20 @@ ShapeRef::~ShapeRef() { assert(_firstVert != NULL); + makeInactive(); + VertInf *it = _firstVert; do { VertInf *tmp = it; it = it->shNext; - // XXX: This could possibly be done less - // safely but faster, all at once. - _router->vertices.removeVertex(tmp); delete tmp; } while (it != _firstVert); _firstVert = _lastVert = NULL; freePoly(_poly); - - makeInactive(); } @@ -131,6 +126,18 @@ void ShapeRef::makeActive(void) // Add to connRefs list. _pos = _router->shapeRefs.insert(_router->shapeRefs.begin(), this); + + // Add points to vertex list. + VertInf *it = _firstVert; + do + { + VertInf *tmp = it; + it = it->shNext; + + _router->vertices.addVertex(tmp); + } + while (it != _firstVert); + _active = true; } @@ -141,6 +148,18 @@ void ShapeRef::makeInactive(void) // Remove from connRefs list. _router->shapeRefs.erase(_pos); + + // Remove points from vertex list. + VertInf *it = _firstVert; + do + { + VertInf *tmp = it; + it = it->shNext; + + _router->vertices.removeVertex(tmp); + } + while (it != _firstVert); + _active = false; } @@ -224,6 +243,43 @@ void ShapeRef::removeFromGraph(void) } +void ShapeRef::markForMove(void) +{ + if (!_inMoveList) + { + _inMoveList = true; + } + else + { + fprintf(stderr, "WARNING: two moves queued for same shape prior to " + "rerouting.\n This is not safe.\n"); + } +} + + +void ShapeRef::clearMoveMark(void) +{ + _inMoveList = false; +} + + +VertInf *ShapeRef::getPointVertex(const Point& point) +{ + VertInf *curr = _firstVert; + do + { + if (curr->point == point) + { + return curr; + } + curr = curr->shNext; + } + while (curr != _firstVert); + + return NULL; +} + + } diff --git a/src/libavoid/shape.h b/src/libavoid/shape.h index cdcbe7839..28f38298d 100644 --- a/src/libavoid/shape.h +++ b/src/libavoid/shape.h @@ -52,12 +52,17 @@ class ShapeRef void makeInactive(void); void removeFromGraph(void); + void markForMove(void); + void clearMoveMark(void); + + VertInf *getPointVertex(const Point& point); private: Router *_router; unsigned int _id; Polygn _poly; bool _active; + bool _inMoveList; ShapeRefList::iterator _pos; VertInf *_firstVert; VertInf *_lastVert; diff --git a/src/libavoid/static.cpp b/src/libavoid/static.cpp index 11ccfd76f..740a4f9c0 100644 --- a/src/libavoid/static.cpp +++ b/src/libavoid/static.cpp @@ -39,7 +39,7 @@ static void computeCompleteVis(Router *router); // This should only be used for the static algorithm. // // XXX: If to set up the vis graph for incremental it would need -// the shapeRef ppinters in obs. +// the shapeRef pointers in obs. // void CreateVisGraph(Router *router, Polygn **obs, int n_obs) { @@ -94,6 +94,8 @@ void DestroyVisGraph(Router *router) conn->removeFromGraph(); conn->unInitialise(); } + // Clear contains info. + router->contains.clear(); assert(router->vertices.connsBegin() == NULL); } diff --git a/src/libavoid/vertices.cpp b/src/libavoid/vertices.cpp index 786919581..c2be955ac 100644 --- a/src/libavoid/vertices.cpp +++ b/src/libavoid/vertices.cpp @@ -30,6 +30,8 @@ #include #include +using std::ostream; + namespace Avoid { @@ -125,7 +127,6 @@ void VertID::print(FILE *file) const fprintf(file, "[%u,%d]", objID, vn); } - void VertID::db_print(void) const { db_printf("[%u,%d]", objID, vn); @@ -136,6 +137,13 @@ const int VertID::src = 1; const int VertID::tar = 2; +ostream& operator<<(ostream& os, const VertID& vID) +{ + return os << '[' << vID.objID << ',' << vID.vn << ']'; +} + + + VertInf::VertInf(Router *router, const VertID& vid, const Point& vpoint) : _router(router) , id(vid) diff --git a/src/libavoid/vertices.h b/src/libavoid/vertices.h index de2e30ae3..e82b163a6 100644 --- a/src/libavoid/vertices.h +++ b/src/libavoid/vertices.h @@ -59,6 +59,7 @@ class VertID VertID& operator++(int); void print(FILE *file = stdout) const; void db_print(void) const; + friend std::ostream& operator<<(std::ostream& os, const VertID& vID); }; diff --git a/src/libavoid/visibility.cpp b/src/libavoid/visibility.cpp index 71c8b1c1b..f540baf21 100644 --- a/src/libavoid/visibility.cpp +++ b/src/libavoid/visibility.cpp @@ -316,14 +316,6 @@ static bool sweepVisible(EdgeSet& T, VertInf *currInf, VertInf *lastInf, *blocker = (*closestIt).vInf1->id.objID; return false; } - else - { - return true; - } - } - else - { - return true; } } else @@ -350,9 +342,9 @@ static bool sweepVisible(EdgeSet& T, VertInf *currInf, VertInf *lastInf, return false; } } - return true; } } + return true; } @@ -443,7 +435,7 @@ void vertexSweep(VertInf *vert) continue; } - Point xaxis = { DBL_MAX, centerInf->point.y }; + Point xaxis(DBL_MAX, centerInf->point.y); if (segmentIntersect(centerInf->point, xaxis, kPrev->point, k->point)) { diff --git a/src/sp-conn-end-pair.cpp b/src/sp-conn-end-pair.cpp index c5cc75251..40f939e25 100644 --- a/src/sp-conn-end-pair.cpp +++ b/src/sp-conn-end-pair.cpp @@ -220,8 +220,8 @@ SPConnEndPair::update(void) NR::Point endPt[2]; getEndpoints(endPt); - Avoid::Point src = { endPt[0][NR::X], endPt[0][NR::Y] }; - Avoid::Point dst = { endPt[1][NR::X], endPt[1][NR::Y] }; + Avoid::Point src(endPt[0][NR::X], endPt[0][NR::Y]); + Avoid::Point dst(endPt[1][NR::X], endPt[1][NR::Y]); _connRef->lateSetup(src, dst); _connRef->setCallback(&emitPathInvalidationNotification, _path); @@ -283,8 +283,8 @@ SPConnEndPair::reroutePath(void) NR::Point endPt[2]; getEndpoints(endPt); - Avoid::Point src = { endPt[0][NR::X], endPt[0][NR::Y] }; - Avoid::Point dst = { endPt[1][NR::X], endPt[1][NR::Y] }; + Avoid::Point src(endPt[0][NR::X], endPt[0][NR::Y]); + Avoid::Point dst(endPt[1][NR::X], endPt[1][NR::Y]); _connRef->updateEndPoint(Avoid::VertID::src, src); _connRef->updateEndPoint(Avoid::VertID::tar, dst); -- 2.30.2