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

1 files changed, 1941 insertions, 1029 deletions

diff --git a/src/libavoid/orthogonal.cpp b/src/libavoid/orthogonal.cpp
index 466d1dd58..2558e0d73 100644
--- a/src/libavoid/orthogonal.cpp
+++ b/src/libavoid/orthogonal.cpp
@@ -3,7 +3,7 @@
  *
  * libavoid - Fast, Incremental, Object-avoiding Line Router
  *
- * Copyright (C) 2009  Monash University
+ * Copyright (C) 2009-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
@@ -12,14 +12,14 @@
  * See the file LICENSE.LGPL distributed with the library.
  *
  * Licensees holding a valid commercial license may use this file in
- * accordance with the commercial license agreement provided with the
+ * accordance with the commercial license agreement provided with the 
  * library.
  *
  * This library is distributed in the hope that it will be useful,
  * but WITHOUT ANY WARRANTY; without even the implied warranty of
- * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.
+ * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  
  *
- * Author(s):   Michael Wybrow <mjwybrow@users.sourceforge.net>
+ * Author(s):  Michael Wybrow
 */
 
 
@@ -34,96 +34,257 @@
 #include "libavoid/geomtypes.h"
 #include "libavoid/shape.h"
 #include "libavoid/orthogonal.h"
+#include "libavoid/connend.h"
 #include "libavoid/connector.h"
+#include "libavoid/junction.h"
 #include "libavoid/vpsc.h"
 #include "libavoid/assertions.h"
+#include "libavoid/scanline.h"
+#include "libavoid/debughandler.h"
 
-#ifdef LIBAVOID_SDL
-  #include <SDL_gfxPrimitives.h>
-#endif
+// For debugging:
+//#define NUDGE_DEBUG
+//#define DEBUG_JUST_UNIFY
 
 
 namespace Avoid {
 
 
-static const double CHANNEL_MAX = 100000000;
+// IDs:
+static const int freeSegmentID  = 0;
+static const int fixedSegmentID = 1;
+static const int channelLeftID  = 2;
+static const int channelRightID = 3;
+// Weights:
+static const double freeWeight   = 0.00001;
+static const double strongWeight = 0.001;
+static const double strongerWeight = 1.0;
+static const double fixedWeight  = 100000;
 
-static const size_t XDIM = 0;
-static const size_t YDIM = 1;
 
+// A pair of unsigned values that can be compared and used as the keys
+// for sets and maps.
+class UnsignedPair
+{
+    public:
+        UnsignedPair(unsigned ind1, unsigned ind2)
+        {
+            COLA_ASSERT(ind1 != ind2);
+            // Assign the lesser value to m_index1.
+            m_index1 = (ind1 < ind2) ? ind1 : ind2;
+            // Assign the greater value to m_index2.
+            m_index2 = (ind1 > ind2) ? ind1 : ind2;
+        }
 
-class ShiftSegment
+        bool operator<(const UnsignedPair& rhs) const
+        {
+            if (m_index1 != rhs.m_index1)
+            {
+                return m_index1 < rhs.m_index1;
+            }
+            return m_index2 < rhs.m_index2;
+        }
+    private:
+        unsigned short m_index1;
+        unsigned short m_index2;
+};
+typedef std::set<UnsignedPair> UnsignedPairSet;
+
+
+// Used to sort points when merging NudgingShiftSegments.
+// Sorts the indexes, by point position in one dimension.
+class CmpIndexes
 {
     public:
-        // For shiftable segments.
-        ShiftSegment(ConnRef *conn, const size_t low, const size_t high,
-                bool isSBend, const size_t dim, double minLim, double maxLim)
+        CmpIndexes(ConnRef *conn, size_t dim)
             : connRef(conn),
-              indexLow(low),
-              indexHigh(high),
-              sBend(isSBend),
-              fixed(false),
-              dimension(dim),
-              variable(NULL),
-              minSpaceLimit(minLim),
-              maxSpaceLimit(maxLim)
+              dimension(dim)
         {
         }
+        bool operator()(size_t lhs, size_t rhs)
+        {
+            return connRef->displayRoute().ps[lhs][dimension] < 
+                    connRef->displayRoute().ps[rhs][dimension];
+        }
+    private:
+        ConnRef *connRef;
+        size_t dimension;
+};
 
+
+class NudgingShiftSegment : public ShiftSegment
+{
+    public:
+        // For shiftable segments.
+        NudgingShiftSegment(ConnRef *conn, const size_t low, const size_t high, 
+                bool isSBend, bool isZBend, const size_t dim, double minLim,
+                double maxLim)
+            : ShiftSegment(dim),
+              connRef(conn),
+              variable(NULL),
+              fixed(false),
+              finalSegment(false),
+              endsInShape(false),
+              singleConnectedSegment(false),
+              sBend(isSBend),
+              zBend(isZBend)
+        {
+            indexes.push_back(low);
+            indexes.push_back(high);
+            minSpaceLimit = minLim;
+            maxSpaceLimit = maxLim;
+        }
         // For fixed segments.
-        ShiftSegment(ConnRef *conn, const size_t low, const size_t high,
+        NudgingShiftSegment(ConnRef *conn, const size_t low, const size_t high, 
                 const size_t dim)
-            : connRef(conn),
-              indexLow(low),
-              indexHigh(high),
-              sBend(false),
+            : ShiftSegment(dim),
+              connRef(conn),
+              variable(NULL),
               fixed(true),
-              dimension(dim),
-              variable(NULL)
+              finalSegment(false),
+              endsInShape(false),
+              singleConnectedSegment(false),
+              sBend(false),
+              zBend(false)
         {
+            indexes.push_back(low);
+            indexes.push_back(high);
             // This has no space to shift.
             minSpaceLimit = lowPoint()[dim];
             maxSpaceLimit = lowPoint()[dim];
         }
-
+        virtual ~NudgingShiftSegment()
+        {
+        }
         Point& lowPoint(void)
         {
-            return connRef->displayRoute().ps[indexLow];
+            return connRef->displayRoute().ps[indexes.front()];
         }
-
         Point& highPoint(void)
         {
-            return connRef->displayRoute().ps[indexHigh];
+            return connRef->displayRoute().ps[indexes.back()];
         }
-
         const Point& lowPoint(void) const
         {
-            return connRef->displayRoute().ps[indexLow];
+            return connRef->displayRoute().ps[indexes.front()];
         }
-
-        const Point& highPoint(void) const
+        const Point& highPoint(void) const 
         {
-            return connRef->displayRoute().ps[indexHigh];
+            return connRef->displayRoute().ps[indexes.back()];
+        }
+        double nudgeDistance(void) const
+        {
+            return connRef->router()->routingParameter(idealNudgingDistance);
+        }
+        bool immovable(void) const
+        {
+            return ! zigzag();
+        }
+        void createSolverVariable(const bool justUnifying)
+        {
+            bool nudgeFinalSegments = connRef->router()->routingOption(
+                    nudgeOrthogonalSegmentsConnectedToShapes);
+            int varID = freeSegmentID;
+            double varPos = lowPoint()[dimension];
+            double weight = freeWeight;
+            if (nudgeFinalSegments && finalSegment)
+            {
+                weight = strongWeight;
+                
+                if (singleConnectedSegment && !justUnifying)
+                {
+                    // This is a single segment connector bridging
+                    // two shapes.  So, we want to try to keep it
+                    // centred rather than shift it.
+                    // Don't do this during Unifying stage, or else 
+                    // these connectors could end up at slightly 
+                    // different positions and get the wrong ordering
+                    // for nudging.
+                    weight = strongerWeight;
+                }
+            }
+            else if (checkpoints.size() > 0)
+            {
+                weight = strongWeight;
+            }
+            else if (zigzag())
+            {
+                COLA_ASSERT(minSpaceLimit > -CHANNEL_MAX);
+                COLA_ASSERT(maxSpaceLimit < CHANNEL_MAX);
+                
+                // For zigzag bends, take the middle as ideal.
+                varPos = minSpaceLimit + ((maxSpaceLimit - minSpaceLimit) / 2);
+            }
+            else if (fixed)
+            {
+                // Fixed segments shouldn't get moved.
+                weight = fixedWeight;
+                varID = fixedSegmentID;
+            }
+            else if ( ! finalSegment )
+            {
+                // Set a higher weight for c-bends to stop them sometimes 
+                // getting pushed out into channels by more-free connectors
+                // to the "inner" side of them.
+                weight = strongWeight;
+            }
+
+            variable = new Variable(varID, varPos, weight);
         }
 
-        int fixedOrder(bool& isFixed) const
+        void updatePositionsFromSolver(const bool justUnifying)
         {
             if (fixed)
             {
+                return;
+            }
+            double newPos = variable->finalPosition;
+
+            // The solver can sometimes cause variables to be outside their
+            // limits by a tiny amount, since all variables are held by
+            // weights.  Thus, just make sure they stay in their limits.
+            newPos = std::max(newPos, minSpaceLimit);
+            newPos = std::min(newPos, maxSpaceLimit);
+
+#ifdef NUDGE_DEBUG
+            printf("Pos: %lX, %.16f\n", (long) connRef, newPos);
+#endif
+            for (size_t it = 0; it < indexes.size(); ++it)
+            {
+                size_t index = indexes[it];
+                connRef->displayRoute().ps[index][dimension] = newPos;
+            }
+
+#ifdef DEBUGHANDLER
+            if (!justUnifying && connRef->router()->debugHandler())
+            {
+                connRef->router()->debugHandler()->updateConnectorRoute(
+                        connRef, indexes[0], indexes[indexes.size() - 1]);
+            }
+#endif
+        }
+        int fixedOrder(bool& isFixed) const
+        {
+            double nudgeDist = nudgeDistance();
+            double pos = lowPoint()[dimension];
+            bool minLimited = ((pos - minSpaceLimit) < nudgeDist);
+            bool maxLimited = ((maxSpaceLimit - pos) < nudgeDist);
+            
+            if (fixed || (minLimited && maxLimited))
+            {
                 isFixed = true;
                 return 0;
             }
-            if (lowC())
+            else if (minLimited)
             {
                 return 1;
             }
-            else if (highC())
+            else if (maxLimited)
             {
                 return -1;
             }
             return 0;
         }
-
         int order(void) const
         {
             if (lowC())
@@ -136,389 +297,264 @@ class ShiftSegment
             }
             return 0;
         }
-
-        bool operator<(const ShiftSegment& rhs) const
+        bool zigzag(void) const
         {
-            const Point& lowPt = lowPoint();
-            const Point& rhsLowPt = rhs.lowPoint();
-
-            if (lowPt[dimension] != rhsLowPt[dimension])
-            {
-                return lowPt[dimension] < rhsLowPt[dimension];
-            }
-            return this < &rhs;
+            return sBend || zBend;
         }
-
-        // This counts segments that are colliear and share an endpoint as
+        // This counts segments that are collinear and share an endpoint as
         // overlapping.  This allows them to be nudged apart where possible.
-        bool overlapsWith(const ShiftSegment& rhs, const size_t dim) const
+        bool overlapsWith(const ShiftSegment *rhsSuper, const size_t dim) const
         {
+            const NudgingShiftSegment *rhs = 
+                    static_cast<const NudgingShiftSegment *> (rhsSuper);
             size_t altDim = (dim + 1) % 2;
             const Point& lowPt = lowPoint();
             const Point& highPt = highPoint();
-            const Point& rhsLowPt = rhs.lowPoint();
-            const Point& rhsHighPt = rhs.highPoint();
-            if ( (lowPt[altDim] <= rhsHighPt[altDim]) &&
-                    (rhsLowPt[altDim] <= highPt[altDim]))
-            {
-                if ( (minSpaceLimit <= rhs.maxSpaceLimit) &&
-                        (rhs.minSpaceLimit <= maxSpaceLimit))
+            const Point& rhsLowPt = rhs->lowPoint();
+            const Point& rhsHighPt = rhs->highPoint();
+            if ( (lowPt[altDim] < rhsHighPt[altDim]) &&
+                    (rhsLowPt[altDim] < highPt[altDim]))
+            {
+                // The segments overlap.
+                if ( (minSpaceLimit <= rhs->maxSpaceLimit) &&
+                        (rhs->minSpaceLimit <= maxSpaceLimit) )
                 {
                     return true;
                 }
             }
-            return false;
-        }
-
-        ConnRef *connRef;
-        size_t indexLow;
-        size_t indexHigh;
-        bool sBend;
-        bool fixed;
-        size_t dimension;
-        Variable *variable;
-        double minSpaceLimit;
-        double maxSpaceLimit;
-    private:
-        bool lowC(void) const
-        {
-            // This is true if this is a cBend and its adjoining points
-            // are at lower positions.
-            if (!sBend && !fixed && (minSpaceLimit == lowPoint()[dimension]))
+            else if ( (lowPt[altDim] == rhsHighPt[altDim]) || 
+                      (rhsLowPt[altDim] == highPt[altDim]) )
             {
-                return true;
-            }
-            return false;
-        }
+                bool nudgeColinearSegments = connRef->router()->routingOption(
+                        nudgeOrthogonalTouchingColinearSegments);
 
-        bool highC(void) const
-        {
-            // This is true if this is a cBend and its adjoining points
-            // are at higher positions.
-            if (!sBend && !fixed && (maxSpaceLimit == lowPoint()[dimension]))
-            {
-                return true;
+                if ( (minSpaceLimit <= rhs->maxSpaceLimit) &&
+                        (rhs->minSpaceLimit <= maxSpaceLimit) )
+                {
+                    // The segments could touch at one end.
+                    if (connRef->router()->routingParameter(
+                            fixedSharedPathPenalty) > 0)
+                    {
+                        // If we are routing with a fixedSharedPathPenalty
+                        // then we don't want these segments to ever touch
+                        // or slide past each other, so they are always 
+                        // considered to be overlapping.
+                        return true;
+                    }
+                    else if ((rhs->sBend && sBend) || (rhs->zBend && zBend))
+                    {
+                        // Count them as overlapping for nudging if they 
+                        // are both s-bends or both z-bends, i.e., when 
+                        // the ordering would matter.
+                        return nudgeColinearSegments;
+                    }
+                    else if ((rhs->finalSegment && finalSegment) &&
+                            (rhs->connRef == connRef))
+                    {
+                        return nudgeColinearSegments;
+                    }
+                }
             }
             return false;
         }
-};
-typedef std::list<ShiftSegment> ShiftSegmentList;
-
-struct Node;
-struct CmpNodePos { bool operator()(const Node* u, const Node* v) const; };
-
-typedef std::set<Node*,CmpNodePos> NodeSet;
-struct Node
-{
-    ShapeRef *v;
-    VertInf *c;
-    ShiftSegment *ss;
-    double pos;
-    double min[2], max[2];
-    Node *firstAbove, *firstBelow;
-    NodeSet::iterator iter;
-
-    Node(ShapeRef *v, const double p)
-        : v(v),
-          c(NULL),
-          ss(NULL),
-          pos(p),
-          firstAbove(NULL),
-          firstBelow(NULL)
-    {
-        //COLA_ASSERT(r->width()<1e40);
-        v->polygon().getBoundingRect(&min[0], &min[1], &max[0], &max[1]);
-    }
-    Node(VertInf *c, const double p)
-        : v(NULL),
-          c(c),
-          ss(NULL),
-          pos(p),
-          firstAbove(NULL),
-          firstBelow(NULL)
-    {
-        min[0] = max[0] = c->point.x;
-        min[1] = max[1] = c->point.y;
-    }
-    Node(ShiftSegment *ss, const double p)
-        : v(NULL),
-          c(NULL),
-          ss(ss),
-          pos(p),
-          firstAbove(NULL),
-          firstBelow(NULL)
-    {
-        // These values shouldn't ever be used, so they don't matter.
-        min[0] = max[0] = min[1] = max[1] = 0;
-    }
-    ~Node()
-    {
-    }
-    // Find the first Node above in the scanline that is a shape edge,
-    // and does not have an open or close event at this position (meaning
-    // it is just about to be removed).
-    double firstObstacleAbove(size_t dim)
-    {
-        Node *curr = firstAbove;
-        while (curr && (curr->ss || (curr->max[dim] > pos)))
-        {
-            curr = curr->firstAbove;
-        }
-
-        if (curr)
-        {
-            return curr->max[dim];
-        }
-        return -DBL_MAX;
-    }
-    // Find the first Node below in the scanline that is a shape edge,
-    // and does not have an open or close event at this position (meaning
-    // it is just about to be removed).
-    double firstObstacleBelow(size_t dim)
-    {
-        Node *curr = firstBelow;
-        while (curr && (curr->ss || (curr->min[dim] < pos)))
+        // These segments are allowed to drift into alignment but don't have to.
+        bool canAlignWith(const NudgingShiftSegment *rhs, 
+                const size_t dim) const
         {
-            curr = curr->firstBelow;
-        }
+            COLA_UNUSED(dim);
 
-        if (curr)
-        {
-            return curr->min[dim];
-        }
-        return DBL_MAX;
-    }
-    // Mark all connector segments above in the scanline as being able
-    // to see to this shape edge.
-    void markShiftSegmentsAbove(size_t dim)
-    {
-        Node *curr = firstAbove;
-        while (curr && (curr->ss || (curr->pos > min[dim])))
-        {
-            if (curr->ss && (curr->pos <= min[dim]))
+            if (connRef != rhs->connRef)
             {
-                curr->ss->maxSpaceLimit =
-                        std::min(min[dim], curr->ss->maxSpaceLimit);
+                return false;
             }
-            curr = curr->firstAbove;
-        }
-    }
-    // Mark all connector segments below in the scanline as being able
-    // to see to this shape edge.
-    void markShiftSegmentsBelow(size_t dim)
-    {
-        Node *curr = firstBelow;
-        while (curr && (curr->ss || (curr->pos < max[dim])))
-        {
-            if (curr->ss && (curr->pos >= max[dim]))
+            
+            // Don't allow segments of the same connector to drift together
+            // where one of them goes via a checkpoint.  We want the path 
+            // through the checkpoint to be maintained.
+            bool hasCheckpoints = checkpoints.size() > 0;
+            bool rhsHasCheckpoints = rhs->checkpoints.size() > 0;
+            if (hasCheckpoints || rhsHasCheckpoints)
             {
-                curr->ss->minSpaceLimit =
-                        std::max(max[dim], curr->ss->minSpaceLimit);
+                return false;
             }
-            curr = curr->firstBelow;
+            return true;
         }
-    }
-    bool findFirstPointAboveAndBelow(const size_t dim, double& firstAbovePos,
-            double& firstBelowPos, double& lastAbovePos, double& lastBelowPos)
-    {
-        bool clearVisibility = true;
-        firstAbovePos = -DBL_MAX;
-        firstBelowPos = DBL_MAX;
-        // We start looking left from the right side of the shape,
-        // and vice versa.
-        lastAbovePos = max[dim];
-        lastBelowPos = min[dim];
-
-        // Find the first blocking edge above this point.  Don't count the
-        // edges as we are travelling out of shapes we are inside, but then
-        // mark clearVisibility as false.
-        Node *curr = firstAbove;
-        while (curr && (curr->max[dim] > min[dim]))
-        {
-            lastAbovePos = std::min(curr->min[dim], lastAbovePos);
-            if ((curr->max[dim] >= min[dim]) && (curr->max[dim] <= max[dim]))
-            {
-                lastAbovePos = std::min(curr->max[dim], lastAbovePos);
+        // These segments should align with each other.
+        bool shouldAlignWith(const ShiftSegment *rhsSuper, 
+                const size_t dim) const
+        {
+            const NudgingShiftSegment *rhs = 
+                    static_cast<const NudgingShiftSegment *> (rhsSuper);
+            if ((connRef == rhs->connRef) && finalSegment && 
+                    rhs->finalSegment && overlapsWith(rhs, dim))
+            {
+                // If both the segments are in shapes then we know limits
+                // and can align.  Otherwise we do this just for segments 
+                // that are very close together, since these will often 
+                // prevent nudging, or force it to have a tiny separation
+                // value.
+                if ((endsInShape && rhs->endsInShape) ||
+                        (fabs(lowPoint()[dim] - rhs->lowPoint()[dim]) < 10))
+                {
+                    return true;
+                }
             }
-            lastBelowPos = std::max(curr->max[dim], lastBelowPos);
-            clearVisibility = false;
-            curr = curr->firstAbove;
-        }
-        if (curr)
-        {
-            firstAbovePos = curr->max[dim];
-        }
-        while (curr)
-        {
-            // There might be a larger shape after this one in the ordering.
-            if (curr->max[dim] < min[dim])
+            else if ((connRef == rhs->connRef) && 
+                     // Not both final
+                     ((finalSegment & rhs->finalSegment) != true))
             {
-                firstAbovePos = std::max(curr->max[dim], firstAbovePos);
+                bool hasCheckpoints = checkpoints.size() > 0;
+                bool rhsHasCheckpoints = rhs->checkpoints.size() > 0;
+
+                if (hasCheckpoints != rhsHasCheckpoints)
+                {
+                    // At least one segment has checkpoints, but not both.
+
+                    size_t altDim = (dim + 1) % 2;
+                    double space = fabs(lowPoint()[dim] - rhs->lowPoint()[dim]);
+                    double touchPos;
+                    bool couldTouch = false;
+                    if (lowPoint()[altDim] == rhs->highPoint()[altDim])
+                    {
+                        couldTouch = true;
+                        touchPos = lowPoint()[altDim];
+                    }
+                    else if (highPoint()[altDim] == rhs->lowPoint()[altDim])
+                    {
+                        couldTouch = true;
+                        touchPos = highPoint()[altDim];
+                    }
+
+                    // We should align these so long as they are close
+                    // together (<= 10) and there isn't a checkpoint at the 
+                    // touch point, i.e., we'd be altering the edges leading 
+                    // into the checkpoint.  We want to keep these in place 
+                    // and opportunistically move other edges to align with 
+                    // them.
+                    return couldTouch && (space <= 10) &&
+                            !hasCheckpointAtPosition(touchPos, altDim) &&
+                            !rhs->hasCheckpointAtPosition(touchPos, altDim);
+                }
             }
-            curr = curr->firstAbove;
+            return false;
         }
-
-        // Find the first blocking edge below this point.  Don't count the
-        // edges as we are travelling out of shapes we are inside, but then
-        // mark clearVisibility as false.
-        curr = firstBelow;
-        while (curr && (curr->min[dim] < max[dim]))
+        // Used for merging segments with end segments that should appear as
+        // a single segment.
+        void mergeWith(const ShiftSegment *rhsSuper, const size_t dim)
         {
-            lastBelowPos = std::max(curr->max[dim], lastBelowPos);
-            if ((curr->min[dim] >= min[dim]) && (curr->min[dim] <= max[dim]))
+            // Adjust limits.
+            minSpaceLimit = std::max(minSpaceLimit, rhsSuper->minSpaceLimit);
+            maxSpaceLimit = std::min(maxSpaceLimit, rhsSuper->maxSpaceLimit);
+ 
+            // Find a new position for the segment, taking into account
+            // the two original positions and the combined limits.
+            double segmentPos = lowPoint()[dimension];
+            double segment2Pos = rhsSuper->lowPoint()[dimension];
+            if (segment2Pos < segmentPos)
             {
-                lastBelowPos = std::max(curr->min[dim], lastBelowPos);
+                segmentPos -= ((segmentPos - segment2Pos) / 2.0);
             }
-            lastAbovePos = std::min(curr->min[dim], lastAbovePos);
-            clearVisibility = false;
-            curr = curr->firstBelow;
-        }
-        if (curr)
-        {
-            firstBelowPos = curr->min[dim];
-        }
-        while (curr)
-        {
-            // There might be a larger shape after this one in the ordering.
-            if (curr->min[dim] > max[dim])
+            else if (segment2Pos > segmentPos)
             {
-                firstBelowPos = std::min(curr->min[dim], firstBelowPos);
+                segmentPos += ((segment2Pos - segmentPos) / 2.0);
             }
-            curr = curr->firstBelow;
-        }
+            segmentPos = std::max(minSpaceLimit, segmentPos);
+            segmentPos = std::min(maxSpaceLimit, segmentPos);
 
-        return clearVisibility;
-    }
-    double firstPointAbove(size_t dim)
-    {
-        Node *curr = firstAbove;
-        while (curr && (curr->max[dim] >= pos))
-        {
-            curr = curr->firstAbove;
-        }
+            // Merge the index lists and sort the new list.
+            const NudgingShiftSegment *rhs = 
+                    static_cast<const NudgingShiftSegment *> (rhsSuper);
+            indexes.insert(indexes.end(), rhs->indexes.begin(), rhs->indexes.end());
+            size_t altDim = (dim + 1) % 2;
+            CmpIndexes compare(connRef, altDim);
+            sort(indexes.begin(), indexes.end(), compare);
 
-        if (curr)
-        {
-            return curr->max[dim];
+            // Apply the new positon to all points to keep them constant.
+            for (size_t it = 0; it < indexes.size(); ++it)
+            {
+                size_t index = indexes[it];
+                connRef->displayRoute().ps[index][dimension] = segmentPos;
+            }
         }
-        return -DBL_MAX;
-    }
-    double firstPointBelow(size_t dim)
-    {
-        Node *curr = firstBelow;
-        while (curr && (curr->min[dim] <= pos))
+        bool hasCheckpointAtPosition(const double position, 
+                const size_t dim) const
         {
-            curr = curr->firstBelow;
+            for (size_t cp = 0; cp < checkpoints.size(); ++cp)
+            {
+                if (checkpoints[cp][dim] == position)
+                {
+                    return true;
+                }
+            }
+            return false;
         }
 
-        if (curr)
-        {
-            return curr->min[dim];
-        }
-        return DBL_MAX;
-    }
-    // This is a bit inefficient, but we won't need to do it once we have
-    // connection points.
-    bool isInsideShape(size_t dimension)
-    {
-        for (Node *curr = firstBelow; curr; curr = curr->firstBelow)
+        ConnRef *connRef;
+        Variable *variable;
+        std::vector<size_t> indexes;
+        bool fixed;
+        bool finalSegment;
+        bool endsInShape;
+        bool singleConnectedSegment;
+        std::vector<Point> checkpoints;
+    private:
+        bool sBend;
+        bool zBend;
+        bool lowC(void) const
         {
-            if ((curr->min[dimension] < pos) && (pos < curr->max[dimension]))
+            // This is true if this is a cBend and its adjoining points
+            // are at lower positions.
+            if (!finalSegment && !zigzag() && !fixed && 
+                    (minSpaceLimit == lowPoint()[dimension]))
             {
                 return true;
             }
+            return false;
         }
-        for (Node *curr = firstAbove; curr; curr = curr->firstAbove)
+        bool highC(void) const
         {
-            if ((curr->min[dimension] < pos) && (pos < curr->max[dimension]))
+            // This is true if this is a cBend and its adjoining points
+            // are at higher positions.
+            if (!finalSegment && !zigzag() && !fixed && 
+                    (maxSpaceLimit == lowPoint()[dimension]))
             {
                 return true;
             }
+            return false;
         }
-        return false;
-    }
 };
 
 
-bool CmpNodePos::operator() (const Node* u, const Node* v) const
-{
-    if (u->pos != v->pos)
-    {
-        return u->pos < v->pos;
-    }
-
-    // Use the pointers to the base objects to differentiate them.
-    void *up = (u->v) ? (void *) u->v :
-            ((u->c) ? (void *) u->c : (void *) u->ss);
-    void *vp = (v->v) ? (void *) v->v :
-            ((v->c) ? (void *) v->c : (void *) v->ss);
-    return up < vp;
-}
-
-
-// Note: Open must come first.
-typedef enum {
-    Open = 1,
-    SegOpen = 2,
-    ConnPoint = 3,
-    SegClose = 4,
-    Close = 5
-} EventType;
-
 
-struct Event
-{
-    Event(EventType t, Node *v, double p)
-        : type(t),
-          v(v),
-          pos(p)
-    {};
-    EventType type;
-    Node *v;
-    double pos;
+enum ScanVisDirFlag {
+    VisDirNone  = 0,
+    VisDirUp    = 1,
+    VisDirDown  = 2
 };
+typedef unsigned int ScanVisDirFlags;
 
-Event **events;
 
-
-// Used for quicksort.  Must return <0, 0, or >0.
-static int compare_events(const void *a, const void *b)
-{
-	Event *ea = *(Event**) a;
-	Event *eb = *(Event**) b;
-    if (ea->pos != eb->pos)
-    {
-        return (ea->pos < eb->pos) ? -1 : 1;
-    }
-    if (ea->type != eb->type)
-    {
-        return ea->type - eb->type;
-    }
-    COLA_ASSERT(ea->v != eb->v);
-    return ea->v - eb->v;
-}
-
-
-// Returns a bitfield of the direction of visibility (in this dimension)
-// made up of ConnDirDown (for visibility towards lower position values)
-// and ConnDirUp (for visibility towards higher position values).
+// Returns a bitfield of the directions of visibility in terms of the scanline
+// in a particular dimension dimension.  It will return either ConnDirDown 
+// (meaning visibility to lower position values) or ConnDirUp (for visibility 
+// towards higher position values).
 //
-static ConnDirFlags getPosVertInfDirection(VertInf *v, size_t dim)
+static ScanVisDirFlags getPosVertInfDirections(VertInf *v, size_t dim)
 {
     if (dim == XDIM) // X-dimension
     {
         unsigned int dirs = v->visDirections & (ConnDirLeft | ConnDirRight);
         if (dirs == (ConnDirLeft | ConnDirRight))
         {
-            return (ConnDirDown | ConnDirUp);
+            return (VisDirDown | VisDirUp);
         }
         else if (dirs == ConnDirLeft)
         {
-            return ConnDirDown;
+            return VisDirDown;
         }
         else if (dirs == ConnDirRight)
         {
-            return ConnDirUp;
+            return VisDirUp;
         }
     }
     else if (dim == YDIM) // Y-dimension
@@ -526,58 +562,72 @@ static ConnDirFlags getPosVertInfDirection(VertInf *v, size_t dim)
         unsigned int dirs = v->visDirections & (ConnDirDown | ConnDirUp);
         if (dirs == (ConnDirDown | ConnDirUp))
         {
-            return (ConnDirDown | ConnDirUp);
+            return (VisDirDown | VisDirUp);
         }
         else if (dirs == ConnDirDown)
         {
-            // For libavoid the Y-axis points downwards, so in terms of
-            // smaller or larger position values, Down is Up and vice versa.
-            return ConnDirUp;
+            // libavoid's Y-axis points downwards, so where the user has 
+            // specified visibility downwards, this results in visibility to
+            // higher scanline positition values. 
+            return VisDirUp;
         }
         else if (dirs == ConnDirUp)
         {
-            // For libavoid the Y-axis points downwards, so in terms of
-            // smaller or larger position values, Down is Up and vice versa.
-            return ConnDirDown;
+            // libavoid's Y-axis points downwards, so where the user has 
+            // specified visibility upwards, this results in visibility to
+            // lower scanline positition values. 
+            return VisDirDown;
         }
     }
 
     // Can occur for ConnDirNone visibility.
-    return ConnDirNone;
+    return VisDirNone;
 }
 
 
 struct PosVertInf
 {
-    PosVertInf(double p, VertInf *vI, ConnDirFlags d = ConnDirNone)
+    PosVertInf(double p, VertInf *vI, ScanVisDirFlags d = VisDirNone)
         : pos(p),
           vert(vI),
-          dir(d)
+          dirs(d)
     {
     }
-
-    bool operator<(const PosVertInf& rhs) const
+    
+    bool operator<(const PosVertInf& rhs) const 
     {
         if (pos != rhs.pos)
         {
             return pos < rhs.pos;
         }
-        return vert < rhs.vert;
+        if ((vert->id == rhs.vert->id) && (vert->id == dummyOrthogID))
+        {
+            // Multiple dummy nodes can get placed at the same point for 
+            // multiple ShapeConnectionPins on junctions (outside of shapes).
+            // We only need one at each position, so multiples can be seen
+            // as equal here.
+            return false;
+        }
+        if (vert->id != rhs.vert->id)
+        {
+            return vert->id < rhs.vert->id;
+        }
+        return dirs < rhs.dirs;
     }
 
     double pos;
     VertInf *vert;
 
     // A bitfield marking the direction of visibility (in this dimension)
-    // made up of ConnDirDown (for visibility towards lower position values)
-    // and ConnDirUp (for visibility towards higher position values).
+    // made up of VisDirDown (for visibility towards lower position values) 
+    // and VisDirUp (for visibility towards higher position values).
     //
-    ConnDirFlags dir;
+    ScanVisDirFlags dirs;
 };
 
 
 struct CmpVertInf
-{
+{ 
     bool operator()(const VertInf* u, const VertInf* v) const
     {
         // Comparator for VertSet, an ordered set of VertInf pointers.
@@ -600,21 +650,21 @@ struct CmpVertInf
 
 typedef std::set<VertInf *, CmpVertInf> VertSet;
 
-// A set of points to break the line segment,
+// A set of points to break the line segment, 
 // along with vertices for these points.
 typedef std::set<PosVertInf> BreakpointSet;
 
-// Temporary structure used to store the possible horizontal visibility
+// Temporary structure used to store the possible horizontal visibility 
 // lines arising from the vertical sweep.
-class LineSegment
+class LineSegment 
 {
 public:
-    LineSegment(const double& b, const double& f, const double& p,
-                bool /*ss*/ = false, VertInf *bvi = NULL, VertInf *fvi = NULL)
+    LineSegment(const double& b, const double& f, const double& p, 
+            bool ss = false, VertInf *bvi = NULL, VertInf *fvi = NULL)
         : begin(b),
           finish(f),
           pos(p),
-          shapeSide(false)
+          shapeSide(ss)
     {
         COLA_ASSERT(begin < finish);
 
@@ -627,7 +677,6 @@ public:
             vertInfs.insert(fvi);
         }
     }
-
     LineSegment(const double& bf, const double& p, VertInf *bfvi = NULL)
         : begin(bf),
           finish(bf),
@@ -639,9 +688,9 @@ public:
             vertInfs.insert(bfvi);
         }
     }
-
+ 
     // Order by begin, pos, finish.
-    bool operator<(const LineSegment& rhs) const
+    bool operator<(const LineSegment& rhs) const 
     {
         if (begin != rhs.begin)
         {
@@ -667,7 +716,7 @@ public:
             // Lines are exactly equal.
             return true;
         }
-
+        
         if (pos == rhs.pos)
         {
             if (((begin >= rhs.begin) && (begin <= rhs.finish)) ||
@@ -686,14 +735,21 @@ public:
         finish = std::max(finish, segment.finish);
         vertInfs.insert(segment.vertInfs.begin(), segment.vertInfs.end());
     }
-
+    
     VertInf *beginVertInf(void) const
     {
         if (vertInfs.empty())
         {
             return NULL;
         }
-        return *vertInfs.begin();
+        VertInf *inf = *vertInfs.begin();
+        if ( ((inf->point.y == begin) && (inf->point.x == pos)) ||
+             ((inf->point.x == begin) && (inf->point.y == pos)) )
+        {
+            // Only return the point if it is actually at the begin pos.
+            return inf;
+        }
+        return NULL;
     }
     VertInf *finishVertInf(void) const
     {
@@ -701,7 +757,14 @@ public:
         {
             return NULL;
         }
-        return *vertInfs.rbegin();
+        VertInf *inf = *vertInfs.rbegin();
+        if ( ((inf->point.y == finish) && (inf->point.x == pos)) ||
+             ((inf->point.x == finish) && (inf->point.y == pos)) )
+        {
+            // Only return the point if it is actually at the finish pos.
+            return inf;
+        }
+        return NULL;
     }
 
     VertInf *commitPositionX(Router *router, double posX)
@@ -724,7 +787,7 @@ public:
         return found;
     }
     // Set begin endpoint vertex if none has been assigned.
-    void commitBegin(Router *router, VertInf *vert = NULL)
+    void horiCommitBegin(Router *router, VertInf *vert = NULL)
     {
         if (vert)
         {
@@ -734,13 +797,16 @@ public:
         if (vertInfs.empty() ||
                 ((*vertInfs.begin())->point.x != begin))
         {
-            vertInfs.insert(new
-                    VertInf(router, dummyOrthogID, Point(begin, pos)));
+            if (begin != -DBL_MAX)
+            {
+                vertInfs.insert(new
+                        VertInf(router, dummyOrthogID, Point(begin, pos)));
+            }
         }
     }
 
     // Set begin endpoint vertex if none has been assigned.
-    void commitFinish(Router *router, VertInf *vert = NULL)
+    void horiCommitFinish(Router *router, VertInf *vert = NULL)
     {
         if (vert)
         {
@@ -750,17 +816,20 @@ public:
         if (vertInfs.empty() ||
                 ((*vertInfs.rbegin())->point.x != finish))
         {
-            vertInfs.insert(new
-                    VertInf(router, dummyOrthogID, Point(finish, pos)));
+            if (finish != DBL_MAX)
+            {
+                vertInfs.insert(new
+                        VertInf(router, dummyOrthogID, Point(finish, pos)));
+            }
         }
     }
 
-    // Converts a section of the points list to a set of breakPoints.
-    // Returns the first of the intersection points occuring at finishPos.
-    VertSet::iterator addSegmentsUpTo(Router */*router*/, double finishPos)
+    // Converts a section of the points list to a set of breakPoints.  
+    // Returns the first of the intersection points occurring at finishPos.
+    VertSet::iterator addSegmentsUpTo(double finishPos)
     {
         VertSet::iterator firstIntersectionPt = vertInfs.end();
-        for (VertSet::iterator vert = vertInfs.begin();
+        for (VertSet::iterator vert = vertInfs.begin(); 
                 vert != vertInfs.end(); ++vert)
         {
             if ((*vert)->point.x > finishPos)
@@ -768,11 +837,11 @@ public:
                 // We're done.
                 break;
             }
-
+            
             breakPoints.insert(PosVertInf((*vert)->point.x, (*vert),
-                        getPosVertInfDirection(*vert, XDIM)));
+                        getPosVertInfDirections(*vert, XDIM)));
 
-            if ((firstIntersectionPt == vertInfs.end()) &&
+            if ((firstIntersectionPt == vertInfs.end()) && 
                     ((*vert)->point.x == finishPos))
             {
                 firstIntersectionPt = vert;
@@ -782,38 +851,125 @@ public:
         return firstIntersectionPt;
     }
 
-    // Add visibility edge(s) for this segment.  There may be multiple if
+    // Add visibility edge(s) for this segment.  There may be multiple if 
     // one of the endpoints is shared by multiple connector endpoints.
     void addEdgeHorizontal(Router *router)
     {
-        commitBegin(router);
-        commitFinish(router);
+        horiCommitBegin(router);
+        horiCommitFinish(router);
+        
+        addSegmentsUpTo(finish);
+    }
+
+    // Set flags to show what can be passed on this visibility line.
+    // This can be used later to disregard some edges in the visibility
+    // graph when routing particular connectors.
+    void setLongRangeVisibilityFlags(size_t dim)
+    {
+        // First, travel in one direction
+        bool seenConnPt = false;
+        bool seenShapeEdge = false;
+        for (BreakpointSet::iterator nvert = breakPoints.begin(); 
+                nvert != breakPoints.end(); ++nvert)
+        {
+            VertIDProps mask = 0;
+            if (dim == XDIM)
+            {
+                if (seenConnPt)
+                {
+                    mask |= XL_CONN;
+                }
+                if (seenShapeEdge)
+                {
+                    mask |= XL_EDGE;
+                }
+            }
+            else // if (dim == YDIM)
+            {
+                if (seenConnPt)
+                {
+                    mask |= YL_CONN;
+                }
+                if (seenShapeEdge)
+                {
+                    mask |= YL_EDGE;
+                }
+            }
+            nvert->vert->orthogVisPropFlags |= mask;
+
+            if (nvert->vert->id.isConnPt())
+            {
+                seenConnPt = true;
+            }
+            if (nvert->vert->id.isOrthShapeEdge())
+            {
+                seenShapeEdge = true;
+            }
+        }
+        // Then in the other direction
+        seenConnPt = false;
+        seenShapeEdge = false;
+        for (BreakpointSet::reverse_iterator rvert = breakPoints.rbegin(); 
+                rvert != breakPoints.rend(); ++rvert)
+        {
+            VertIDProps mask = 0;
+            if (dim == XDIM)
+            {
+                if (seenConnPt)
+                {
+                    mask |= XH_CONN;
+                }
+                if (seenShapeEdge)
+                {
+                    mask |= XH_EDGE;
+                }
+            }
+            else // if (dim == YDIM)
+            {
+                if (seenConnPt)
+                {
+                    mask |= YH_CONN;
+                }
+                if (seenShapeEdge)
+                {
+                    mask |= YH_EDGE;
+                }
+            }
+            rvert->vert->orthogVisPropFlags |= mask;
 
-        addSegmentsUpTo(router, finish);
+            if (rvert->vert->id.isConnPt())
+            {
+                seenConnPt = true;
+            }
+            if (rvert->vert->id.isOrthShapeEdge())
+            {
+                seenShapeEdge = true;
+            }
+        }
     }
 
     // Add visibility edge(s) for this segment up until an intersection.
     // Then, move the segment beginning to the intersection point, so we
     // later only consider the remainder of the segment.
-    // There may be multiple segments added to the graph if the beginning
+    // There may be multiple segments added to the graph if the beginning 
     // endpoint of the segment is shared by multiple connector endpoints.
-    VertSet addEdgeHorizontalTillIntersection(Router *router,
+    VertSet addEdgeHorizontalTillIntersection(Router *router, 
             LineSegment& vertLine)
     {
         VertSet intersectionSet;
 
-        commitBegin(router);
+        horiCommitBegin(router);
 
         // Does a vertex already exist for this point.
         commitPositionX(router, vertLine.pos);
-
-        // Generate segments and set end iterator to the first point
+   
+        // Generate segments and set end iterator to the first point 
         // at the intersection position.
-        VertSet::iterator restBegin = addSegmentsUpTo(router, vertLine.pos);
+        VertSet::iterator restBegin = addSegmentsUpTo(vertLine.pos);
 
         // Add the intersections points to intersectionSet.
         VertSet::iterator restEnd = restBegin;
-        while ((restEnd != vertInfs.end()) &&
+        while ((restEnd != vertInfs.end()) && 
                 (*restEnd)->point.x == vertLine.pos)
         {
             ++restEnd;
@@ -826,7 +982,7 @@ public:
 
         return intersectionSet;
     }
-
+                
     // Insert vertical breakpoints.
     void insertBreakpointsBegin(Router *router, LineSegment& vertLine)
     {
@@ -839,15 +995,15 @@ public:
         {
             vert = vertLine.finishVertInf();
         }
-        commitBegin(router, vert);
+        horiCommitBegin(router, vert);
 
         for (VertSet::iterator v = vertInfs.begin();
                 v != vertInfs.end(); ++v)
         {
             if ((*v)->point.x == begin)
             {
-                vertLine.breakPoints.insert(PosVertInf(pos, *v,
-                        getPosVertInfDirection(*v, YDIM)));
+                vertLine.breakPoints.insert(PosVertInf(pos, *v, 
+                        getPosVertInfDirections(*v, YDIM)));
             }
         }
     }
@@ -864,7 +1020,7 @@ public:
         {
             vert = vertLine.finishVertInf();
         }
-        commitFinish(router, vert);
+        horiCommitFinish(router, vert);
 
         for (VertSet::iterator v = vertInfs.begin();
                 v != vertInfs.end(); ++v)
@@ -872,37 +1028,82 @@ public:
             if ((*v)->point.x == finish)
             {
                 vertLine.breakPoints.insert(PosVertInf(pos, *v,
-                        getPosVertInfDirection(*v, YDIM)));
+                        getPosVertInfDirections(*v, YDIM)));
             }
         }
     }
     void generateVisibilityEdgesFromBreakpointSet(Router *router, size_t dim)
     {
-        if ((breakPoints.begin())->pos != begin)
+        if (breakPoints.empty() || ((breakPoints.begin())->pos > begin))
         {
-            if (!beginVertInf())
+            // Add a begin point if there was not already an intersection
+            // found at that point. Though, don't do this if the line
+            // segment goes off to infinity -- we can't reach anything
+            // by going in that direction!
+            if (begin == -DBL_MAX)
             {
+                // Shorten line to first intersection point.
+                COLA_ASSERT(!breakPoints.empty());
+                begin = breakPoints.begin()->pos;
+            }
+            else
+            {
+                // Add begin point.
                 Point point(pos, pos);
                 point[dim] = begin;
-                // Add begin point if it didn't intersect another line.
                 VertInf *vert = new VertInf(router, dummyOrthogID, point);
                 breakPoints.insert(PosVertInf(begin, vert));
             }
         }
-        if ((breakPoints.rbegin())->pos != finish)
+        if (breakPoints.empty() || ((breakPoints.rbegin())->pos < finish))
         {
-            if (!finishVertInf())
+            // Add a finish point if there was not already an intersection
+            // found at that point. Though, don't do this if the line
+            // segment goes off to infinity -- we can't reach anything
+            // by going in that direction!
+            if (finish == DBL_MAX)
+            {
+                // Shorten line to last intersection point.
+                finish = breakPoints.rbegin()->pos;
+            }
+            else
             {
+                // Add finish point.
                 Point point(pos, pos);
                 point[dim] = finish;
-                // Add finish point if it didn't intersect another line.
                 VertInf *vert = new VertInf(router, dummyOrthogID, point);
                 breakPoints.insert(PosVertInf(finish, vert));
             }
         }
 
+        // Set flags for orthogonal routing optimisation.
+        setLongRangeVisibilityFlags(dim);
+
         const bool orthogonal = true;
         BreakpointSet::iterator vert, last;
+#if 0
+        last = breakPoints.end();
+        for (vert = breakPoints.begin(); vert != breakPoints.end();)
+        {
+            if (vert->vert->id == dummyOrthogID)
+            {
+                if (last == breakPoints.end() || 
+                        (last->vert->point != vert->vert->point))
+                {
+                    last = vert;
+                }
+                else
+                {
+                    // Already seen a dummy orthogonal point at this 
+                    // position, delete it.
+
+            }
+            else
+            {
+                ++vert;
+            }
+        }
+#endif
         for (vert = last = breakPoints.begin(); vert != breakPoints.end();)
         {
             BreakpointSet::iterator firstPrev = last;
@@ -912,15 +1113,15 @@ public:
                 // Assert points are not at the same position.
                 COLA_ASSERT(vert->vert->point != last->vert->point);
 
-                if ( !(vert->vert->id.isShape || last->vert->id.isShape))
+                if (vert->vert->id.isConnPt() && last->vert->id.isConnPt())
                 {
                     // Here we have a pair of two endpoints that are both
                     // connector endpoints and both are inside a shape.
-
+                    
                     // Give vert visibility back to the first non-connector
                     // endpoint vertex (i.e., the side of the shape).
                     BreakpointSet::iterator side = last;
-                    while (!side->vert->id.isShape)
+                    while (side->vert->id.isConnPt())
                     {
                         if (side == breakPoints.begin())
                         {
@@ -928,54 +1129,58 @@ public:
                         }
                         --side;
                     }
-                    bool canSeeDown = (vert->dir & ConnDirDown);
-                    if (canSeeDown && side->vert->id.isShape)
+                    bool canSeeDown = (vert->dirs & VisDirDown);
+                    if (canSeeDown && !(side->vert->id.isConnPt()))
                     {
-                        EdgeInf *edge = new
+                        EdgeInf *edge = new 
                                 EdgeInf(side->vert, vert->vert, orthogonal);
-                        edge->setDist(vert->vert->point[dim] -
+                        edge->setDist(vert->vert->point[dim] - 
                                 side->vert->point[dim]);
                     }
 
                     // Give last visibility back to the first non-connector
                     // endpoint vertex (i.e., the side of the shape).
                     side = vert;
-                    while ((side != breakPoints.end()) &&
-                            !side->vert->id.isShape)
+                    while ((side != breakPoints.end()) && 
+                            side->vert->id.isConnPt())
                     {
                         ++side;
                     }
-                    bool canSeeUp = (last->dir & ConnDirUp);
+                    bool canSeeUp = (last->dirs & VisDirUp);
                     if (canSeeUp && (side != breakPoints.end()))
                     {
-                        EdgeInf *edge = new
+                        EdgeInf *edge = new 
                                 EdgeInf(last->vert, side->vert, orthogonal);
-                        edge->setDist(side->vert->point[dim] -
+                        edge->setDist(side->vert->point[dim] - 
                                 last->vert->point[dim]);
                     }
                 }
-
+                
                 // The normal case.
                 //
-                // Note: It's okay to give two connector endpoints visbility
-                // here since we only consider the partner endpoint as a
+                // Note: It's okay to give two connector endpoints visibility 
+                // here since we only consider the partner endpoint as a 
                 // candidate while searching if it is the other endpoint of
                 // the connector in question.
                 //
                 bool generateEdge = true;
-                if (!last->vert->id.isShape && !(last->dir & ConnDirUp))
+                if (last->vert->id.isConnPt() && !(last->dirs & VisDirUp))
                 {
+                    // Don't generate the visibility segment if the ConnEnd
+                    // doesn't have visibility in that direction.
                     generateEdge = false;
                 }
-                else if (!vert->vert->id.isShape && !(vert->dir & ConnDirDown))
+                else if (vert->vert->id.isConnPt() && !(vert->dirs & VisDirDown))
                 {
+                    // Don't generate the visibility segment if the ConnEnd
+                    // doesn't have visibility in that direction.
                     generateEdge = false;
                 }
                 if (generateEdge)
                 {
-                    EdgeInf *edge =
+                    EdgeInf *edge = 
                             new EdgeInf(last->vert, vert->vert, orthogonal);
-                    edge->setDist(vert->vert->point[dim] -
+                    edge->setDist(vert->vert->point[dim] - 
                             last->vert->point[dim]);
                 }
 
@@ -992,8 +1197,8 @@ public:
             }
             else
             {
-                // vert has moved to the beginning of a number number group.
-                // Last is now in the right place, so do nothing.
+                // vert has moved to the beginning of a group at a new 
+                // position.  Last is now in the right place, so do nothing.
             }
         }
     }
@@ -1001,14 +1206,16 @@ public:
     double begin;
     double finish;
     double pos;
-    bool shapeSide;
 
+    // XXX shapeSide is unused and could possibly be removed?
+    bool shapeSide;
+    
     VertSet vertInfs;
     BreakpointSet breakPoints;
 private:
-	// MSVC wants to generate the assignment operator and the default
-	// constructor, but fails.  Therefore we declare them private and
-	// don't implement them.
+    // MSVC wants to generate the assignment operator and the default 
+    // constructor, but fails.  Therefore we declare them private and 
+    // don't implement them.
     LineSegment & operator=(LineSegment const &);
     LineSegment();
 };
@@ -1037,7 +1244,7 @@ class SegmentListWrapper
                     }
                     else
                     {
-                        // This is the first overlapping segment, so just
+                        // This is the first overlapping segment, so just 
                         // merge the new segment with this one.
                         curr->mergeVertInfs(segment);
                         found = curr;
@@ -1066,11 +1273,15 @@ class SegmentListWrapper
 // Given a router instance and a set of possible horizontal segments, and a
 // possible vertical visibility segment, compute and add edges to the
 // orthogonal visibility graph for all the visibility edges.
-static void intersectSegments(Router *router, SegmentList& segments,
+static void intersectSegments(Router *router, SegmentList& segments, 
         LineSegment& vertLine)
 {
-    COLA_ASSERT(vertLine.beginVertInf() == NULL);
-    COLA_ASSERT(vertLine.finishVertInf() == NULL);
+    // XXX: It seems that this case can sometimes occur... maybe when
+    // there are many overlapping rectangles.
+    //COLA_ASSERT(vertLine.beginVertInf() == NULL);
+    //COLA_ASSERT(vertLine.finishVertInf() == NULL);
+
+    COLA_ASSERT(!segments.empty());
     for (SegmentList::iterator it = segments.begin(); it != segments.end(); )
     {
         LineSegment& horiLine = *it;
@@ -1078,40 +1289,28 @@ static void intersectSegments(Router *router, SegmentList& segments,
         bool inVertSegRegion = ((vertLine.begin <= horiLine.pos) &&
                                 (vertLine.finish >= horiLine.pos));
 
-        if (horiLine.finish < vertLine.pos)
-        {
-            // Add horizontal visibility segment.
-            horiLine.addEdgeHorizontal(router);
-
-            size_t dim = XDIM; // x-dimension
-            horiLine.generateVisibilityEdgesFromBreakpointSet(router, dim);
-
-            // We've now swept past this horizontal segment, so delete.
-            it = segments.erase(it);
-            continue;
-        }
-        else if (horiLine.begin > vertLine.pos)
+        if (vertLine.pos < horiLine.begin)
         {
             // We've yet to reach this segment in the sweep, so ignore.
             ++it;
             continue;
         }
-        else if (horiLine.begin == vertLine.pos)
+        else if (vertLine.pos == horiLine.begin)
         {
             if (inVertSegRegion)
             {
                 horiLine.insertBreakpointsBegin(router, vertLine);
             }
         }
-        else if (horiLine.finish == vertLine.pos)
+        else if (vertLine.pos == horiLine.finish)
         {
             if (inVertSegRegion)
             {
                 // Add horizontal visibility segment.
                 horiLine.addEdgeHorizontal(router);
-
+            
                 horiLine.insertBreakpointsFinish(router, vertLine);
-
+                
                 size_t dim = XDIM; // x-dimension
                 horiLine.generateVisibilityEdgesFromBreakpointSet(router, dim);
 
@@ -1120,15 +1319,27 @@ static void intersectSegments(Router *router, SegmentList& segments,
                 continue;
             }
         }
+        else if (vertLine.pos > horiLine.finish)
+        {
+            // Add horizontal visibility segment.
+            horiLine.addEdgeHorizontal(router);
+
+            size_t dim = XDIM; // x-dimension
+            horiLine.generateVisibilityEdgesFromBreakpointSet(router, dim);
+
+            // We've now swept past this horizontal segment, so delete.
+            it = segments.erase(it);
+            continue;
+        }
         else
         {
-            COLA_ASSERT(horiLine.begin < vertLine.pos);
-            COLA_ASSERT(horiLine.finish > vertLine.pos);
+            COLA_ASSERT(vertLine.pos > horiLine.begin);
+            COLA_ASSERT(vertLine.pos < horiLine.finish);
 
             if (inVertSegRegion)
             {
                 // Add horizontal visibility segment.
-                VertSet intersectionVerts =
+                VertSet intersectionVerts = 
                         horiLine.addEdgeHorizontalTillIntersection(
                             router, vertLine);
 
@@ -1136,7 +1347,7 @@ static void intersectSegments(Router *router, SegmentList& segments,
                         v != intersectionVerts.end(); ++v)
                 {
                     vertLine.breakPoints.insert(PosVertInf(horiLine.pos, *v,
-                            getPosVertInfDirection(*v, YDIM)));
+                            getPosVertInfDirections(*v, YDIM)));
                 }
             }
         }
@@ -1149,16 +1360,16 @@ static void intersectSegments(Router *router, SegmentList& segments,
 }
 
 
-// Processes an event for the vertical sweep used for computing the static
-// orthogonal visibility graph.  This adds possible visibility sgments to
-// the segments list.
+// Processes an event for the vertical sweep used for computing the static 
+// orthogonal visibility graph.  This adds possible horizontal visibility 
+// segments to the segments list.
 // The first pass is adding the event to the scanline, the second is for
 // processing the event and the third for removing it from the scanline.
-static void processEventVert(Router *router, NodeSet& scanline,
+static void processEventVert(Router *router, NodeSet& scanline, 
         SegmentListWrapper& segments, Event *e, unsigned int pass)
 {
     Node *v = e->v;
-
+    
     if ( ((pass == 1) && (e->type == Open)) ||
          ((pass == 2) && (e->type == ConnPoint)) )
     {
@@ -1168,53 +1379,54 @@ static void processEventVert(Router *router, NodeSet& scanline,
 
         NodeSet::iterator it = v->iter;
         // Work out neighbours
-        if (it != scanline.begin())
+        if (it != scanline.begin()) 
         {
             Node *u = *(--it);
             v->firstAbove = u;
             u->firstBelow = v;
         }
         it = v->iter;
-        if (++it != scanline.end())
+        if (++it != scanline.end()) 
         {
             Node *u = *it;
             v->firstBelow = u;
             u->firstAbove = v;
         }
     }
-
+    
     if (pass == 2)
     {
         if ((e->type == Open) || (e->type == Close))
         {
+            // Only difference between Open and Close is whether the line
+            // segments are at the top or bottom of the shape.  Decide here.
+            double lineY = (e->type == Open) ? v->min[YDIM] : v->max[YDIM];
+
             // Shape edge positions.
-            double minShape = v->min[0];
-            double maxShape = v->max[0];
+            double minShape = v->min[XDIM];
+            double maxShape = v->max[XDIM];
             // As far as we can see.
             double minLimit, maxLimit;
             double minLimitMax, maxLimitMin;
-            v->findFirstPointAboveAndBelow(0, minLimit, maxLimit,
+            v->findFirstPointAboveAndBelow(XDIM, lineY, minLimit, maxLimit,
                     minLimitMax, maxLimitMin);
 
-            // Only difference between Open and Close is whether the line
-            // segments are at the top or bottom of the shape.  Decide here.
-            double lineY = (e->type == Open) ? v->min[1] : v->max[1];
-
+            // Insert possible visibility segments.
             if (minLimitMax >= maxLimitMin)
             {
-                // Insert possible visibility segments.
-                VertInf *vI1 = new VertInf(router, dummyOrthogID,
+                // These vertices represent the shape corners.
+                VertInf *vI1 = new VertInf(router, dummyOrthogShapeID, 
                             Point(minShape, lineY));
-                VertInf *vI2 = new VertInf(router, dummyOrthogID,
+                VertInf *vI2 = new VertInf(router, dummyOrthogShapeID, 
                             Point(maxShape, lineY));
-
+                
                 // There are no overlapping shapes, so give full visibility.
                 if (minLimit < minShape)
                 {
                     segments.insert(LineSegment(minLimit, minShape, lineY,
                                 true, NULL, vI1));
                 }
-                segments.insert(LineSegment(minShape, maxShape, lineY,
+                segments.insert(LineSegment(minShape, maxShape, lineY, 
                             true, vI1, vI2));
                 if (maxShape < maxLimit)
                 {
@@ -1224,15 +1436,25 @@ static void processEventVert(Router *router, NodeSet& scanline,
             }
             else
             {
+                // There are overlapping shapes along this shape edge.
+
                 if ((minLimitMax > minLimit) && (minLimitMax >= minShape))
                 {
-                    segments.insert(LineSegment(minLimit, minLimitMax, lineY,
-                                true, NULL, NULL));
+                    LineSegment *line = segments.insert(
+                            LineSegment(minLimit, minLimitMax, lineY, true));
+                    // Shape corner:
+                    VertInf *vI1 = new VertInf(router, dummyOrthogShapeID, 
+                                Point(minShape, lineY));
+                    line->vertInfs.insert(vI1);
                 }
                 if ((maxLimitMin < maxLimit) && (maxLimitMin <= maxShape))
                 {
-                    segments.insert(LineSegment(maxLimitMin, maxLimit, lineY,
-                                true, NULL, NULL));
+                    LineSegment *line = segments.insert(
+                            LineSegment(maxLimitMin, maxLimit, lineY, true));
+                    // Shape corner:
+                    VertInf *vI2 = new VertInf(router, dummyOrthogShapeID, 
+                                Point(maxShape, lineY));
+                    line->vertInfs.insert(vI2);
                 }
             }
         }
@@ -1243,27 +1465,32 @@ static void processEventVert(Router *router, NodeSet& scanline,
             Point& cp = centreVert->point;
 
             // As far as we can see.
-            double minLimit = v->firstPointAbove(0);
-            double maxLimit = v->firstPointBelow(0);
-            bool inShape = v->isInsideShape(0);
-
+            double minLimit = v->firstPointAbove(XDIM);
+            double maxLimit = v->firstPointBelow(XDIM);
+            bool inShape = v->isInsideShape(XDIM);
+            
+            // Insert if we have visibility in that direction and the segment
+            // length is greater than zero.
             LineSegment *line1 = NULL, *line2 = NULL;
-            if (!inShape || (centreVert->visDirections & ConnDirLeft))
+            if ((centreVert->visDirections & ConnDirLeft) && (minLimit < cp.x))
             {
-                line1 = segments.insert(LineSegment(minLimit, cp.x, e->pos,
+                line1 = segments.insert(LineSegment(minLimit, cp.x, e->pos, 
                         true, NULL, centreVert));
             }
-            if (!inShape || (centreVert->visDirections & ConnDirRight))
+            if ((centreVert->visDirections & ConnDirRight) && (cp.x < maxLimit))
             {
-                line2 = segments.insert(LineSegment(cp.x, maxLimit, e->pos,
+                line2 = segments.insert(LineSegment(cp.x, maxLimit, e->pos, 
                         true, centreVert, NULL));
+                // If there was a line1, then we just merged with it, so
+                // that pointer will be invalid (and now unnecessary).
+                line1 = NULL;
             }
             if (!line1 && !line2)
             {
                 // Add a point segment for the centre point.
                 segments.insert(LineSegment(cp.x, e->pos, centreVert));
             }
-
+            
             if (!inShape)
             {
                 // This is not contained within a shape so add a normal
@@ -1284,13 +1511,13 @@ static void processEventVert(Router *router, NodeSet& scanline,
             }
         }
     }
-
+    
     if ( ((pass == 3) && (e->type == Close)) ||
          ((pass == 2) && (e->type == ConnPoint)) )
     {
         // Clean up neighbour pointers.
         Node *l = v->firstAbove, *r = v->firstBelow;
-        if (l != NULL)
+        if (l != NULL) 
         {
             l->firstBelow = v->firstBelow;
         }
@@ -1309,22 +1536,23 @@ static void processEventVert(Router *router, NodeSet& scanline,
             size_t result;
             result = scanline.erase(v);
             COLA_ASSERT(result == 1);
+            COLA_UNUSED(result);  // Avoid warning.
             delete v;
         }
     }
 }
 
 
-// Processes an event for the vertical sweep used for computing the static
-// orthogonal visibility graph.  This adds possible visibility sgments to
-// the segments list.
+// Processes an event for the vertical sweep used for computing the static 
+// orthogonal visibility graph.  This adds possible vertical visibility 
+// segments to the segments list.
 // The first pass is adding the event to the scanline, the second is for
 // processing the event and the third for removing it from the scanline.
-static void processEventHori(Router */*router*/, NodeSet& scanline,
+static void processEventHori(Router *router, NodeSet& scanline, 
         SegmentListWrapper& segments, Event *e, unsigned int pass)
 {
     Node *v = e->v;
-
+    
     if ( ((pass == 1) && (e->type == Open)) ||
          ((pass == 2) && (e->type == ConnPoint)) )
     {
@@ -1334,56 +1562,72 @@ static void processEventHori(Router */*router*/, NodeSet& scanline,
 
         NodeSet::iterator it = v->iter;
         // Work out neighbours
-        if (it != scanline.begin())
+        if (it != scanline.begin()) 
         {
             Node *u = *(--it);
             v->firstAbove = u;
             u->firstBelow = v;
         }
         it = v->iter;
-        if (++it != scanline.end())
+        if (++it != scanline.end()) 
         {
             Node *u = *it;
             v->firstBelow = u;
             u->firstAbove = v;
         }
     }
-
+    
     if (pass == 2)
     {
         if ((e->type == Open) || (e->type == Close))
         {
+            // Only difference between Open and Close is whether the line
+            // segments are at the left or right of the shape.  Decide here.
+            double lineX = (e->type == Open) ? v->min[XDIM] : v->max[XDIM];
+
             // Shape edge positions.
-            double minShape = v->min[1];
-            double maxShape = v->max[1];
+            double minShape = v->min[YDIM];
+            double maxShape = v->max[YDIM];
             // As far as we can see.
             double minLimit, maxLimit;
             double minLimitMax, maxLimitMin;
-            v->findFirstPointAboveAndBelow(1, minLimit, maxLimit,
+            v->findFirstPointAboveAndBelow(YDIM, lineX, minLimit, maxLimit,
                     minLimitMax, maxLimitMin);
 
-            // Only difference between Open and Close is whether the line
-            // segments are at the left or right of the shape.  Decide here.
-            double lineX = (e->type == Open) ? v->min[0] : v->max[0];
-
             if (minLimitMax >= maxLimitMin)
             {
-                LineSegment vertSeg = LineSegment(minLimit, maxLimit, lineX);
-                segments.insert(vertSeg);
+                LineSegment *line = segments.insert(
+                        LineSegment(minLimit, maxLimit, lineX));
+
+                // Shape corners:
+                VertInf *vI1 = new VertInf(router, dummyOrthogShapeID, 
+                        Point(lineX, minShape));
+                VertInf *vI2 = new VertInf(router, dummyOrthogShapeID, 
+                        Point(lineX, maxShape));
+                line->vertInfs.insert(vI1);
+                line->vertInfs.insert(vI2);
             }
             else
             {
                 if ((minLimitMax > minLimit) && (minLimitMax >= minShape))
                 {
-                    LineSegment vertSeg =
-                            LineSegment(minLimit, minLimitMax, lineX);
-                    segments.insert(vertSeg);
+                    LineSegment *line = segments.insert(
+                            LineSegment(minLimit, minLimitMax, lineX));
+
+                    // Shape corner:
+                    VertInf *vI1 = new VertInf(router, dummyOrthogShapeID, 
+                                Point(lineX, minShape));
+                    line->vertInfs.insert(vI1);
                 }
                 if ((maxLimitMin < maxLimit) && (maxLimitMin <= maxShape))
                 {
-                    LineSegment vertSeg =
-                            LineSegment(maxLimitMin, maxLimit, lineX);
-                    segments.insert(vertSeg);
+                    LineSegment *line = segments.insert(
+                            LineSegment(maxLimitMin, maxLimit, lineX));
+
+                    // Shape corner:
+                    VertInf *vI2 = new VertInf(router, dummyOrthogShapeID, 
+                                Point(lineX, maxShape));
+                    line->vertInfs.insert(vI2);
                 }
             }
         }
@@ -1394,27 +1638,29 @@ static void processEventHori(Router */*router*/, NodeSet& scanline,
             Point& cp = centreVert->point;
 
             // As far as we can see.
-            double minLimit = v->firstPointAbove(1);
-            double maxLimit = v->firstPointBelow(1);
-            bool inShape = v->isInsideShape(1);
-
-            if (!inShape || (centreVert->visDirections & ConnDirUp))
+            double minLimit = v->firstPointAbove(YDIM);
+            double maxLimit = v->firstPointBelow(YDIM);
+            
+            // Insert if we have visibility in that direction and the segment
+            // length is greater than zero.
+            if ((centreVert->visDirections & ConnDirUp) && (minLimit < cp.y))
             {
                 segments.insert(LineSegment(minLimit, cp.y, e->pos));
             }
-            if (!inShape || (centreVert->visDirections & ConnDirDown))
+
+            if ((centreVert->visDirections & ConnDirDown) && (cp.y < maxLimit))
             {
                 segments.insert(LineSegment(cp.y, maxLimit, e->pos));
             }
         }
     }
-
+    
     if ( ((pass == 3) && (e->type == Close)) ||
          ((pass == 2) && (e->type == ConnPoint)) )
     {
         // Clean up neighbour pointers.
         Node *l = v->firstAbove, *r = v->firstBelow;
-        if (l != NULL)
+        if (l != NULL) 
         {
             l->firstBelow = v->firstBelow;
         }
@@ -1433,47 +1679,138 @@ static void processEventHori(Router */*router*/, NodeSet& scanline,
             size_t result;
             result = scanline.erase(v);
             COLA_ASSERT(result == 1);
+            COLA_UNUSED(result);  // Avoid warning.
             delete v;
         }
     }
 }
 
+// Correct visibility for pins or connector endpoints on the leading or
+// trailing edge of the visibility graph which may only have visibility in 
+// the outward direction where there will not be a possible path.
+void fixConnectionPointVisibilityOnOutsideOfVisibilityGraph(Event **events, 
+        size_t totalEvents, ConnDirFlags addedVisibility)
+{
+    if (totalEvents > 0)
+    {
+        double firstPos = events[0]->pos;
+        size_t index = 0;
+        while (index < totalEvents)
+        {
+            if (events[index]->pos > firstPos)
+            {
+                break;
+            }
+
+            if (events[index]->v->c)
+            {
+                events[index]->v->c->visDirections |= addedVisibility;
+            }
+            ++index;
+        }
+        index = 0;
+        double lastPos = events[totalEvents - 1]->pos;
+        while (index < totalEvents)
+        {
+            size_t revIndex = totalEvents - 1 - index;
+            if (events[revIndex]->pos < lastPos)
+            {
+                break;
+            }
+
+            if (events[revIndex]->v->c)
+            {
+                events[revIndex]->v->c->visDirections |= addedVisibility;
+            }
+            ++index;
+        }
+    }
+}
 
 extern void generateStaticOrthogonalVisGraph(Router *router)
 {
-    const size_t n = router->shapeRefs.size();
+    const size_t n = router->m_obstacles.size();
     const unsigned cpn = router->vertices.connsSize();
     // Set up the events for the vertical sweep.
     size_t totalEvents = (2 * n) + cpn;
-    events = new Event*[totalEvents];
+    Event **events = new Event*[totalEvents];
     unsigned ctr = 0;
-    ShapeRefList::iterator shRefIt = router->shapeRefs.begin();
+    ObstacleList::iterator obstacleIt = router->m_obstacles.begin();
     for (unsigned i = 0; i < n; i++)
     {
-        ShapeRef *shRef = *shRefIt;
-        double minX, minY, maxX, maxY;
-        shRef->polygon().getBoundingRect(&minX, &minY, &maxX, &maxY);
-        double midX = minX + ((maxX - minX) / 2);
-        Node *v = new Node(shRef, midX);
-        events[ctr++] = new Event(Open, v, minY);
-        events[ctr++] = new Event(Close, v, maxY);
-
-        ++shRefIt;
+        Obstacle *obstacle = *obstacleIt;
+#ifndef PAPER
+        JunctionRef *junction = dynamic_cast<JunctionRef *> (obstacle);
+        if (junction && ! junction->positionFixed())
+        {
+            // Junctions that are free to move are not treated as obstacles.
+            ++obstacleIt;
+            totalEvents -= 2;
+            continue;
+        }
+#endif
+
+        Box bbox = obstacle->routingBox();
+        double midX = bbox.min.x + ((bbox.max.x - bbox.min.x) / 2);
+        Node *v = new Node(obstacle, midX);
+        events[ctr++] = new Event(Open, v, bbox.min.y);
+        events[ctr++] = new Event(Close, v, bbox.max.y);
+
+        ++obstacleIt;
+    }
+
+#ifdef DEBUGHANDLER
+    if (router->debugHandler())
+    {
+        std::vector<Box> obstacleBoxes;
+        ObstacleList::iterator obstacleIt = router->m_obstacles.begin();
+        for (unsigned i = 0; i < n; i++)
+        {
+            Obstacle *obstacle = *obstacleIt;
+            JunctionRef *junction = dynamic_cast<JunctionRef *> (obstacle);
+            if (junction && ! junction->positionFixed())
+            {
+                // Junctions that are free to move are not treated as obstacles.
+                ++obstacleIt;
+                continue;
+            }
+            Box bbox = obstacle->routingBox();
+            obstacleBoxes.push_back(bbox);
+            ++obstacleIt;
+        }
+        router->debugHandler()->updateObstacleBoxes(obstacleBoxes);
     }
-    for (VertInf *curr = router->vertices.connsBegin();
-            curr && (curr != router->vertices.shapesBegin());
+#endif
+
+    for (VertInf *curr = router->vertices.connsBegin(); 
+            curr && (curr != router->vertices.shapesBegin()); 
             curr = curr->lstNext)
     {
+        if (curr->visDirections == ConnDirNone)
+        {
+            // This is a connector endpoint that is attached to a connection
+            // pin on a shape, so it doesn't need to be given visibility.
+            // Thus, skip it and record that there is one less total event.
+            --totalEvents;
+            continue;
+        }
         Point& point = curr->point;
 
         Node *v = new Node(curr, point.x);
         events[ctr++] = new Event(ConnPoint, v, point.y);
     }
     qsort((Event*)events, (size_t) totalEvents, sizeof(Event*), compare_events);
-
-    // Process the vertical sweep.
+    
+    // Correct visibility for pins or connector endpoints on the leading or
+    // trailing edge of the visibility graph which may only have visibility in 
+    // the outward direction where there will not be a possible path.  We
+    // fix this by giving them visibility left and right.
+    fixConnectionPointVisibilityOnOutsideOfVisibilityGraph(events, totalEvents, 
+            (ConnDirLeft | ConnDirRight));
+
+    // Process the vertical sweep -- creating cadidate horizontal edges.
     // We do multiple passes over sections of the list so we can add relevant
-    // entries to the scanline that might follow, before process them.
+    // entries to the scanline that might follow, before processing them.
     SegmentListWrapper segments;
     NodeSet scanline;
     double thisPos = (totalEvents > 0) ? events[0]->pos : 0;
@@ -1481,6 +1818,11 @@ extern void generateStaticOrthogonalVisGraph(Router *router)
     unsigned int posFinishIndex = 0;
     for (unsigned i = 0; i <= totalEvents; ++i)
     {
+        // Progress reporting and continuation check.
+        router->performContinuationCheck(
+                TransactionPhaseOrthogonalVisibilityGraphScanX, 
+                i, totalEvents);
+
         // If we have finished the current scanline or all events, then we
         // process the events on the current scanline in a couple of passes.
         if ((i == totalEvents) || (events[i]->pos != thisPos))
@@ -1490,7 +1832,7 @@ extern void generateStaticOrthogonalVisGraph(Router *router)
             {
                 for (unsigned j = posStartIndex; j < posFinishIndex; ++j)
                 {
-                    processEventVert(router, scanline, segments,
+                    processEventVert(router, scanline, segments, 
                             events[j], pass);
                 }
             }
@@ -1505,12 +1847,12 @@ extern void generateStaticOrthogonalVisGraph(Router *router)
             posStartIndex = i;
         }
 
-        // Do the first sweep event handling -- building the correct
+        // Do the first sweep event handling -- building the correct 
         // structure of the scanline.
         const int pass = 1;
         processEventVert(router, scanline, segments, events[i], pass);
     }
-    COLA_ASSERT(scanline.empty());
+    COLA_ASSERT(scanline.size() == 0);
     for (unsigned i = 0; i < totalEvents; ++i)
     {
         delete events[i];
@@ -1521,23 +1863,38 @@ extern void generateStaticOrthogonalVisGraph(Router *router)
     // Set up the events for the horizontal sweep.
     SegmentListWrapper vertSegments;
     ctr = 0;
-    shRefIt = router->shapeRefs.begin();
+    obstacleIt = router->m_obstacles.begin();
     for (unsigned i = 0; i < n; i++)
     {
-        ShapeRef *shRef = *shRefIt;
-        double minX, minY, maxX, maxY;
-        shRef->polygon().getBoundingRect(&minX, &minY, &maxX, &maxY);
-        double midY = minY + ((maxY - minY) / 2);
-        Node *v = new Node(shRef, midY);
-        events[ctr++] = new Event(Open, v, minX);
-        events[ctr++] = new Event(Close, v, maxX);
-
-        ++shRefIt;
+        Obstacle *obstacle = *obstacleIt;
+#ifndef PAPER
+        JunctionRef *junction = dynamic_cast<JunctionRef *> (obstacle);
+        if (junction && ! junction->positionFixed())
+        {
+            // Junctions that are free to move are not treated as obstacles.
+            ++obstacleIt;
+            continue;
+        }
+#endif
+        Box bbox = obstacle->routingBox();
+        double midY = bbox.min.y + ((bbox.max.y - bbox.min.y) / 2);
+        Node *v = new Node(obstacle, midY);
+        events[ctr++] = new Event(Open, v, bbox.min.x);
+        events[ctr++] = new Event(Close, v, bbox.max.x);
+
+        ++obstacleIt;
     }
-    for (VertInf *curr = router->vertices.connsBegin();
-            curr && (curr != router->vertices.shapesBegin());
+    for (VertInf *curr = router->vertices.connsBegin(); 
+            curr && (curr != router->vertices.shapesBegin()); 
             curr = curr->lstNext)
     {
+        if (curr->visDirections == ConnDirNone)
+        {
+            // This is a connector endpoint that is attached to a connection
+            // pin on a shape, so it doesn't need to be given visibility.
+            // Thus, skip it.
+            continue;
+        }
         Point& point = curr->point;
 
         Node *v = new Node(curr, point.y);
@@ -1545,11 +1902,23 @@ extern void generateStaticOrthogonalVisGraph(Router *router)
     }
     qsort((Event*)events, (size_t) totalEvents, sizeof(Event*), compare_events);
 
-    // Process the horizontal sweep
+    // Correct visibility for pins or connector endpoints on the leading or
+    // trailing edge of the visibility graph which may only have visibility in 
+    // the outward direction where there will not be a possible path.  We
+    // fix this by giving them visibility up and down.
+    fixConnectionPointVisibilityOnOutsideOfVisibilityGraph(events, totalEvents, 
+            (ConnDirUp | ConnDirDown));
+
+    // Process the horizontal sweep -- creating vertical visibility edges.
     thisPos = (totalEvents > 0) ? events[0]->pos : 0;
     posStartIndex = 0;
     for (unsigned i = 0; i <= totalEvents; ++i)
     {
+        // Progress reporting and continuation check.
+        router->performContinuationCheck(
+                TransactionPhaseOrthogonalVisibilityGraphScanY, 
+                i, totalEvents);
+
         // If we have finished the current scanline or all events, then we
         // process the events on the current scanline in a couple of passes.
         if ((i == totalEvents) || (events[i]->pos != thisPos))
@@ -1559,11 +1928,11 @@ extern void generateStaticOrthogonalVisGraph(Router *router)
             {
                 for (unsigned j = posStartIndex; j < posFinishIndex; ++j)
                 {
-                    processEventHori(router, scanline, vertSegments,
+                    processEventHori(router, scanline, vertSegments, 
                             events[j], pass);
                 }
             }
-
+            
             // Process the merged line segments.
             vertSegments.list().sort();
             for (SegmentList::iterator curr = vertSegments.list().begin();
@@ -1583,27 +1952,27 @@ extern void generateStaticOrthogonalVisGraph(Router *router)
             posStartIndex = i;
         }
 
-        // Do the first sweep event handling -- building the correct
+        // Do the first sweep event handling -- building the correct 
         // structure of the scanline.
         const int pass = 1;
         processEventHori(router, scanline, vertSegments, events[i], pass);
     }
-    COLA_ASSERT(scanline.empty());
+    COLA_ASSERT(scanline.size() == 0);
     for (unsigned i = 0; i < totalEvents; ++i)
     {
         delete events[i];
     }
-    delete [] events;
+    delete [] events; 
 
-    // Add portions of the horizontal line that are after the final vertical
+    // Add portions of horizontal lines that are after the final vertical
     // position we considered.
-    for (SegmentList::iterator it = segments.list().begin();
+    for (SegmentList::iterator it = segments.list().begin(); 
             it != segments.list().end(); )
     {
         LineSegment& horiLine = *it;
 
         horiLine.addEdgeHorizontal(router);
-
+        
         size_t dim = XDIM; // x-dimension
         horiLine.generateVisibilityEdgesFromBreakpointSet(router, dim);
 
@@ -1617,386 +1986,300 @@ extern void generateStaticOrthogonalVisGraph(Router *router)
 //============================================================================
 
 
+typedef std::pair<Point, Point> RectBounds;
 
-
-// Processes sweep events used to determine each horizontal and vertical
-// line segment in a connector's channel of visibility.
-// Four calls to this function are made at each position by the scanline:
-//   1) Handle all Close event processing.
-//   2) Remove Close event objects from the scanline.
-//   3) Add Open event objects to the scanline.
-//   4) Handle all Open event processing.
-//
-static void processShiftEvent(Router */*router*/, NodeSet& scanline,
-                              ShiftSegmentList& /*segments*/, Event *e, size_t dim,
-                              unsigned int pass)
+static bool insideRectBounds(const Point& point, const RectBounds& rectBounds)
 {
-    Node *v = e->v;
-
-    if ( ((pass == 3) && (e->type == Open)) ||
-         ((pass == 3) && (e->type == SegOpen)) )
+    Point zero(0, 0);
+    if ((rectBounds.first == zero) && (rectBounds.second == zero))
     {
-        std::pair<NodeSet::iterator, bool> result = scanline.insert(v);
-        v->iter = result.first;
-        COLA_ASSERT(result.second);
-
-        NodeSet::iterator it = v->iter;
-        // Work out neighbours
-        if (it != scanline.begin())
-        {
-            Node *u = *(--it);
-            v->firstAbove = u;
-            u->firstBelow = v;
-        }
-        it = v->iter;
-        if (++it != scanline.end())
-        {
-            Node *u = *it;
-            v->firstBelow = u;
-            u->firstAbove = v;
-        }
-    }
-
-    if ( ((pass == 4) && (e->type == Open)) ||
-         ((pass == 4) && (e->type == SegOpen)) ||
-         ((pass == 1) && (e->type == SegClose)) ||
-         ((pass == 1) && (e->type == Close)) )
-    {
-        if (v->ss)
-        {
-            // As far as we can see.
-            double minLimit = v->firstObstacleAbove(dim);
-            double maxLimit = v->firstObstacleBelow(dim);
-
-            v->ss->minSpaceLimit =
-                    std::max(minLimit, v->ss->minSpaceLimit);
-            v->ss->maxSpaceLimit =
-                    std::min(maxLimit, v->ss->maxSpaceLimit);
-        }
-        else
-        {
-            v->markShiftSegmentsAbove(dim);
-            v->markShiftSegmentsBelow(dim);
-        }
+        // We can't be inside the invalid rectangle.
+        return false;
     }
 
-    if ( ((pass == 2) && (e->type == SegClose)) ||
-         ((pass == 2) && (e->type == Close)) )
+    for (size_t i = 0; i < 2; ++i)
     {
-        // Clean up neighbour pointers.
-        Node *l = v->firstAbove, *r = v->firstBelow;
-        if (l != NULL)
+        if (point[i] < rectBounds.first[i])
         {
-            l->firstBelow = v->firstBelow;
+            return false;
         }
-        if (r != NULL)
+        if (point[i] > rectBounds.second[i])
         {
-            r->firstAbove = v->firstAbove;
+            return false;
         }
-
-        size_t result;
-        result = scanline.erase(v);
-        COLA_ASSERT(result == 1);
-        delete v;
     }
+    return true;
 }
 
 
-static void buildOrthogonalChannelInfo(Router *router,
+static void buildOrthogonalNudgingSegments(Router *router, 
         const size_t dim, ShiftSegmentList& segmentList)
 {
-    if (router->routingPenalty(segmentPenalty) == 0)
+    if (router->routingParameter(segmentPenalty) == 0)
     {
-        // This code assumes the routes are pretty optimal, so we don't
-        // do this adjustment if the routes have no segment penalty.
+        // The nudging code assumes the routes are pretty optimal.  This will
+        // only be true if a segment penalty is set, so just return if this 
+        // is not the case.
         return;
     }
+    bool nudgeFinalSegments = 
+            router->routingOption(nudgeOrthogonalSegmentsConnectedToShapes);
+    std::vector<RectBounds> shapeLimits;
+    if (nudgeFinalSegments)
+    {
+        // If we're going to nudge final segments, then cache the shape 
+        // rectangles to save us rebuilding them multiple times.
+        const size_t n = router->m_obstacles.size();
+        shapeLimits = std::vector<RectBounds>(n);
+
+        double zeroBufferDist = 0.0;
+
+        ObstacleList::iterator obstacleIt = router->m_obstacles.begin();
+        for (unsigned i = 0; i < n; i++)
+        {
+            ShapeRef *shape = dynamic_cast<ShapeRef *> (*obstacleIt);
+            JunctionRef *junction = dynamic_cast<JunctionRef *> (*obstacleIt);
+            if (shape)
+            {
+                // Take the real bounds of the shape
+                Box bBox = shape->polygon().offsetBoundingBox(zeroBufferDist);
+                shapeLimits[i] = std::make_pair(bBox.min, bBox.max);
+            }
+            else if (junction)
+            {
+                // Don't nudge segments attached to junctions,
+                // so just use the junction position here.
+                Point pos = junction->position();
+                shapeLimits[i] = std::make_pair(pos, pos);
+            }
+            ++obstacleIt;
+        }
+    }
 
     size_t altDim = (dim + 1) % 2;
     // For each connector.
-    for (ConnRefList::const_iterator curr = router->connRefs.begin();
-            curr != router->connRefs.end(); ++curr)
+    for (ConnRefList::const_iterator curr = router->connRefs.begin(); 
+            curr != router->connRefs.end(); ++curr) 
     {
         if ((*curr)->routingType() != ConnType_Orthogonal)
         {
             continue;
         }
         Polygon& displayRoute = (*curr)->displayRoute();
-        // Determine all line segments that we are interested in shifting.
+        // Determine all line segments that we are interested in shifting. 
         // We don't consider the first or last segment of a path.
-        for (size_t i = 1; i < displayRoute.size()-1; ++i)
+        for (size_t i = 1; i < displayRoute.size(); ++i)
         {
             if (displayRoute.ps[i - 1][dim] == displayRoute.ps[i][dim])
             {
                 // It's a segment in the dimension we are processing,
                 size_t indexLow = i - 1;
                 size_t indexHigh = i;
-                if (displayRoute.ps[i - 1][altDim] > displayRoute.ps[i][altDim])
+                if (displayRoute.ps[i - 1][altDim] == 
+                        displayRoute.ps[i][altDim])
+                {
+                    // This is a zero length segment, so ignore it.
+                    continue;
+                }
+                else if (displayRoute.ps[i - 1][altDim] > 
+                        displayRoute.ps[i][altDim])
                 {
                     indexLow = i;
                     indexHigh = i - 1;
                 }
-                COLA_ASSERT(displayRoute.at(indexLow)[altDim] <
-                        displayRoute.at(indexHigh)[altDim]);
 
+                // Find the checkpoints on the current segment and the 
+                // checkpoints on the adjoining segments that aren't on
+                // the corner (hence the +1 and -1 modifiers).
+                std::vector<Point> checkpoints = 
+                        displayRoute.checkpointsOnSegment(i - 1);
+                std::vector<Point> prevCheckpoints = 
+                        displayRoute.checkpointsOnSegment(i - 2, -1);
+                std::vector<Point> nextCheckpoints = 
+                        displayRoute.checkpointsOnSegment(i, +1);
+                bool hasCheckpoints = (checkpoints.size() > 0); 
+                if (hasCheckpoints && !nudgeFinalSegments)
+                {
+                    // This segment includes one of the routing
+                    // checkpoints so we shouldn't shift it.
+                    segmentList.push_back(new NudgingShiftSegment(
+                            *curr, indexLow, indexHigh, dim));
+                    continue;
+                }
+
+                double thisPos = displayRoute.ps[i][dim];
+                
                 if ((i == 1) || ((i + 1) == displayRoute.size()))
                 {
-                    // The first and last segment of a connector can't be
-                    // shifted.  We call them fixed segments.  Note: this
-                    // will change if we later allow connection channels.
-                    segmentList.push_back(
-                            ShiftSegment(*curr, indexLow, indexHigh, dim));
+                    // Is first or last segment of route.
+                    
+                    if (nudgeFinalSegments)
+                    {
+                        // Determine available space for nudging these
+                        // final segments.
+                        double minLim = -CHANNEL_MAX;
+                        double maxLim = CHANNEL_MAX;
+                        
+                        // If the position of the opposite end of the
+                        // attached segment is within the shape boundaries
+                        // then we want to use this as an ideal position
+                        // for the segment.
+
+                        // Bitflags indicating whether this segment starts 
+                        // and/or ends in a shape.
+                        unsigned int endsInShapes = 0;
+                        // Also limit their movement to the edges of the 
+                        // shapes they begin or end within.
+                        for (size_t k = 0; k < shapeLimits.size(); ++k)
+                        {
+                            double shapeMin = shapeLimits[k].first[dim];
+                            double shapeMax = shapeLimits[k].second[dim];
+                            if (insideRectBounds(displayRoute.ps[i - 1], 
+                                        shapeLimits[k]))
+                            {
+                                minLim = std::max(minLim, shapeMin);
+                                maxLim = std::min(maxLim, shapeMax);
+                                endsInShapes |= 0x01;
+                            }
+                            if (insideRectBounds(displayRoute.ps[i], 
+                                        shapeLimits[k]))
+                            {
+                                minLim = std::max(minLim, shapeMin);
+                                maxLim = std::min(maxLim, shapeMax);
+                                endsInShapes |= 0x10;
+                            }
+                        }
+
+                        if ( endsInShapes == 0 )
+                        {
+                            // If the segment is not within a shape, then we
+                            // should limit it's nudging buffer so we don't
+                            // combine many unnecessary regions.
+                            double pos = displayRoute.ps[i - 1][dim];
+                            double freeConnBuffer = 15;
+                            minLim = std::max(minLim, pos - freeConnBuffer);
+                            maxLim = std::min(maxLim, pos + freeConnBuffer);
+                        }
+
+                        if ((minLim == maxLim) || (*curr)->hasFixedRoute())
+                        {
+                            // Fixed.
+                            segmentList.push_back(new NudgingShiftSegment(*curr, 
+                                    indexLow, indexHigh, dim));
+                        }
+                        else
+                        {
+                            // Shiftable.
+                            NudgingShiftSegment *segment = new NudgingShiftSegment(
+                                    *curr, indexLow, indexHigh, false, false, dim, 
+                                    minLim, maxLim);
+                            segment->finalSegment = true;
+                            segment->endsInShape = (endsInShapes > 0);
+                            if ((displayRoute.size() == 2) && 
+                                    (endsInShapes = 0x11))
+                            {
+                                // This is a single segment connector bridging
+                                // two shapes.  So, we want to try to keep the
+                                // segment centred rather than shift it.
+                                segment->singleConnectedSegment = true;
+                            }
+                            segmentList.push_back(segment);
+                        }
+                    }
+                    else
+                    {
+                        // The first and last segment of a connector can't be 
+                        // shifted.  We call them fixed segments.  
+                        segmentList.push_back(new NudgingShiftSegment(*curr, 
+                               indexLow, indexHigh, dim));
+                    }
                     continue;
                 }
+                
 
                 // The segment probably has space to be shifted.
                 double minLim = -CHANNEL_MAX;
                 double maxLim = CHANNEL_MAX;
-                bool isSBend = false;
 
-                double prevPos = displayRoute.ps[i - 2][dim];
-                double nextPos = displayRoute.ps[i + 1][dim];
-                if (((prevPos < displayRoute.ps[i][dim]) &&
-                     (nextPos > displayRoute.ps[i][dim]))
-                     ||
-                    ((prevPos > displayRoute.ps[i][dim]) &&
-                     (nextPos < displayRoute.ps[i][dim])) )
+                // Constrain these segments by checkpoints along the
+                // adjoining segments.  Ignore checkpoints at ends of
+                // those segments.  XXX Perhaps this should not
+                // affect the ideal centre position in the channel.
+                for (size_t cp = 0; cp < nextCheckpoints.size(); ++cp)
                 {
-                    isSBend = true;
-
-                    // Determine limits if the s-bend is not due to an
-                    // obstacle.  In this case we need to limit the channel
-                    // to the span of the adjoining segments to this one.
-                    if ((prevPos < displayRoute.ps[i][dim]) &&
-                        (nextPos > displayRoute.ps[i][dim]))
+                    if (nextCheckpoints[cp][dim] < thisPos)
                     {
-                        minLim = std::max(minLim, prevPos);
-                        maxLim = std::min(maxLim, nextPos);
+                        // Not at thisPoint, so constrain.
+                        minLim = std::max(minLim, nextCheckpoints[cp][dim]);
                     }
-                    else
+                    else if (nextCheckpoints[cp][dim] > thisPos)
                     {
-                        minLim = std::max(minLim, nextPos);
-                        maxLim = std::min(maxLim, prevPos);
+                        // Not at thisPoint, so constrain.
+                        maxLim = std::min(maxLim, nextCheckpoints[cp][dim]);
                     }
                 }
-                else
+                for (size_t cp = 0; cp < prevCheckpoints.size(); ++cp)
                 {
-                    // isCBend: Both adjoining segments are in the same
-                    // direction.  We indicate this for later by setting
-                    // the maxLim or minLim to the segment position.
-                    if (prevPos < displayRoute.ps[i][dim])
+                    if (prevCheckpoints[cp][dim] < thisPos)
                     {
-                        minLim = displayRoute.ps[i][dim];
+                        // Not at thisPoint, so constrain.
+                        minLim = std::max(minLim, prevCheckpoints[cp][dim]);
                     }
-                    else
+                    else if (prevCheckpoints[cp][dim] > thisPos)
                     {
-                        maxLim = displayRoute.ps[i][dim];
+                        // Not at thisPoint, so constrain.
+                        maxLim = std::min(maxLim, prevCheckpoints[cp][dim]);
                     }
                 }
 
-                segmentList.push_back(ShiftSegment(*curr, indexLow,
-                            indexHigh, isSBend, dim, minLim, maxLim));
-            }
-        }
-    }
-    if (segmentList.empty())
-    {
-        // There are no segments, so we can just return now.
-        return;
-    }
-
-    // Do a sweep and shift these segments.
-    const size_t n = router->shapeRefs.size();
-    const size_t cpn = segmentList.size();
-    // Set up the events for the sweep.
-    size_t totalEvents = 2 * (n + cpn);
-    events = new Event*[totalEvents];
-    unsigned ctr = 0;
-    ShapeRefList::iterator shRefIt = router->shapeRefs.begin();
-    for (unsigned i = 0; i < n; i++)
-    {
-        ShapeRef *shRef = *shRefIt;
-        Point min, max;
-        shRef->polygon().getBoundingRect(&min.x, &min.y, &max.x, &max.y);
-        double mid = min[dim] + ((max[dim] - min[dim]) / 2);
-        Node *v = new Node(shRef, mid);
-        events[ctr++] = new Event(Open, v, min[altDim]);
-        events[ctr++] = new Event(Close, v, max[altDim]);
-
-        ++shRefIt;
-    }
-    for (ShiftSegmentList::iterator curr = segmentList.begin();
-            curr != segmentList.end(); ++curr)
-    {
-        const Point& lowPt = curr->lowPoint();
-        const Point& highPt = curr->highPoint();
-
-        COLA_ASSERT(lowPt[dim] == highPt[dim]);
-        COLA_ASSERT(lowPt[altDim] < highPt[altDim]);
-        Node *v = new Node(&(*curr), lowPt[dim]);
-        events[ctr++] = new Event(SegOpen, v, lowPt[altDim]);
-        events[ctr++] = new Event(SegClose, v, highPt[altDim]);
-    }
-    qsort((Event*)events, (size_t) totalEvents, sizeof(Event*), compare_events);
+                bool isSBend = false;
+                bool isZBend = false;
 
-    // Process the sweep.
-    // We do multiple passes over sections of the list so we can add relevant
-    // entries to the scanline that might follow, before process them.
-    NodeSet scanline;
-    double thisPos = (totalEvents > 0) ? events[0]->pos : 0;
-    unsigned int posStartIndex = 0;
-    unsigned int posFinishIndex = 0;
-    for (unsigned i = 0; i <= totalEvents; ++i)
-    {
-        // If we have finished the current scanline or all events, then we
-        // process the events on the current scanline in a couple of passes.
-        if ((i == totalEvents) || (events[i]->pos != thisPos))
-        {
-            posFinishIndex = i;
-            for (int pass = 2; pass <= 4; ++pass)
-            {
-                for (unsigned j = posStartIndex; j < posFinishIndex; ++j)
+                if (checkpoints.empty())
                 {
-                    processShiftEvent(router, scanline, segmentList, events[j],
-                            dim, pass);
+                    // Segments with checkpoints are held in place, but for
+                    // other segments, we should limit their movement based 
+                    // on the limits of the segments at either end.
+
+                    double prevPos = displayRoute.ps[i - 2][dim];
+                    double nextPos = displayRoute.ps[i + 1][dim];
+                    if ( ((prevPos < thisPos) && (nextPos > thisPos)) ||
+                         ((prevPos > thisPos) && (nextPos < thisPos)) )
+                    {
+                        // Determine limits if the s-bend is not due to an 
+                        // obstacle.  In this case we need to limit the channel 
+                        // to the span of the adjoining segments to this one.
+                        if ((prevPos < thisPos) && (nextPos > thisPos))
+                        {
+                            minLim = std::max(minLim, prevPos);
+                            maxLim = std::min(maxLim, nextPos);
+                            isZBend = true;
+                        }
+                        else // if ((prevPos > thisPos) && (nextPos < thisPos))
+                        {
+                            minLim = std::max(minLim, nextPos);
+                            maxLim = std::min(maxLim, prevPos);
+                            isSBend = true;
+                        }
+                    }
                 }
-            }
 
-            if (i == totalEvents)
-            {
-                // We have cleaned up, so we can now break out of loop.
-                break;
+                NudgingShiftSegment *nss = new NudgingShiftSegment(*curr,
+                        indexLow, indexHigh, isSBend, isZBend, dim,
+                        minLim, maxLim);
+                nss->checkpoints = checkpoints;
+                segmentList.push_back(nss);
             }
-
-            thisPos = events[i]->pos;
-            posStartIndex = i;
         }
-
-        // Do the first sweep event handling -- building the correct
-        // structure of the scanline.
-        const int pass = 1;
-        processShiftEvent(router, scanline, segmentList, events[i],
-                dim, pass);
     }
-    COLA_ASSERT(scanline.empty());
-    for (unsigned i = 0; i < totalEvents; ++i)
-    {
-        delete events[i];
-    }
-    delete [] events;
 }
 
 
-static void simplifyOrthogonalRoutes(Router *router)
-{
-    // Simplify routes.
-    for (ConnRefList::const_iterator curr = router->connRefs.begin();
-            curr != router->connRefs.end(); ++curr)
-    {
-        if ((*curr)->routingType() != ConnType_Orthogonal)
-        {
-            continue;
-        }
-        (*curr)->set_route((*curr)->displayRoute().simplify());
-    }
-}
-
-
-static void buildOrthogonalNudgingOrderInfo(Router *router,
-        PtOrderMap& pointOrders)
-{
-    // Simplify routes.
-    simplifyOrthogonalRoutes(router);
-
-    int crossingsN = 0;
-
-    // Do segment splitting.
-    for (ConnRefList::const_iterator curr = router->connRefs.begin();
-            curr != router->connRefs.end(); ++curr)
-    {
-        if ((*curr)->routingType() != ConnType_Orthogonal)
-        {
-            continue;
-        }
-        ConnRef *conn = *curr;
-
-        for (ConnRefList::const_iterator curr2 = router->connRefs.begin();
-                curr2 != router->connRefs.end(); ++curr2)
-        {
-            if ((*curr2)->routingType() != ConnType_Orthogonal)
-            {
-                continue;
-            }
-            ConnRef *conn2 = *curr2;
-
-            if (conn == conn2)
-            {
-                continue;
-            }
-
-            Avoid::Polygon& route = conn->displayRoute();
-            Avoid::Polygon& route2 = conn2->displayRoute();
-            splitBranchingSegments(route2, true, route);
-        }
-    }
-
-    for (ConnRefList::const_iterator curr = router->connRefs.begin();
-            curr != router->connRefs.end(); ++curr)
-    {
-        if ((*curr)->routingType() != ConnType_Orthogonal)
-        {
-            continue;
-        }
-        ConnRef *conn = *curr;
-
-        for (ConnRefList::const_iterator curr2 = curr;
-                curr2 != router->connRefs.end(); ++curr2)
-        {
-            if ((*curr2)->routingType() != ConnType_Orthogonal)
-            {
-                continue;
-            }
-            ConnRef *conn2 = *curr2;
-
-            if (conn == conn2)
-            {
-                continue;
-            }
+typedef std::vector<ConnRef *> ConnRefVector;
+typedef std::vector<Polygon> RouteVector;
 
-            Avoid::Polygon& route = conn->displayRoute();
-            Avoid::Polygon& route2 = conn2->displayRoute();
-            bool checkForBranchingSegments = false;
-            int crossings = 0;
-            for (size_t i = 1; i < route.size(); ++i)
-            {
-                const bool finalSegment = ((i + 1) == route.size());
-                crossings += countRealCrossings(route2, true, route, i,
-                        checkForBranchingSegments, finalSegment, NULL,
-                        &pointOrders, conn2, conn).first;
-            }
-            if (crossings > 0)
-            {
-                crossingsN += crossings;
-            }
-        }
-    }
-
-    // Sort the point orders.
-    PtOrderMap::iterator finish = pointOrders.end();
-    for (PtOrderMap::iterator it = pointOrders.begin(); it != finish; ++it)
-    {
-        //const VertID& ptID = it->first;
-        PtOrder& order = it->second;
-
-        for (size_t dim = XDIM; dim <= YDIM; ++dim)
-        {
-            order.sort(dim);
-        }
-    }
-}
 
-
-class CmpLineOrder
+class CmpLineOrder 
 {
     public:
         CmpLineOrder(PtOrderMap& ord, const size_t dim)
@@ -2004,66 +2287,73 @@ class CmpLineOrder
               dimension(dim)
         {
         }
-        bool operator()(const ShiftSegment& lhs, const ShiftSegment& rhs,
+        bool operator()(const ShiftSegment *lhsSuper, 
+                const ShiftSegment *rhsSuper,
                 bool *comparable = NULL) const
         {
+            const NudgingShiftSegment *lhs = 
+                    static_cast<const NudgingShiftSegment *> (lhsSuper);
+            const NudgingShiftSegment *rhs = 
+                    static_cast<const NudgingShiftSegment *> (rhsSuper);
             if (comparable)
             {
                 *comparable = true;
             }
-            Point lhsLow  = lhs.lowPoint();
-            Point rhsLow  = rhs.lowPoint();
-#ifndef NDEBUG
-            const Point& lhsHigh = lhs.highPoint();
-            const Point& rhsHigh = rhs.highPoint();
-#endif
+            Point lhsLow  = lhs->lowPoint(); 
+            Point rhsLow  = rhs->lowPoint(); 
             size_t altDim = (dimension + 1) % 2;
-
+#ifndef NDEBUG
+            const Point& lhsHigh = lhs->highPoint(); 
+            const Point& rhsHigh = rhs->highPoint(); 
             COLA_ASSERT(lhsLow[dimension] == lhsHigh[dimension]);
             COLA_ASSERT(rhsLow[dimension] == rhsHigh[dimension]);
+#endif
 
+            // We consider things at effectively the same position to 
+            // be ordered based on their order and fixedOrder, so only 
+            // compare segments further apart than the nudgeDistance.
             if (lhsLow[dimension] != rhsLow[dimension])
             {
                 return lhsLow[dimension] < rhsLow[dimension];
             }
 
             // If one of these is fixed, then determine order based on
-            // fixed segment, that is, order so the fixed segment doesn't
+            // fixed segment, that is, order so the fixed segment doesn't 
             // block movement.
             bool oneIsFixed = false;
-            const int lhsFixedOrder = lhs.fixedOrder(oneIsFixed);
-            const int rhsFixedOrder = rhs.fixedOrder(oneIsFixed);
+            const int lhsFixedOrder = lhs->fixedOrder(oneIsFixed);
+            const int rhsFixedOrder = rhs->fixedOrder(oneIsFixed);
             if (oneIsFixed && (lhsFixedOrder != rhsFixedOrder))
             {
                 return lhsFixedOrder < rhsFixedOrder;
             }
 
-            // C-bends that did not have a clear order with s-bends might
-            // not have a good ordering here, so compare their order in
+            // C-bends that did not have a clear order with s-bends might 
+            // not have a good ordering here, so compare their order in 
             // terms of C-bend direction and S-bends and use that if it
             // differs for the two segments.
-            const int lhsOrder = lhs.order();
-            const int rhsOrder = rhs.order();
+            const int lhsOrder = lhs->order();
+            const int rhsOrder = rhs->order();
             if (lhsOrder != rhsOrder)
             {
                 return lhsOrder < rhsOrder;
             }
-
+            
             // Need to index using the original point into the map, so find it.
             Point& unchanged = (lhsLow[altDim] > rhsLow[altDim]) ?
                     lhsLow : rhsLow;
 
             PtOrder& lowOrder = orders[unchanged];
-            int lhsPos = lowOrder.positionFor(lhs.connRef, dimension);
-            int rhsPos = lowOrder.positionFor(rhs.connRef, dimension);
+            int lhsPos = lowOrder.positionFor(dimension, lhs->connRef);
+            int rhsPos = lowOrder.positionFor(dimension, rhs->connRef);
             if ((lhsPos == -1) || (rhsPos == -1))
             {
                 // A value for rhsPos or lhsPos mean the points are not directly
                 // comparable, meaning they are at the same position but cannot
-                // overlap (they are just collinear.  The relative order for
+                // overlap (they are just collinear.  The relative order for 
                 // these segments is not important since we do not constrain
                 // them against each other.
-                //COLA_ASSERT(lhs.overlapsWith(rhs, dimension) == false);
+                //COLA_ASSERT(lhs->overlapsWith(rhs, dimension) == false);
                 // We do need to be consistent though.
                 if (comparable)
                 {
@@ -2071,7 +2361,6 @@ class CmpLineOrder
                 }
                 return lhsLow[altDim] < rhsLow[altDim];
             }
-
             return lhsPos < rhsPos;
         }
 
@@ -2080,29 +2369,63 @@ class CmpLineOrder
 };
 
 
-// We can use the normaal sort algorithm for lists since it is not possible
-// to comapre all elements, but there will be an ordering defined between
-// most of the elements.  Hence we order these, using insertion sort, and
-// the case of them not being able to be compared is handled by not setting
+// We can't use the normal sort algorithm for lists since it is not possible 
+// to compare all elements, but there will be an ordering defined between 
+// most of the elements.  Hence we order these, using insertion sort, and 
+// the case of them not being able to be compared is handled by not setting 
 // up any constraints between such segments when doing the nudging.
 //
-static ShiftSegmentList linesort(ShiftSegmentList origList,
-        CmpLineOrder& comparison)
+static ShiftSegmentList linesort(bool nudgeFinalSegments, 
+        ShiftSegmentList origList, CmpLineOrder& comparison)
 {
+    // Cope with end segments that are getting moved and will line up with
+    // other segments of the same connector.  We do this by merging them into
+    // a single NudgingShiftSegment.
+    if (nudgeFinalSegments)
+    {
+        for (ShiftSegmentList::iterator currSegIt = origList.begin();
+                currSegIt != origList.end(); ++currSegIt)
+        {
+            for (ShiftSegmentList::iterator otherSegIt = currSegIt;
+                    otherSegIt != origList.end(); )
+            {
+                NudgingShiftSegment *currSeg = 
+                        static_cast<NudgingShiftSegment *> (*currSegIt);
+                NudgingShiftSegment *otherSeg = 
+                        static_cast<NudgingShiftSegment *> (*otherSegIt);
+                if ((currSegIt != otherSegIt) && currSeg && otherSeg && 
+                        currSeg->shouldAlignWith(otherSeg, comparison.dimension))
+                {
+                    currSeg->mergeWith(otherSeg, comparison.dimension);
+                    delete otherSeg;
+                    otherSegIt = origList.erase(otherSegIt);
+                }
+                else
+                {
+                    ++otherSegIt;
+                }
+            }
+        }
+    }
+
     ShiftSegmentList resultList;
 
+    size_t origListSize = origList.size();
+    size_t deferredN = 0; 
     while (!origList.empty())
     {
         // Get and remove the first element from the origList.
-        ShiftSegment segment = origList.front();
+        ShiftSegment *segment = origList.front();
         origList.pop_front();
 
         // Find the insertion point in the resultList.
+        bool allComparable = true;
         ShiftSegmentList::iterator curr;
         for (curr = resultList.begin(); curr != resultList.end(); ++curr)
         {
             bool comparable = false;
             bool lessThan = comparison(segment, *curr, &comparable);
+            allComparable &= comparable;
 
             if (comparable && lessThan)
             {
@@ -2111,9 +2434,22 @@ static ShiftSegmentList linesort(ShiftSegmentList origList,
                 break;
             }
         }
-
-        // Insert the element into the reultList at the required point.
-        resultList.insert(curr, segment);
+    
+        if (resultList.empty() || allComparable || (deferredN >= origListSize))
+        {
+            // Insert the element into the resultList at the required point.
+            resultList.insert(curr, segment);
+            // Reset the origListSize and deferred counter.
+            deferredN = 0;
+            origListSize = origList.size();
+        }
+        else
+        {
+            // This wasn't comparable to anything in the sorted list, 
+            // so defer addition of the segment till later.
+            origList.push_back(segment);
+            deferredN++;
+        }
     }
 
     return resultList;
@@ -2122,28 +2458,182 @@ static ShiftSegmentList linesort(ShiftSegmentList origList,
 
 typedef std::list<ShiftSegment *> ShiftSegmentPtrList;
 
+class PotentialSegmentConstraint
+{
+    public:
+        PotentialSegmentConstraint(size_t index1, size_t index2,
+                const Variables& vs)
+            : index1(index1),
+              index2(index2),
+              vs(vs)
+        {
+        }
+
+        bool operator<(const PotentialSegmentConstraint rhs) const
+        {
+            return sepDistance() < rhs.sepDistance();
+        }
+        double sepDistance(void) const
+        {
+            if (!stillValid())
+            {
+                return 0;
+            }
+            return fabs(vs[index1]->finalPosition - vs[index2]->finalPosition);
+        }
+        bool stillValid(void) const
+        {
+            return (index1 != index2);
+        }
+        void rewriteIndex(size_t oldIndex, size_t newIndex)
+        {
+            if (index1 == oldIndex)
+            {
+                index1 = newIndex;
+            }
+
+            if (index2 == oldIndex)
+            {
+                index2 = newIndex;
+            }
+        }
+
+        size_t index1;
+        size_t index2;
+
+    private:
+        const Variables& vs;
+};
+
 
-static void nudgeOrthogonalRoutes(Router *router, size_t dimension,
-        PtOrderMap& pointOrders, ShiftSegmentList& segmentList)
+class ImproveOrthogonalRoutes
 {
+public:
+    ImproveOrthogonalRoutes(Router *router);
+    void execute(void);
+
+private:
+    void simplifyOrthogonalRoutes(void);
+    void buildOrthogonalNudgingOrderInfo(void);
+    void nudgeOrthogonalRoutes(size_t dimension,
+           bool justUnifying = false);
+
+    Router *m_router;
+    PtOrderMap m_point_orders;
+    UnsignedPairSet m_shared_path_connectors_with_common_endpoints;
+    ShiftSegmentList m_segment_list;
+};
+
+
+ImproveOrthogonalRoutes::ImproveOrthogonalRoutes(Router *router)
+    : m_router(router)
+{
+}
+
+void ImproveOrthogonalRoutes::execute(void)
+{
+    TIMER_START(m_router, tmOrthogNudge);
+
+    m_shared_path_connectors_with_common_endpoints.clear();
+
+    // Simplify routes.
+    simplifyOrthogonalRoutes();
+
+    // Build a cache that denotes whether a certain segment of a connector
+    // contains a checkpoint.  We can't just compare positions, since routes
+    // can be moved away from their original positions during nudging.
+    buildConnectorRouteCheckpointCache(m_router);
+
+    // Do Unifying first, by itself.  This greedily tries to position free
+    // segments in overlapping channels at the same position.  This way they
+    // have correct nudging orders determined for them since they will form
+    // shared paths, rather than segments just positioned as an results of
+    // the routing process.  Of course, don't do this when rerouting with
+    // a fixedSharedPathPenalty since these routes include extra segments
+    // we want to keep apart which prevent some shared paths.
+    if (m_router->routingOption(performUnifyingNudgingPreprocessingStep) &&
+            (m_router->routingParameter(fixedSharedPathPenalty) == 0))
+    {
+        for (size_t dimension = 0; dimension < 2; ++dimension)
+        {
+            // Just perform Unifying operation.
+            bool justUnifying = true;
+            m_segment_list.clear();
+            buildOrthogonalNudgingSegments(m_router, dimension, m_segment_list);
+            buildOrthogonalChannelInfo(m_router, dimension, m_segment_list);
+            nudgeOrthogonalRoutes(dimension, justUnifying);
+        }
+    }
+
+#ifndef DEBUG_JUST_UNIFY
+    // Do the Nudging and centring.
+    for (size_t dimension = 0; dimension < 2; ++dimension)
+    {
+        m_point_orders.clear();
+        // Build nudging info.
+        // XXX Needs to be rebuilt for each dimension, cause of shifting
+        //     points.  Maybe we could modify the point orders.
+        buildOrthogonalNudgingOrderInfo();
+
+        // Do the centring and nudging.
+        m_segment_list.clear();
+        buildOrthogonalNudgingSegments(m_router, dimension, m_segment_list);
+        buildOrthogonalChannelInfo(m_router, dimension, m_segment_list);
+        nudgeOrthogonalRoutes(dimension);
+    }
+#endif // DEBUG_JUST_UNIFY
+
+    // Resimplify all the display routes that may have been split.
+    simplifyOrthogonalRoutes();
+
+    m_router->improveOrthogonalTopology();
+
+    // Clear the segment-checkpoint cache for connectors.
+    clearConnectorRouteCheckpointCache(m_router);
+
+    TIMER_STOP(m_router);
+}
+
+void ImproveOrthogonalRoutes::nudgeOrthogonalRoutes(size_t dimension,
+       bool justUnifying)
+{
+    bool nudgeFinalSegments = m_router->routingOption(
+            nudgeOrthogonalSegmentsConnectedToShapes);
+    bool nudgeSharedPathsWithCommonEnd = m_router->routingOption(
+            nudgeSharedPathsWithCommonEndPoint);
+    double baseSepDist = m_router->routingParameter(idealNudgingDistance);
+    COLA_ASSERT(baseSepDist >= 0);
+    // If we can fit things with the desired separation distance, then
+    // we try 10 times, reducing each time by a 10th of the original amount.
+    double reductionSteps = 10.0;
+
+    size_t totalSegmentsToShift = m_segment_list.size();
+    size_t numOfSegmentsShifted = 0;
     // Do the actual nudging.
     ShiftSegmentList currentRegion;
-    while (!segmentList.empty())
+    while (!m_segment_list.empty())
     {
+        // Progress reporting and continuation check.
+        numOfSegmentsShifted = totalSegmentsToShift - m_segment_list.size();
+        m_router->performContinuationCheck(
+                (dimension == XDIM) ? TransactionPhaseOrthogonalNudgingX :
+                TransactionPhaseOrthogonalNudgingY, numOfSegmentsShifted,
+                totalSegmentsToShift);
+
         // Take a reference segment
-        ShiftSegment& currentSegment = segmentList.front();
+        ShiftSegment *currentSegment = m_segment_list.front();
         // Then, find the segments that overlap this one.
         currentRegion.clear();
         currentRegion.push_back(currentSegment);
-        segmentList.erase(segmentList.begin());
-        for (ShiftSegmentList::iterator curr = segmentList.begin();
-                curr != segmentList.end(); )
+        m_segment_list.erase(m_segment_list.begin());
+        for (ShiftSegmentList::iterator curr = m_segment_list.begin();
+                curr != m_segment_list.end(); )
         {
             bool overlaps = false;
             for (ShiftSegmentList::iterator curr2 = currentRegion.begin();
                     curr2 != currentRegion.end(); ++curr2)
             {
-                if (curr->overlapsWith(*curr2, dimension))
+                if ((*curr)->overlapsWith(*curr2, dimension))
                 {
                     overlaps = true;
                     break;
@@ -2152,90 +2642,131 @@ static void nudgeOrthogonalRoutes(Router *router, size_t dimension,
             if (overlaps)
             {
                 currentRegion.push_back(*curr);
-                segmentList.erase(curr);
-                // Consider segments from the beginning, since we mave have
+                m_segment_list.erase(curr);
+                // Consider segments from the beginning, since we may have
                 // since passed segments that overlap with the new set.
-                curr = segmentList.begin();
+                curr = m_segment_list.begin();
             }
             else
             {
                 ++curr;
             }
         }
-        CmpLineOrder lineSortComp(pointOrders, dimension);
-        currentRegion = linesort(currentRegion, lineSortComp);
+
+        if (! justUnifying)
+        {
+            CmpLineOrder lineSortComp(m_point_orders, dimension);
+            currentRegion = linesort(nudgeFinalSegments, currentRegion,
+                    lineSortComp);
+        }
 
         if (currentRegion.size() == 1)
         {
             // Save creating the solver instance if there is just one
-            // immovable segment.
-            if (!currentRegion.front().sBend)
+            // immovable segment, or if we are in the unifying stage.
+            if (currentRegion.front()->immovable() || justUnifying)
             {
+                delete currentRegion.front();
                 continue;
             }
         }
 
         // Process these segments.
+        std::list<size_t> freeIndexes;
         Variables vs;
         Constraints cs;
+        Constraints gapcs;
         ShiftSegmentPtrList prevVars;
-        // IDs:
-        const int freeID    = 0;
-        const int fixedID   = 1;
-        // Weights:
-        double freeWeight   = 0.00001;
-        double strongWeight = 0.001;
-        double fixedWeight  = 100000;
-        //printf("-------------------------------------------------------\n");
-        //printf("Nudge -- size: %d\n", (int) currentRegion.size());
-        for (ShiftSegmentList::iterator currSegment = currentRegion.begin();
-                currSegment != currentRegion.end(); ++currSegment)
+        double sepDist = baseSepDist;
+#ifdef NUDGE_DEBUG
+        fprintf(stderr, "-------------------------------------------------------\n");
+        fprintf(stderr, "%s -- size: %d\n", (justUnifying) ? "Unifying" : "Nudging",
+                (int) currentRegion.size());
+#endif
+#ifdef NUDGE_DEBUG_SVG
+        printf("\n\n");
+#endif
+        for (ShiftSegmentList::iterator currSegmentIt = currentRegion.begin();
+                currSegmentIt != currentRegion.end(); ++currSegmentIt )
         {
-            Point& lowPt = currSegment->lowPoint();
+            NudgingShiftSegment *currSegment = static_cast<NudgingShiftSegment *> (*currSegmentIt);
 
             // Create a solver variable for the position of this segment.
-            int varID = freeID;
-            double idealPos = lowPt[dimension];
-            double weight = freeWeight;
-            if (currSegment->sBend)
-            {
-                COLA_ASSERT(currSegment->minSpaceLimit > -CHANNEL_MAX);
-                COLA_ASSERT(currSegment->maxSpaceLimit < CHANNEL_MAX);
+            currSegment->createSolverVariable(justUnifying);
 
-                // For s-bends, take the middle as ideal.
-                idealPos = currSegment->minSpaceLimit +
-                        ((currSegment->maxSpaceLimit -
-                          currSegment->minSpaceLimit) / 2);
-            }
-            else if (currSegment->fixed)
+            vs.push_back(currSegment->variable);
+            size_t index = vs.size() - 1;
+#ifdef NUDGE_DEBUG
+            fprintf(stderr,"line(%d)  %.15f  dim: %d pos: %.16f\n"
+                   "min: %.16f  max: %.16f\n"
+                   "minEndPt: %.16f  maxEndPt: %.16f weight: %g cc: %d\n",
+                    currSegment->connRef->id(),
+                    currSegment->lowPoint()[dimension], (int) dimension,
+                    currSegment->variable->desiredPosition,
+                    currSegment->minSpaceLimit, currSegment->maxSpaceLimit,
+                    currSegment->lowPoint()[!dimension], currSegment->highPoint()[!dimension],
+                    currSegment->variable->weight,
+                    (int) currSegment->checkpoints.size());
+#endif
+#ifdef NUDGE_DEBUG_SVG
+            // Debugging info:
+            double minP = std::max(currSegment->minSpaceLimit, -5000.0);
+            double maxP = std::min(currSegment->maxSpaceLimit, 5000.0);
+            fprintf(stdout, "<rect style=\"fill: #f00; opacity: 0.2;\" "
+                    "x=\"%g\" y=\"%g\" width=\"%g\" height=\"%g\" />\n",
+                    currSegment->lowPoint()[XDIM], minP,
+                    currSegment->highPoint()[XDIM] - currSegment->lowPoint()[XDIM],
+                    maxP - minP);
+            fprintf(stdout, "<line style=\"stroke: #000;\" x1=\"%g\" "
+                    "y1=\"%g\" x2=\"%g\" y2=\"%g\" />\n",
+                    currSegment->lowPoint()[XDIM], currSegment->lowPoint()[YDIM],
+                    currSegment->highPoint()[XDIM], currSegment->highPoint()[YDIM]);
+#endif
+
+            if (justUnifying)
             {
-                // Fixed segments shouldn't get moved.
-                weight = fixedWeight;
-                varID = fixedID;
+                // Just doing centring, not nudging.
+                // Record the index of the variable so we can use it as
+                // a segment to potentially constrain to other segments.
+                if (currSegment->variable->weight == freeWeight)
+                {
+                    freeIndexes.push_back(index);
+                }
+                // Thus, we don't need to constrain position against other
+                // segments.
+                prevVars.push_back(&(*currSegment));
+                continue;
             }
-            else
+
+            // The constraints generated here must be in order of 
+            // leftBoundary-segment ... segment-segment ... segment-rightBoundary
+            // since this order is leveraged later for rewriting the 
+            // separations of unsatisfable channel groups.
+
+            // Constrain to channel boundary.
+            if (!currSegment->fixed)
             {
-                // Set a higher weight for c-bends to stop them sometimes
-                // getting pushed out into channels by more-free connectors
-                // to the "inner" side of them.
-                weight = strongWeight;
+                // If this segment sees a channel boundary to its left,
+                // then constrain its placement as such.
+                if (currSegment->minSpaceLimit > -CHANNEL_MAX)
+                {
+                    vs.push_back(new Variable(channelLeftID,
+                                currSegment->minSpaceLimit, fixedWeight));
+                    cs.push_back(new Constraint(vs[vs.size() - 1], vs[index],
+                                0.0));
+                }
             }
-            currSegment->variable = new Variable(varID, idealPos, weight);
-            vs.push_back(currSegment->variable);
-            size_t index = vs.size() - 1;
-            //printf("line  %.15f  pos: %g   min: %g  max: %g\n",
-            //        lowPt[dimension], idealPos, currSegment->minSpaceLimit,
-            //        currSegment->maxSpaceLimit);
 
             // Constrain position in relation to previously seen segments,
             // if necessary (i.e. when they could overlap).
             for (ShiftSegmentPtrList::iterator prevVarIt = prevVars.begin();
-                    prevVarIt != prevVars.end(); )
+                    prevVarIt != prevVars.end(); ++prevVarIt)
             {
-                ShiftSegment *prevSeg = *prevVarIt;
+                NudgingShiftSegment *prevSeg =
+                        static_cast<NudgingShiftSegment *> (*prevVarIt);
                 Variable *prevVar = prevSeg->variable;
 
-                if (currSegment->overlapsWith(*prevSeg, dimension) &&
+                if (currSegment->overlapsWith(prevSeg, dimension) &&
                         (!(currSegment->fixed) || !(prevSeg->fixed)))
                 {
                     // If there is a previous segment to the left that
@@ -2243,104 +2774,485 @@ static void nudgeOrthogonalRoutes(Router *router, size_t dimension,
                     // constrain the two segments to be separated.
                     // Though don't add the constraint if both the
                     // segments are fixed in place.
-                    cs.push_back(new Constraint(prevVar, vs[index],
-                            router->orthogonalNudgeDistance()));
-                    prevVarIt = prevVars.erase(prevVarIt);
-                }
-                else
-                {
-                    ++prevVarIt;
+                    double thisSepDist = sepDist;
+                    bool equality = false;
+                    if (currSegment->shouldAlignWith(prevSeg, dimension))
+                    {
+                        // Handles the case where the two end segments can
+                        // be brought together to make a single segment. This
+                        // can help in situations where having the small kink
+                        // can restrict other kinds of nudging.
+                        thisSepDist = 0;
+                        equality = true;
+                    }
+                    else if (currSegment->canAlignWith(prevSeg, dimension))
+                    {
+                        // We need to address the problem of two neighbouring
+                        // segments of the same connector being kept separated
+                        // due only to a kink created in the other dimension.
+                        // Here, we let such segments drift back together.
+                        thisSepDist = 0;
+                    }
+                    else if (!nudgeSharedPathsWithCommonEnd &&
+                            (m_shared_path_connectors_with_common_endpoints.count(
+                                 UnsignedPair(currSegment->connRef->id(), prevSeg->connRef->id())) > 0))
+                    {
+                        // We don't want to nudge apart these two segments
+                        // since they are from a shared path with a common
+                        // endpoint.  There might be multiple chains of
+                        // segments that don't all have the same endpoints
+                        // so we need to make this an equality to prevent
+                        // some of them possibly getting nudged apart.
+                        thisSepDist = 0;
+                        equality = true;
+                    }
+
+                    Constraint *constraint = new Constraint(prevVar,
+                            vs[index], thisSepDist, equality);
+                    cs.push_back(constraint);
+                    if (thisSepDist)
+                    {
+                        // Add to the list of gap constraints so we can
+                        // rewrite the separation distance later.
+                        gapcs.push_back(constraint);
+                    }
                 }
             }
 
             if (!currSegment->fixed)
             {
-                // If this segment sees a channel boundary to its left,
-                // then constrain its placement as such.
-                if (currSegment->minSpaceLimit > -CHANNEL_MAX)
-                {
-                    vs.push_back(new Variable(fixedID,
-                                currSegment->minSpaceLimit, fixedWeight));
-                    cs.push_back(new Constraint(vs[vs.size() - 1], vs[index],
-                                0.0));
-                }
-
                 // If this segment sees a channel boundary to its right,
                 // then constrain its placement as such.
                 if (currSegment->maxSpaceLimit < CHANNEL_MAX)
                 {
-                    vs.push_back(new Variable(fixedID,
+                    vs.push_back(new Variable(channelRightID,
                                 currSegment->maxSpaceLimit, fixedWeight));
                     cs.push_back(new Constraint(vs[index], vs[vs.size() - 1],
                                 0.0));
                 }
             }
+
             prevVars.push_back(&(*currSegment));
         }
-#if 0
-        for(unsigned i=0;i<vs.size();i++) {
-            printf("-vs[%d]=%f\n",i,vs[i]->desiredPosition);
+
+        std::list<PotentialSegmentConstraint> potentialConstraints;
+        if (justUnifying)
+        {
+            for (std::list<size_t>::iterator curr = freeIndexes.begin();
+                    curr != freeIndexes.end(); ++curr)
+            {
+                for (std::list<size_t>::iterator curr2 = curr;
+                        curr2 != freeIndexes.end(); ++curr2)
+                {
+                    if (curr == curr2)
+                    {
+                        continue;
+                    }
+                    potentialConstraints.push_back(
+                            PotentialSegmentConstraint(*curr, *curr2, vs));
+                }
+            }
         }
-#endif
-        IncSolver f(vs,cs);
-        f.solve();
-        bool satisfied = true;
-        for (size_t i = 0; i < vs.size(); ++i)
+#ifdef NUDGE_DEBUG
+        for (unsigned i = 0;i < vs.size(); ++i)
         {
-            if (vs[i]->id == fixedID)
+            fprintf(stderr, "-vs[%d]=%f\n", i, vs[i]->desiredPosition);
+        }
+#endif
+        // Repeatedly try solving this.  There are two cases:
+        //  -  When Unifying, we greedily place as many free segments as
+        //     possible at the same positions, that way they have more
+        //     accurate nudging orders determined for them in the Nudging
+        //     stage.
+        //  -  When Nudging, if we can't fit all the segments with the
+        //     default nudging distance we try smaller separation
+        //     distances till we find a solution that is satisfied.
+        bool justAddedConstraint = false;
+        bool satisfied;
+
+        typedef std::pair<size_t, size_t> UnsatisfiedRange;
+        std::list<UnsatisfiedRange> unsatisfiedRanges;
+        do
+        {
+            IncSolver f(vs, cs);
+            f.solve();
+
+            // Determine if the problem was satisfied.
+            satisfied = true;
+            for (size_t i = 0; i < vs.size(); ++i)
+            {
+                // For each variable...
+                if (vs[i]->id != freeSegmentID)
+                {
+                    // If it is a fixed segment (should stay still)...
+                    if (fabs(vs[i]->finalPosition -
+                            vs[i]->desiredPosition) > 0.0001)
+                    {
+                        // and it is not at it's desired position, then
+                        // we consider the problem to be unsatisfied.
+                        satisfied = false;
+
+                        // We record ranges of unsatisfied variables based on
+                        // the channel edges.
+                        if (vs[i]->id == channelLeftID)
+                        {
+                            // This is the left-hand-side of a channel.
+                            if (unsatisfiedRanges.empty() ||
+                                    (unsatisfiedRanges.back().first !=
+                                    unsatisfiedRanges.back().second))
+                            {
+                                // There are no existing unsatisfied ranges,
+                                // or there are but they are a valid range
+                                // (we've encountered the right-hand channel
+                                // edges already).
+                                // So, start a new unsatisfied range.
+                                unsatisfiedRanges.push_back(
+                                        std::make_pair(i, i + 1));
+                            }
+                        }
+                        else if (vs[i]->id == channelRightID)
+                        {
+                            // This is the right-hand-side of a channel.
+                            if (unsatisfiedRanges.empty())
+                            {
+                                // There are no existing unsatisfied ranges,
+                                // so start a new unsatisfied range.
+                                // We are looking at a unsatisfied right side
+                                // where the left side was satisfied, so the 
+                                // range begins at the previous variable
+                                // which should be a left channel side.
+                                COLA_ASSERT(i > 0);
+                                COLA_ASSERT(vs[i - 1]->id == channelLeftID);
+                                unsatisfiedRanges.push_back(
+                                        std::make_pair(i - 1, i));
+                            }
+                            else
+                            {
+                                // Expand the existing range to include index.
+                                unsatisfiedRanges.back().second = i;
+                            }
+                        }
+                        else if (vs[i]->id == fixedSegmentID)
+                        {
+                            // Fixed connector segments can also start and
+                            // extend unsatisfied variable ranges.
+                            if (unsatisfiedRanges.empty())
+                            {
+                                // There are no existing unsatisfied ranges,
+                                // so start a new unsatisfied range.
+                                unsatisfiedRanges.push_back(
+                                        std::make_pair(i, i));
+                            }
+                            else
+                            {
+                                // Expand the existing range to include index.
+                                unsatisfiedRanges.back().second = i;
+                            }
+                        }
+                    }
+                }
+            }
+
+#ifdef NUDGE_DEBUG
+            if (!satisfied)
+            {
+                fprintf(stderr,"unsatisfied\n");
+            }
+#endif
+
+            if (justUnifying)
             {
-                if (fabs(vs[i]->finalPosition - vs[i]->desiredPosition) > 0.01)
+                // When we're centring, we'd like to greedily place as many
+                // segments as possible at the same positions, that way they
+                // have more accurate nudging orders determined for them.
+                //
+                // We do this by taking pairs of adjoining free segments and
+                // attempting to constrain them to have the same position,
+                // starting from the closest up to the furthest.
+
+                if (justAddedConstraint)
                 {
+                    COLA_ASSERT(potentialConstraints.size() > 0);
+                    if (!satisfied)
+                    {
+                        // We couldn't satisfy the problem with the added
+                        // potential constraint, so we can't position these
+                        // segments together.  Roll back.
+                        potentialConstraints.pop_front();
+                        delete cs.back();
+                        cs.pop_back();
+                    }
+                    else
+                    {
+                        // We could position these two segments together.
+                        PotentialSegmentConstraint& pc =
+                                potentialConstraints.front();
+
+                        // Rewrite the indexes of these two variables to
+                        // one, so we need not worry about redundant
+                        // equality constraints.
+                        for (std::list<PotentialSegmentConstraint>::iterator
+                                it = potentialConstraints.begin();
+                                it != potentialConstraints.end(); ++it)
+                        {
+                            it->rewriteIndex(pc.index1, pc.index2);
+                        }
+                        potentialConstraints.pop_front();
+                    }
+                }
+                potentialConstraints.sort();
+                justAddedConstraint = false;
+
+                // Remove now invalid potential segment constraints.
+                // This could have been caused by the variable rewriting.
+                while (!potentialConstraints.empty() &&
+                       !potentialConstraints.front().stillValid())
+                {
+                    potentialConstraints.pop_front();
+                }
+
+                if (!potentialConstraints.empty())
+                {
+                    // We still have more possibilities to consider.
+                    // Create a constraint for this, add it, and mark as
+                    // unsatisfied, so the problem gets re-solved.
+                    PotentialSegmentConstraint& pc =
+                            potentialConstraints.front();
+                    COLA_ASSERT(pc.index1 != pc.index2);
+                    cs.push_back(new Constraint(vs[pc.index1], vs[pc.index2],
+                            0, true));
                     satisfied = false;
-                    break;
+                    justAddedConstraint = true;
+                }
+            }
+            else
+            {
+                if (!satisfied)
+                {
+                    COLA_ASSERT(unsatisfiedRanges.size() > 0);
+                    // Reduce the separation distance.
+                    sepDist -= (baseSepDist / reductionSteps);
+#ifndef NDEBUG
+                    for (std::list<UnsatisfiedRange>::iterator it =
+                            unsatisfiedRanges.begin();
+                            it != unsatisfiedRanges.end(); ++it)
+                    {
+                        COLA_ASSERT(vs[it->first]->id != freeSegmentID);
+                        COLA_ASSERT(vs[it->second]->id != freeSegmentID);
+                    }
+#endif
+#ifdef NUDGE_DEBUG
+                    for (std::list<UnsatisfiedRange>::iterator it =
+                            unsatisfiedRanges.begin();
+                            it != unsatisfiedRanges.end(); ++it)
+                    {
+                        fprintf(stderr, "unsatisfiedVarRange(%ld, %ld)\n",
+                                it->first, it->second);
+                    }
+                    fprintf(stderr, "unsatisfied, trying %g\n", sepDist);
+#endif
+                    // And rewrite all the gap constraints to have the new
+                    // reduced separation distance.
+                    bool withinUnsatisfiedGroup = false;
+                    for (Constraints::iterator cIt = cs.begin();
+                            cIt != cs.end(); ++cIt)
+                    {
+                        UnsatisfiedRange& range = unsatisfiedRanges.front();
+                        Constraint *constraint = *cIt;
+
+                        if (constraint->left == vs[range.first])
+                        {
+                            // Entered an unsatisfied range of variables.
+                            withinUnsatisfiedGroup = true;
+                        }
+
+                        if (withinUnsatisfiedGroup && (constraint->gap > 0))
+                        {
+                            // Rewrite constraints in unsatisfied ranges
+                            // that have a non-zero gap.
+                            constraint->gap = sepDist;
+                        }
+
+                        if (constraint->right == vs[range.second])
+                        {
+                            // Left an unsatisfied range of variables.
+                            withinUnsatisfiedGroup = false;
+                            unsatisfiedRanges.pop_front();
+                            if (unsatisfiedRanges.empty())
+                            {
+                                // And there are no more unsatisfied variables.
+                                break;
+                            }
+                        }
+                    }
                 }
             }
         }
+        while (!satisfied && (sepDist > 0.0001));
+
         if (satisfied)
         {
+#ifdef NUDGE_DEBUG
+            fprintf(stderr,"satisfied at nudgeDist = %g\n", sepDist);
+#endif
             for (ShiftSegmentList::iterator currSegment = currentRegion.begin();
                     currSegment != currentRegion.end(); ++currSegment)
             {
-                Point& lowPt = currSegment->lowPoint();
-                Point& highPt = currSegment->highPoint();
-                double newPos = currSegment->variable->finalPosition;
-                //printf("Pos: %X, %g\n", (int) currSegment->connRef, newPos);
-                lowPt[dimension] = newPos;
-                highPt[dimension] = newPos;
+                NudgingShiftSegment *segment =
+                        static_cast<NudgingShiftSegment *> (*currSegment);
+
+                segment->updatePositionsFromSolver(justUnifying);
             }
         }
-#if 0
+#ifdef NUDGE_DEBUG
         for(unsigned i=0;i<vs.size();i++) {
-            printf("+vs[%d]=%f\n",i,vs[i]->finalPosition);
+            fprintf(stderr, "+vs[%d]=%f\n",i,vs[i]->finalPosition);
         }
 #endif
-        for_each(vs.begin(),vs.end(),delete_object());
-        for_each(cs.begin(),cs.end(),delete_object());
+#ifdef NUDGE_DEBUG_SVG
+        for (ShiftSegmentList::iterator currSegment = currentRegion.begin();
+                currSegment != currentRegion.end(); ++currSegment)
+        {
+            NudgingShiftSegment *segment =
+                    static_cast<NudgingShiftSegment *> (*currSegment);
+
+            fprintf(stdout, "<line style=\"stroke: #00F;\" x1=\"%g\" "
+                    "y1=\"%g\" x2=\"%g\" y2=\"%g\" />\n",
+                    segment->lowPoint()[XDIM], segment->variable->finalPosition,
+                    segment->highPoint()[XDIM], segment->variable->finalPosition);
+        }
+#endif
+        for_each(currentRegion.begin(), currentRegion.end(), delete_object());
+        for_each(vs.begin(), vs.end(), delete_object());
+        for_each(cs.begin(), cs.end(), delete_object());
     }
 }
 
 
-extern void improveOrthogonalRoutes(Router *router)
+void ImproveOrthogonalRoutes::simplifyOrthogonalRoutes(void)
 {
-    router->timers.Register(tmOrthogNudge, timerStart);
-    for (size_t dimension = 0; dimension < 2; ++dimension)
+    // Simplify routes.
+    for (ConnRefList::const_iterator curr = m_router->connRefs.begin();
+            curr != m_router->connRefs.end(); ++curr)
     {
-        // Build nudging info.
-        // XXX: We need to build the point orders separately in each
-        //      dimension since things move.  There is probably a more
-        //      efficient way to do this.
-        PtOrderMap pointOrders;
-        buildOrthogonalNudgingOrderInfo(router, pointOrders);
+        if ((*curr)->routingType() != ConnType_Orthogonal)
+        {
+            continue;
+        }
+        (*curr)->set_route((*curr)->displayRoute().simplify());
+    }
+}
 
-        // Simplify routes.
-        simplifyOrthogonalRoutes(router);
 
-        // Do the centring and nudging.
-        ShiftSegmentList segLists;
-        buildOrthogonalChannelInfo(router, dimension, segLists);
-        nudgeOrthogonalRoutes(router, dimension, pointOrders, segLists);
+// Populates m_point_orders and m_shared_path_connectors_with_common_endpoints.
+void ImproveOrthogonalRoutes::buildOrthogonalNudgingOrderInfo(void)
+{
+    // Simplify routes.
+    simplifyOrthogonalRoutes();
+
+    int crossingsN = 0;
+
+    bool buildSharedPathInfo = false;
+    if (!m_router->routingOption(Avoid::nudgeSharedPathsWithCommonEndPoint) &&
+            m_shared_path_connectors_with_common_endpoints.empty())
+    {
+        // We're not going to nudge apart shared paths with common ends so we
+        // will need to store information about this during the crossing
+        // detection.
+        buildSharedPathInfo = true;
+    }
+
+
+    // Make a vector of the ConnRefList, for convenience.
+    ConnRefVector connRefs(m_router->connRefs.begin(), m_router->connRefs.end());
+
+    // Make a temporary copy of all the connector displayRoutes.
+    RouteVector connRoutes(connRefs.size());
+    for (size_t ind = 0; ind < connRefs.size(); ++ind)
+    {
+        connRoutes[ind] = connRefs[ind]->displayRoute();
     }
-    router->timers.Stop();
+
+    // Do segment splitting.
+    for (size_t ind1 = 0; ind1 < connRefs.size(); ++ind1)
+    {
+        ConnRef *conn = connRefs[ind1];
+        if (conn->routingType() != ConnType_Orthogonal)
+        {
+            continue;
+        }
+
+        for (size_t ind2 = 0; ind2 < connRefs.size(); ++ind2)
+        {
+            if (ind1 == ind2)
+            {
+                continue;
+            }
+
+            ConnRef *conn2 = connRefs[ind2];
+            if (conn2->routingType() != ConnType_Orthogonal)
+            {
+                continue;
+            }
+
+            Avoid::Polygon& route = connRoutes[ind1];
+            Avoid::Polygon& route2 = connRoutes[ind2];
+            splitBranchingSegments(route2, true, route);
+        }
+    }
+
+    for (size_t ind1 = 0; ind1 < connRefs.size(); ++ind1)
+    {
+        ConnRef *conn = connRefs[ind1];
+        if (conn->routingType() != ConnType_Orthogonal)
+        {
+            continue;
+        }
+
+        for (size_t ind2 = ind1 + 1; ind2 < connRefs.size(); ++ind2)
+        {
+            ConnRef *conn2 = connRefs[ind2];
+            if (conn2->routingType() != ConnType_Orthogonal)
+            {
+                continue;
+            }
+
+            Avoid::Polygon& route = connRoutes[ind1];
+            Avoid::Polygon& route2 = connRoutes[ind2];
+            int crossings = 0;
+            unsigned int crossingFlags = 0;
+            ConnectorCrossings cross(route2, true, route, conn2, conn);
+            cross.pointOrders = &m_point_orders;
+            for (size_t i = 1; i < route.size(); ++i)
+            {
+                const bool finalSegment = ((i + 1) == route.size());
+                cross.countForSegment(i, finalSegment);
+
+                crossings += cross.crossingCount;
+                crossingFlags |= cross.crossingFlags;
+            }
+            if (crossings > 0)
+            {
+                crossingsN += crossings;
+            }
+
+            if (buildSharedPathInfo &&
+                    (crossingFlags & CROSSING_SHARES_PATH_AT_END))
+            {
+                // Record if these two connectors have a shared path with a
+                // common end point.
+                m_shared_path_connectors_with_common_endpoints.insert(
+                        UnsignedPair(conn->id(), conn2->id()));
+            }
+        }
+    }
+}
+
+
+extern void improveOrthogonalRoutes(Router *router)
+{
+    ImproveOrthogonalRoutes improver(router);
+    improver.execute();
 }