diff options
Diffstat (limited to 'src/libavoid/connector.cpp')
| -rw-r--r-- | src/libavoid/connector.cpp | 1902 |
1 files changed, 1283 insertions, 619 deletions
diff --git a/src/libavoid/connector.cpp b/src/libavoid/connector.cpp index 36892c668..de4206e33 100644 --- a/src/libavoid/connector.cpp +++ b/src/libavoid/connector.cpp @@ -3,7 +3,7 @@ * * libavoid - Fast, Incremental, Object-avoiding Line Router * - * Copyright (C) 2004-2009 Monash University + * Copyright (C) 2004-2014 Monash University * * This library is free software; you can redistribute it and/or * modify it under the terms of the GNU Lesser General Public @@ -19,7 +19,7 @@ * but WITHOUT ANY WARRANTY; without even the implied warranty of * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. * - * Author(s): Michael Wybrow <mjwybrow@users.sourceforge.net> + * Author(s): Michael Wybrow */ @@ -27,297 +27,288 @@ #include <cfloat> #include <cmath> #include <cstdlib> +#include <algorithm> +#include <queue> +#include <limits> -#include "libavoid/graph.h" #include "libavoid/connector.h" -#include "libavoid/makepath.h" +#include "libavoid/connend.h" +#include "libavoid/router.h" #include "libavoid/visibility.h" #include "libavoid/debug.h" -#include "libavoid/router.h" #include "libavoid/assertions.h" +#include "libavoid/junction.h" +#include "libavoid/makepath.h" +#include "libavoid/debughandler.h" namespace Avoid { -ConnEnd::ConnEnd(const Point& point) - : _point(point), - _directions(ConnDirAll), - _shapeRef(NULL) +ConnRef::ConnRef(Router *router, const unsigned int id) + : m_router(router), + m_type(router->validConnType()), + m_reroute_flag_ptr(NULL), + m_needs_reroute_flag(true), + m_false_path(false), + m_needs_repaint(false), + m_active(false), + m_hate_crossings(false), + m_has_fixed_route(false), + m_route_dist(0), + m_src_vert(NULL), + m_dst_vert(NULL), + m_start_vert(NULL), + m_callback_func(NULL), + m_connector(NULL), + m_src_connend(NULL), + m_dst_connend(NULL) { -} + COLA_ASSERT(m_router != NULL); + m_id = m_router->assignId(id); + // TODO: Store endpoints and details. + m_route.clear(); -ConnEnd::ConnEnd(const Point& point, const ConnDirFlags visDirs) - : _point(point), - _directions(visDirs), - _shapeRef(NULL) -{ + m_reroute_flag_ptr = m_router->m_conn_reroute_flags.addConn(this); } -ConnEnd::ConnEnd(ShapeRef *shapeRef, const double x_pos, const double y_pos, - const double insideOffset, const ConnDirFlags visDirs) - : _directions(visDirs), - _shapeRef(shapeRef), - _xPosition(x_pos), - _yPosition(y_pos), - _insideOffset(insideOffset) + +ConnRef::ConnRef(Router *router, const ConnEnd& src, const ConnEnd& dst, + const unsigned int id) + : m_router(router), + m_type(router->validConnType()), + m_reroute_flag_ptr(NULL), + m_needs_reroute_flag(true), + m_false_path(false), + m_needs_repaint(false), + m_active(false), + m_hate_crossings(false), + m_has_fixed_route(false), + m_route_dist(0), + m_src_vert(NULL), + m_dst_vert(NULL), + m_callback_func(NULL), + m_connector(NULL), + m_src_connend(NULL), + m_dst_connend(NULL) { + COLA_ASSERT(m_router != NULL); + m_id = m_router->assignId(id); + m_route.clear(); + + // Set endpoint values. + setEndpoints(src, dst); + + m_reroute_flag_ptr = m_router->m_conn_reroute_flags.addConn(this); } -const Point ConnEnd::point(void) const -{ - if (_shapeRef) - { - const Polygon& poly = _shapeRef->polygon(); - double x_min = DBL_MAX; - double x_max = -DBL_MAX; - double y_min = DBL_MAX; - double y_max = -DBL_MAX; - for (size_t i = 0; i < poly.size(); ++i) - { - x_min = std::min(x_min, poly.ps[i].x); - x_max = std::max(x_max, poly.ps[i].x); - y_min = std::min(y_min, poly.ps[i].y); - y_max = std::max(y_max, poly.ps[i].y); - } +ConnRef::~ConnRef() +{ + COLA_ASSERT(m_router); - Point point; + if (m_router->m_currently_calling_destructors == false) + { + err_printf("ERROR: ConnRef::~ConnRef() shouldn't be called directly.\n"); + err_printf(" It is owned by the router. Call Router::deleteConnector() instead.\n"); + abort(); + } - // We want to place connection points on the edges of shapes, - // or possibly slightly inside them (if _insideOfset is set). + m_router->m_conn_reroute_flags.removeConn(this); - point.vn = kUnassignedVertexNumber; - if (_xPosition == ATTACH_POS_LEFT) - { - point.x = x_min + _insideOffset; - point.vn = 6; - } - else if (_xPosition == ATTACH_POS_RIGHT) - { - point.x = x_max - _insideOffset; - point.vn = 4; - } - else - { - point.x = x_min + (_xPosition * (x_max - x_min)); - } + m_router->removeObjectFromQueuedActions(this); - if (_yPosition == ATTACH_POS_TOP) - { - point.y = y_max - _insideOffset; - point.vn = 5; - } - else if (_yPosition == ATTACH_POS_BOTTOM) - { - point.y = y_min + _insideOffset; - point.vn = 7; - } - else - { - point.y = y_min + (_yPosition * (y_max - y_min)); - point.vn = kUnassignedVertexNumber; - } + freeRoutes(); - return point; + if (m_src_vert) + { + m_src_vert->removeFromGraph(); + m_router->vertices.removeVertex(m_src_vert); + delete m_src_vert; + m_src_vert = NULL; } - else + if (m_src_connend) { - return _point; + m_src_connend->disconnect(); + m_src_connend->freeActivePin(); + delete m_src_connend; + m_src_connend = NULL; } -} - -ConnDirFlags ConnEnd::directions(void) const -{ - if (_shapeRef) + if (m_dst_vert) { - ConnDirFlags visDir = _directions; - if (_directions == ConnDirNone) - { - // None is set, use the defaults: - if (_xPosition == ATTACH_POS_LEFT) - { - visDir = ConnDirLeft; - } - else if (_xPosition == ATTACH_POS_RIGHT) - { - visDir = ConnDirRight; - } - if (_yPosition == ATTACH_POS_TOP) - { - visDir = ConnDirDown; - } - else if (_yPosition == ATTACH_POS_BOTTOM) - { - visDir = ConnDirUp; - } - - if (visDir == ConnDirNone) - { - visDir = ConnDirAll; - } - } - return visDir; + m_dst_vert->removeFromGraph(); + m_router->vertices.removeVertex(m_dst_vert); + delete m_dst_vert; + m_dst_vert = NULL; } - else + if (m_dst_connend) { - return _directions; + m_dst_connend->disconnect(); + m_dst_connend->freeActivePin(); + delete m_dst_connend; + m_dst_connend = NULL; } -} + // Clear checkpoint vertices. + for (size_t i = 0; i < m_checkpoint_vertices.size(); ++i) + { + m_checkpoint_vertices[i]->removeFromGraph(true); + m_router->vertices.removeVertex(m_checkpoint_vertices[i]); + delete m_checkpoint_vertices[i]; + } + m_checkpoint_vertices.clear(); -ConnRef::ConnRef(Router *router, const unsigned int id) - : _router(router), - _type(router->validConnType()), - _srcId(0), - _dstId(0), - _needs_reroute_flag(true), - _false_path(false), - _needs_repaint(false), - _active(false), - _route_dist(0), - _srcVert(NULL), - _dstVert(NULL), - _startVert(NULL), - _initialised(false), - _callback(NULL), - _connector(NULL), - _hateCrossings(false) -{ - _id = router->assignId(id); - - // TODO: Store endpoints and details. - _route.clear(); + if (m_active) + { + makeInactive(); + } } -ConnRef::ConnRef(Router *router, const ConnEnd& src, const ConnEnd& dst, - const unsigned int id) - : _router(router), - _type(router->validConnType()), - _srcId(0), - _dstId(0), - _needs_reroute_flag(true), - _false_path(false), - _needs_repaint(false), - _active(false), - _route_dist(0), - _srcVert(NULL), - _dstVert(NULL), - _initialised(false), - _callback(NULL), - _connector(NULL), - _hateCrossings(false) -{ - _id = router->assignId(id); - _route.clear(); - - bool isShape = false; - _srcVert = new VertInf(_router, VertID(_id, isShape, 1), src.point()); - _srcVert->visDirections = src.directions(); - _dstVert = new VertInf(_router, VertID(_id, isShape, 2), dst.point()); - _dstVert->visDirections = dst.directions(); - makeActive(); - _initialised = true; - - setEndpoints(src, dst); +ConnType ConnRef::routingType(void) const +{ + return m_type; } -ConnRef::~ConnRef() +void ConnRef::setRoutingType(ConnType type) { - _router->removeQueuedConnectorActions(this); - removeFromGraph(); - - freeRoutes(); - - if (_srcVert) + type = m_router->validConnType(type); + if (m_type != type) { - _router->vertices.removeVertex(_srcVert); - delete _srcVert; - _srcVert = NULL; - } + m_type = type; - if (_dstVert) - { - _router->vertices.removeVertex(_dstVert); - delete _dstVert; - _dstVert = NULL; - } + makePathInvalid(); - makeInactive(); + m_router->modifyConnector(this); + } } -ConnType ConnRef::routingType(void) const +std::vector<Checkpoint> ConnRef::routingCheckpoints(void) const { - return _type; + return m_checkpoints; } -void ConnRef::setRoutingType(ConnType type) +void ConnRef::setRoutingCheckpoints(const std::vector<Checkpoint>& checkpoints) { - type = _router->validConnType(type); - if (_type != type) + m_checkpoints = checkpoints; + + // Clear previous checkpoint vertices. + for (size_t i = 0; i < m_checkpoint_vertices.size(); ++i) { - _type = type; + m_checkpoint_vertices[i]->removeFromGraph(true); + m_router->vertices.removeVertex(m_checkpoint_vertices[i]); + delete m_checkpoint_vertices[i]; + } + m_checkpoint_vertices.clear(); - makePathInvalid(); + for (size_t i = 0; i < m_checkpoints.size(); ++i) + { + VertID ptID(m_id, 2 + i, + VertID::PROP_ConnPoint | VertID::PROP_ConnCheckpoint); + VertInf *vertex = new VertInf(m_router, ptID, m_checkpoints[i].point); + vertex->visDirections = ConnDirAll; - _router->modifyConnector(this); + m_checkpoint_vertices.push_back(vertex); + } + if (m_router->m_allows_polyline_routing) + { + for (size_t i = 0; i < m_checkpoints.size(); ++i) + { + vertexVisibility(m_checkpoint_vertices[i], NULL, true, true); + } } } -void ConnRef::common_updateEndPoint(const unsigned int type, const ConnEnd& connEnd) +void ConnRef::common_updateEndPoint(const unsigned int type, ConnEnd connEnd) { - const Point& point = connEnd.point(); + const Point& point = connEnd.position(); //db_printf("common_updateEndPoint(%d,(pid=%d,vn=%d,(%f,%f)))\n", // type,point.id,point.vn,point.x,point.y); COLA_ASSERT((type == (unsigned int) VertID::src) || (type == (unsigned int) VertID::tar)); - - if (!_initialised) + + // The connEnd is a copy of a ConnEnd that will get disconnected, + // so don't leave it looking like it is still connected. + connEnd.m_conn_ref = NULL; + + if (!m_active) { makeActive(); - _initialised = true; } VertInf *altered = NULL; - // VertInf *partner = NULL; - bool isShape = false; + VertIDProps properties = VertID::PROP_ConnPoint; + if (connEnd.isPinConnection()) + { + properties |= VertID::PROP_DummyPinHelper; + } + VertID ptID(m_id, type, properties); if (type == (unsigned int) VertID::src) { - if (_srcVert) + if (m_src_vert) { - _srcVert->Reset(VertID(_id, isShape, type), point); + m_src_vert->Reset(ptID, point); } else { - _srcVert = new VertInf(_router, VertID(_id, isShape, type), point); + m_src_vert = new VertInf(m_router, ptID, point); + } + m_src_vert->visDirections = connEnd.directions(); + + if (m_src_connend) + { + m_src_connend->disconnect(); + m_src_connend->freeActivePin(); + delete m_src_connend; + m_src_connend = NULL; + } + if (connEnd.isPinConnection()) + { + m_src_connend = new ConnEnd(connEnd); + m_src_connend->connect(this); + // Don't need this to have visibility since we won't + // be connecting to it. + m_src_vert->visDirections = ConnDirNone; } - _srcVert->visDirections = connEnd.directions(); - altered = _srcVert; - // partner = _dstVert; + altered = m_src_vert; } else // if (type == (unsigned int) VertID::tar) { - if (_dstVert) + if (m_dst_vert) { - _dstVert->Reset(VertID(_id, isShape, type), point); + m_dst_vert->Reset(ptID, point); } else { - _dstVert = new VertInf(_router, VertID(_id, isShape, type), point); + m_dst_vert = new VertInf(m_router, ptID, point); } - _dstVert->visDirections = connEnd.directions(); + m_dst_vert->visDirections = connEnd.directions(); - altered = _dstVert; - // partner = _srcVert; + if (m_dst_connend) + { + m_dst_connend->disconnect(); + m_dst_connend->freeActivePin(); + delete m_dst_connend; + m_dst_connend = NULL; + } + if (connEnd.isPinConnection()) + { + m_dst_connend = new ConnEnd(connEnd); + m_dst_connend->connect(this); + // Don't need this to have visibility since we won't + // be connecting to it. + m_dst_vert->visDirections = ConnDirNone; + } + + altered = m_dst_vert; } // XXX: Seems to be faster to just remove the edges and recreate @@ -325,32 +316,77 @@ void ConnRef::common_updateEndPoint(const unsigned int type, const ConnEnd& conn altered->removeFromGraph(isConn); makePathInvalid(); - _router->setStaticGraphInvalidated(true); + m_router->setStaticGraphInvalidated(true); } void ConnRef::setEndpoints(const ConnEnd& srcPoint, const ConnEnd& dstPoint) { - _router->modifyConnector(this, VertID::src, srcPoint); - _router->modifyConnector(this, VertID::tar, dstPoint); + m_router->modifyConnector(this, VertID::src, srcPoint); + m_router->modifyConnector(this, VertID::tar, dstPoint); } void ConnRef::setEndpoint(const unsigned int type, const ConnEnd& connEnd) { - _router->modifyConnector(this, type, connEnd); + m_router->modifyConnector(this, type, connEnd); } void ConnRef::setSourceEndpoint(const ConnEnd& srcPoint) { - _router->modifyConnector(this, VertID::src, srcPoint); + m_router->modifyConnector(this, VertID::src, srcPoint); } void ConnRef::setDestEndpoint(const ConnEnd& dstPoint) { - _router->modifyConnector(this, VertID::tar, dstPoint); + m_router->modifyConnector(this, VertID::tar, dstPoint); +} + + +// Given the start or end vertex of a connector, returns the ConnEnd that +// can be used to reproduce that endpoint. This is used for hyperedge routing. +// +bool ConnRef::getConnEndForEndpointVertex(VertInf *vertex, + ConnEnd& connEnd) const +{ + if (vertex == NULL) + { + err_printf("Warning: In ConnRef::getConnEndForEndpointVertex():\n" + " ConnEnd for connector %d is uninitialised. It may have been\n" + " set but Router::processTrancaction has not yet been called.\n", + (int) id()); + return false; + } + + if (vertex == m_src_vert) + { + if (m_src_connend) + { + connEnd = *m_src_connend; + } + else + { + connEnd = ConnEnd(Point(m_src_vert->point.x, m_src_vert->point.y), + m_src_vert->visDirections); + } + return true; + } + else if (vertex == m_dst_vert) + { + if (m_dst_connend) + { + connEnd = *m_dst_connend; + } + else + { + connEnd = ConnEnd(Point(m_dst_vert->point.x, m_dst_vert->point.y), + m_dst_vert->visDirections); + } + return true; + } + return false; } @@ -358,26 +394,132 @@ void ConnRef::updateEndPoint(const unsigned int type, const ConnEnd& connEnd) { common_updateEndPoint(type, connEnd); - if (_router->_polyLineRouting) + if (m_has_fixed_route) + { + // Don't need to continue and compute visibility if route is fixed. + return; + } + + if (m_router->m_allows_polyline_routing) { bool knownNew = true; bool genContains = true; if (type == (unsigned int) VertID::src) { - vertexVisibility(_srcVert, _dstVert, knownNew, genContains); + bool dummySrc = m_src_connend && m_src_connend->isPinConnection(); + if (!dummySrc) + { + // Only generate visibility if not attached to a pin. + vertexVisibility(m_src_vert, m_dst_vert, knownNew, genContains); + } } else { - vertexVisibility(_dstVert, _srcVert, knownNew, genContains); + bool dummyDst = m_dst_connend && m_dst_connend->isPinConnection(); + if (!dummyDst) + { + // Only generate visibility if not attached to a pin. + vertexVisibility(m_dst_vert, m_src_vert, knownNew, genContains); + } + } + } +} + + +void ConnRef::outputCode(FILE *fp) const +{ + fprintf(fp, " // connRef%u\n", id()); + fprintf(fp, " connRef = new ConnRef(router, %u);\n", id()); + if (m_src_connend) + { + m_src_connend->outputCode(fp, "src"); + fprintf(fp, " connRef->setSourceEndpoint(srcPt);\n"); + } + else if (src()) + { + fprintf(fp, " srcPt = ConnEnd(Point(%" PREC "g, %" PREC "g), %u);\n", + src()->point.x, src()->point.y, src()->visDirections); + fprintf(fp, " connRef->setSourceEndpoint(srcPt);\n"); + } + if (m_dst_connend) + { + m_dst_connend->outputCode(fp, "dst"); + fprintf(fp, " connRef->setDestEndpoint(dstPt);\n"); + } + else if (dst()) + { + fprintf(fp, " dstPt = ConnEnd(Point(%" PREC "g, %" PREC "g), %u);\n", + dst()->point.x, dst()->point.y, dst()->visDirections); + fprintf(fp, " connRef->setDestEndpoint(dstPt);\n"); + } + fprintf(fp, " connRef->setRoutingType((ConnType)%u);\n", routingType()); + + if (m_has_fixed_route) + { + PolyLine currRoute = route(); + fprintf(fp, " newRoute._id = %u;\n", id()); + fprintf(fp, " newRoute.ps.resize(%d);\n", (int)currRoute.size()); + for (size_t i = 0; i < currRoute.size(); ++i) + { + fprintf(fp, " newRoute.ps[%d] = Point(%" PREC "g, %" PREC "g);\n", + (int) i, currRoute.ps[i].x, currRoute.ps[i].y); + fprintf(fp, " newRoute.ps[%d].id = %u;\n", + (int) i, currRoute.ps[i].id); + fprintf(fp, " newRoute.ps[%d].vn = %u;\n", + (int) i, currRoute.ps[i].vn); + } + fprintf(fp, " connRef->setFixedRoute(newRoute);\n"); + } + + if (!m_checkpoints.empty()) + { + fprintf(fp, " std::vector<Checkpoint> checkpoints%u(%d);\n", id(), + (int) m_checkpoints.size()); + for (size_t cInd = 0; cInd < m_checkpoints.size(); ++cInd) + { + fprintf(fp, " checkpoints%u[%d] = Checkpoint(Point(" + "%" PREC "g, %" PREC "g), (ConnDirFlags) %d, " + "(ConnDirFlags) %d);\n", id(), (int) cInd, + m_checkpoints[cInd].point.x, m_checkpoints[cInd].point.y, + m_checkpoints[cInd].arrivalDirections, + m_checkpoints[cInd].departureDirections); } + fprintf(fp, " connRef->setRoutingCheckpoints(checkpoints%u);\n", + id()); + } + fprintf(fp, "\n"); +} + + +std::pair<Obstacle *, Obstacle *> ConnRef::endpointAnchors(void) const +{ + std::pair<Obstacle *, Obstacle *> anchors; + anchors.first = NULL; + anchors.second = NULL; + + if (m_src_connend) + { + anchors.first = m_src_connend->m_anchor_obj; + } + if (m_dst_connend) + { + anchors.second = m_dst_connend->m_anchor_obj; } + return anchors; } +std::pair<ConnEnd, ConnEnd> ConnRef::endpointConnEnds(void) const +{ + std::pair<ConnEnd, ConnEnd> endpoints; + getConnEndForEndpointVertex(m_src_vert, endpoints.first); + getConnEndForEndpointVertex(m_dst_vert, endpoints.second); + return endpoints; +} bool ConnRef::setEndpoint(const unsigned int type, const VertID& pointID, Point *pointSuggestion) { - VertInf *vInf = _router->vertices.getVertexByID(pointID); + VertInf *vInf = m_router->vertices.getVertexByID(pointID); if (vInf == NULL) { return false; @@ -395,217 +537,266 @@ bool ConnRef::setEndpoint(const unsigned int type, const VertID& pointID, // Give this visibility just to the point it is over. EdgeInf *edge = new EdgeInf( - (type == VertID::src) ? _srcVert : _dstVert, vInf); + (type == VertID::src) ? m_src_vert : m_dst_vert, vInf); // XXX: We should be able to set this to zero, but can't due to // assumptions elsewhere in the code. edge->setDist(0.001); - _router->processTransaction(); + m_router->processTransaction(); return true; } -void ConnRef::setEndPointId(const unsigned int type, const unsigned int id) -{ - if (type == (unsigned int) VertID::src) - { - _srcId = id; - } - else // if (type == (unsigned int) VertID::dst) - { - _dstId = id; - } -} - - -unsigned int ConnRef::getSrcShapeId(void) -{ - return _srcId; -} - - -unsigned int ConnRef::getDstShapeId(void) +void ConnRef::makeActive(void) { - return _dstId; + COLA_ASSERT(!m_active); + + // Add to connRefs list. + m_connrefs_pos = m_router->connRefs.insert(m_router->connRefs.begin(), this); + m_active = true; } -void ConnRef::makeActive(void) +void ConnRef::freeActivePins(void) { - COLA_ASSERT(!_active); - - // Add to connRefs list. - _pos = _router->connRefs.insert(_router->connRefs.begin(), this); - _active = true; + if (m_src_connend) + { + m_src_connend->freeActivePin(); + } + if (m_dst_connend) + { + m_dst_connend->freeActivePin(); + } } void ConnRef::makeInactive(void) { - if (_active) { - // Remove from connRefs list. - _router->connRefs.erase(_pos); - _active = false; - } + COLA_ASSERT(m_active); + + // Remove from connRefs list. + m_router->connRefs.erase(m_connrefs_pos); + m_active = false; } void ConnRef::freeRoutes(void) { - _route.clear(); - _display_route.clear(); + m_route.clear(); + m_display_route.clear(); } const PolyLine& ConnRef::route(void) const { - return _route; + return m_route; } PolyLine& ConnRef::routeRef(void) { - return _route; + return m_route; } void ConnRef::set_route(const PolyLine& route) { - if (&_display_route == &route) + if (&m_display_route == &route) { db_printf("Error:\tTrying to update libavoid route with itself.\n"); return; } - _display_route.ps = route.ps; + m_display_route.ps = route.ps; //_display_route.clear(); } +void ConnRef::setFixedExistingRoute(void) +{ + COLA_ASSERT(m_route.size() >= 2); + m_has_fixed_route = true; + m_router->registerSettingsChange(); +} + +void ConnRef::setFixedRoute(const PolyLine& route) +{ + if (route.size() >= 2) + { + // Set endpoints based on the fixed route incase the + // fixed route is later cleared. + setEndpoints(route.ps[0], route.ps[route.size() - 1]); + } + m_has_fixed_route = true; + m_route = route; + m_display_route = m_route.simplify(); + m_router->registerSettingsChange(); +} + +bool ConnRef::hasFixedRoute(void) const +{ + return m_has_fixed_route; +} + +void ConnRef::clearFixedRoute(void) +{ + m_has_fixed_route = false; + makePathInvalid(); + m_router->registerSettingsChange(); +} Polygon& ConnRef::displayRoute(void) { - if (_display_route.empty()) + if (m_display_route.empty()) { // No displayRoute is set. Simplify the current route to get it. - _display_route = _route.simplify(); + m_display_route = m_route.simplify(); } - return _display_route; + return m_display_route; } void ConnRef::calcRouteDist(void) { double (*dist)(const Point& a, const Point& b) = - (_type == ConnType_PolyLine) ? euclideanDist : manhattanDist; + (m_type == ConnType_PolyLine) ? euclideanDist : manhattanDist; - _route_dist = 0; - for (size_t i = 1; i < _route.size(); ++i) + m_route_dist = 0; + for (size_t i = 1; i < m_route.size(); ++i) { - _route_dist += dist(_route.at(i), _route.at(i - 1)); + m_route_dist += dist(m_route.at(i), m_route.at(i - 1)); } } bool ConnRef::needsRepaint(void) const { - return _needs_repaint; + return m_needs_repaint; } unsigned int ConnRef::id(void) const { - return _id; + return m_id; } -VertInf *ConnRef::src(void) +Point midpoint(Point a, Point b) { - return _srcVert; + Point midpoint; + + midpoint.x = (a.x + b.x) / 2.0; + midpoint.y = (a.y + b.y) / 2.0; + + return midpoint; +} + + +std::pair<JunctionRef *, ConnRef *> ConnRef::splitAtSegment( + const size_t segmentN) +{ + ConnRef *newConn = NULL; + JunctionRef *newJunction = NULL; + + if (m_display_route.size() > segmentN) + { + // Position the junction at the midpoint of the desired segment. + Point junctionPos = midpoint(m_display_route.at(segmentN - 1), + m_display_route.at(segmentN)); + + // Create the new junction. + newJunction = new JunctionRef(router(), junctionPos); + router()->addJunction(newJunction); + newJunction->preferOrthogonalDimension( + (m_display_route.at(segmentN - 1).x == + m_display_route.at(segmentN).x) ? YDIM : XDIM); + + // Create a new connection routing from the junction to the original + // connector's endpoint. + ConnEnd newConnSrc = ConnEnd(newJunction); + ConnEnd newConnDst = *m_dst_connend; + newConn = new ConnRef(router(), newConnSrc, newConnDst); + + // Reroute the endpoint of the original connector to attach to the + // new junction. + ConnEnd oldConnDst = ConnEnd(newJunction); + this->setDestEndpoint(oldConnDst); + } + + return std::make_pair(newJunction, newConn); +} + + +VertInf *ConnRef::src(void) const +{ + return m_src_vert; } -VertInf *ConnRef::dst(void) +VertInf *ConnRef::dst(void) const { - return _dstVert; + return m_dst_vert; } VertInf *ConnRef::start(void) { - return _startVert; + return m_start_vert; } -bool ConnRef::isInitialised(void) +bool ConnRef::isInitialised(void) const { - return _initialised; + return m_active; } void ConnRef::unInitialise(void) { - _router->vertices.removeVertex(_srcVert); - _router->vertices.removeVertex(_dstVert); + m_router->vertices.removeVertex(m_src_vert); + m_router->vertices.removeVertex(m_dst_vert); makeInactive(); - _initialised = false; } void ConnRef::removeFromGraph(void) { - if (_srcVert) { - _srcVert->removeFromGraph(); + if (m_src_vert) + { + m_src_vert->removeFromGraph(); } - if (_dstVert) { - _dstVert->removeFromGraph(); + + if (m_dst_vert) + { + m_dst_vert->removeFromGraph(); } } void ConnRef::setCallback(void (*cb)(void *), void *ptr) { - _callback = cb; - _connector = ptr; + m_callback_func = cb; + m_connector = ptr; } void ConnRef::performCallback(void) { - if (_callback) + if (m_callback_func) { - _callback(_connector); + m_callback_func(m_connector); } } void ConnRef::makePathInvalid(void) { - _needs_reroute_flag = true; + m_needs_reroute_flag = true; } Router *ConnRef::router(void) const { - return _router; -} - - -bool ConnRef::generatePath(Point /*p0*/, Point /*p1*/) -{ - // XXX Code to determine when connectors really need to be rerouted - // does not yet work for orthogonal connectors. - if (_type != ConnType_Orthogonal) - { - if (!_false_path && !_needs_reroute_flag) - { - // This connector is up to date. - return false; - } - } - - bool result = generatePath(); - - return result; + return m_router; } @@ -615,6 +806,11 @@ bool ConnRef::generatePath(Point /*p0*/, Point /*p1*/) // bool validateBendPoint(VertInf *aInf, VertInf *bInf, VertInf *cInf) { + if (bInf->id.isConnectionPin() || bInf->id.isConnCheckpoint()) + { + // We shouldn't check connection pins or checkpoints. + return true; + } bool bendOkay = true; if ((aInf == NULL) || (cInf == NULL)) @@ -656,9 +852,10 @@ bool validateBendPoint(VertInf *aInf, VertInf *bInf, VertInf *cInf) if (abc == 0) { // The three consecutive point on the path are in a line. - // Thus, there should always be an equally short path that - // skips this bend point. - bendOkay = false; + // There should always be an equally short path that skips this + // bend point, but this check is used during rubber-band routing + // so we allow this case. + bendOkay = true; } else // (abc != 0) { @@ -695,40 +892,288 @@ bool validateBendPoint(VertInf *aInf, VertInf *bInf, VertInf *cInf) } +std::pair<bool, bool> ConnRef::assignConnectionPinVisibility(const bool connect) +{ + // XXX This is kind of a hack for connection pins. Probably we want to + // not use m_src_vert and m_dst_vert. For the moment we will clear + // their visibility and give them visibility to the pins. + bool dummySrc = m_src_connend && m_src_connend->isPinConnection(); + if (dummySrc) + { + m_src_vert->removeFromGraph(); + if (connect) + { + m_src_connend->assignPinVisibilityTo(m_src_vert, m_dst_vert); + } + } + bool dummyDst = m_dst_connend && m_dst_connend->isPinConnection(); + if (dummyDst) + { + m_dst_vert->removeFromGraph(); + if (connect) + { + m_dst_connend->assignPinVisibilityTo(m_dst_vert, m_src_vert); + } + } + + return std::make_pair(dummySrc, dummyDst); +} + + bool ConnRef::generatePath(void) { - if (!_false_path && !_needs_reroute_flag) + // XXX Currently rubber-band routing only works when dragging the + // destination point of a connector, but not the source. The code + // needs to be reworked to work in both directions. + + if (!m_false_path && !m_needs_reroute_flag) { // This connector is up to date. return false; } - if (!_dstVert || !_srcVert) + if (!m_dst_vert || !m_src_vert) { - // Connector is not fully initialised.. + // Connector is not fully initialised. return false; } //COLA_ASSERT(_srcVert->point != _dstVert->point); - _false_path = false; - _needs_reroute_flag = false; + m_false_path = false; + m_needs_reroute_flag = false; - VertInf *tar = _dstVert; - _startVert = _srcVert; + m_start_vert = m_src_vert; - bool *flag = &(_needs_reroute_flag); - + // Some connectors may attach to connection pins, which means they route + // to the closest of multiple pins on a shape. How we handle this is to + // add a dummy vertex as the source or target vertex. This is then given + // visibility to each of the possible pins and tiny distance. Here we + // assign this visibility by adding edges to the visibility graph that we + // later remove. + std::pair<bool, bool> isDummyAtEnd = assignConnectionPinVisibility(true); + + + if (m_router->RubberBandRouting && route().size() > 0) + { + if (isDummyAtEnd.first) + { + //ShapeConnectionPin *activePin = m_src_connend->active + Point firstPoint = m_src_vert->point; + firstPoint.id = m_src_vert->id.objID; + firstPoint.vn = m_src_vert->id.vn; + PolyLine& existingRoute = routeRef(); + existingRoute.ps.insert(existingRoute.ps.begin(), 1, firstPoint); + } + } + + std::vector<Point> path; + std::vector<VertInf *> vertices; + if (m_checkpoints.empty()) + { + generateStandardPath(path, vertices); + } + else + { + generateCheckpointsPath(path, vertices); + } + + COLA_ASSERT(vertices.size() >= 2); + COLA_ASSERT(vertices[0] == src()); + COLA_ASSERT(vertices[vertices.size() - 1] == dst()); + COLA_ASSERT(m_reroute_flag_ptr != NULL); + + for (size_t i = 1; i < vertices.size(); ++i) + { + if (m_router->InvisibilityGrph && (m_type == ConnType_PolyLine)) + { + // TODO: Again, we could know this edge without searching. + EdgeInf *edge = EdgeInf::existingEdge(vertices[i - 1], vertices[i]); + if (edge) { + edge->addConn(m_reroute_flag_ptr); + } + } + else + { + m_false_path = true; + } + + VertInf *vertex = vertices[i]; + if (vertex->pathNext && + (vertex->pathNext->point == vertex->point)) + { + if (!(vertex->pathNext->id.isConnPt()) && !(vertex->id.isConnPt())) + { + // Check for consecutive points on opposite + // corners of two touching shapes. + COLA_ASSERT(abs(vertex->pathNext->id.vn - vertex->id.vn) != 2); + } + } + } + + // Get rid of dummy ShapeConnectionPin bridging points at beginning + // and end of path. + std::vector<Point> clippedPath; + std::vector<Point>::iterator pathBegin = path.begin(); + std::vector<Point>::iterator pathEnd = path.end(); + if (path.size() > 2 && isDummyAtEnd.first) + { + ++pathBegin; + m_src_connend->usePinVertex(vertices[1]); + } + if (path.size() > 2 && isDummyAtEnd.second) + { + --pathEnd; + m_dst_connend->usePinVertex(vertices[vertices.size() - 2]); + } + clippedPath.insert(clippedPath.end(), pathBegin, pathEnd); + + // Clear visibility edges added for connection pins dummy vertices. + assignConnectionPinVisibility(false); + + freeRoutes(); + PolyLine& output_route = m_route; + output_route.ps = clippedPath; + +#ifdef PATHDEBUG + db_printf("Output route:\n"); + for (size_t i = 0; i < output_route.ps.size(); ++i) + { + db_printf("[%d,%d] %g, %g ", output_route.ps[i].id, + output_route.ps[i].vn, output_route.ps[i].x, + output_route.ps[i].y); + } + db_printf("\n\n"); +#endif + +#ifdef DEBUGHANDLER + if (m_router->debugHandler()) + { + m_router->debugHandler()->updateConnectorRoute(this, -1, -1); + } +#endif + + return true; +} + +void ConnRef::generateCheckpointsPath(std::vector<Point>& path, + std::vector<VertInf *>& vertices) +{ + std::vector<VertInf *> checkpoints = m_checkpoint_vertices; + checkpoints.insert(checkpoints.begin(), src()); + checkpoints.push_back(dst()); + + path.clear(); + vertices.clear(); + path.push_back(src()->point); + vertices.push_back(src()); + + size_t lastSuccessfulIndex = 0; + for (size_t i = 1; i < checkpoints.size(); ++i) + { + VertInf *start = checkpoints[lastSuccessfulIndex]; + VertInf *end = checkpoints[i]; + + // Handle checkpoint directions by disabling some visibility edges. + if (lastSuccessfulIndex > 0) + { + Checkpoint& srcCP = m_checkpoints[lastSuccessfulIndex - 1]; + if (srcCP.departureDirections != ConnDirAll) + { + start->setVisibleDirections(srcCP.departureDirections); + } + } + if ((i + 1) < checkpoints.size()) + { + Checkpoint& dstCP = m_checkpoints[i - 1]; + if (dstCP.arrivalDirections != ConnDirAll) + { + end->setVisibleDirections(dstCP.arrivalDirections); + } + } + + AStarPath aStar; + // Route the connector + aStar.search(this, start, end, NULL); + + // Restore changes made for checkpoint visibility directions. + if (lastSuccessfulIndex > 0) + { + start->setVisibleDirections(ConnDirAll); + } + if ((i + 1) < checkpoints.size()) + { + end->setVisibleDirections(ConnDirAll); + } + + // Process the path. + int pathlen = end->pathLeadsBackTo(start); + if (pathlen >= 2) + { + size_t prev_path_size = path.size(); + path.resize(prev_path_size + (pathlen - 1)); + vertices.resize(prev_path_size + (pathlen - 1)); + VertInf *vertInf = end; + for (size_t index = path.size() - 1; index >= prev_path_size; + --index) + { + path[index] = vertInf->point; + if (vertInf->id.isConnPt()) + { + path[index].id = m_id; + path[index].vn = kUnassignedVertexNumber; + } + else + { + path[index].id = vertInf->id.objID; + path[index].vn = vertInf->id.vn; + } + vertices[index] = vertInf; + vertInf = vertInf->pathNext; + } + lastSuccessfulIndex = i; + } + else if (i + 1 == checkpoints.size()) + { + // There is no valid path. + db_printf("Warning: Path not found...\n"); + m_needs_reroute_flag = true; + + path.push_back(dst()->point); + vertices.push_back(dst()); + + COLA_ASSERT(path.size() >= 2); + } + else + { + err_printf("Warning: skipping checkpoint for connector " + "%d at (%g, %g).\n", (int) id(), + checkpoints[i]->point.x, checkpoints[i]->point.y); + fflush(stderr); + } + } + // Use topbit to differentiate between start and end point of connector. + // They need unique IDs for nudging. + unsigned int topbit = ((unsigned int) 1) << 31; + path[path.size() - 1].id = m_id | topbit; + path[path.size() - 1].vn = kUnassignedVertexNumber; +} + + +void ConnRef::generateStandardPath(std::vector<Point>& path, + std::vector<VertInf *>& vertices) +{ + VertInf *tar = m_dst_vert; size_t existingPathStart = 0; const PolyLine& currRoute = route(); - if (_router->RubberBandRouting) + if (m_router->RubberBandRouting) { - COLA_ASSERT(_router->IgnoreRegions == true); + COLA_ASSERT(m_router->IgnoreRegions == true); #ifdef PATHDEBUG db_printf("\n"); - _srcVert->id.db_print(); - db_printf(": %g, %g\n", _srcVert->point.x, _srcVert->point.y); + src()->id.db_print(); + db_printf(": %g, %g\n", src()->point.x, src()->point.y); tar->id.db_print(); db_printf(": %g, %g\n", tar->point.x, tar->point.y); for (size_t i = 0; i < currRoute.ps.size(); ++i) @@ -739,33 +1184,27 @@ bool ConnRef::generatePath(void) #endif if (currRoute.size() > 2) { - if (_srcVert->point == currRoute.ps[0]) + if (m_src_vert->point == currRoute.ps[0]) { existingPathStart = currRoute.size() - 2; COLA_ASSERT(existingPathStart != 0); const Point& pnt = currRoute.at(existingPathStart); - bool isShape = true; - VertID vID(pnt.id, isShape, pnt.vn); + VertID vID(pnt.id, pnt.vn); - _startVert = _router->vertices.getVertexByID(vID); + m_start_vert = m_router->vertices.getVertexByID(vID); + COLA_ASSERT(m_start_vert); } } } //db_printf("GO\n"); - //db_printf("src: %X strt: %X dst: %x\n", (int) _srcVert, (int) _startVert, (int) _dstVert); - bool found = false; - while (!found) + //db_printf("src: %X strt: %X dst: %X\n", (int) m_src_vert, (int) m_start_vert, (int) m_dst_vert); + unsigned int pathlen = 0; + while (pathlen == 0) { - makePath(this, flag); - for (VertInf *i = tar; i != NULL; i = i->pathNext) - { - if (i == _srcVert) - { - found = true; - break; - } - } - if (!found) + AStarPath aStar; + aStar.search(this, src(), dst(), start()); + pathlen = dst()->pathLeadsBackTo(src()); + if (pathlen < 2) { if (existingPathStart == 0) { @@ -776,13 +1215,14 @@ bool ConnRef::generatePath(void) #endif existingPathStart--; const Point& pnt = currRoute.at(existingPathStart); - bool isShape = (existingPathStart > 0); - VertID vID(pnt.id, isShape, pnt.vn); + VertIDProps props = (existingPathStart > 0) ? 0 : + VertID::PROP_ConnPoint; + VertID vID(pnt.id, pnt.vn, props); - _startVert = _router->vertices.getVertexByID(vID); - COLA_ASSERT(_startVert); + m_start_vert = m_router->vertices.getVertexByID(vID); + COLA_ASSERT(m_start_vert); } - else if (_router->RubberBandRouting) + else if (m_router->RubberBandRouting) { // found. bool unwind = false; @@ -791,7 +1231,7 @@ bool ConnRef::generatePath(void) db_printf("\n\n\nSTART:\n\n"); #endif VertInf *prior = NULL; - for (VertInf *curr = tar; curr != _startVert->pathNext; + for (VertInf *curr = tar; curr != m_start_vert->pathNext; curr = curr->pathNext) { if (!validateBendPoint(curr->pathNext, curr, prior)) @@ -812,243 +1252,233 @@ bool ConnRef::generatePath(void) } existingPathStart--; const Point& pnt = currRoute.at(existingPathStart); - bool isShape = (existingPathStart > 0); - VertID vID(pnt.id, isShape, pnt.vn); + VertIDProps props = (existingPathStart > 0) ? 0 : + VertID::PROP_ConnPoint; + VertID vID(pnt.id, pnt.vn, props); - _startVert = _router->vertices.getVertexByID(vID); - COLA_ASSERT(_startVert); + m_start_vert = m_router->vertices.getVertexByID(vID); + COLA_ASSERT(m_start_vert); - found = false; + pathlen = 0; } } } - - bool result = true; - - int pathlen = 1; - for (VertInf *i = tar; i != _srcVert; i = i->pathNext) + if (pathlen < 2) { - pathlen++; - if (i == NULL) + // There is no valid path. + db_printf("Warning: Path not found...\n"); + m_needs_reroute_flag = true; + pathlen = 2; + tar->pathNext = m_src_vert; + if ((m_type == ConnType_PolyLine) && m_router->InvisibilityGrph) { - db_printf("Warning: Path not found...\n"); - pathlen = 2; - tar->pathNext = _srcVert; - if ((_type == ConnType_PolyLine) && _router->InvisibilityGrph) - { - // TODO: Could we know this edge already? - EdgeInf *edge = EdgeInf::existingEdge(_srcVert, tar); - COLA_ASSERT(edge != NULL); - edge->addCycleBlocker(); - } - break; + // TODO: Could we know this edge already? + //EdgeInf *edge = EdgeInf::existingEdge(m_src_vert, tar); + //COLA_ASSERT(edge != NULL); + //edge->addCycleBlocker(); } - // Check we don't have an apparent infinite connector path. -//#ifdef PATHDEBUG - db_printf("Path length: %i\n", pathlen); -//#endif - COLA_ASSERT(pathlen < 10000); } - std::vector<Point> path(pathlen); + path.resize(pathlen); + vertices.resize(pathlen); - int j = pathlen - 1; - for (VertInf *i = tar; i != _srcVert; i = i->pathNext) + unsigned int j = pathlen - 1; + for (VertInf *i = tar; i != m_src_vert; i = i->pathNext) { - if (_router->InvisibilityGrph && (_type == ConnType_PolyLine)) - { - // TODO: Again, we could know this edge without searching. - EdgeInf *edge = EdgeInf::existingEdge(i, i->pathNext); - COLA_ASSERT(edge != NULL); - edge->addConn(flag); - } - else - { - _false_path = true; - } path[j] = i->point; - if (i->id.isShape) - { - path[j].id = i->id.objID; - path[j].vn = i->id.vn; - } - else - { - path[j].id = _id; - path[j].vn = kUnassignedVertexNumber; - } - j--; + vertices[j] = i; + path[j].id = i->id.objID; + path[j].vn = i->id.vn; - if (i->pathNext && (i->pathNext->point == i->point)) - { - if (i->pathNext->id.isShape && i->id.isShape) - { - // Check for consecutive points on opposite - // corners of two touching shapes. - COLA_ASSERT(abs(i->pathNext->id.objID - i->id.objID) != 2); - } - } + j--; } - path[0] = _srcVert->point; - // Use topbit to differentiate between start and end point of connector. - // They need unique IDs for nudging. - unsigned int topbit = ((unsigned int) 1) << 31; - path[0].id = _id | topbit; - path[0].vn = kUnassignedVertexNumber; + vertices[0] = m_src_vert; + path[0] = m_src_vert->point; + path[0].id = m_src_vert->id.objID; + path[0].vn =m_src_vert->id.vn; +} - // Would clear visibility for endpoints here if required. - freeRoutes(); - PolyLine& output_route = _route; - output_route.ps = path; - -#ifdef PATHDEBUG - db_printf("Output route:\n"); - for (size_t i = 0; i < output_route.ps.size(); ++i) - { - db_printf("[%d,%d] %g, %g ", output_route.ps[i].id, - output_route.ps[i].vn, output_route.ps[i].x, - output_route.ps[i].y); - } - db_printf("\n\n"); -#endif +void ConnRef::setHateCrossings(bool value) +{ + m_hate_crossings = value; +} - return result; + +bool ConnRef::doesHateCrossings(void) const +{ + return m_hate_crossings; } -void ConnRef::setHateCrossings(bool value) +std::vector<Point> ConnRef::possibleDstPinPoints(void) const { - _hateCrossings = value; + std::vector<Point> points; + if (m_dst_connend) + { + points = m_dst_connend->possiblePinPoints(); + } + return points; } -bool ConnRef::doesHateCrossings(void) +PtOrder::PtOrder() { - return _hateCrossings; + // We have sorted neither list initially. + for (size_t dim = 0; dim < 2; ++dim) + { + sorted[dim] = false; + } } PtOrder::~PtOrder() { - // Free the PointRep lists. - for (int dim = 0; dim < 2; ++dim) +} + + +PointRepVector PtOrder::sortedPoints(const size_t dim) +{ + // Sort if not already sorted. + if (sorted[dim] == false) { - PointRepList::iterator curr = connList[dim].begin(); - while (curr != connList[dim].end()) - { - PointRep *doomed = *curr; - curr = connList[dim].erase(curr); - delete doomed; - } + sort(dim); } + return sortedConnVector[dim]; } -bool PointRep::follow_inner(PointRep *target) + +int PtOrder::positionFor(const size_t dim, const ConnRef *conn) { - if (this == target) + // Sort if not already sorted. + if (sorted[dim] == false) { - return true; + sort(dim); } - else + + // Just return position from the sorted list. + size_t i = 0; + for ( ; i < sortedConnVector[dim].size(); ++i) { - for (PointRepSet::iterator curr = inner_set.begin(); - curr != inner_set.end(); ++curr) + if (sortedConnVector[dim][i].second == conn) { - if ((*curr)->follow_inner(target)) - { - return true; - } + return (int) i; } } - return false; + return -1; } -int PtOrder::positionFor(const ConnRef *conn, const size_t dim) const +size_t PtOrder::insertPoint(const size_t dim, const PtConnPtrPair& pointPair) { - int position = 0; - for (PointRepList::const_iterator curr = connList[dim].begin(); - curr != connList[dim].end(); ++curr) + // Is this connector bendpoint already inserted? + size_t i = 0; + for ( ; i < nodes[dim].size(); ++i) { - if ((*curr)->conn == conn) + if (nodes[dim][i].second == pointPair.second) { - return position; + return i; } - ++position; } - // Not found. - return -1; + // Not found, insert. + nodes[dim].push_back(pointPair); + return nodes[dim].size() - 1; +} + +void PtOrder::addPoints(const size_t dim, const PtConnPtrPair& arg1, + const PtConnPtrPair& arg2) +{ + // Add points, but not ordering information. + insertPoint(dim, arg1); + insertPoint(dim, arg2); } -bool PtOrder::addPoints(const int dim, PtConnPtrPair innerArg, - PtConnPtrPair outerArg, bool swapped) +void PtOrder::addOrderedPoints(const size_t dim, const PtConnPtrPair& innerArg, + const PtConnPtrPair& outerArg, bool swapped) { PtConnPtrPair inner = (swapped) ? outerArg : innerArg; PtConnPtrPair outer = (swapped) ? innerArg : outerArg; COLA_ASSERT(inner != outer); - //printf("addPoints(%d, [%g, %g]-%X, [%g, %g]-%X)\n", dim, - // inner->x, inner->y, (int) inner, outer->x, outer->y, (int) outer); + // Add points. + size_t innerIndex = insertPoint(dim, inner); + size_t outerIndex = insertPoint(dim, outer); + + // And edge for ordering information. + links[dim].push_back(std::make_pair(outerIndex, innerIndex)); +} - PointRep *innerPtr = NULL; - PointRep *outerPtr = NULL; - for (PointRepList::iterator curr = connList[dim].begin(); - curr != connList[dim].end(); ++curr) - { - if ((*curr)->point == inner.first) - { - innerPtr = *curr; - } - if ((*curr)->point == outer.first) - { - outerPtr = *curr; - } - } - - if (innerPtr == NULL) + +void PtOrder::sort(const size_t dim) +{ + // This is just a topological sort of the points using the edges info. + + sorted[dim] = true; + + size_t n = nodes[dim].size(); + + // Build an adjacency matrix for easy lookup. + std::vector<std::vector<bool> > adjacencyMatrix(n); + for (size_t i = 0; i < n; ++i) { - innerPtr = new PointRep(inner.first, inner.second); - connList[dim].push_back(innerPtr); + adjacencyMatrix[i].assign(n, false); } - - if (outerPtr == NULL) + std::vector<int> incomingDegree(n); + std::queue<size_t> queue; + + // Populate the dependency matrix. + for (NodeIndexPairLinkList::iterator it = links[dim].begin(); + it != links[dim].end(); ++it) { - outerPtr = new PointRep(outer.first, outer.second); - connList[dim].push_back(outerPtr); + adjacencyMatrix[it->first][it->second] = true; } - // TODO COLA_ASSERT(innerPtr->inner_set.find(outerPtr) == innerPtr->inner_set.end()); - bool cycle = innerPtr->follow_inner(outerPtr); - if (cycle) + + // Build incoming degree lookup structure, and add nodes with no + // incoming edges to queue. + for (size_t i = 0; i < n; ++i) { - // Must reverse to avoid a cycle. - innerPtr->inner_set.insert(outerPtr); + int degree = 0; + + for (size_t j = 0; j < n; ++j) + { + if (adjacencyMatrix[j][i]) + { + degree++; + } + } + incomingDegree[i] = degree; + + if (degree == 0) + { + queue.push(i); + } } - else + + while (queue.empty() == false) { - outerPtr->inner_set.insert(innerPtr); - } - return cycle; -} + size_t k = queue.front(); + assert(k < nodes[dim].size()); + queue.pop(); + // Insert node k into the sorted list + sortedConnVector[dim].push_back(nodes[dim][k]); -// Assuming that addPoints has been called for each pair of points in the -// shared path at that corner, then the contents of inner_set can be used -// to determine the correct ordering. -static bool pointRepLessThan(PointRep *r1, PointRep *r2) -{ - size_t r1less = r1->inner_set.size(); - size_t r2less = r2->inner_set.size(); - //COLA_ASSERT(r1less != r2less); - - return (r1less > r2less); -} - - -void PtOrder::sort(const int dim) -{ - connList[dim].sort(pointRepLessThan); + // Remove all edges leaving node k: + for (size_t i = 0; i < n; ++i) + { + if (adjacencyMatrix[k][i]) + { + adjacencyMatrix[k][i] = false; + incomingDegree[i]--; + + if (incomingDegree[i] == 0) + { + queue.push(i); + } + } + } + } } @@ -1241,29 +1671,110 @@ static int segDir(const Point& p1, const Point& p2) } +static bool posInlineWithConnEndSegs(const double pos, const size_t dim, + const Avoid::Polygon& poly, const Avoid::Polygon& conn) +{ + size_t pLast = poly.size() - 1; + size_t cLast = conn.size() - 1; + if (( + // Is inline with the beginning of the "poly" line + ((pos == poly.ps[0][dim]) && (pos == poly.ps[1][dim])) || + // Is inline with the end of the "poly" line + ((pos == poly.ps[pLast][dim]) && (pos == poly.ps[pLast - 1][dim])) + ) && ( + // Is inline with the beginning of the "conn" line + ((pos == conn.ps[0][dim]) && (pos == conn.ps[1][dim])) || + // Is inline with the end of the "conn" line + ((pos == conn.ps[cLast][dim]) && (pos == conn.ps[cLast - 1][dim])) + )) + { + return true; + } + return false; +} + +ConnectorCrossings::ConnectorCrossings(Avoid::Polygon& poly, bool polyIsConn, + Avoid::Polygon& conn, ConnRef *polyConnRef, ConnRef *connConnRef) + : poly(poly), + polyIsConn(polyIsConn), + conn(conn), + checkForBranchingSegments(false), + polyConnRef(polyConnRef), + connConnRef(connConnRef), + crossingPoints(NULL), + pointOrders(NULL), + sharedPaths(NULL) +{ +} + +void ConnectorCrossings::clear(void) +{ + crossingCount = 0; + crossingFlags = CROSSING_NONE; + firstSharedPathAtEndLength = DBL_MAX; + secondSharedPathAtEndLength = DBL_MAX; +} + + +// Computes the *shared* length of these two shared paths. +// +static double pathLength(Avoid::Point **c_path, Avoid::Point **p_path, + size_t size) +{ + double length = 0; + + for (unsigned int ind = 1; ind < size; ++ind) + { + if ( (*(c_path[ind - 1]) == *(p_path[ind - 1])) && + (*(c_path[ind]) == *(p_path[ind])) ) + { + // This segment is shared by both paths. + // + // This function will only be used for orthogonal paths, so we + // can use Manhattan distance here since it will be faster to + // compute. + length += manhattanDist(*(c_path[ind - 1]), *(c_path[ind])); + } + } + + return length; +} + // Works out if the segment conn[cIndex-1]--conn[cIndex] really crosses poly. // This does not not count non-crossing shared paths as crossings. // poly can be either a connector (polyIsConn = true) or a cluster // boundary (polyIsConn = false). // -CrossingsInfoPair countRealCrossings(Avoid::Polygon& poly, - bool polyIsConn, Avoid::Polygon& conn, size_t cIndex, - bool checkForBranchingSegments, const bool finalSegment, - PointSet *crossingPoints, PtOrderMap *pointOrders, - ConnRef *polyConnRef, ConnRef *connConnRef) +void ConnectorCrossings::countForSegment(size_t cIndex, const bool finalSegment) { - unsigned int crossingFlags = CROSSING_NONE; - if (checkForBranchingSegments) + clear(); + + bool polyIsOrthogonal = (polyConnRef && + (polyConnRef->routingType() == ConnType_Orthogonal)); + bool connIsOrthogonal = (connConnRef && + (connConnRef->routingType() == ConnType_Orthogonal)); + + // Fixed routes are will not have segment breaks at possible crossings. + bool polyIsFixed = (polyConnRef && polyConnRef->hasFixedRoute()); + bool connIsFixed = (connConnRef && connConnRef->hasFixedRoute()); + + // We need to split apart connectors at potential crossing points if + // either has a fixed route or it is a polyline connector. This is not + // needed for orthogonal connectors where crossings occur at vertices + // in visibility graph and on the raw connector routes. + if (checkForBranchingSegments || polyIsFixed || connIsFixed || + !polyIsOrthogonal || !connIsOrthogonal) { + double epsilon = std::numeric_limits<double>::epsilon(); size_t conn_pn = conn.size(); // XXX When doing the pointOnLine test we allow the points to be // slightly non-collinear. This addresses a problem with clustered // routing where connectors could otherwise route cheaply through // shape corners that were not quite on the cluster boundary, but // reported to be on there by the line segment intersection code, - // which I suspect is not numerically accurate enough. This occured + // which I suspect is not numerically accurate enough. This occurred // for points that only differed by about 10^-12 in the y-dimension. - double tolerance = (!polyIsConn) ? 0.00001 : 0.0; + double tolerance = (!polyIsConn) ? epsilon : 0.0; splitBranchingSegments(poly, polyIsConn, conn, tolerance); // cIndex is going to be the last, so take into account added points. cIndex += (conn.size() - conn_pn); @@ -1271,21 +1782,20 @@ CrossingsInfoPair countRealCrossings(Avoid::Polygon& poly, COLA_ASSERT(cIndex >= 1); COLA_ASSERT(cIndex < conn.size()); - bool polyIsOrthogonal = (polyConnRef && - (polyConnRef->routingType() == ConnType_Orthogonal)); - bool connIsOrthogonal = (connConnRef && - (connConnRef->routingType() == ConnType_Orthogonal)); - size_t poly_size = poly.size(); - int crossingCount = 0; - std::vector<Avoid::Point *> c_path; - std::vector<Avoid::Point *> p_path; Avoid::Point& a1 = conn.ps[cIndex - 1]; Avoid::Point& a2 = conn.ps[cIndex]; //db_printf("a1: %g %g\n", a1.x, a1.y); //db_printf("a2: %g %g\n", a2.x, a2.y); + // Allocate arrays for computing shared paths. + // Don't use dynamic array due to portablity issues. + size_t max_path_size = std::min(poly_size, conn.size()); + Avoid::Point **c_path = new Avoid::Point*[max_path_size]; + Avoid::Point **p_path = new Avoid::Point*[max_path_size]; + size_t size = 0; + for (size_t j = ((polyIsConn) ? 1 : 0); j < poly_size; ++j) { Avoid::Point& b1 = poly.ps[(j - 1 + poly_size) % poly_size]; @@ -1293,8 +1803,8 @@ CrossingsInfoPair countRealCrossings(Avoid::Polygon& poly, //db_printf("b1: %g %g\n", b1.x, b1.y); //db_printf("b2: %g %g\n", b2.x, b2.y); - p_path.clear(); - c_path.clear(); + size = 0; + bool converging = false; const bool a1_eq_b1 = (a1 == b1); @@ -1417,14 +1927,14 @@ CrossingsInfoPair countRealCrossings(Avoid::Polygon& poly, ((trace_p >= 0) && (trace_p < (int) poly_size))) ) { // If poly is a cluster boundary, then it is a closed - // poly-line and so it wraps arounds. + // poly-line and so it wraps around. size_t index_p = (size_t) ((trace_p + (2 * poly_size)) % poly_size); size_t index_c = (size_t) trace_c; - c_path.push_back(&conn.ps[index_c]); - p_path.push_back(&poly.ps[index_p]); - if ((c_path.size() > 1) && - (conn.ps[index_c] != poly.ps[index_p])) + c_path[size] = &conn.ps[index_c]; + p_path[size] = &poly.ps[index_p]; + ++size; + if ((size > 1) && (conn.ps[index_c] != poly.ps[index_p])) { // Points don't match, so break out of loop. break; @@ -1434,67 +1944,185 @@ CrossingsInfoPair countRealCrossings(Avoid::Polygon& poly, } // Are there diverging points at the ends of the shared path. - bool front_same = (*(c_path.front()) == *(p_path.front())); - bool back_same = (*(c_path.back()) == *(p_path.back())); + bool front_same = (*(c_path[0]) == *(p_path[0])); + bool back_same = (*(c_path[size - 1]) == *(p_path[size - 1])); - size_t size = c_path.size(); + // Determine if the shared path originates at a junction. + bool terminatesAtJunction = false; + if (polyConnRef && connConnRef && (front_same || back_same)) + { + // To do this we find the two ConnEnds at the common + // end of the shared path. Then check if they are + // attached to a junction and it is the same one. + std::pair<ConnEnd, ConnEnd> connEnds = + connConnRef->endpointConnEnds(); + JunctionRef *connJunction = NULL; + + std::pair<ConnEnd, ConnEnd> polyEnds = + polyConnRef->endpointConnEnds(); + JunctionRef *polyJunction = NULL; + + // The front of the c_path corresponds to destination + // of the connector. + connJunction = (front_same) ? connEnds.second.junction() : + connEnds.first.junction(); + bool use_first = back_same; + if (p_dir_back) + { + // Reversed, so use opposite. + use_first = !use_first; + } + // The front of the p_path corresponds to destination + // of the connector. + polyJunction = (use_first) ? polyEnds.second.junction() : + polyEnds.first.junction(); + + terminatesAtJunction = (connJunction && + (connJunction == polyJunction)); + } + + if (sharedPaths) + { + // Store a copy of the shared path + size_t start = (front_same) ? 0 : 1; + size_t limit = size - ((back_same) ? 0 : 1); + PointList sPath(limit - start); + for (size_t i = start; i < limit; ++i) + { + sPath[i - start] = *(c_path[i]); + } + sharedPaths->push_back(sPath); + } + // Check to see if these share a fixed segment. if (polyIsOrthogonal && connIsOrthogonal) { size_t startPt = (front_same) ? 0 : 1; - if (c_path[startPt]->x == c_path[startPt + 1]->x) + size_t endPt = size - ((back_same) ? 1 : 2); + for (size_t dim = 0; dim < 2; ++dim) { - // Vertical - double xPos = c_path[startPt]->x; - // See if this is inline with either the start - // or end point of both connectors. - if ( ((xPos == poly.ps[0].x) || - (xPos == poly.ps[poly_size - 1].x)) && - ((xPos == conn.ps[0].x) || - (xPos == conn.ps[cIndex].x)) ) + if ((*c_path[startPt])[dim] == (*c_path[endPt])[dim]) { - crossingFlags |= CROSSING_SHARES_FIXED_SEGMENT; + double pos = (*c_path[startPt])[dim]; + // See if this is inline with either the start + // or end point of both connectors. We don't + // count them as crossing if they originate at a + // junction and are part of the same hyperedge. + if ( ((pos == poly.ps[0][dim]) || + (pos == poly.ps[poly_size - 1][dim])) && + ((pos == conn.ps[0][dim]) || + (pos == conn.ps[cIndex][dim])) && + (terminatesAtJunction == false)) + { + crossingFlags |= CROSSING_SHARES_FIXED_SEGMENT; + } } } - else + + if (!front_same && !back_same) { - // Horizontal - double yPos = c_path[startPt]->y; - // See if this is inline with either the start - // or end point of both connectors. - if ( ((yPos == poly.ps[0].y) || - (yPos == poly.ps[poly_size - 1].y)) && - ((yPos == conn.ps[0].y) || - (yPos == conn.ps[cIndex].y)) ) + // Find overlapping segments that are constrained by + // the fact that both the adjoining segments are fixed + // in the other dimension, i.e., + // + // X------++---X + // || + // || + // X---++------X + // + // In the example above, altDim is X, and dim is Y. + // + + // For each dimension... + for (size_t dim = 0; dim < 2; ++dim) { - crossingFlags |= CROSSING_SHARES_FIXED_SEGMENT; + size_t end = size - 1; + size_t altDim = (dim + 1) % 2; + // If segment is in this dimension... + if ((*c_path[1])[altDim] == (*c_path[end - 1])[altDim]) + { + double posBeg = (*c_path[1])[dim]; + double posEnd = (*c_path[end - 1])[dim]; + // If both segment ends diverge at right-angles... + if ( (posBeg == (*c_path[0])[dim]) && + (posBeg == (*p_path[0])[dim]) && + (posEnd == (*c_path[end])[dim]) && + (posEnd == (*p_path[end])[dim]) ) + { + // and these segments are inline with the conn and path ends themselves... + if (posInlineWithConnEndSegs(posBeg, dim, + conn, poly) && + posInlineWithConnEndSegs(posEnd, dim, + conn, poly)) + { + // If all endpoints branch at right angles, + // then penalise this since it is a segment + // will will not be able to nudge apart + // without introducing fixed segment + // crossings. + crossingFlags |= + CROSSING_SHARES_FIXED_SEGMENT; + } + } + } } } + +#if 0 + // XXX: What is this code for? It is pretty much + // incomprehensible and also causes one of the test + // cases to fail. + // + if (!front_same && !back_same) + { + for (size_t dim = 0; dim < 2; ++dim) + { + size_t altDim = (dim + 1) % 2; + if ((*c_path[1])[altDim] == (*c_path[1])[altDim]) + { + size_t n = c_path.size(); + double yPosB = (*c_path[1])[dim]; + if ( (yPosB == (*c_path[0])[dim]) && + (yPosB == (*p_path[0])[dim]) ) + { + crossingFlags |= + CROSSING_SHARES_FIXED_SEGMENT; + } + + double yPosE = (*c_path[n - 2])[dim]; + if ( (yPosE == (*c_path[n - 1])[dim]) && + (yPosE == (*p_path[n - 1])[dim]) ) + { + crossingFlags |= + CROSSING_SHARES_FIXED_SEGMENT; + } + } + } + } +#endif } - int prevTurnDir = -1; + // {start,end}CornerSide specifies which side of conn the + // poly path enters and leaves. int startCornerSide = 1; int endCornerSide = 1; + + bool reversed = false; if (!front_same) { // If there is a divergence at the beginning, // then order the shared path based on this. - prevTurnDir = vecDir(*c_path[0], *c_path[1], *c_path[2]); startCornerSide = Avoid::cornerSide(*c_path[0], *c_path[1], - *c_path[2], *p_path[0]) - * segDir(*c_path[1], *c_path[2]); + *c_path[2], *p_path[0]); } if (!back_same) { // If there is a divergence at the end of the path, // then order the shared path based on this. - prevTurnDir = vecDir(*c_path[size - 3], - *c_path[size - 2], *c_path[size - 1]); endCornerSide = Avoid::cornerSide(*c_path[size - 3], *c_path[size - 2], *c_path[size - 1], - *p_path[size - 1]) - * segDir(*c_path[size - 3], *c_path[size - 2]); + *p_path[size - 1]); } else { @@ -1505,9 +2133,56 @@ CrossingsInfoPair countRealCrossings(Avoid::Polygon& poly, startCornerSide = endCornerSide; } + if (endCornerSide != startCornerSide) + { + // Mark that the shared path crosses. + //db_printf("shared path crosses.\n"); + crossingCount += 1; + if (crossingPoints) + { + crossingPoints->insert(*c_path[1]); + } + } + if (front_same || back_same) { crossingFlags |= CROSSING_SHARES_PATH_AT_END; + + // Reduce the cost of paths that stay straight after + // the split, and make this length available so that the + // paths can be ordered during the improveCrossings() + // step and the straight (usually better) paths will be + // left alone while the router attempts to find better + // paths for the others. + double straightModifier = 200; + firstSharedPathAtEndLength = secondSharedPathAtEndLength = + pathLength(c_path, p_path, size); + if (back_same && (size > 2)) + { + if (vecDir(*p_path[0], *p_path[1], *p_path[2]) == 0) + { + firstSharedPathAtEndLength -= straightModifier; + } + + if (vecDir(*c_path[0], *c_path[1], *c_path[2]) == 0) + { + secondSharedPathAtEndLength -= straightModifier; + } + } + else if (front_same && (size > 2)) + { + if (vecDir(*p_path[size - 3], *p_path[size - 2], + *p_path[size - 1]) == 0) + { + firstSharedPathAtEndLength -= straightModifier; + } + + if (vecDir(*c_path[size - 3], *c_path[size - 2], + *c_path[size - 1]) == 0) + { + secondSharedPathAtEndLength -= straightModifier; + } + } } else if (polyIsOrthogonal && connIsOrthogonal) { @@ -1519,8 +2194,7 @@ CrossingsInfoPair countRealCrossings(Avoid::Polygon& poly, // other. So order based on not introducing overlap // of the diverging segments when these are nudged // apart. - startCornerSide = -cStartDir * - segDir(*c_path[1], *c_path[2]); + startCornerSide = -cStartDir; } else { @@ -1534,14 +2208,13 @@ CrossingsInfoPair countRealCrossings(Avoid::Polygon& poly, // each other. So order based on not introducing // overlap of the diverging segments when these // are nudged apart. - startCornerSide = -cEndDir * segDir( - *c_path[size - 3], *c_path[size - 2]); + startCornerSide = -cEndDir; } } } #if 0 - prevTurnDir = 0; + int prevTurnDir = 0; if (pointOrders) { // Return the ordering for the shared path. @@ -1564,7 +2237,7 @@ CrossingsInfoPair countRealCrossings(Avoid::Polygon& poly, // become the outer path and vice versa. reversed = !reversed; } - bool orderSwapped = (*pointOrders)[an].addPoints( + bool orderSwapped = (*pointOrders)[an].addOrderedPoints( &bn, &an, reversed); if (orderSwapped) { @@ -1577,12 +2250,12 @@ CrossingsInfoPair countRealCrossings(Avoid::Polygon& poly, #endif if (pointOrders) { - bool reversed = false; + reversed = false; size_t startPt = (front_same) ? 0 : 1; // Orthogonal should always have at least one segment. - COLA_ASSERT(c_path.size() > (startPt + 1)); - + COLA_ASSERT(size > (startPt + 1)); + if (startCornerSide > 0) { reversed = !reversed; @@ -1590,51 +2263,48 @@ CrossingsInfoPair countRealCrossings(Avoid::Polygon& poly, int prevDir = 0; // Return the ordering for the shared path. - COLA_ASSERT(c_path.size() > 0 || back_same); - size_t adj_size = (c_path.size() - ((back_same) ? 0 : 1)); - for (size_t i = (front_same) ? 0 : 1; i < adj_size; ++i) + COLA_ASSERT(size > 0 || back_same); + size_t adj_size = (size - ((back_same) ? 0 : 1)); + for (size_t i = startPt; i < adj_size; ++i) { Avoid::Point& an = *(c_path[i]); Avoid::Point& bn = *(p_path[i]); COLA_ASSERT(an == bn); - int thisDir = prevDir; - if ((i > 0) && (*(c_path[i - 1]) == *(p_path[i - 1]))) - { - thisDir = segDir(*c_path[i - 1], *c_path[i]); - } - - if (thisDir != prevDir) - { - reversed = !reversed; - } - prevDir = thisDir; - if (i > startPt) { Avoid::Point& ap = *(c_path[i - 1]); Avoid::Point& bp = *(p_path[i - 1]); + + int thisDir = segDir(ap, an); + if (prevDir == 0) + { + if (thisDir > 0) + { + reversed = !reversed; + } + } + else if (thisDir != prevDir) + { + reversed = !reversed; + } + int orientation = (ap.x == an.x) ? 0 : 1; //printf("prevOri %d\n", prevOrientation); //printf("1: %X, %X\n", (int) &(bn), (int) &(an)); - bool orderSwapped = (*pointOrders)[an].addPoints( + (*pointOrders)[an].addOrderedPoints( orientation, std::make_pair(&bn, polyConnRef), std::make_pair(&an, connConnRef), reversed); - if (orderSwapped) - { - // Reverse the order for later points. - reversed = !reversed; - } COLA_ASSERT(ap == bp); //printf("2: %X, %X\n", (int) &bp, (int) &ap); - orderSwapped = (*pointOrders)[ap].addPoints( + (*pointOrders)[ap].addOrderedPoints( orientation, std::make_pair(&bp, polyConnRef), std::make_pair(&ap, connConnRef), reversed); - COLA_ASSERT(!orderSwapped); + prevDir = thisDir; } } } @@ -1678,16 +2348,6 @@ CrossingsInfoPair countRealCrossings(Avoid::Polygon& poly, } #endif - if (endCornerSide != startCornerSide) - { - // Mark that the shared path crosses. - //db_printf("shared path crosses.\n"); - crossingCount += 1; - if (crossingPoints) - { - crossingPoints->insert(*c_path[1]); - } - } crossingFlags |= CROSSING_TOUCHES; } else if (cIndex >= 2) @@ -1697,7 +2357,7 @@ CrossingsInfoPair countRealCrossings(Avoid::Polygon& poly, // Crossing shouldn't be at an endpoint. COLA_ASSERT(cIndex >= 2); - COLA_ASSERT(polyIsConn && (j >= 2)); + COLA_ASSERT(!polyIsConn || (j >= 2)); Avoid::Point& b0 = poly.ps[(j - 2 + poly_size) % poly_size]; Avoid::Point& a0 = conn.ps[cIndex - 2]; @@ -1729,18 +2389,19 @@ CrossingsInfoPair countRealCrossings(Avoid::Polygon& poly, // XXX: Why do we need to invert the reversed values // here? Are they wrong for orthogonal points // in the other places? - (*pointOrders)[b1].addPoints(0, + (*pointOrders)[b1].addOrderedPoints(0, std::make_pair(&b1, polyConnRef), std::make_pair(&a1, connConnRef), !reversedX); - (*pointOrders)[b1].addPoints(1, + (*pointOrders)[b1].addOrderedPoints(1, std::make_pair(&b1, polyConnRef), std::make_pair(&a1, connConnRef), !reversedY); } +#if 0 +// Unused code. else - { /// \todo FIXME: this whole branch was not doing anything - /* + { int turnDirA = vecDir(a0, a1, a2); int turnDirB = vecDir(b0, b1, b2); bool reversed = (side1 != -turnDirA); @@ -1763,10 +2424,10 @@ CrossingsInfoPair countRealCrossings(Avoid::Polygon& poly, // TODO COLA_ASSERT((turnDirB != 0) || // (turnDirA != 0)); } - VertID vID(b1.id, true, b1.vn); - //(*pointOrders)[b1].addPoints(&b1, &a1, reversed); - */ + VertID vID(b1.id, b1.vn); + //(*pointOrders)[b1].addOrderedPoints(&b1, &a1, reversed); } +#endif } } } @@ -1811,8 +2472,11 @@ CrossingsInfoPair countRealCrossings(Avoid::Polygon& poly, } } } - //db_printf("crossingcount %d\n", crossingCount); - return std::make_pair(crossingCount, crossingFlags); + //db_printf("crossingcount %d %d\n", crossingCount, crossingFlags); + + // Free shared path memory. + delete[] c_path; + delete[] p_path; } |