Merge https://gitlab.com/inkscape/inkscape into selectable-knots

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;
 }