![[tokkee]](http://tokkee.org/images/avatar.png){kind=avatar}
diff --git a/src/libavoid/router.cpp b/src/libavoid/router.cpp
--- /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 <mjwybrow@users.sourceforge.net>
+ *
+ * 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<VertID, VertID> ids(tmp->ids());
+ VertID eID1 = ids.first;
+ VertID eID2 = ids.second;
+ pair<Point, Point> 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<VertID, VertID> 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");
+}
+
+
+}
+