From e8325ddfe05ac8dd00fbf1e25a583ee33887c031 Mon Sep 17 00:00:00 2001 From: mjwybrow Date: Wed, 15 Feb 2006 13:25:54 +0000 Subject: [PATCH] * 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. --- src/conn-avoid-ref.cpp | 22 +- src/conn-avoid-ref.h | 6 +- src/connector-context.cpp | 3 +- src/document.cpp | 9 + src/document.h | 7 + src/graphlayout/graphlayout.cpp | 2 +- src/libavoid/Makefile_insert | 4 +- src/libavoid/connector.cpp | 141 +++---- src/libavoid/connector.h | 35 +- src/libavoid/debug.h | 2 +- src/libavoid/geometry.cpp | 7 +- src/libavoid/geometry.h | 6 +- src/libavoid/geomtypes.h | 4 +- src/libavoid/graph.cpp | 490 ++---------------------- src/libavoid/graph.h | 30 +- src/libavoid/incremental.cpp | 139 ------- src/libavoid/incremental.h | 40 -- src/libavoid/libavoid.h | 4 +- src/libavoid/makepath.cpp | 22 +- src/libavoid/makepath.h | 7 +- src/libavoid/polyutil.cpp | 7 +- src/libavoid/polyutil.h | 2 +- src/libavoid/router.cpp | 654 ++++++++++++++++++++++++++++++++ src/libavoid/router.h | 105 +++++ src/libavoid/shape.cpp | 50 ++- src/libavoid/shape.h | 18 +- src/libavoid/static.cpp | 47 ++- src/libavoid/static.h | 10 +- src/libavoid/timer.cpp | 5 +- src/libavoid/timer.h | 11 +- src/libavoid/vertices.cpp | 28 +- src/libavoid/vertices.h | 9 +- src/libavoid/visibility.cpp | 92 ++--- src/libavoid/visibility.h | 14 +- src/sp-conn-end-pair.cpp | 5 +- 35 files changed, 1087 insertions(+), 950 deletions(-) delete mode 100644 src/libavoid/incremental.cpp delete mode 100644 src/libavoid/incremental.h create mode 100644 src/libavoid/router.cpp create mode 100644 src/libavoid/router.h diff --git a/src/conn-avoid-ref.cpp b/src/conn-avoid-ref.cpp index d832a34b4..df885d44c 100644 --- a/src/conn-avoid-ref.cpp +++ b/src/conn-avoid-ref.cpp @@ -15,7 +15,7 @@ #include "conn-avoid-ref.h" #include "libnr/nr-rect-ops.h" #include "libavoid/polyutil.h" -#include "libavoid/incremental.h" +#include "libavoid/router.h" #include "libavoid/connector.h" #include "xml/simple-node.cpp" #include "document.h" @@ -27,6 +27,8 @@ #include "inkscape.h" +using Avoid::Router; + static Avoid::Polygn avoid_item_poly(SPItem const *item); @@ -44,9 +46,10 @@ SPAvoidRef::~SPAvoidRef() { _transformed_connection.disconnect(); if (shapeRef) { + Router *router = shapeRef->router(); // shapeRef is finalised by delShape, // so no memory is lost here. - Avoid::delShape(shapeRef); + router->delShape(shapeRef); shapeRef = NULL; } } @@ -71,6 +74,8 @@ void SPAvoidRef::handleSettingChange(void) if (desktop == NULL) { return; } + + Router *router = item->document->router; if (new_setting == setting) { // Don't need to make any changes @@ -90,10 +95,10 @@ void SPAvoidRef::handleSettingChange(void) // Get a unique ID for the item. GQuark itemID = g_quark_from_string(id); - shapeRef = new Avoid::ShapeRef(itemID, poly); + shapeRef = new Avoid::ShapeRef(router, itemID, poly); Avoid::freePoly(poly); - Avoid::addShape(shapeRef); + router->addShape(shapeRef); } } else @@ -102,7 +107,7 @@ void SPAvoidRef::handleSettingChange(void) // shapeRef is finalised by delShape, // so no memory is lost here. - Avoid::delShape(shapeRef); + router->delShape(shapeRef); shapeRef = NULL; } setting = new_setting; @@ -115,7 +120,7 @@ GSList *SPAvoidRef::getAttachedShapes(const unsigned int type) Avoid::IntList shapes; GQuark shapeId = g_quark_from_string(item->id); - Avoid::attachedShapes(shapes, shapeId, type); + item->document->router->attachedShapes(shapes, shapeId, type); Avoid::IntList::iterator finish = shapes.end(); for (Avoid::IntList::iterator i = shapes.begin(); i != finish; ++i) { @@ -139,7 +144,7 @@ GSList *SPAvoidRef::getAttachedConnectors(const unsigned int type) Avoid::IntList conns; GQuark shapeId = g_quark_from_string(item->id); - Avoid::attachedConns(conns, shapeId, type); + item->document->router->attachedConns(conns, shapeId, type); Avoid::IntList::iterator finish = conns.end(); for (Avoid::IntList::iterator i = conns.begin(); i != finish; ++i) { @@ -245,10 +250,11 @@ void avoid_item_move(NR::Matrix const *mp, SPItem *moved_item) Avoid::ShapeRef *shapeRef = moved_item->avoidRef->shapeRef; g_assert(shapeRef); + Router *router = moved_item->document->router; Avoid::Polygn poly = avoid_item_poly(moved_item); if (poly.pn > 0) { // moveShape actually destroys the old shapeRef and returns a new one. - moved_item->avoidRef->shapeRef = Avoid::moveShape(shapeRef, &poly); + moved_item->avoidRef->shapeRef = router->moveShape(shapeRef, &poly); Avoid::freePoly(poly); } } diff --git a/src/conn-avoid-ref.h b/src/conn-avoid-ref.h index a30dc4b93..c60cf7afd 100644 --- a/src/conn-avoid-ref.h +++ b/src/conn-avoid-ref.h @@ -33,9 +33,9 @@ public: // Returns a list of SPItems of all connectors/shapes attached to // this object. Pass one of the following for 'type': - // Avoid::ConnRef::runningTo - // Avoid::ConnRef::runningFrom - // Avoid::ConnRef::runningToAndFrom + // Avoid::runningTo + // Avoid::runningFrom + // Avoid::runningToAndFrom GSList *getAttachedShapes(const unsigned int type); GSList *getAttachedConnectors(const unsigned int type); diff --git a/src/connector-context.cpp b/src/connector-context.cpp index 93db0f844..f3296aebf 100644 --- a/src/connector-context.cpp +++ b/src/connector-context.cpp @@ -788,7 +788,8 @@ spcc_connector_set_subsequent_point(SPConnectorContext *const cc, NR::Point cons Avoid::Point dst = { d[NR::X], d[NR::Y] }; if (!cc->newConnRef) { - cc->newConnRef = new Avoid::ConnRef(0, src, dst); + Avoid::Router *router = SP_DT_DOCUMENT(dt)->router; + cc->newConnRef = new Avoid::ConnRef(router, 0, src, dst); cc->newConnRef->updateEndPoint(Avoid::VertID::src, src); } cc->newConnRef->updateEndPoint(Avoid::VertID::tar, dst); diff --git a/src/document.cpp b/src/document.cpp index e5c0cd824..b53a7b7fa 100644 --- a/src/document.cpp +++ b/src/document.cpp @@ -50,6 +50,7 @@ #include "dir-util.h" #include "unit-constants.h" #include "prefs-utils.h" +#include "libavoid/router.h" #include "display/nr-arena-item.h" @@ -86,6 +87,9 @@ SPDocument::SPDocument() { _collection_queue = NULL; + // Initialise instance of connector router. + router = new Avoid::Router(); + p = new SPDocumentPrivate(); p->iddef = g_hash_table_new(g_direct_hash, g_direct_equal); @@ -164,6 +168,11 @@ SPDocument::~SPDocument() { keepalive = FALSE; } + if (router) { + delete router; + router = NULL; + } + //delete this->_whiteboard_session_manager; } diff --git a/src/document.h b/src/document.h index da8b656ef..7cf1dc2de 100644 --- a/src/document.h +++ b/src/document.h @@ -27,6 +27,10 @@ #include "gc-finalized.h" #include "gc-anchored.h" +namespace Avoid { +class Router; +} + struct SPDesktop; struct SPItem; struct SPObject; @@ -79,6 +83,9 @@ struct SPDocument : public Inkscape::GC::Managed<>, /// Handler ID guint modified_id; + // Instance of the connector router + Avoid::Router *router; + sigc::connection connectModified(ModifiedSignal::slot_type slot); sigc::connection connectURISet(URISetSignal::slot_type slot); sigc::connection connectResized(ResizedSignal::slot_type slot); diff --git a/src/graphlayout/graphlayout.cpp b/src/graphlayout/graphlayout.cpp index ba3ca6e10..00829dac8 100644 --- a/src/graphlayout/graphlayout.cpp +++ b/src/graphlayout/graphlayout.cpp @@ -108,7 +108,7 @@ void graphlayout(GSList const *const items) { SPItem *iu=*i; std::cout<<"Getting neighbours for id: "<id<id]; - GSList *nlist=iu->avoidRef->getAttachedShapes(Avoid::ConnRef::runningFrom); + GSList *nlist=iu->avoidRef->getAttachedShapes(Avoid::runningFrom); std::list neighbours; neighbours.insert >(neighbours.end(),nlist,NULL); for (std::list::iterator j(neighbours.begin()); diff --git a/src/libavoid/Makefile_insert b/src/libavoid/Makefile_insert index 146344813..aac4595a2 100644 --- a/src/libavoid/Makefile_insert +++ b/src/libavoid/Makefile_insert @@ -14,12 +14,12 @@ libavoid_libavoid_a_SOURCES = \ libavoid/geomtypes.h \ libavoid/graph.cpp \ libavoid/graph.h \ - libavoid/incremental.cpp \ - libavoid/incremental.h \ libavoid/makepath.cpp \ libavoid/makepath.h \ libavoid/polyutil.cpp \ libavoid/polyutil.h \ + libavoid/router.cpp \ + libavoid/router.h \ libavoid/shape.cpp \ libavoid/shape.h \ libavoid/static.cpp \ diff --git a/src/libavoid/connector.cpp b/src/libavoid/connector.cpp index 4d5821741..d8c299ba0 100644 --- a/src/libavoid/connector.cpp +++ b/src/libavoid/connector.cpp @@ -2,7 +2,7 @@ * vim: ts=4 sw=4 et tw=0 wm=0 * * libavoid - Fast, Incremental, Object-avoiding Line Router - * Copyright (C) 2004-2005 Michael Wybrow + * 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 @@ -20,21 +20,21 @@ * */ -#include "libavoid/connector.h" #include "libavoid/graph.h" +#include "libavoid/connector.h" #include "libavoid/makepath.h" #include "libavoid/visibility.h" #include "libavoid/debug.h" +#include "libavoid/router.h" namespace Avoid { -ConnRefList connRefs; - - -ConnRef::ConnRef(const unsigned int id) - : _id(id) +ConnRef::ConnRef(Router *router, const unsigned int id) + : _router(router) + , _id(id) + , _type(ConnType_PolyLine) , _srcId(0) , _dstId(0) , _needs_reroute_flag(true) @@ -53,8 +53,11 @@ ConnRef::ConnRef(const unsigned int id) } -ConnRef::ConnRef(const unsigned int id, const Point& src, const Point& dst) - : _id(id) +ConnRef::ConnRef(Router *router, const unsigned int id, + const Point& src, const Point& dst) + : _router(router) + , _id(id) + , _type(ConnType_PolyLine) , _srcId(0) , _dstId(0) , _needs_reroute_flag(true) @@ -70,13 +73,13 @@ ConnRef::ConnRef(const unsigned int id, const Point& src, const Point& dst) _route.pn = 0; _route.ps = NULL; - if (IncludeEndpoints) + if (_router->IncludeEndpoints) { bool isShape = false; - _srcVert = new VertInf(VertID(id, isShape, 1), src); - _dstVert = new VertInf(VertID(id, isShape, 2), dst); - vertices.addVertex(_srcVert); - vertices.addVertex(_dstVert); + _srcVert = new VertInf(_router, VertID(id, isShape, 1), src); + _dstVert = new VertInf(_router, VertID(id, isShape, 2), dst); + _router->vertices.addVertex(_srcVert); + _router->vertices.addVertex(_dstVert); makeActive(); _initialised = true; } @@ -89,14 +92,14 @@ ConnRef::~ConnRef() if (_srcVert) { - vertices.removeVertex(_srcVert); + _router->vertices.removeVertex(_srcVert); delete _srcVert; _srcVert = NULL; } if (_dstVert) { - vertices.removeVertex(_dstVert); + _router->vertices.removeVertex(_dstVert); delete _dstVert; _dstVert = NULL; } @@ -107,6 +110,13 @@ ConnRef::~ConnRef() } } + +void ConnRef::setType(unsigned int type) +{ + _type = type; +} + + void ConnRef::updateEndPoint(const unsigned int type, const Point& point) { assert((type == (unsigned int) VertID::src) || @@ -131,8 +141,8 @@ void ConnRef::updateEndPoint(const unsigned int type, const Point& point) } else { - _srcVert = new VertInf(VertID(_id, isShape, type), point); - vertices.addVertex(_srcVert); + _srcVert = new VertInf(_router, VertID(_id, isShape, type), point); + _router->vertices.addVertex(_srcVert); } altered = _srcVert; @@ -146,8 +156,8 @@ void ConnRef::updateEndPoint(const unsigned int type, const Point& point) } else { - _dstVert = new VertInf(VertID(_id, isShape, type), point); - vertices.addVertex(_dstVert); + _dstVert = new VertInf(_router, VertID(_id, isShape, type), point); + _router->vertices.addVertex(_dstVert); } altered = _dstVert; @@ -177,7 +187,7 @@ void ConnRef::makeActive(void) assert(!_active); // Add to connRefs list. - _pos = connRefs.insert(connRefs.begin(), this); + _pos = _router->connRefs.insert(_router->connRefs.begin(), this); _active = true; } @@ -187,7 +197,7 @@ void ConnRef::makeInactive(void) assert(_active); // Remove from connRefs list. - connRefs.erase(_pos); + _router->connRefs.erase(_pos); _active = false; } @@ -240,10 +250,10 @@ void ConnRef::lateSetup(const Point& src, const Point& dst) assert(!_initialised); bool isShape = false; - _srcVert = new VertInf(VertID(_id, isShape, 1), src); - _dstVert = new VertInf(VertID(_id, isShape, 2), dst); - vertices.addVertex(_srcVert); - vertices.addVertex(_dstVert); + _srcVert = new VertInf(_router, VertID(_id, isShape, 1), src); + _dstVert = new VertInf(_router, VertID(_id, isShape, 2), dst); + _router->vertices.addVertex(_srcVert); + _router->vertices.addVertex(_dstVert); makeActive(); _initialised = true; } @@ -269,8 +279,8 @@ bool ConnRef::isInitialised(void) void ConnRef::unInitialise(void) { - vertices.removeVertex(_srcVert); - vertices.removeVertex(_dstVert); + _router->vertices.removeVertex(_srcVert); + _router->vertices.removeVertex(_dstVert); makeInactive(); _initialised = false; } @@ -327,6 +337,12 @@ void ConnRef::makePathInvalid(void) } +Router *ConnRef::router(void) +{ + return _router; +} + + int ConnRef::generatePath(Point p0, Point p1) { if (!_false_path && !_needs_reroute_flag) { @@ -340,7 +356,7 @@ int ConnRef::generatePath(Point p0, Point p1) VertInf *src = _srcVert; VertInf *tar = _dstVert; - if (!IncludeEndpoints) + if ( !(_router->IncludeEndpoints) ) { lateSetup(p0, p1); @@ -368,7 +384,7 @@ int ConnRef::generatePath(Point p0, Point p1) db_printf("Warning: Path not found...\n"); pathlen = 2; tar->pathNext = src; - if (InvisibilityGrph) + if (_router->InvisibilityGrph) { // TODO: Could we know this edge already? EdgeInf *edge = EdgeInf::existingEdge(src, tar); @@ -389,7 +405,7 @@ int ConnRef::generatePath(Point p0, Point p1) int j = pathlen - 1; for (VertInf *i = tar; i != src; i = i->pathNext) { - if (InvisibilityGrph) + if (_router->InvisibilityGrph) { // TODO: Again, we could know this edge without searching. EdgeInf *edge = EdgeInf::existingEdge(i, i->pathNext); @@ -416,69 +432,6 @@ int ConnRef::generatePath(Point p0, Point p1) //============================================================================ -const unsigned int ConnRef::runningTo = 1; -const unsigned int ConnRef::runningFrom = 2; -const unsigned int ConnRef::runningToAndFrom = - ConnRef::runningTo | ConnRef::runningFrom; - -// XXX: attachedShapes and attachedConns both need to be rewritten -// for constant time lookup of attached objects once this info -// is stored better within libavoid. - - - // Returns a list of connector Ids of all the connectors of type - // 'type' attached to the shape with the ID 'shapeId'. -void 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 & ConnRef::runningTo) && ((*i)->_dstId == shapeId)) { - conns.push_back((*i)->_srcId); - } - else if ((type & ConnRef::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 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 & ConnRef::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 & ConnRef::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 callbackAllInvalidConnectors(void) -{ - ConnRefList::iterator fin = connRefs.end(); - for (ConnRefList::iterator i = connRefs.begin(); i != fin; ++i) { - (*i)->handleInvalid(); - } -} - - } diff --git a/src/libavoid/connector.h b/src/libavoid/connector.h index a08b9ab8a..81f79641f 100644 --- a/src/libavoid/connector.h +++ b/src/libavoid/connector.h @@ -2,7 +2,7 @@ * vim: ts=4 sw=4 et tw=0 wm=0 * * libavoid - Fast, Incremental, Object-avoiding Line Router - * Copyright (C) 2004-2005 Michael Wybrow + * 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 @@ -23,6 +23,7 @@ #ifndef AVOID_CONNECTOR_H #define AVOID_CONNECTOR_H +#include "libavoid/router.h" #include "libavoid/geometry.h" #include "libavoid/shape.h" #include @@ -30,19 +31,20 @@ namespace Avoid { -class ConnRef; -typedef std::list ConnRefList; -typedef std::list IntList; +static const int ConnType_PolyLine = 1; +static const int ConnType_Orthogonal = 2; class ConnRef { public: - ConnRef(const unsigned int id); - ConnRef(const unsigned int id, const Point& src, const Point& dst); + ConnRef(Router *router, const unsigned int id); + ConnRef(Router *router, const unsigned int id, + const Point& src, const Point& dst); ~ConnRef(); + void setType(unsigned int type); PolyLine& route(void); bool needsReroute(void); void moveRoute(const int& diff_x, const int& diff_y); @@ -62,19 +64,18 @@ class ConnRef void handleInvalid(void); int generatePath(Point p0, Point p1); void makePathInvalid(void); + Router *router(void); - friend void markConnectors(ShapeRef *shape); - friend void attachedShapes(IntList &shapes, + friend void Router::attachedShapes(IntList &shapes, const unsigned int shapeId, const unsigned int type); - friend void attachedConns(IntList &conns, + friend void Router::attachedConns(IntList &conns, const unsigned int shapeId, const unsigned int type); - - static const unsigned int runningTo; - static const unsigned int runningFrom; - static const unsigned int runningToAndFrom; + friend void Router::markConnectors(ShapeRef *shape); private: + Router *_router; unsigned int _id; + unsigned int _type; unsigned int _srcId, _dstId; bool _needs_reroute_flag; bool _false_path; @@ -90,14 +91,6 @@ class ConnRef }; -extern ConnRefList connRefs; - -extern void callbackAllInvalidConnectors(void); -extern void attachedConns(IntList &conns, const unsigned int shapeId, - const unsigned int type); -extern void attachedShapes(IntList &shapes, const unsigned int shapeId, - const unsigned int type); - } diff --git a/src/libavoid/debug.h b/src/libavoid/debug.h index 0b182d442..1a6879e85 100644 --- a/src/libavoid/debug.h +++ b/src/libavoid/debug.h @@ -2,7 +2,7 @@ * vim: ts=4 sw=4 et tw=0 wm=0 * * libavoid - Fast, Incremental, Object-avoiding Line Router - * Copyright (C) 2004-2005 Michael Wybrow + * 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 diff --git a/src/libavoid/geometry.cpp b/src/libavoid/geometry.cpp index d720693ac..20f045231 100644 --- a/src/libavoid/geometry.cpp +++ b/src/libavoid/geometry.cpp @@ -2,7 +2,7 @@ * vim: ts=4 sw=4 et tw=0 wm=0 * * libavoid - Fast, Incremental, Object-avoiding Line Router - * Copyright (C) 2004-2005 Michael Wybrow + * Copyright (C) 2004-2006 Michael Wybrow * * -------------------------------------------------------------------- * Much of the code in this module is based on code published with @@ -27,6 +27,7 @@ */ #include "libavoid/graph.h" +#include "libavoid/geometry.h" #include "libavoid/polyutil.h" #include @@ -103,8 +104,8 @@ bool segmentIntersect(const Point& a, const Point& b, const Point& c, // // Based on the code of 'InCone'. // -bool inValidRegion(const Point& a0, const Point& a1, const Point& a2, - const Point& b) +bool inValidRegion(bool IgnoreRegions, const Point& a0, const Point& a1, + const Point& a2, const Point& b) { int rSide = vecDir(b, a0, a1); int sSide = vecDir(b, a1, a2); diff --git a/src/libavoid/geometry.h b/src/libavoid/geometry.h index 500da6273..07bfd5d33 100644 --- a/src/libavoid/geometry.h +++ b/src/libavoid/geometry.h @@ -2,7 +2,7 @@ * vim: ts=4 sw=4 et tw=0 wm=0 * * libavoid - Fast, Incremental, Object-avoiding Line Router - * Copyright (C) 2004-2005 Michael Wybrow + * Copyright (C) 2004-2006 Michael Wybrow * * -------------------------------------------------------------------- * Much of the code in this module is based on code published with @@ -39,8 +39,8 @@ extern double dist(const Point& a, const Point& b); 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 inValidRegion(const Point& a0, const Point& a1, const Point& a2, - const Point& b); +extern bool inValidRegion(bool IgnoreRegions, const Point& a0, + const Point& a1, const Point& a2, const Point& b); // Direction from vector. diff --git a/src/libavoid/geomtypes.h b/src/libavoid/geomtypes.h index 9b682759a..53f58af81 100644 --- a/src/libavoid/geomtypes.h +++ b/src/libavoid/geomtypes.h @@ -2,7 +2,7 @@ * vim: ts=4 sw=4 et tw=0 wm=0 * * libavoid - Fast, Incremental, Object-avoiding Line Router - * Copyright (C) 2004-2005 Michael Wybrow + * 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 @@ -55,6 +55,8 @@ typedef struct Point b; } Edge; +typedef Edge BBox; + } diff --git a/src/libavoid/graph.cpp b/src/libavoid/graph.cpp index 05b59a79d..5e41f79f5 100644 --- a/src/libavoid/graph.cpp +++ b/src/libavoid/graph.cpp @@ -2,7 +2,7 @@ * vim: ts=4 sw=4 et tw=0 wm=0 * * libavoid - Fast, Incremental, Object-avoiding Line Router - * Copyright (C) 2004-2005 Michael Wybrow + * 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 @@ -23,29 +23,34 @@ #include "libavoid/debug.h" #include "libavoid/graph.h" #include "libavoid/connector.h" +#include "libavoid/geometry.h" #include "libavoid/polyutil.h" #include "libavoid/timer.h" +#include "libavoid/vertices.h" +#include "libavoid/router.h" #include namespace Avoid { -static int st_checked_edges = 0; - -EdgeList visGraph; -EdgeList invisGraph; - - EdgeInf::EdgeInf(VertInf *v1, VertInf *v2) : lstPrev(NULL) , lstNext(NULL) + , _router(NULL) , _added(false) , _visible(false) , _v1(v1) , _v2(v2) , _dist(-1) { + // Not passed NULL values. + assert(v1 && v2); + + // We are in the same instance + assert(_v1->_router == _v2->_router); + _router = _v1->_router; + _blockers.clear(); _conns.clear(); } @@ -66,7 +71,7 @@ void EdgeInf::makeActive(void) if (_visible) { - visGraph.addEdge(this); + _router->visGraph.addEdge(this); _pos1 = _v1->visList.insert(_v1->visList.begin(), this); _v1->visListSize++; _pos2 = _v2->visList.insert(_v2->visList.begin(), this); @@ -74,7 +79,7 @@ void EdgeInf::makeActive(void) } else // if (invisible) { - invisGraph.addEdge(this); + _router->invisGraph.addEdge(this); _pos1 = _v1->invisList.insert(_v1->invisList.begin(), this); _v1->invisListSize++; _pos2 = _v2->invisList.insert(_v2->invisList.begin(), this); @@ -90,7 +95,7 @@ void EdgeInf::makeInactive(void) if (_visible) { - visGraph.removeEdge(this); + _router->visGraph.removeEdge(this); _v1->visList.erase(_pos1); _v1->visListSize--; _v2->visList.erase(_pos2); @@ -98,7 +103,7 @@ void EdgeInf::makeInactive(void) } else // if (invisible) { - invisGraph.removeEdge(this); + _router->invisGraph.removeEdge(this); _v1->invisList.erase(_pos1); _v1->invisListSize--; _v2->invisList.erase(_pos2); @@ -159,7 +164,7 @@ void EdgeInf::addCycleBlocker(void) void EdgeInf::addBlocker(int b) { - assert(InvisibilityGrph); + assert(_router->InvisibilityGrph); if (_added && _visible) { @@ -178,7 +183,7 @@ void EdgeInf::addBlocker(int b) bool EdgeInf::hasBlocker(int b) { - assert(InvisibilityGrph); + assert(_router->InvisibilityGrph); ShapeList::iterator finish = _blockers.end(); for (ShapeList::iterator it = _blockers.begin(); it != finish; ++it) @@ -245,16 +250,16 @@ void EdgeInf::checkVis(void) const Point& iPoint = i->point; const Point& jPoint = j->point; - st_checked_edges++; + _router->st_checked_edges++; if (iID.isShape) { - cone1 = inValidRegion(i->shPrev->point, iPoint, i->shNext->point, - jPoint); + cone1 = inValidRegion(_router->IgnoreRegions, i->shPrev->point, + iPoint, i->shNext->point, jPoint); } else { - ShapeSet& ss = contains[iID]; + ShapeSet& ss = _router->contains[iID]; if ((jID.isShape) && (ss.find(jID.objID) != ss.end())) { @@ -270,12 +275,12 @@ void EdgeInf::checkVis(void) // If outside the first cone, don't even bother checking. if (jID.isShape) { - cone2 = inValidRegion(j->shPrev->point, jPoint, j->shNext->point, - iPoint); + cone2 = inValidRegion(_router->IgnoreRegions, j->shPrev->point, + jPoint, j->shNext->point, iPoint); } else { - ShapeSet& ss = contains[jID]; + ShapeSet& ss = _router->contains[jID]; if ((iID.isShape) && (ss.find(iID.objID) != ss.end())) { @@ -299,7 +304,7 @@ void EdgeInf::checkVis(void) setDist(d); } - else if (InvisibilityGrph) + else if (_router->InvisibilityGrph) { #if 0 db_printf("%d, %d, %d\n", cone1, cone2, blocker); @@ -325,6 +330,7 @@ int EdgeInf::firstBlocker(void) VertID& iID = _v1->id; VertID& jID = _v2->id; + ContainsMap &contains = _router->contains; if (!(iID.isShape)) { ss.insert(contains[iID].begin(), contains[iID].end()); @@ -334,8 +340,8 @@ int EdgeInf::firstBlocker(void) ss.insert(contains[jID].begin(), contains[jID].end()); } - VertInf *last = vertices.end(); - for (VertInf *k = vertices.shapesBegin(); k != last; ) + VertInf *last = _router->vertices.end(); + for (VertInf *k = _router->vertices.shapesBegin(); k != last; ) { VertID kID = k->id; if ((ss.find(kID.objID) != ss.end())) @@ -391,6 +397,7 @@ VertInf *EdgeInf::otherVert(VertInf *vert) EdgeInf *EdgeInf::checkEdgeVisibility(VertInf *i, VertInf *j, bool knownNew) { + Router *router = i->_router; EdgeInf *edge = NULL; if (knownNew) @@ -407,7 +414,7 @@ EdgeInf *EdgeInf::checkEdgeVisibility(VertInf *i, VertInf *j, bool knownNew) } } edge->checkVis(); - if (!(edge->_added) && !InvisibilityGrph) + if (!(edge->_added) && !(router->InvisibilityGrph)) { delete edge; edge = NULL; @@ -546,441 +553,6 @@ EdgeInf *EdgeList::end(void) } -// General visibility graph utility functions - - -void 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 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 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 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 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 adjustContainsWithDel(const int p_shape) -{ - for (VertInf *k = vertices.connsBegin(); k != vertices.shapesBegin(); - k = k->lstNext) - { - contains[k->id].erase(p_shape); - } -} - - -// Maybe this one should be in with the connector stuff, but it may later -// need to operate on a particular section of the visibility graph so it -// may have to stay here. -// -#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 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 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"); -} - - } diff --git a/src/libavoid/graph.h b/src/libavoid/graph.h index d30f394cf..080309d52 100644 --- a/src/libavoid/graph.h +++ b/src/libavoid/graph.h @@ -2,7 +2,7 @@ * vim: ts=4 sw=4 et tw=0 wm=0 * * libavoid - Fast, Incremental, Object-avoiding Line Router - * Copyright (C) 2004-2005 Michael Wybrow + * 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 @@ -28,20 +28,12 @@ #include #include using std::pair; - #include "libavoid/vertices.h" - namespace Avoid { - -extern bool UseAStarSearch; -extern bool IgnoreRegions; -extern bool SelectiveReroute; -extern bool IncludeEndpoints; -extern bool UseLeesAlgorithm; -extern bool InvisibilityGrph; -extern bool PartialFeedback; +class ConnRef; +class Router; typedef std::list ShapeList; @@ -72,6 +64,7 @@ class EdgeInf EdgeInf *lstPrev; EdgeInf *lstNext; private: + Router *_router; bool _added; bool _visible; VertInf *_v1; @@ -104,21 +97,6 @@ class EdgeList }; -extern EdgeList visGraph; -extern EdgeList invisGraph; - -class ShapeRef; - -extern void newBlockingShape(Polygn *poly, int pid); -extern void checkAllBlockedEdges(int pid); -extern void checkAllMissingEdges(void); -extern void generateContains(VertInf *pt); -extern void adjustContainsWithAdd(const Polygn& poly, const int p_shape); -extern void adjustContainsWithDel(const int p_shape); -extern void markConnectors(ShapeRef *shape); -extern void printInfo(void); - - } diff --git a/src/libavoid/incremental.cpp b/src/libavoid/incremental.cpp deleted file mode 100644 index f7d48ac70..000000000 --- a/src/libavoid/incremental.cpp +++ /dev/null @@ -1,139 +0,0 @@ -/* - * vim: ts=4 sw=4 et tw=0 wm=0 - * - * libavoid - Fast, Incremental, Object-avoiding Line Router - * Copyright (C) 2004-2005 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/connector.h" -#include "libavoid/graph.h" -#include "libavoid/visibility.h" - -namespace Avoid { - - -void 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 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 *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(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; -} - - -} - diff --git a/src/libavoid/incremental.h b/src/libavoid/incremental.h deleted file mode 100644 index 6bc69a6a7..000000000 --- a/src/libavoid/incremental.h +++ /dev/null @@ -1,40 +0,0 @@ -/* - * vim: ts=4 sw=4 et tw=0 wm=0 - * - * libavoid - Fast, Incremental, Object-avoiding Line Router - * Copyright (C) 2004-2005 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 - * -*/ - - -#ifndef AVOID_INCREMENTAL_H -#define AVOID_INCREMENTAL_H - -#include "libavoid/shape.h" - - -namespace Avoid { - -extern void addShape(ShapeRef *shape); -extern void delShape(ShapeRef *shape); -extern ShapeRef *moveShape(ShapeRef *oldShape, Polygn *newPoly, - const bool first_move = false); - -} - - -#endif diff --git a/src/libavoid/libavoid.h b/src/libavoid/libavoid.h index 0b6c7a819..d598c6c74 100644 --- a/src/libavoid/libavoid.h +++ b/src/libavoid/libavoid.h @@ -2,7 +2,7 @@ * vim: ts=4 sw=4 et tw=0 wm=0 * * libavoid - Fast, Incremental, Object-avoiding Line Router - * Copyright (C) 2004-2005 Michael Wybrow + * 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 @@ -33,7 +33,7 @@ #include "libavoid/vertices.h" #include "libavoid/visibility.h" #include "libavoid/static.h" -#include "libavoid/incremental.h" +#include "libavoid/router.h" #endif diff --git a/src/libavoid/makepath.cpp b/src/libavoid/makepath.cpp index 37b4f1801..5f3ef3ac6 100644 --- a/src/libavoid/makepath.cpp +++ b/src/libavoid/makepath.cpp @@ -2,7 +2,7 @@ * vim: ts=4 sw=4 et tw=0 wm=0 * * libavoid - Fast, Incremental, Object-avoiding Line Router - * Copyright (C) 2004-2005 Michael Wybrow + * Copyright (C) 2004-2006 Michael Wybrow * * -------------------------------------------------------------------- * The dijkstraPath function is based on code published and described @@ -25,8 +25,12 @@ * */ +#include "libavoid/vertices.h" +#include "libavoid/makepath.h" +#include "libavoid/geometry.h" #include "libavoid/connector.h" #include "libavoid/graph.h" +#include "libavoid/router.h" #include #include @@ -108,11 +112,13 @@ double cost(const double dist, VertInf *inf1, // static void dijkstraPath(VertInf *src, VertInf *tar) { + Router *router = src->_router; + double unseen = (double) INT_MAX; // initialize arrays - VertInf *finish = vertices.end(); - for (VertInf *t = vertices.connsBegin(); t != finish; t = t->lstNext) + VertInf *finish = router->vertices.end(); + for (VertInf *t = router->vertices.connsBegin(); t != finish; t = t->lstNext) { t->pathNext = NULL; t->pathDist = -unseen; @@ -399,12 +405,13 @@ static void aStarPath(VertInf *src, VertInf *tar) // void makePath(ConnRef *lineRef, bool *flag) { + Router *router = lineRef->router(); VertInf *src = lineRef->src(); VertInf *tar = lineRef->dst(); // TODO: Could be more efficient here. EdgeInf *directEdge = EdgeInf::existingEdge(src, tar); - if (!IncludeEndpoints && directVis(src, tar)) + if (!(router->IncludeEndpoints) && directVis(src, tar)) { Point p = src->point; Point q = tar->point; @@ -418,7 +425,8 @@ void makePath(ConnRef *lineRef, bool *flag) return; } - else if (IncludeEndpoints && directEdge && (directEdge->getDist() > 0)) + else if (router->IncludeEndpoints && directEdge && + (directEdge->getDist() > 0)) { tar->pathNext = src; directEdge->addConn(flag); @@ -427,7 +435,7 @@ void makePath(ConnRef *lineRef, bool *flag) { // Mark the path endpoints as not being able to see // each other. This is true if we are here. - if (!IncludeEndpoints && InvisibilityGrph) + if (!(router->IncludeEndpoints) && router->InvisibilityGrph) { if (!directEdge) { @@ -436,7 +444,7 @@ void makePath(ConnRef *lineRef, bool *flag) directEdge->addBlocker(0); } - if (UseAStarSearch) + if (router->UseAStarSearch) { aStarPath(src, tar); } diff --git a/src/libavoid/makepath.h b/src/libavoid/makepath.h index 5ab21b993..4d68a01e3 100644 --- a/src/libavoid/makepath.h +++ b/src/libavoid/makepath.h @@ -2,7 +2,7 @@ * vim: ts=4 sw=4 et tw=0 wm=0 * * libavoid - Fast, Incremental, Object-avoiding Line Router - * Copyright (C) 2004-2005 Michael Wybrow + * 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 @@ -23,13 +23,10 @@ #ifndef AVOID_MAKEPATH_H #define AVOID_MAKEPATH_H -#include "libavoid/connector.h" namespace Avoid { - -extern double segmt_penalty; -extern double angle_penalty; +class ConnRef; extern void makePath(ConnRef *lineRef, bool *flag); diff --git a/src/libavoid/polyutil.cpp b/src/libavoid/polyutil.cpp index 6ece50e63..3ce4cf64f 100644 --- a/src/libavoid/polyutil.cpp +++ b/src/libavoid/polyutil.cpp @@ -2,7 +2,7 @@ * vim: ts=4 sw=4 et tw=0 wm=0 * * libavoid - Fast, Incremental, Object-avoiding Line Router - * Copyright (C) 2004-2005 Michael Wybrow + * 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 @@ -20,7 +20,12 @@ * */ +#include +#include +#include "libavoid/polyutil.h" +#include "libavoid/geomtypes.h" +#include "libavoid/vertices.h" #include "libavoid/shape.h" namespace Avoid { diff --git a/src/libavoid/polyutil.h b/src/libavoid/polyutil.h index 456e190fb..9340df5f4 100644 --- a/src/libavoid/polyutil.h +++ b/src/libavoid/polyutil.h @@ -2,7 +2,7 @@ * vim: ts=4 sw=4 et tw=0 wm=0 * * libavoid - Fast, Incremental, Object-avoiding Line Router - * Copyright (C) 2004-2005 Michael Wybrow + * 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 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"); +} + + +} + diff --git a/src/libavoid/router.h b/src/libavoid/router.h new file mode 100644 index 000000000..bcb4ea67c --- /dev/null +++ b/src/libavoid/router.h @@ -0,0 +1,105 @@ +/* + * 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 + * +*/ + + +#ifndef AVOID_ROUTER_H +#define AVOID_ROUTER_H + +//#define LINEDEBUG + +#include "libavoid/shape.h" +#include "libavoid/graph.h" +#include "libavoid/timer.h" +#ifdef LINEDEBUG + #include +#endif + + +namespace Avoid { + +class ConnRef; +typedef std::list ConnRefList; +typedef std::list IntList; + + +static const unsigned int runningTo = 1; +static const unsigned int runningFrom = 2; +static const unsigned int runningToAndFrom = runningTo | runningFrom; + + +class Router { + public: + Router(); + + ShapeRefList shapeRefs; + ConnRefList connRefs; + EdgeList visGraph; + EdgeList invisGraph; + ContainsMap contains; + VertInfList vertices; + + bool PartialTime; + double segmt_penalty; + double angle_penalty; + + bool UseAStarSearch; + bool IgnoreRegions; + bool SelectiveReroute; + bool IncludeEndpoints; + bool UseLeesAlgorithm; + bool InvisibilityGrph; + bool PartialFeedback; + + // Instrumentation: + Timer timers; + int st_checked_edges; +#ifdef LINEDEBUG + SDL_Surface *avoid_screen; +#endif + + void addShape(ShapeRef *shape); + void delShape(ShapeRef *shape); + ShapeRef *moveShape(ShapeRef *oldShape, Polygn *newPoly, + const bool first_move = false); + + void attachedConns(IntList &conns, const unsigned int shapeId, + const unsigned int type); + void attachedShapes(IntList &shapes, const unsigned int shapeId, + const unsigned int type); + + void markConnectors(ShapeRef *shape); + void generateContains(VertInf *pt); + void printInfo(void); + private: + void newBlockingShape(Polygn *poly, int pid); + void checkAllBlockedEdges(int pid); + void checkAllMissingEdges(void); + void adjustContainsWithAdd(const Polygn& poly, const int p_shape); + void adjustContainsWithDel(const int p_shape); + void callbackAllInvalidConnectors(void); +}; + +} + + + +#endif diff --git a/src/libavoid/shape.cpp b/src/libavoid/shape.cpp index 431950801..f2fd6d6b3 100644 --- a/src/libavoid/shape.cpp +++ b/src/libavoid/shape.cpp @@ -2,7 +2,7 @@ * vim: ts=4 sw=4 et tw=0 wm=0 * * libavoid - Fast, Incremental, Object-avoiding Line Router - * Copyright (C) 2004-2005 Michael Wybrow + * 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 @@ -20,19 +20,21 @@ * */ +#include +#include "libavoid/shape.h" #include "libavoid/graph.h" // For alertConns +#include "libavoid/vertices.h" #include "libavoid/polyutil.h" +#include "libavoid/router.h" namespace Avoid { -ShapeRefList shapeRefs; - - -ShapeRef::ShapeRef(unsigned int id, Polygn& ply) - : _id(id) +ShapeRef::ShapeRef(Router *router, unsigned int id, Polygn& ply) + : _router(router) + , _id(id) , _poly(copyPoly(ply)) , _active(false) , _firstVert(NULL) @@ -45,7 +47,7 @@ ShapeRef::ShapeRef(unsigned int id, Polygn& ply) VertInf *node = NULL; for (int pt_i = 0; pt_i < _poly.pn; pt_i++) { - node = new VertInf(i, _poly.ps[pt_i]); + node = new VertInf(_router, i, _poly.ps[pt_i]); if (!_firstVert) { @@ -58,7 +60,7 @@ ShapeRef::ShapeRef(unsigned int id, Polygn& ply) //node->lstPrev = last; //last->lstNext = node; } - vertices.addVertex(node); + _router->vertices.addVertex(node); last = node; i++; @@ -86,7 +88,7 @@ ShapeRef::~ShapeRef() // XXX: This could possibly be done less // safely but faster, all at once. - vertices.removeVertex(tmp); + _router->vertices.removeVertex(tmp); delete tmp; } while (it != _firstVert); @@ -103,7 +105,7 @@ void ShapeRef::makeActive(void) assert(!_active); // Add to connRefs list. - _pos = shapeRefs.insert(shapeRefs.begin(), this); + _pos = _router->shapeRefs.insert(_router->shapeRefs.begin(), this); _active = true; } @@ -113,7 +115,7 @@ void ShapeRef::makeInactive(void) assert(_active); // Remove from connRefs list. - shapeRefs.erase(_pos); + _router->shapeRefs.erase(_pos); _active = false; } @@ -142,6 +144,32 @@ Polygn ShapeRef::poly(void) } +Router *ShapeRef::router(void) +{ + return _router; +} + + +void ShapeRef::boundingBox(BBox& bbox) +{ + assert(_poly.pn > 0); + + bbox.a = bbox.b = _poly.ps[0]; + Point& a = bbox.a; + Point& b = bbox.b; + + for (int i = 1; i < _poly.pn; ++i) + { + const Point& p = _poly.ps[i]; + + a.x = (p.x < a.x) ? p.x : a.x; + a.y = (p.y < a.y) ? p.y : a.y; + b.x = (p.x > b.x) ? p.x : b.x; + b.y = (p.y > b.y) ? p.y : b.y; + } +} + + void ShapeRef::removeFromGraph(void) { for (VertInf *iter = firstVert(); iter != lastVert()->lstNext; ) diff --git a/src/libavoid/shape.h b/src/libavoid/shape.h index acdb36983..1960c2256 100644 --- a/src/libavoid/shape.h +++ b/src/libavoid/shape.h @@ -2,7 +2,7 @@ * vim: ts=4 sw=4 et tw=0 wm=0 * * libavoid - Fast, Incremental, Object-avoiding Line Router - * Copyright (C) 2004-2005 Michael Wybrow + * 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 @@ -29,23 +29,23 @@ namespace Avoid { -typedef unsigned int uint; - -class ShapeRef; class VertInf; - +class Router; +class ShapeRef; typedef std::list ShapeRefList; - + class ShapeRef { public: - ShapeRef(uint id, Polygn& poly); + ShapeRef(Router *router, uint id, Polygn& poly); ~ShapeRef(); VertInf *firstVert(void); VertInf *lastVert(void); uint id(void); Polygn poly(void); + Router *router(void); + void boundingBox(BBox& bbox); void makeActive(void); void makeInactive(void); @@ -53,6 +53,7 @@ class ShapeRef void removeFromGraph(void); private: + Router *_router; uint _id; Polygn _poly; bool _active; @@ -62,9 +63,6 @@ class ShapeRef }; -extern ShapeRefList shapeRefs; - - } diff --git a/src/libavoid/static.cpp b/src/libavoid/static.cpp index 72d3e3b07..11ccfd76f 100644 --- a/src/libavoid/static.cpp +++ b/src/libavoid/static.cpp @@ -2,7 +2,7 @@ * vim: ts=4 sw=4 et tw=0 wm=0 * * libavoid - Fast, Incremental, Object-avoiding Line Router - * Copyright (C) 2004-2005 Michael Wybrow + * 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 @@ -21,35 +21,62 @@ */ #include +#include +#include "libavoid/vertices.h" #include "libavoid/connector.h" +#include "libavoid/graph.h" +#include "libavoid/static.h" +#include "libavoid/shape.h" #include "libavoid/visibility.h" +#include "libavoid/debug.h" +#include "libavoid/router.h" namespace Avoid { +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. // -void CreateVisGraph(Polygn **obs, int n_obs) +void CreateVisGraph(Router *router, Polygn **obs, int n_obs) { for (int poly_i = 0; poly_i < n_obs; poly_i++) { unsigned int id = obs[poly_i]->id; - new ShapeRef(id, *(obs[poly_i])); + new ShapeRef(router, id, *(obs[poly_i])); + } + computeCompleteVis(router); +} + + +static void computeCompleteVis(Router *router) +{ + VertInf *beginVert = router->vertices.shapesBegin(); + VertInf *endVert = router->vertices.end(); + for (VertInf *i = beginVert; i != endVert; i = i->lstNext) + { + db_printf("-- CONSIDERING --\n"); + i->id.db_print(); + + for (VertInf *j = i->lstPrev ; j != NULL; j = j->lstPrev) + { + bool knownNew = true; + EdgeInf::checkEdgeVisibility(i, j, knownNew); + } } - computeCompleteVis(); } -void DestroyVisGraph(void) +void DestroyVisGraph(Router *router) { - ShapeRefList::iterator sFinish = shapeRefs.end(); + ShapeRefList::iterator sFinish = router->shapeRefs.end(); ShapeRefList::iterator sCurr; - while ((sCurr = shapeRefs.begin()) != sFinish) + while ((sCurr = router->shapeRefs.begin()) != sFinish) { ShapeRef *shape = (*sCurr); @@ -57,10 +84,10 @@ void DestroyVisGraph(void) delete shape; } - ConnRefList::iterator cFinish = connRefs.end(); + ConnRefList::iterator cFinish = router->connRefs.end(); ConnRefList::iterator cCurr; - while ((cCurr = connRefs.begin())!= cFinish) + while ((cCurr = router->connRefs.begin())!= cFinish) { ConnRef *conn = (*cCurr); @@ -68,7 +95,7 @@ void DestroyVisGraph(void) conn->unInitialise(); } - assert(vertices.connsBegin() == NULL); + assert(router->vertices.connsBegin() == NULL); } diff --git a/src/libavoid/static.h b/src/libavoid/static.h index c02c6be2f..18e9ac278 100644 --- a/src/libavoid/static.h +++ b/src/libavoid/static.h @@ -2,7 +2,7 @@ * vim: ts=4 sw=4 et tw=0 wm=0 * * libavoid - Fast, Incremental, Object-avoiding Line Router - * Copyright (C) 2004-2005 Michael Wybrow + * 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 @@ -29,8 +29,12 @@ namespace Avoid { -extern void CreateVisGraph(Polygn **obstacles, int n_obstacles); -extern void DestroyVisGraph(void); +class Router; + + +extern void CreateVisGraph(Router *router, Polygn **obstacles, + int n_obstacles); +extern void DestroyVisGraph(Router *router); } diff --git a/src/libavoid/timer.cpp b/src/libavoid/timer.cpp index 7e930d011..e4349bea9 100644 --- a/src/libavoid/timer.cpp +++ b/src/libavoid/timer.cpp @@ -2,7 +2,7 @@ * vim: ts=4 sw=4 et tw=0 wm=0 * * libavoid - Fast, Incremental, Object-avoiding Line Router - * Copyright (C) 2004-2005 Michael Wybrow + * 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 @@ -31,9 +31,6 @@ using std::abort; namespace Avoid { -Timer timers = Timer(); - - Timer::Timer() { Reset(); diff --git a/src/libavoid/timer.h b/src/libavoid/timer.h index 9446ecc51..a7e6081fa 100644 --- a/src/libavoid/timer.h +++ b/src/libavoid/timer.h @@ -2,7 +2,7 @@ * vim: ts=4 sw=4 et tw=0 wm=0 * * libavoid - Fast, Incremental, Object-avoiding Line Router - * Copyright (C) 2004-2005 Michael Wybrow + * 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 @@ -37,10 +37,10 @@ namespace Avoid { #else - #define register_timer(t) timers.Register(t) - #define regstart_timer(t) timers.Register(t, timerStart) - #define start_timer() timers.Start() - #define stop_timer() timers.Stop() + #define register_timer(t) router->timers.Register(t) + #define regstart_timer(t) router->timers.Register(t, timerStart) + #define start_timer() router->timers.Start() + #define stop_timer() router->timers.Stop() #endif @@ -85,7 +85,6 @@ class Timer int type, lasttype; }; -extern Timer timers; } diff --git a/src/libavoid/vertices.cpp b/src/libavoid/vertices.cpp index 7e74509f0..786919581 100644 --- a/src/libavoid/vertices.cpp +++ b/src/libavoid/vertices.cpp @@ -2,7 +2,7 @@ * vim: ts=4 sw=4 et tw=0 wm=0 * * libavoid - Fast, Incremental, Object-avoiding Line Router - * Copyright (C) 2004-2005 Michael Wybrow + * 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 @@ -20,18 +20,20 @@ * */ +#include "libavoid/vertices.h" #include "libavoid/geometry.h" #include "libavoid/graph.h" // For alertConns #include "libavoid/debug.h" +#include "libavoid/router.h" +#include +#include +#include namespace Avoid { -ContainsMap contains; - - VertID::VertID() { } @@ -134,8 +136,9 @@ const int VertID::src = 1; const int VertID::tar = 2; -VertInf::VertInf(const VertID& vid, const Point& vpoint) - : id(vid) +VertInf::VertInf(Router *router, const VertID& vid, const Point& vpoint) + : _router(router) + , id(vid) , point(vpoint) , lstPrev(NULL) , lstNext(NULL) @@ -195,6 +198,11 @@ bool directVis(VertInf *src, VertInf *dst) VertID& pID = src->id; VertID& qID = dst->id; + // We better be part of the same instance of libavoid. + Router *router = src->_router; + assert(router == dst->_router); + + ContainsMap& contains = router->contains; if (!(pID.isShape)) { ss.insert(contains[pID].begin(), contains[pID].end()); @@ -206,8 +214,9 @@ bool directVis(VertInf *src, VertInf *dst) // The "beginning" should be the first shape vertex, rather // than an endpoint, which are also stored in "vertices". - VertInf *endVert = vertices.end(); - for (VertInf *k = vertices.shapesBegin(); k != endVert; k = k->lstNext) + VertInf *endVert = router->vertices.end(); + for (VertInf *k = router->vertices.shapesBegin(); k != endVert; + k = k->lstNext) { if ((ss.find(k->id.objID) == ss.end())) { @@ -430,9 +439,6 @@ VertInf *VertInfList::end(void) } -VertInfList vertices; - - } diff --git a/src/libavoid/vertices.h b/src/libavoid/vertices.h index c2ff6977f..de2e30ae3 100644 --- a/src/libavoid/vertices.h +++ b/src/libavoid/vertices.h @@ -2,7 +2,7 @@ * vim: ts=4 sw=4 et tw=0 wm=0 * * libavoid - Fast, Incremental, Object-avoiding Line Router - * Copyright (C) 2004-2005 Michael Wybrow + * 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 @@ -32,6 +32,7 @@ namespace Avoid { class EdgeInf; +class Router; typedef std::list EdgeInfList; @@ -64,10 +65,11 @@ class VertID class VertInf { public: - VertInf(const VertID& vid, const Point& vpoint); + VertInf(Router *router, const VertID& vid, const Point& vpoint); void Reset(const Point& vpoint); void removeFromGraph(const bool isConnVert = true); + Router *_router; VertID id; Point point; VertInf *lstPrev; @@ -112,9 +114,6 @@ class VertInfList typedef std::set ShapeSet; typedef std::map ContainsMap; -extern ContainsMap contains; -extern VertInfList vertices; - } diff --git a/src/libavoid/visibility.cpp b/src/libavoid/visibility.cpp index 6154bd396..71c8b1c1b 100644 --- a/src/libavoid/visibility.cpp +++ b/src/libavoid/visibility.cpp @@ -2,7 +2,7 @@ * vim: ts=4 sw=4 et tw=0 wm=0 * * libavoid - Fast, Incremental, Object-avoiding Line Router - * Copyright (C) 2004-2005 Michael Wybrow + * 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 @@ -29,6 +29,7 @@ #include "libavoid/vertices.h" #include "libavoid/graph.h" #include "libavoid/geometry.h" +#include "libavoid/router.h" #include @@ -39,38 +40,11 @@ namespace Avoid { -bool UseAStarSearch = true; -bool IgnoreRegions = true; -bool SelectiveReroute = true; -bool IncludeEndpoints = true; -bool UseLeesAlgorithm = false; -bool InvisibilityGrph = true; -bool PartialFeedback = false; - -bool PartialTime = false; - - -void computeCompleteVis(void) -{ - VertInf *beginVert = vertices.shapesBegin(); - VertInf *endVert = vertices.end(); - for (VertInf *i = beginVert; i != endVert; i = i->lstNext) - { - db_printf("-- CONSIDERING --\n"); - i->id.db_print(); - - for (VertInf *j = i->lstPrev ; j != NULL; j = j->lstPrev) - { - bool knownNew = true; - EdgeInf::checkEdgeVisibility(i, j, knownNew); - } - } -} - - void shapeVis(ShapeRef *shape) { - if (!InvisibilityGrph) + Router *router = shape->router(); + + if ( !(router->InvisibilityGrph) ) { // Clear shape from graph. shape->removeFromGraph(); @@ -80,13 +54,13 @@ void shapeVis(ShapeRef *shape) VertInf *shapeEnd = shape->lastVert()->lstNext; VertInf *pointsBegin = NULL; - if (IncludeEndpoints) + if (router->IncludeEndpoints) { - pointsBegin = vertices.connsBegin(); + pointsBegin = router->vertices.connsBegin(); } else { - pointsBegin = vertices.shapesBegin(); + pointsBegin = router->vertices.shapesBegin(); } for (VertInf *curr = shapeBegin; curr != shapeEnd; curr = curr->lstNext) @@ -103,7 +77,7 @@ void shapeVis(ShapeRef *shape) } db_printf("\tSecond Half:\n"); - VertInf *pointsEnd = vertices.end(); + VertInf *pointsEnd = router->vertices.end(); for (VertInf *k = shapeEnd; k != pointsEnd; k = k->lstNext) { EdgeInf::checkEdgeVisibility(curr, k, knownNew); @@ -114,7 +88,9 @@ void shapeVis(ShapeRef *shape) void shapeVisSweep(ShapeRef *shape) { - if (!InvisibilityGrph) + Router *router = shape->router(); + + if ( !(router->InvisibilityGrph) ) { // Clear shape from graph. shape->removeFromGraph(); @@ -133,34 +109,35 @@ void shapeVisSweep(ShapeRef *shape) void vertexVisibility(VertInf *point, VertInf *partner, bool knownNew, const bool gen_contains) { + Router *router = point->_router; const VertID& pID = point->id; // Make sure we're only doing ptVis for endpoints. assert(!(pID.isShape)); - if (!InvisibilityGrph) + if ( !(router->InvisibilityGrph) ) { point->removeFromGraph(); } if (gen_contains && !(pID.isShape)) { - generateContains(point); + router->generateContains(point); } - if (UseLeesAlgorithm) + if (router->UseLeesAlgorithm) { vertexSweep(point); } else { - VertInf *shapesEnd = vertices.end(); - for (VertInf *k = vertices.shapesBegin(); k != shapesEnd; + VertInf *shapesEnd = router->vertices.end(); + for (VertInf *k = router->vertices.shapesBegin(); k != shapesEnd; k = k->lstNext) { EdgeInf::checkEdgeVisibility(point, k, knownNew); } - if (IncludeEndpoints && partner) + if (router->IncludeEndpoints && partner) { EdgeInf::checkEdgeVisibility(point, partner, knownNew); } @@ -177,10 +154,6 @@ static Point centerPoint; static VertID centerID; static double centerAngle; -#ifdef LINEDEBUG - SDL_Surface *avoid_screen = NULL; -#endif - class PointPair { @@ -385,6 +358,7 @@ static bool sweepVisible(EdgeSet& T, VertInf *currInf, VertInf *lastInf, void vertexSweep(VertInf *vert) { + Router *router = vert->_router; VertID& pID = vert->id; Point& pPoint = vert->point; @@ -399,8 +373,8 @@ void vertexSweep(VertInf *vert) VertList v; // Initialise the vertex list - VertInf *beginVert = vertices.connsBegin(); - VertInf *endVert = vertices.end(); + VertInf *beginVert = router->vertices.connsBegin(); + VertInf *endVert = router->vertices.end(); for (VertInf *inf = beginVert; inf != endVert; inf = inf->lstNext) { if (inf->id == centerID) @@ -416,7 +390,7 @@ void vertexSweep(VertInf *vert) } else { - if (IncludeEndpoints) + if (router->IncludeEndpoints) { if (centerID.isShape) { @@ -441,11 +415,11 @@ void vertexSweep(VertInf *vert) v.sort(ppCompare); EdgeSet e; - ShapeSet& ss = contains[centerID]; + ShapeSet& ss = router->contains[centerID]; // And edge to T that intersect the initial ray. - VertInf *last = vertices.end(); - for (VertInf *k = vertices.shapesBegin(); k != last; ) + VertInf *last = router->vertices.end(); + for (VertInf *k = router->vertices.shapesBegin(); k != last; ) { VertID kID = k->id; if (!(centerID.isShape) && (ss.find(kID.objID) != ss.end())) @@ -497,7 +471,7 @@ void vertexSweep(VertInf *vert) bool lastVisible = false; int lastBlocker = 0; - isBoundingShape isBounding(contains[centerID]); + isBoundingShape isBounding(router->contains[centerID]); VertList::iterator vfst = v.begin(); VertList::iterator vfin = v.end(); for (VertList::iterator t = vfst; t != vfin; ++t) @@ -526,7 +500,7 @@ void vertexSweep(VertInf *vert) // Ignore vertices from bounding shapes, if sweeping round an endpoint. if (!(centerID.isShape) && isBounding(*t)) { - if (InvisibilityGrph) + if (router->InvisibilityGrph) { // if p and t can't see each other, add blank edge db_printf("\tSkipping visibility edge... \n\t\t"); @@ -540,19 +514,21 @@ void vertexSweep(VertInf *vert) bool cone1 = true, cone2 = true; if (centerID.isShape) { - cone1 = inValidRegion(centerInf->shPrev->point, centerPoint, + cone1 = inValidRegion(router->IgnoreRegions, + centerInf->shPrev->point, centerPoint, centerInf->shNext->point, currInf->point); } if (currInf->id.isShape) { - cone2 = inValidRegion(currInf->shPrev->point, currInf->point, + cone2 = inValidRegion(router->IgnoreRegions, + currInf->shPrev->point, currInf->point, currInf->shNext->point, centerPoint); } if (!cone1 || !cone2) { lastInf = NULL; - if (InvisibilityGrph) + if (router->InvisibilityGrph) { db_printf("\tSetting invisibility edge... \n\t\t"); edge->addBlocker(0); @@ -578,7 +554,7 @@ void vertexSweep(VertInf *vert) edge->setDist(currDist); edge->db_print(); } - else if (InvisibilityGrph) + else if (router->InvisibilityGrph) { db_printf("\tSetting invisibility edge... \n\t\t"); edge->addBlocker(blocker); diff --git a/src/libavoid/visibility.h b/src/libavoid/visibility.h index edfc3b16c..dd68ac692 100644 --- a/src/libavoid/visibility.h +++ b/src/libavoid/visibility.h @@ -2,7 +2,7 @@ * vim: ts=4 sw=4 et tw=0 wm=0 * * libavoid - Fast, Incremental, Object-avoiding Line Router - * Copyright (C) 2004-2005 Michael Wybrow + * 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 @@ -26,20 +26,8 @@ #include "libavoid/vertices.h" -//#define LINEDEBUG - -#ifdef LINEDEBUG - #include -#endif - - namespace Avoid { -extern bool PartialTime; -#ifdef LINEDEBUG - extern SDL_Surface *avoid_screen; -#endif - extern void vertexVisibility(VertInf *point, VertInf *partner, bool knownNew, const bool gen_contains = false); diff --git a/src/sp-conn-end-pair.cpp b/src/sp-conn-end-pair.cpp index 5b36f8796..85d9ccce2 100644 --- a/src/sp-conn-end-pair.cpp +++ b/src/sp-conn-end-pair.cpp @@ -17,6 +17,8 @@ #include "xml/repr.h" #include "sp-path.h" #include "libavoid/vertices.h" +#include "libavoid/router.h" +#include "document.h" SPConnEndPair::SPConnEndPair(SPPath *const owner) @@ -93,8 +95,9 @@ SPConnEndPair::setAttr(unsigned const key, gchar const *const value) if (value && (strcmp(value, "polyline") == 0)) { _connType = SP_CONNECTOR_POLYLINE; + Avoid::Router *router = _path->document->router; GQuark itemID = g_quark_from_string(SP_OBJECT(_path)->id); - _connRef = new Avoid::ConnRef(itemID); + _connRef = new Avoid::ConnRef(router, itemID); _invalid_path_connection = connectInvalidPath( sigc::ptr_fun(&sp_conn_adjust_invalid_path)); _transformed_connection = _path->connectTransformed( -- 2.30.2