Add forgotten libavoid files

(bzr r8856)

1 files changed, 2343 insertions, 0 deletions

diff --git a/src/libavoid/orthogonal.cpp b/src/libavoid/orthogonal.cpp
new file mode 100644
index 000000000..747fd1f86
--- /dev/null
+++ b/src/libavoid/orthogonal.cpp
@@ -0,0 +1,2343 @@
+/*
+ * vim: ts=4 sw=4 et tw=0 wm=0
+ *
+ * libavoid - Fast, Incremental, Object-avoiding Line Router
+ *
+ * Copyright (C) 2009  Monash University
+ *
+ * This library is free software; you can redistribute it and/or
+ * modify it under the terms of the GNU Lesser General Public
+ * License as published by the Free Software Foundation; either
+ * version 2.1 of the License, or (at your option) any later version.
+ * 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 
+ * 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.  
+ *
+ * Author(s):   Michael Wybrow <mjwybrow@users.sourceforge.net>
+*/
+
+
+#include <cstdlib>
+#include <cfloat>
+#include <cmath>
+#include <set>
+#include <list>
+#include <algorithm>
+
+#include "libavoid/router.h"
+#include "libavoid/geomtypes.h"
+#include "libavoid/shape.h"
+#include "libavoid/orthogonal.h"
+#include "libavoid/connector.h"
+#include "libavoid/vpsc.h"
+#include "libavoid/assertions.h"
+
+#ifdef LIBAVOID_SDL
+  #include <SDL_gfxPrimitives.h>
+#endif
+
+
+namespace Avoid {
+
+
+static const double CHANNEL_MAX = 100000000;
+
+static const size_t XDIM = 0;
+static const size_t YDIM = 1;
+
+
+class ShiftSegment 
+{
+    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)
+            : connRef(conn),
+              indexLow(low),
+              indexHigh(high),
+              sBend(isSBend),
+              fixed(false),
+              dimension(dim),
+              variable(NULL),
+              minSpaceLimit(minLim),
+              maxSpaceLimit(maxLim)
+        {
+        }
+        // For fixed segments.
+        ShiftSegment(ConnRef *conn, const size_t low, const size_t high, 
+                const size_t dim)
+            : connRef(conn),
+              indexLow(low),
+              indexHigh(high),
+              sBend(false),
+              fixed(true),
+              dimension(dim),
+              variable(NULL)
+        {
+            // This has no space to shift.
+            minSpaceLimit = lowPoint()[dim];
+            maxSpaceLimit = lowPoint()[dim];
+        }
+        Point& lowPoint(void)
+        {
+            return connRef->displayRoute().ps[indexLow];
+        }
+        Point& highPoint(void)
+        {
+            return connRef->displayRoute().ps[indexHigh];
+        }
+        const Point& lowPoint(void) const
+        {
+            return connRef->displayRoute().ps[indexLow];
+        }
+        const Point& highPoint(void) const 
+        {
+            return connRef->displayRoute().ps[indexHigh];
+        }
+        const int fixedOrder(bool& isFixed) const
+        {
+            if (fixed)
+            {
+                isFixed = true;
+                return 0;
+            }
+            if (lowC())
+            {
+                return 1;
+            }
+            else if (highC())
+            {
+                return -1;
+            }
+            return 0;
+        }
+        const int order(void) const
+        {
+            if (lowC())
+            {
+                return -1;
+            }
+            else if (highC())
+            {
+                return 1;
+            }
+            return 0;
+        }
+        bool operator<(const ShiftSegment& rhs) const
+        {
+            const Point& lowPt = lowPoint();
+            const Point& rhsLowPt = rhs.lowPoint();
+            
+            if (lowPt[dimension] != rhsLowPt[dimension])
+            {
+                return lowPt[dimension] < rhsLowPt[dimension];
+            }
+            return this < &rhs;
+        }
+        // This counts segments that are colliear 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
+        {
+            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))
+                {
+                    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:
+        const 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]))
+            {
+                return true;
+            }
+            return false;
+        }
+        const 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;
+            }
+            return false;
+        }
+};
+typedef std::list<ShiftSegment> ShiftSegmentList;
+
+bool cmpShiftSegment(const ShiftSegment& u, const ShiftSegment& v)
+{
+    return u < v;
+}
+
+
+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)))
+        {
+            curr = curr->firstBelow;
+        }
+        
+        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]))
+            {
+                curr->ss->maxSpaceLimit = 
+                        std::min(min[dim], curr->ss->maxSpaceLimit);
+            }
+            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]))
+            {
+                curr->ss->minSpaceLimit = 
+                        std::max(max[dim], curr->ss->minSpaceLimit);
+            }
+            curr = curr->firstBelow;
+        }
+    }
+    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);
+            }
+            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])
+            {
+                firstAbovePos = std::max(curr->max[dim], firstAbovePos);
+            }
+            curr = curr->firstAbove;
+        }
+        
+        // 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]))
+        {
+            lastBelowPos = std::max(curr->max[dim], lastBelowPos);
+            if ((curr->min[dim] >= min[dim]) && (curr->min[dim] <= max[dim]))
+            {
+                lastBelowPos = std::max(curr->min[dim], lastBelowPos);
+            }
+            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])
+            {
+                firstBelowPos = std::min(curr->min[dim], firstBelowPos);
+            }
+            curr = curr->firstBelow;
+        }
+
+        return clearVisibility;
+    }
+    double firstPointAbove(size_t dim) 
+    { 
+        Node *curr = firstAbove; 
+        while (curr && (curr->max[dim] >= pos)) 
+        { 
+            curr = curr->firstAbove; 
+        } 
+        
+        if (curr) 
+        { 
+            return curr->max[dim]; 
+        } 
+        return -DBL_MAX; 
+    } 
+    double firstPointBelow(size_t dim) 
+    { 
+        Node *curr = firstBelow; 
+        while (curr && (curr->min[dim] <= pos)) 
+        { 
+            curr = curr->firstBelow; 
+        } 
+         
+        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)
+        {
+            if ((curr->min[dimension] < pos) && (pos < curr->max[dimension]))
+            {
+                return true;
+            }
+        }
+        for (Node *curr = firstAbove; curr; curr = curr->firstAbove)
+        {
+            if ((curr->min[dimension] < pos) && (pos < curr->max[dimension]))
+            {
+                return true;
+            }
+        }
+        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;
+};
+
+Event **events;
+
+
+// Used for quicksort.  Must return <0, 0, or >0.
+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).
+//
+static ConnDirFlags getPosVertInfDirection(VertInf *v, size_t dim)
+{
+    if (dim == XDIM) // X-dimension
+    {
+        unsigned int dirs = v->visDirections & (ConnDirLeft | ConnDirRight);
+        if (dirs == (ConnDirLeft | ConnDirRight))
+        {
+            return (ConnDirDown | ConnDirUp);
+        }
+        else if (dirs == ConnDirLeft)
+        {
+            return ConnDirDown;
+        }
+        else if (dirs == ConnDirRight)
+        {
+            return ConnDirUp;
+        }
+    }
+    else if (dim == YDIM) // Y-dimension
+    {
+        unsigned int dirs = v->visDirections & (ConnDirDown | ConnDirUp);
+        if (dirs == (ConnDirDown | ConnDirUp))
+        {
+            return (ConnDirDown | ConnDirUp);
+        }
+        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;
+        }
+        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;
+        }
+    }
+
+    // Can occur for ConnDirNone visibility.
+    return ConnDirNone;
+}
+
+
+struct PosVertInf
+{
+    PosVertInf(double p, VertInf *vI, ConnDirFlags d = ConnDirNone)
+        : pos(p),
+          vert(vI),
+          dir(d)
+    {
+    }
+    
+    bool operator<(const PosVertInf& rhs) const 
+    {
+        if (pos != rhs.pos)
+        {
+            return pos < rhs.pos;
+        }
+        return vert < rhs.vert;
+    }
+
+    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).
+    //
+    ConnDirFlags dir;
+};
+
+
+struct CmpVertInf
+{ 
+    bool operator()(const VertInf* u, const VertInf* v) const
+    {
+        // Comparator for VertSet, an ordered set of VertInf pointers.
+        // It is assumed vertical sets of points will all have the same
+        // x position and horizontal sets all share a y position, so this
+        // method can be used to sort both these sets.
+        COLA_ASSERT((u->point.x == v->point.x) || (u->point.y == v->point.y));
+        if (u->point.x != v->point.x)
+        {
+            return u->point.x < v->point.x;
+        }
+        else if (u->point.y != v->point.y)
+        {
+            return u->point.y < v->point.y;
+        }
+        return u < v;
+    }
+};
+
+
+typedef std::set<VertInf *, CmpVertInf> VertSet;
+
+// 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 
+// lines arising from the vertical sweep.
+class LineSegment 
+{
+public:
+    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)
+    {
+        COLA_ASSERT(begin < finish);
+
+        if (bvi)
+        {
+            vertInfs.insert(bvi);
+        }
+        if (fvi)
+        {
+            vertInfs.insert(fvi);
+        }
+    }
+    LineSegment(const double& bf, const double& p, VertInf *bfvi = NULL)
+        : begin(bf),
+          finish(bf),
+          pos(p),
+          shapeSide(false)
+    {
+        if (bfvi)
+        {
+            vertInfs.insert(bfvi);
+        }
+    }
+ 
+    // Order by begin, pos, finish.
+    bool operator<(const LineSegment& rhs) const 
+    {
+        if (begin != rhs.begin)
+        {
+            return begin < rhs.begin;
+        }
+        if (pos != rhs.pos)
+        {
+            return pos < rhs.pos;
+        }
+        if (finish != rhs.finish)
+        {
+            return finish < rhs.finish;
+        }
+        COLA_ASSERT(shapeSide == rhs.shapeSide);
+        return false;
+    }
+
+    bool overlaps(const LineSegment& rhs) const
+    {
+        if ((begin == rhs.begin) && (pos == rhs.pos) &&
+                (finish == rhs.finish))
+        {
+            // Lines are exactly equal.
+            return true;
+        }
+        
+        if (pos == rhs.pos)
+        {
+            if (((begin >= rhs.begin) && (begin <= rhs.finish)) ||
+                ((rhs.begin >= begin) && (rhs.begin <= finish)) )
+            {
+                // They are colinear and overlap by some amount.
+                return true;
+            }
+        }
+        return false;
+    }
+
+    void mergeVertInfs(const LineSegment& segment)
+    {
+        begin = std::min(begin, segment.begin);
+        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 *finishVertInf(void) const
+    {
+        if (vertInfs.empty())
+        {
+            return NULL;
+        }
+        return *vertInfs.rbegin();
+    }
+
+    VertInf *commitPositionX(Router *router, double posX)
+    {
+        VertInf *found = NULL;
+        for (VertSet::iterator v = vertInfs.begin();
+                v != vertInfs.end(); ++v)
+        {
+            if ((*v)->point.x == posX)
+            {
+                found = *v;
+                break;
+            }
+        }
+        if (!found)
+        {
+            found = new VertInf(router, dummyOrthogID, Point(posX, pos));
+            vertInfs.insert(found);
+        }
+        return found;
+    }
+    // Set begin endpoint vertex if none has been assigned.
+    void commitBegin(Router *router, VertInf *vert = NULL)
+    {
+        if (vert)
+        {
+            vertInfs.insert(vert);
+        }
+
+        if (vertInfs.empty() ||
+                ((*vertInfs.begin())->point.x != begin))
+        {
+            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)
+    {
+        if (vert)
+        {
+            vertInfs.insert(vert);
+        }
+
+        if (vertInfs.empty() ||
+                ((*vertInfs.rbegin())->point.x != finish))
+        {
+            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)
+    {
+        VertSet::iterator firstIntersectionPt = vertInfs.end();
+        for (VertSet::iterator vert = vertInfs.begin(); 
+                vert != vertInfs.end(); ++vert)
+        {
+            if ((*vert)->point.x > finishPos)
+            {
+                // We're done.
+                break;
+            }
+            
+            breakPoints.insert(PosVertInf((*vert)->point.x, (*vert),
+                        getPosVertInfDirection(*vert, XDIM)));
+
+            if ((firstIntersectionPt == vertInfs.end()) && 
+                    ((*vert)->point.x == finishPos))
+            {
+                firstIntersectionPt = vert;
+            }
+        }
+        // Returns the first of the intersection points at finishPos.
+        return firstIntersectionPt;
+    }
+
+    // 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);
+        
+        addSegmentsUpTo(router, finish);
+    }
+
+    // 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 
+    // endpoint of the segment is shared by multiple connector endpoints.
+    VertSet addEdgeHorizontalTillIntersection(Router *router, 
+            LineSegment& vertLine)
+    {
+        VertSet intersectionSet;
+
+        commitBegin(router);
+
+        // Does a vertex already exist for this point.
+        commitPositionX(router, vertLine.pos);
+   
+        // Generate segments and set end iterator to the first point 
+        // at the intersection position.
+        VertSet::iterator restBegin = addSegmentsUpTo(router, vertLine.pos);
+
+        // Add the intersections points to intersectionSet.
+        VertSet::iterator restEnd = restBegin;
+        while ((restEnd != vertInfs.end()) && 
+                (*restEnd)->point.x == vertLine.pos)
+        {
+            ++restEnd;
+        }
+        intersectionSet.insert(restBegin, restEnd);
+
+        // Adjust segment to remove processed portion.
+        begin = vertLine.pos;
+        vertInfs.erase(vertInfs.begin(), restBegin);
+
+        return intersectionSet;
+    }
+                
+    // Insert vertical breakpoints.
+    void insertBreakpointsBegin(Router *router, LineSegment& vertLine)
+    {
+        VertInf *vert = NULL;
+        if (pos == vertLine.begin && vertLine.beginVertInf())
+        {
+            vert = vertLine.beginVertInf();
+        }
+        else if (pos == vertLine.finish && vertLine.finishVertInf())
+        {
+            vert = vertLine.finishVertInf();
+        }
+        commitBegin(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)));
+            }
+        }
+    }
+
+    // Insert vertical breakpoints.
+    void insertBreakpointsFinish(Router *router, LineSegment& vertLine)
+    {
+        VertInf *vert = NULL;
+        if (pos == vertLine.begin && vertLine.beginVertInf())
+        {
+            vert = vertLine.beginVertInf();
+        }
+        else if (pos == vertLine.finish && vertLine.finishVertInf())
+        {
+            vert = vertLine.finishVertInf();
+        }
+        commitFinish(router, vert);
+
+        for (VertSet::iterator v = vertInfs.begin();
+                v != vertInfs.end(); ++v)
+        {
+            if ((*v)->point.x == finish)
+            {
+                vertLine.breakPoints.insert(PosVertInf(pos, *v,
+                        getPosVertInfDirection(*v, YDIM)));
+            }
+        }
+    }
+    void generateVisibilityEdgesFromBreakpointSet(Router *router, size_t dim)
+    {
+        if ((breakPoints.begin())->pos != begin)
+        {
+            if (!beginVertInf())
+            {
+                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 (!finishVertInf())
+            {
+                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));
+            }
+        }
+
+        const bool orthogonal = true;
+        BreakpointSet::iterator vert, last;
+        for (vert = last = breakPoints.begin(); vert != breakPoints.end();)
+        {
+            BreakpointSet::iterator firstPrev = last;
+            while (last->vert->point[dim] != vert->vert->point[dim])
+            {
+                COLA_ASSERT(vert != last);
+                // 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))
+                {
+                    // 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)
+                    {
+                        if (side == breakPoints.begin())
+                        {
+                            break;
+                        }
+                        --side;
+                    }
+                    bool canSeeDown = (vert->dir & ConnDirDown);
+                    if (canSeeDown && side->vert->id.isShape)
+                    {
+                        EdgeInf *edge = new 
+                                EdgeInf(side->vert, vert->vert, orthogonal);
+                        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)
+                    {
+                        ++side;
+                    }
+                    bool canSeeUp = (last->dir & ConnDirUp);
+                    if (canSeeUp && (side != breakPoints.end()))
+                    {
+                        EdgeInf *edge = new 
+                                EdgeInf(last->vert, side->vert, orthogonal);
+                        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 
+                // 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))
+                {
+                    generateEdge = false;
+                }
+                else if (!vert->vert->id.isShape && !(vert->dir & ConnDirDown))
+                {
+                    generateEdge = false;
+                }
+                if (generateEdge)
+                {
+                    EdgeInf *edge = 
+                            new EdgeInf(last->vert, vert->vert, orthogonal);
+                    edge->setDist(vert->vert->point[dim] - 
+                            last->vert->point[dim]);
+                }
+
+                ++last;
+            }
+
+            ++vert;
+
+            if ((vert != breakPoints.end()) &&
+                    (last->vert->point[dim] == vert->vert->point[dim]))
+            {
+                // Still looking at same pair, just reset prev number pointer.
+                last = firstPrev;
+            }
+            else
+            {
+                // vert has moved to the beginning of a number number group.
+                // Last is now in the right place, so do nothing.
+            }
+        }
+    }
+
+    double begin;
+    double finish;
+    double pos;
+    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.
+    LineSegment & operator=(LineSegment const &);
+    LineSegment();
+};
+
+typedef std::list<LineSegment> SegmentList;
+
+class SegmentListWrapper
+{
+    public:
+        LineSegment *insert(LineSegment segment)
+        {
+            SegmentList::iterator found = _list.end();
+            for (SegmentList::iterator curr = _list.begin();
+                    curr != _list.end(); ++curr)
+            {
+                if (curr->overlaps(segment))
+                {
+                    if (found != _list.end())
+                    {
+                        // This is not the first segment that overlaps,
+                        // so we need to merge and then delete an existing
+                        // segment.
+                        curr->mergeVertInfs(*found);
+                        _list.erase(found);
+                        found = curr;
+                    }
+                    else
+                    {
+                        // This is the first overlapping segment, so just 
+                        // merge the new segment with this one.
+                        curr->mergeVertInfs(segment);
+                        found = curr;
+                    }
+                }
+            }
+
+            if (found == _list.end())
+            {
+                // Add this line.
+                _list.push_back(segment);
+                return &(_list.back());
+            }
+
+            return &(*found);
+        }
+        SegmentList& list(void)
+        {
+            return _list;
+        }
+    private:
+        SegmentList _list;
+};
+
+
+// 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, 
+        LineSegment& vertLine)
+{
+    COLA_ASSERT(vertLine.beginVertInf() == NULL);
+    COLA_ASSERT(vertLine.finishVertInf() == NULL);
+    for (SegmentList::iterator it = segments.begin(); it != segments.end(); )
+    {
+        LineSegment& horiLine = *it;
+
+        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)
+        {
+            // We've yet to reach this segment in the sweep, so ignore.
+            ++it;
+            continue;
+        }
+        else if (horiLine.begin == vertLine.pos)
+        {
+            if (inVertSegRegion)
+            {
+                horiLine.insertBreakpointsBegin(router, vertLine);
+            }
+        }
+        else if (horiLine.finish == vertLine.pos)
+        {
+            if (inVertSegRegion)
+            {
+                // Add horizontal visibility segment.
+                horiLine.addEdgeHorizontal(router);
+            
+                horiLine.insertBreakpointsFinish(router, vertLine);
+                
+                size_t dim = XDIM; // x-dimension
+                horiLine.generateVisibilityEdgesFromBreakpointSet(router, dim);
+
+                // And we've now finished with the segment, so delete.
+                it = segments.erase(it);
+                continue;
+            }
+        }
+        else
+        {
+            COLA_ASSERT(horiLine.begin < vertLine.pos);
+            COLA_ASSERT(horiLine.finish > vertLine.pos);
+
+            if (inVertSegRegion)
+            {
+                // Add horizontal visibility segment.
+                VertSet intersectionVerts = 
+                        horiLine.addEdgeHorizontalTillIntersection(
+                            router, vertLine);
+
+                for (VertSet::iterator v = intersectionVerts.begin();
+                        v != intersectionVerts.end(); ++v)
+                {
+                    vertLine.breakPoints.insert(PosVertInf(horiLine.pos, *v,
+                            getPosVertInfDirection(*v, YDIM)));
+                }
+            }
+        }
+        ++it;
+    }
+
+    // Split breakPoints set into visibility segments.
+    size_t dimension = YDIM; // y-dimension
+    vertLine.generateVisibilityEdgesFromBreakpointSet(router, dimension);
+}
+
+
+// Processes an event for the vertical sweep used for computing the static 
+// orthogonal visibility graph.  This adds possible visibility sgments 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, 
+        SegmentListWrapper& segments, Event *e, unsigned int pass)
+{
+    Node *v = e->v;
+    
+    if ( ((pass == 1) && (e->type == Open)) ||
+         ((pass == 2) && (e->type == ConnPoint)) )
+    {
+        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 == 2)
+    {
+        if ((e->type == Open) || (e->type == Close))
+        {
+            // Shape edge positions.
+            double minShape = v->min[0];
+            double maxShape = v->max[0];
+            // As far as we can see.
+            double minLimit, maxLimit;
+            double minLimitMax, maxLimitMin;
+            v->findFirstPointAboveAndBelow(0, 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];
+
+            if (minLimitMax >= maxLimitMin)
+            {
+                // Insert possible visibility segments.
+                VertInf *vI1 = new VertInf(router, dummyOrthogID, 
+                            Point(minShape, lineY));
+                VertInf *vI2 = new VertInf(router, dummyOrthogID, 
+                            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, 
+                            true, vI1, vI2));
+                if (maxShape < maxLimit)
+                {
+                    segments.insert(LineSegment(maxShape, maxLimit, lineY,
+                                true, vI2, NULL));
+                }
+            }
+            else
+            {
+                if ((minLimitMax > minLimit) && (minLimitMax >= minShape))
+                {
+                    segments.insert(LineSegment(minLimit, minLimitMax, lineY,
+                                true, NULL, NULL));
+                }
+                if ((maxLimitMin < maxLimit) && (maxLimitMin <= maxShape))
+                {
+                    segments.insert(LineSegment(maxLimitMin, maxLimit, lineY,
+                                true, NULL, NULL));
+                }
+            }
+        }
+        else if (e->type == ConnPoint)
+        {
+            // Connection point.
+            VertInf *centreVert = e->v->c;
+            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);
+
+            LineSegment *line1 = NULL, *line2 = NULL;
+            if (!inShape || (centreVert->visDirections & ConnDirLeft))
+            {
+                line1 = segments.insert(LineSegment(minLimit, cp.x, e->pos, 
+                        true, NULL, centreVert));
+            }
+            if (!inShape || (centreVert->visDirections & ConnDirRight))
+            {
+                line2 = segments.insert(LineSegment(cp.x, maxLimit, e->pos, 
+                        true, centreVert, 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
+                // visibility graph point here too (since paths won't route
+                // *through* connector endpoint vertices).
+                if (line1 || line2)
+                {
+                    VertInf *cent = new VertInf(router, dummyOrthogID, cp);
+                    if (line1)
+                    {
+                        line1->vertInfs.insert(cent);
+                    }
+                    if (line2)
+                    {
+                        line2->vertInfs.insert(cent);
+                    }
+                }
+            }
+        }
+    }
+    
+    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) 
+        {
+            l->firstBelow = v->firstBelow;
+        }
+        if (r != NULL)
+        {
+            r->firstAbove = v->firstAbove;
+        }
+
+        if (e->type == ConnPoint)
+        {
+            scanline.erase(v->iter);
+            delete v;
+        }
+        else  // if (e->type == Close)
+        {
+            size_t result;
+            result = scanline.erase(v);
+            COLA_ASSERT(result == 1);
+            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.
+// 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, 
+        SegmentListWrapper& segments, Event *e, unsigned int pass)
+{
+    Node *v = e->v;
+    
+    if ( ((pass == 1) && (e->type == Open)) ||
+         ((pass == 2) && (e->type == ConnPoint)) )
+    {
+        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 == 2)
+    {
+        if ((e->type == Open) || (e->type == Close))
+        {
+            // Shape edge positions.
+            double minShape = v->min[1];
+            double maxShape = v->max[1];
+            // As far as we can see.
+            double minLimit, maxLimit;
+            double minLimitMax, maxLimitMin;
+            v->findFirstPointAboveAndBelow(1, 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);
+            }
+            else
+            {
+                if ((minLimitMax > minLimit) && (minLimitMax >= minShape))
+                {
+                    LineSegment vertSeg = 
+                            LineSegment(minLimit, minLimitMax, lineX);
+                    segments.insert(vertSeg);
+                }
+                if ((maxLimitMin < maxLimit) && (maxLimitMin <= maxShape))
+                {
+                    LineSegment vertSeg = 
+                            LineSegment(maxLimitMin, maxLimit, lineX);
+                    segments.insert(vertSeg);
+                }
+            }
+        }
+        else if (e->type == ConnPoint)
+        {
+            // Connection point.
+            VertInf *centreVert = e->v->c;
+            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))
+            {
+                segments.insert(LineSegment(minLimit, cp.y, e->pos));
+            }
+            if (!inShape || (centreVert->visDirections & ConnDirDown))
+            {
+                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) 
+        {
+            l->firstBelow = v->firstBelow;
+        }
+        if (r != NULL)
+        {
+            r->firstAbove = v->firstAbove;
+        }
+
+        if (e->type == ConnPoint)
+        {
+            scanline.erase(v->iter);
+            delete v;
+        }
+        else  // if (e->type == Close)
+        {
+            size_t result;
+            result = scanline.erase(v);
+            COLA_ASSERT(result == 1);
+            delete v;
+        }
+    }
+}
+
+
+extern void generateStaticOrthogonalVisGraph(Router *router)
+{
+    const size_t n = router->shapeRefs.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];
+    unsigned ctr = 0;
+    ShapeRefList::iterator shRefIt = router->shapeRefs.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;
+    }
+    for (VertInf *curr = router->vertices.connsBegin(); 
+            curr && (curr != router->vertices.shapesBegin()); 
+            curr = curr->lstNext)
+    {
+        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.
+    // We do multiple passes over sections of the list so we can add relevant
+    // entries to the scanline that might follow, before process them.
+    SegmentListWrapper segments;
+    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 <= 3; ++pass)
+            {
+                for (unsigned j = posStartIndex; j < posFinishIndex; ++j)
+                {
+                    processEventVert(router, scanline, segments, 
+                            events[j], pass);
+                }
+            }
+
+            if (i == totalEvents)
+            {
+                // We have cleaned up, so we can now break out of loop.
+                break;
+            }
+
+            thisPos = events[i]->pos;
+            posStartIndex = i;
+        }
+
+        // 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.size() == 0);
+    for (unsigned i = 0; i < totalEvents; ++i)
+    {
+        delete events[i];
+    }
+
+    segments.list().sort();
+
+    // Set up the events for the horizontal sweep.
+    SegmentListWrapper vertSegments;
+    ctr = 0;
+    shRefIt = router->shapeRefs.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;
+    }
+    for (VertInf *curr = router->vertices.connsBegin(); 
+            curr && (curr != router->vertices.shapesBegin()); 
+            curr = curr->lstNext)
+    {
+        Point& point = curr->point;
+
+        Node *v = new Node(curr, point.y);
+        events[ctr++] = new Event(ConnPoint, v, point.x);
+    }
+    qsort((Event*)events, (size_t) totalEvents, sizeof(Event*), compare_events);
+
+    // Process the horizontal sweep
+    thisPos = (totalEvents > 0) ? events[0]->pos : 0;
+    posStartIndex = 0;
+    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 <= 3; ++pass)
+            {
+                for (unsigned j = posStartIndex; j < posFinishIndex; ++j)
+                {
+                    processEventHori(router, scanline, vertSegments, 
+                            events[j], pass);
+                }
+            }
+            
+            // Process the merged line segments.
+            vertSegments.list().sort();
+            for (SegmentList::iterator curr = vertSegments.list().begin();
+                    curr != vertSegments.list().end(); ++curr)
+            {
+                intersectSegments(router, segments.list(), *curr);
+            }
+            vertSegments.list().clear();
+
+            if (i == totalEvents)
+            {
+                // We have cleaned up, so we can now break out of loop.
+                break;
+            }
+
+            thisPos = events[i]->pos;
+            posStartIndex = i;
+        }
+
+        // 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.size() == 0);
+    for (unsigned i = 0; i < totalEvents; ++i)
+    {
+        delete events[i];
+    }
+    delete [] events;
+
+    // Add portions of the horizontal line that are after the final vertical
+    // position we considered.
+    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);
+
+        it = segments.list().erase(it);
+    }
+}
+
+
+//============================================================================
+//                           Path Adjustment code
+//============================================================================
+
+
+
+
+// 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)
+{
+    Node *v = e->v;
+    
+    if ( ((pass == 3) && (e->type == Open)) ||
+         ((pass == 3) && (e->type == SegOpen)) )
+    {
+        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);
+        }
+    }
+    
+    if ( ((pass == 2) && (e->type == SegClose)) ||
+         ((pass == 2) && (e->type == Close)) )
+    {
+        // Clean up neighbour pointers.
+        Node *l = v->firstAbove, *r = v->firstBelow;
+        if (l != NULL) 
+        {
+            l->firstBelow = v->firstBelow;
+        }
+        if (r != NULL)
+        {
+            r->firstAbove = v->firstAbove;
+        }
+
+        size_t result;
+        result = scanline.erase(v);
+        COLA_ASSERT(result == 1);
+        delete v;
+    }
+}
+
+
+static void buildOrthogonalChannelInfo(Router *router, 
+        const size_t dim, ShiftSegmentList& segmentList)
+{
+    if (router->routingPenalty(segmentPenalty) == 0)
+    {
+        // This code assumes the routes are pretty optimal, so we don't
+        // do this adjustment if the routes have no segment penalty.
+        return;
+    }
+
+    size_t altDim = (dim + 1) % 2;
+    // For each connector.
+    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. 
+        // We don't consider the first or last segment of a path.
+        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])
+                {
+                    indexLow = i;
+                    indexHigh = i - 1;
+                }
+                COLA_ASSERT(displayRoute.at(indexLow)[altDim] < 
+                        displayRoute.at(indexHigh)[altDim]);
+
+                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));
+                    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])) )
+                {
+                    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]))
+                    {
+                        minLim = std::max(minLim, prevPos);
+                        maxLim = std::min(maxLim, nextPos);
+                    }
+                    else
+                    {
+                        minLim = std::max(minLim, nextPos);
+                        maxLim = std::min(maxLim, prevPos);
+                    }
+                }
+                else
+                {
+                    // 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])
+                    {
+                        minLim = displayRoute.ps[i][dim];
+                    }
+                    else
+                    {
+                        maxLim = displayRoute.ps[i][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);
+
+    // 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)
+                {
+                    processShiftEvent(router, scanline, segmentList, events[j], 
+                            dim, pass);
+                }
+            }
+
+            if (i == totalEvents)
+            {
+                // We have cleaned up, so we can now break out of loop.
+                break;
+            }
+
+            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.size() == 0);
+    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;
+            }
+            
+            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 
+{
+    public:
+        CmpLineOrder(PtOrderMap& ord, const size_t dim)
+            : orders(ord),
+              dimension(dim)
+        {
+        }
+        bool operator()(const ShiftSegment& lhs, const ShiftSegment& rhs,
+                bool *comparable = NULL) const
+        {
+            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
+            size_t altDim = (dimension + 1) % 2;
+
+            COLA_ASSERT(lhsLow[dimension] == lhsHigh[dimension]);
+            COLA_ASSERT(rhsLow[dimension] == rhsHigh[dimension]);
+
+            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 
+            // block movement.
+            bool oneIsFixed = false;
+            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 
+            // 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();
+            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);
+            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 
+                // these segments is not important since we do not constrain
+                // them against each other.
+                //COLA_ASSERT(lhs.overlapsWith(rhs, dimension) == false);
+                // We do need to be consistent though.
+                if (comparable)
+                {
+                    *comparable = false;
+                }
+                return lhsLow[altDim] < rhsLow[altDim];
+            }
+
+            return lhsPos < rhsPos;
+        }
+
+        PtOrderMap& orders;
+        const size_t dimension;
+};
+
+
+// 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 
+// up any constraints between such segments when doing the nudging.
+//
+static ShiftSegmentList linesort(ShiftSegmentList origList, 
+        CmpLineOrder& comparison)
+{
+    ShiftSegmentList resultList;
+
+    while (!origList.empty())
+    {
+        // Get and remove the first element from the origList.
+        ShiftSegment segment = origList.front();
+        origList.pop_front();
+
+        // Find the insertion point in the resultList.
+        ShiftSegmentList::iterator curr;
+        for (curr = resultList.begin(); curr != resultList.end(); ++curr)
+        {
+            bool comparable = false;
+            bool lessThan = comparison(segment, *curr, &comparable);
+
+            if (comparable && lessThan)
+            {
+                // If it is comparable and lessThan, then we have found the
+                // insertion point.
+                break;
+            }
+        }
+
+        // Insert the element into the reultList at the required point.
+        resultList.insert(curr, segment);
+    }
+
+    return resultList;
+}
+
+
+typedef std::list<ShiftSegment *> ShiftSegmentPtrList;
+
+
+static void nudgeOrthogonalRoutes(Router *router, size_t dimension, 
+        PtOrderMap& pointOrders, ShiftSegmentList& segmentList)
+{
+    // Do the actual nudging.
+    ShiftSegmentList currentRegion;
+    while (!segmentList.empty())
+    {
+        // Take a reference segment
+        ShiftSegment& currentSegment = segmentList.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(); )
+        {
+            bool overlaps = false;
+            for (ShiftSegmentList::iterator curr2 = currentRegion.begin();
+                    curr2 != currentRegion.end(); ++curr2)
+            {
+                if (curr->overlapsWith(*curr2, dimension))
+                {
+                    overlaps = true;
+                    break;
+                }
+            }
+            if (overlaps)
+            {
+                currentRegion.push_back(*curr);
+                segmentList.erase(curr);
+                // Consider segments from the beginning, since we mave have
+                // since passed segments that overlap with the new set.
+                curr = segmentList.begin();
+            }
+            else
+            {
+                ++curr;
+            }
+        }
+        CmpLineOrder lineSortComp(pointOrders, dimension);
+        currentRegion = linesort(currentRegion, lineSortComp);
+        
+        if (currentRegion.size() == 1)
+        {
+            // Save creating the solver instance if there is just one
+            // immovable segment.
+            if (!currentRegion.front().sBend)
+            {
+                continue;
+            }
+        }
+
+        // Process these segments.
+        Variables vs;
+        Constraints cs;
+        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)
+        {
+            Point& lowPt = currSegment->lowPoint();
+            
+            // 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);
+                
+                // For s-bends, take the middle as ideal.
+                idealPos = currSegment->minSpaceLimit +
+                        ((currSegment->maxSpaceLimit -
+                          currSegment->minSpaceLimit) / 2);
+            }
+            else if (currSegment->fixed)
+            {
+                // Fixed segments shouldn't get moved.
+                weight = fixedWeight;
+                varID = fixedID;
+            }
+            else
+            {
+                // 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;
+            }
+            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(); )
+            {
+                ShiftSegment *prevSeg = *prevVarIt;
+                Variable *prevVar = prevSeg->variable;
+
+                if (currSegment->overlapsWith(*prevSeg, dimension) &&
+                        (!(currSegment->fixed) || !(prevSeg->fixed)))
+                {
+                    // If there is a previous segment to the left that 
+                    // could overlap this in the shift direction, then 
+                    // 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;
+                }
+            }
+
+            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, 
+                                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);
+        }
+#endif
+        IncSolver f(vs,cs);
+        f.solve();
+        bool satisfied = true;
+        for (size_t i = 0; i < vs.size(); ++i) 
+        {
+            if (vs[i]->id == fixedID)
+            {
+                if (fabs(vs[i]->finalPosition - vs[i]->desiredPosition) > 0.01)
+                {
+                    satisfied = false;
+                    break;
+                }
+            }
+        }
+        if (satisfied)
+        {
+            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;
+            }
+        }
+#if 0
+        for(unsigned i=0;i<vs.size();i++) {
+            printf("+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());
+    }
+}
+
+
+extern void improveOrthogonalRoutes(Router *router)
+{
+    router->timers.Register(tmOrthogNudge, timerStart);
+    for (size_t dimension = 0; dimension < 2; ++dimension)
+    {
+        // 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);
+
+        // Simplify routes.
+        simplifyOrthogonalRoutes(router);
+
+        // Do the centring and nudging.
+        ShiftSegmentList segLists;
+        buildOrthogonalChannelInfo(router, dimension, segLists);
+        nudgeOrthogonalRoutes(router, dimension, pointOrders, segLists);
+    }
+    router->timers.Stop();
+}
+
+
+}