From 618fe74db3717f5c37f7a51d0d6df95776efbfe1 Mon Sep 17 00:00:00 2001 From: mjwybrow Date: Wed, 15 Feb 2006 13:25:54 +0000 Subject: * src/document.cpp, src/document.h, src/sp-conn-end-pair.cpp, src/connector-context.cpp, src/conn-avoid-ref.cpp: Keep a seperate connector router for each document. * src/libavoid/Makefile_insert, src/libavoid/connector.cpp, src/libavoid/connector.h, src/libavoid/debug.h, src/libavoid/geometry.cpp, src/libavoid/geometry.h, src/libavoid/geomtypes.h, src/libavoid/graph.cpp, src/libavoid/graph.h, src/libavoid/incremental.cpp, src/libavoid/incremental.h, src/libavoid/libavoid.h, src/libavoid/makepath.cpp, src/libavoid/makepath.h, src/libavoid/polyutil.cpp, src/libavoid/polyutil.h, src/libavoid/router.cpp, src/libavoid/router.h, src/libavoid/shape.cpp, src/libavoid/shape.h, src/libavoid/static.cpp, src/libavoid/static.h, src/libavoid/timer.cpp, src/libavoid/timer.h, src/libavoid/vertices.cpp, src/libavoid/vertices.h, src/libavoid/visibility.cpp, src/libavoid/visibility.h: Upstream changes to libavoid that allow multiple connector router instances, as well a few other minor bugfixes. (bzr r144) --- src/libavoid/router.cpp | 654 ++++++++++++++++++++++++++++++++++++++++++++++++ 1 file changed, 654 insertions(+) create mode 100644 src/libavoid/router.cpp (limited to 'src/libavoid/router.cpp') diff --git a/src/libavoid/router.cpp b/src/libavoid/router.cpp new file mode 100644 index 000000000..78bfa33db --- /dev/null +++ b/src/libavoid/router.cpp @@ -0,0 +1,654 @@ +/* + * vim: ts=4 sw=4 et tw=0 wm=0 + * + * libavoid - Fast, Incremental, Object-avoiding Line Router + * Copyright (C) 2004-2006 Michael Wybrow + * + * This library is free software; you can redistribute it and/or + * modify it under the terms of the GNU Lesser General Public + * License as published by the Free Software Foundation; either + * version 2.1 of the License, or (at your option) any later version. + * + * This library is distributed in the hope that it will be useful, + * but WITHOUT ANY WARRANTY; without even the implied warranty of + * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU + * Lesser General Public License for more details. + * + * You should have received a copy of the GNU Lesser General Public + * License along with this library; if not, write to the Free Software + * Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA 02111-1307 USA + * +*/ + +#include "libavoid/shape.h" +#include "libavoid/router.h" +#include "libavoid/visibility.h" +#include "libavoid/connector.h" +#include "libavoid/polyutil.h" +#include "libavoid/debug.h" +#include "math.h" + + +namespace Avoid { + + +Router::Router() + : PartialTime(false) + // Algorithm options: + , UseAStarSearch(true) + , IgnoreRegions(true) + , SelectiveReroute(true) + , IncludeEndpoints(true) + , UseLeesAlgorithm(false) + , InvisibilityGrph(true) + , PartialFeedback(false) + // Instrumentation: + , st_checked_edges(0) +#ifdef LINEDEBUG + , avoid_screen(NULL) +#endif +{ } + + + + +void Router::addShape(ShapeRef *shape) +{ + unsigned int pid = shape->id(); + Polygn poly = shape->poly(); + + adjustContainsWithAdd(poly, pid); + + // o Check all visibility edges to see if this one shape + // blocks them. + newBlockingShape(&poly, pid); + + // o Calculate visibility for the new vertices. + if (UseLeesAlgorithm) + { + shapeVisSweep(shape); + } + else + { + shapeVis(shape); + } + callbackAllInvalidConnectors(); +} + + +void Router::delShape(ShapeRef *shape) +{ + unsigned int pid = shape->id(); + + // o Remove entries related to this shape's vertices + shape->removeFromGraph(); + + if (SelectiveReroute) + { + markConnectors(shape); + } + + adjustContainsWithDel(pid); + + delete shape; + + // o Check all edges that were blocked by this shape. + if (InvisibilityGrph) + { + checkAllBlockedEdges(pid); + } + else + { + // check all edges not in graph + checkAllMissingEdges(); + } + callbackAllInvalidConnectors(); +} + + +ShapeRef *Router::moveShape(ShapeRef *oldShape, Polygn *newPoly, const bool first_move) +{ + unsigned int pid = oldShape->id(); + + // o Remove entries related to this shape's vertices + oldShape->removeFromGraph(); + + if (SelectiveReroute && (!(PartialFeedback && PartialTime) || first_move)) + { + markConnectors(oldShape); + } + + adjustContainsWithDel(pid); + + delete oldShape; + oldShape = NULL; + + adjustContainsWithAdd(*newPoly, pid); + + // o Check all edges that were blocked by this shape. + if (InvisibilityGrph) + { + checkAllBlockedEdges(pid); + } + else + { + // check all edges not in graph + checkAllMissingEdges(); + } + + ShapeRef *newShape = new ShapeRef(this, pid, *newPoly); + + // o Check all visibility edges to see if this one shape + // blocks them. + if (!(PartialFeedback && PartialTime)) + { + newBlockingShape(newPoly, pid); + } + + // o Calculate visibility for the new vertices. + if (UseLeesAlgorithm) + { + shapeVisSweep(newShape); + } + else + { + shapeVis(newShape); + } + callbackAllInvalidConnectors(); + + return newShape; +} + + + +//---------------------------------------------------------------------------- + +// XXX: attachedShapes and attachedConns both need to be rewritten +// for constant time lookup of attached objects once this info +// is stored better within libavoid. Also they shouldn't need to +// be friends of ConnRef. + + // Returns a list of connector Ids of all the connectors of type + // 'type' attached to the shape with the ID 'shapeId'. +void Router::attachedConns(IntList &conns, const unsigned int shapeId, + const unsigned int type) +{ + ConnRefList::iterator fin = connRefs.end(); + for (ConnRefList::iterator i = connRefs.begin(); i != fin; ++i) { + + if ((type & runningTo) && ((*i)->_dstId == shapeId)) { + conns.push_back((*i)->_srcId); + } + else if ((type & runningFrom) && ((*i)->_srcId == shapeId)) { + conns.push_back((*i)->_dstId); + } + } +} + + + // Returns a list of shape Ids of all the shapes attached to the + // shape with the ID 'shapeId' with connection type 'type'. +void Router::attachedShapes(IntList &shapes, const unsigned int shapeId, + const unsigned int type) +{ + ConnRefList::iterator fin = connRefs.end(); + for (ConnRefList::iterator i = connRefs.begin(); i != fin; ++i) { + if ((type & runningTo) && ((*i)->_dstId == shapeId)) { + if ((*i)->_srcId != 0) + { + // Only if there is a shape attached to the other end. + shapes.push_back((*i)->_srcId); + } + } + else if ((type & runningFrom) && ((*i)->_srcId == shapeId)) { + if ((*i)->_dstId != 0) + { + // Only if there is a shape attached to the other end. + shapes.push_back((*i)->_dstId); + } + } + } +} + + + // It's intended this function is called after shape movement has + // happened to alert connectors that they need to be rerouted. +void Router::callbackAllInvalidConnectors(void) +{ + ConnRefList::iterator fin = connRefs.end(); + for (ConnRefList::iterator i = connRefs.begin(); i != fin; ++i) { + (*i)->handleInvalid(); + } +} + + +void Router::newBlockingShape(Polygn *poly, int pid) +{ + // o Check all visibility edges to see if this one shape + // blocks them. + EdgeInf *finish = visGraph.end(); + for (EdgeInf *iter = visGraph.begin(); iter != finish ; ) + { + EdgeInf *tmp = iter; + iter = iter->lstNext; + + if (tmp->getDist() != 0) + { + pair ids(tmp->ids()); + VertID eID1 = ids.first; + VertID eID2 = ids.second; + pair points(tmp->points()); + Point e1 = points.first; + Point e2 = points.second; + bool blocked = false; + + bool ep_in_poly1 = !(eID1.isShape) ? inPoly(*poly, e1) : false; + bool ep_in_poly2 = !(eID2.isShape) ? inPoly(*poly, e2) : false; + if (ep_in_poly1 || ep_in_poly2) + { + // Don't check edges that have a connector endpoint + // and are inside the shape being added. + continue; + } + + for (int pt_i = 0; pt_i < poly->pn; pt_i++) + { + int pt_n = (pt_i == (poly->pn - 1)) ? 0 : pt_i + 1; + if (segmentIntersect(e1, e2, poly->ps[pt_i], poly->ps[pt_n])) + { + blocked = true; + break; + } + } + if (blocked) + { + db_printf("\tRemoving newly blocked edge (by shape %3d)" + "... \n\t\t", pid); + tmp->alertConns(); + tmp->db_print(); + if (InvisibilityGrph) + { + tmp->addBlocker(pid); + } + else + { + delete tmp; + } + } + } + } +} + + +void Router::checkAllBlockedEdges(int pid) +{ + assert(InvisibilityGrph); + + for (EdgeInf *iter = invisGraph.begin(); iter != invisGraph.end() ; ) + { + EdgeInf *tmp = iter; + iter = iter->lstNext; + + if (tmp->hasBlocker(pid)) + { + tmp->checkVis(); + } + } +} + + +void Router::checkAllMissingEdges(void) +{ + assert(!InvisibilityGrph); + + VertInf *first = NULL; + + if (IncludeEndpoints) + { + first = vertices.connsBegin(); + } + else + { + first = vertices.shapesBegin(); + } + + VertInf *pend = vertices.end(); + for (VertInf *i = first; i != pend; i = i->lstNext) + { + VertID iID = i->id; + + // Check remaining, earlier vertices + for (VertInf *j = first ; j != i; j = j->lstNext) + { + VertID jID = j->id; + if (!(iID.isShape) && (iID.objID != jID.objID)) + { + // Don't keep visibility between edges of different conns + continue; + } + + // See if the edge is already there? + bool found = (EdgeInf::existingEdge(i, j) != NULL); + + if (!found) + { + // Didn't already exist, check. + bool knownNew = true; + EdgeInf::checkEdgeVisibility(i, j, knownNew); + } + } + } +} + + +void Router::generateContains(VertInf *pt) +{ + contains[pt->id].clear(); + + ShapeRefList::iterator finish = shapeRefs.end(); + for (ShapeRefList::iterator i = shapeRefs.begin(); i != finish; ++i) + { + Polygn poly = copyPoly(*i); + if (inPoly(poly, pt->point)) + { + contains[pt->id].insert((*i)->id()); + } + freePoly(poly); + } +} + + +void Router::adjustContainsWithAdd(const Polygn& poly, const int p_shape) +{ + for (VertInf *k = vertices.connsBegin(); k != vertices.shapesBegin(); + k = k->lstNext) + { + if (inPoly(poly, k->point)) + { + contains[k->id].insert(p_shape); + } + } +} + + +void Router::adjustContainsWithDel(const int p_shape) +{ + for (VertInf *k = vertices.connsBegin(); k != vertices.shapesBegin(); + k = k->lstNext) + { + contains[k->id].erase(p_shape); + } +} + + +#define MIN(a, b) (((a) <= (b)) ? (a) : (b)) +#define MAX(a, b) (((a) >= (b)) ? (a) : (b)) + +#ifdef SELECTIVE_DEBUG +static double AngleAFromThreeSides(const double a, const double b, + const double c) +{ + // returns angle A, the angle opposite from side a, in radians + return acos((pow(b, 2) + pow(c, 2) - pow(a, 2)) / (2 * b * c)); +} +#endif + +void Router::markConnectors(ShapeRef *shape) +{ + assert(SelectiveReroute); + + ConnRefList::iterator end = connRefs.end(); + for (ConnRefList::iterator it = connRefs.begin(); it != end; ++it) + { + ConnRef *conn = (*it); + + if (conn->_route.pn == 0) + { + // Ignore uninitialised connectors. + continue; + } + + Point start = conn->_route.ps[0]; + Point end = conn->_route.ps[conn->_route.pn - 1]; + + double conndist = conn->_route_dist; + + double estdist; + double e1, e2; + + VertInf *beginV = shape->firstVert(); + VertInf *endV = shape->lastVert()->lstNext; + for (VertInf *i = beginV; i != endV; i = i->lstNext) + { + const Point& p1 = i->point; + const Point& p2 = i->shNext->point; + + double offy; + double a; + double b; + double c; + double d; + + double min; + double max; + + if (p1.y == p2.y) + { + // Standard case + offy = p1.y; + a = start.x; + b = start.y - offy; + c = end.x; + d = end.y - offy; + + min = MIN(p1.x, p2.x); + max = MAX(p1.x, p2.x); + } + else if (p1.x == p2.x) + { + // Other Standard case + offy = p1.x; + a = start.y; + b = start.x - offy; + c = end.y; + d = end.x - offy; + + min = MIN(p1.y, p2.y); + max = MAX(p1.y, p2.y); + } + 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 }; + //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); + + double theta = 0 - atan2(n_p2.y, n_p2.x); + //printf("theta = %.2f\n", theta * (180 / PI)); + + Point r_p1 = {0, 0}; + Point r_p2 = n_p2; + start = n_start; + end = n_end; + + double cosv = cos(theta); + double sinv = sin(theta); + + r_p2.x = cosv * n_p2.x - sinv * n_p2.y; + r_p2.y = cosv * n_p2.y + sinv * n_p2.x; + start.x = cosv * n_start.x - sinv * n_start.y; + start.y = cosv * n_start.y + sinv * n_start.x; + end.x = cosv * n_end.x - sinv * n_end.y; + end.y = cosv * n_end.y + sinv * n_end.x; + //printf("r_p2: (%.1f, %.1f)\n", r_p2.x, r_p2.y); + //printf("r_start: (%.1f, %.1f)\n", start.x, start.y); + //printf("r_end: (%.1f, %.1f)\n", end.x, end.y); + + if (((int) r_p2.y) != 0) + { + printf("r_p2.y: %f != 0\n", r_p2.y); + abort(); + } + // This might be slightly off. + r_p2.y = 0; + + offy = r_p1.y; + a = start.x; + b = start.y - offy; + c = end.x; + d = end.y - offy; + + min = MIN(r_p1.x, r_p2.x); + max = MAX(r_p1.x, r_p2.x); + + } + + double x; + if ((b + d) == 0) + { + db_printf("WARNING: (b + d) == 0\n"); + d = d * -1; + } + + if ((b == 0) && (d == 0)) + { + db_printf("WARNING: b == d == 0\n"); + if (((a < min) && (c < min)) || + ((a > max) && (c > max))) + { + // It's going to get adjusted. + x = a; + } + else + { + continue; + } + } + else + { + x = ((b*c) + (a*d)) / (b + d); + } + + //printf("%.1f, %.1f, %.1f, %.1f\n", a, b, c, d); + //printf("x = %.1f\n", x); + + // XXX: Use MAX and MIN + x = (x < min) ? min : x; + x = (x > max) ? max : x; + + //printf("x = %.1f\n", x); + + Point xp; + if (p1.x == p2.x) + { + xp.x = offy; + xp.y = x; + } + else + { + xp.x = x; + xp.y = offy; + } + //printf("(%.1f, %.1f)\n", xp.x, xp.y); + + e1 = dist(start, xp); + e2 = dist(xp, end); + estdist = e1 + e2; + + + //printf("is %.1f < %.1f\n", estdist, conndist); + if (estdist < conndist) + { +#ifdef SELECTIVE_DEBUG + //double angle = AngleAFromThreeSides(dist(start, end), + // e1, e2); + printf("[%3d] - Possible better path found (%.1f < %.1f)\n", + conn->_id, estdist, conndist); +#endif + conn->_needs_reroute_flag = true; + break; + } + + } + } +} + + +void Router::printInfo(void) +{ + FILE *fp = stdout; + fprintf(fp, "\nVisibility Graph info:\n"); + fprintf(fp, "----------------------\n"); + + unsigned int currshape = 0; + int st_shapes = 0; + int st_vertices = 0; + int st_endpoints = 0; + int st_valid_shape_visedges = 0; + int st_valid_endpt_visedges = 0; + int st_invalid_visedges = 0; + VertInf *finish = vertices.end(); + for (VertInf *t = vertices.connsBegin(); t != finish; t = t->lstNext) + { + VertID pID = t->id; + + if ((pID.isShape) && (pID.objID != currshape)) + { + currshape = pID.objID; + st_shapes++; + } + if (pID.isShape) + { + st_vertices++; + } + else + { + // The shape 0 ones are temporary and not considered. + st_endpoints++; + } + } + for (EdgeInf *t = visGraph.begin(); t != visGraph.end(); + t = t->lstNext) + { + std::pair idpair = t->ids(); + + if (!(idpair.first.isShape) || !(idpair.second.isShape)) + { + st_valid_endpt_visedges++; + } + else + { + st_valid_shape_visedges++; + } + } + for (EdgeInf *t = invisGraph.begin(); t != invisGraph.end(); + t = t->lstNext) + { + st_invalid_visedges++; + } + fprintf(fp, "Number of shapes: %d\n", st_shapes); + fprintf(fp, "Number of vertices: %d (%d real, %d endpoints)\n", + st_vertices + st_endpoints, st_vertices, st_endpoints); + fprintf(fp, "Number of vis_edges: %d (%d valid [%d normal, %d endpt], " + "%d invalid)\n", st_valid_shape_visedges + st_invalid_visedges + + st_valid_endpt_visedges, st_valid_shape_visedges + + st_valid_endpt_visedges, st_valid_shape_visedges, + st_valid_endpt_visedges, st_invalid_visedges); + fprintf(fp, "----------------------\n"); + fprintf(fp, "checkVisEdge tally: %d\n", st_checked_edges); + fprintf(fp, "----------------------\n"); + + fprintf(fp, "ADDS: "); timers.Print(tmAdd); + fprintf(fp, "DELS: "); timers.Print(tmDel); + fprintf(fp, "MOVS: "); timers.Print(tmMov); + fprintf(fp, "***S: "); timers.Print(tmSev); + fprintf(fp, "PTHS: "); timers.Print(tmPth); + fprintf(fp, "\n"); +} + + +} + -- cgit v1.2.3