moving trunk for module inkscape

(bzr r1)

29 files changed, 4873 insertions, 0 deletions

diff --git a/src/libavoid/.cvsignore b/src/libavoid/.cvsignore
new file mode 100644
index 000000000..38efca7bc
--- /dev/null
+++ b/src/libavoid/.cvsignore
@@ -0,0 +1,3 @@
+.deps
+.dirstamp
+makefile
diff --git a/src/libavoid/Makefile_insert b/src/libavoid/Makefile_insert
new file mode 100644
index 000000000..146344813
--- /dev/null
+++ b/src/libavoid/Makefile_insert
@@ -0,0 +1,33 @@
+## Makefile.am fragment sourced by src/Makefile.am.
+
+libavoid/all: libavoid/libavoid.a
+
+libavoid/clean:
+	rm -f libavoid/libavoid.a $(libavoid_libavoid_a_OBJECTS)
+
+libavoid_libavoid_a_SOURCES =	\
+	libavoid/connector.cpp	\
+	libavoid/connector.h	\
+	libavoid/debug.h	\
+	libavoid/geometry.cpp	\
+	libavoid/geometry.h	\
+	libavoid/geomtypes.h	\
+	libavoid/graph.cpp	\
+	libavoid/graph.h	\
+	libavoid/incremental.cpp	\
+	libavoid/incremental.h	\
+	libavoid/makepath.cpp	\
+	libavoid/makepath.h	\
+	libavoid/polyutil.cpp	\
+	libavoid/polyutil.h	\
+	libavoid/shape.cpp	\
+	libavoid/shape.h	\
+	libavoid/static.cpp	\
+	libavoid/static.h	\
+	libavoid/timer.cpp	\
+	libavoid/timer.h	\
+	libavoid/vertices.cpp	\
+	libavoid/vertices.h	\
+	libavoid/visibility.cpp	\
+	libavoid/visibility.h	\
+	libavoid/libavoid.h
diff --git a/src/libavoid/README b/src/libavoid/README
new file mode 100644
index 000000000..ada0e9908
--- /dev/null
+++ b/src/libavoid/README
@@ -0,0 +1,5 @@
+This directory contains libavoid-0.1.  It has been included here since it is
+a new library without wide availablity.
+
+The project page is http://www.sourceforge.net/projects/libavoid/
+The library's maintainer is Michael Wybrow, an Inkscape developer.
diff --git a/src/libavoid/connector.cpp b/src/libavoid/connector.cpp
new file mode 100644
index 000000000..cde387c5b
--- /dev/null
+++ b/src/libavoid/connector.cpp
@@ -0,0 +1,408 @@
+/*
+ * vim: ts=4 sw=4 et tw=0 wm=0
+ *
+ * libavoid - Fast, Incremental, Object-avoiding Line Router
+ * Copyright (C) 2004-2005  Michael Wybrow <mjwybrow@users.sourceforge.net>
+ *
+ * This library is free software; you can redistribute it and/or
+ * modify it under the terms of the GNU Lesser General Public
+ * License as published by the Free Software Foundation; either
+ * version 2.1 of the License, or (at your option) any later version.
+ *
+ * This library is distributed in the hope that it will be useful,
+ * but WITHOUT ANY WARRANTY; without even the implied warranty of
+ * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU
+ * Lesser General Public License for more details.
+ *
+ * You should have received a copy of the GNU Lesser General Public
+ * License along with this library; if not, write to the Free Software
+ * Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA  02111-1307  USA
+ * 
+*/
+
+#include "libavoid/graph.h"
+#include "libavoid/makepath.h"
+#include "libavoid/visibility.h"
+#include "libavoid/debug.h"
+
+
+namespace Avoid {
+
+    
+ConnRefList connRefs;
+
+
+ConnRef::ConnRef(const uint id)
+    : _id(id)
+    , _needs_reroute_flag(true)
+    , _false_path(false)
+    , _active(false)
+    , _route_dist(0)
+    , _srcVert(NULL)
+    , _dstVert(NULL)
+    , _initialised(false)
+    , _callback(NULL)
+    , _connector(NULL)
+{
+    // TODO: Store endpoints and details.
+    _route.pn = 0;
+    _route.ps = NULL;
+}
+
+
+ConnRef::ConnRef(const uint id, const Point& src, const Point& dst)
+    : _id(id)
+    , _needs_reroute_flag(true)
+    , _false_path(false)
+    , _active(false)
+    , _route_dist(0)
+    , _srcVert(NULL)
+    , _dstVert(NULL)
+    , _initialised(false)
+    , _callback(NULL)
+    , _connector(NULL)
+{
+    _route.pn = 0;
+    _route.ps = NULL;
+
+    if (IncludeEndpoints)
+    {
+        bool isShape = false;
+        _srcVert = new VertInf(VertID(id, isShape, 1), src);
+        _dstVert = new VertInf(VertID(id, isShape, 2), dst);
+        vertices.addVertex(_srcVert);
+        vertices.addVertex(_dstVert);
+        makeActive();
+        _initialised = true;
+    }
+}
+
+
+ConnRef::~ConnRef()
+{
+    freeRoute();
+
+    if (_srcVert)
+    {
+        vertices.removeVertex(_srcVert);
+        delete _srcVert;
+        _srcVert = NULL;
+    }
+
+    if (_dstVert)
+    {
+        vertices.removeVertex(_dstVert);
+        delete _dstVert;
+        _dstVert = NULL;
+    }
+
+    if (_active)
+    {
+        makeInactive();
+    }
+}
+
+void ConnRef::updateEndPoint(const uint type, const Point& point)
+{
+    assert((type == (uint) VertID::src) || (type == (uint) VertID::tar));
+    //assert(IncludeEndpoints);
+
+    VertInf *altered = NULL;
+    VertInf *partner = NULL;
+    bool isShape = false;
+
+    if (type == (uint) VertID::src)
+    {
+        if (_srcVert)
+        {
+            _srcVert->Reset(point);
+        }
+        else
+        {
+            _srcVert = new VertInf(VertID(_id, isShape, type), point);
+            vertices.addVertex(_srcVert);
+        }
+        
+        altered = _srcVert;
+        partner = _dstVert;
+    }
+    else // if (type == (uint) VertID::dst)
+    {
+        if (_dstVert)
+        {
+            _dstVert->Reset(point);
+        }
+        else
+        {
+            _dstVert = new VertInf(VertID(_id, isShape, type), point);
+            vertices.addVertex(_dstVert);
+        }
+        
+        altered = _dstVert;
+        partner = _srcVert;
+    }
+
+    bool knownNew = false;
+    vertexVisibility(altered, partner, knownNew, true);
+}
+
+
+void ConnRef::makeActive(void)
+{
+    assert(!_active);
+    
+    // Add to connRefs list.
+    _pos = connRefs.insert(connRefs.begin(), this);
+    _active = true;
+}
+
+
+void ConnRef::makeInactive(void)
+{
+    assert(_active);
+    
+    // Remove from connRefs list.
+    connRefs.erase(_pos);
+    _active = false;
+}
+
+
+void ConnRef::freeRoute(void)
+{
+    if (_route.ps)
+    {
+        _route.pn = 0;
+        std::free(_route.ps);
+        _route.ps = NULL;
+    }
+}
+    
+
+PolyLine& ConnRef::route(void)
+{
+    return _route;
+}
+
+
+void ConnRef::calcRouteDist(void)
+{
+    _route_dist = 0;
+    for (int i = 1; i < _route.pn; i++)
+    {
+        _route_dist += dist(_route.ps[i], _route.ps[i - 1]);
+    }
+}
+
+
+bool ConnRef::needsReroute(void)
+{
+    return (_false_path || _needs_reroute_flag);
+}
+
+
+void ConnRef::moveRoute(const int& diff_x, const int& diff_y)
+{
+    for (int i = 0; i < _route.pn; i++)
+    {
+        _route.ps[i].x += diff_x;
+        _route.ps[i].y += diff_y;
+    }
+}
+
+
+void ConnRef::lateSetup(const Point& src, const Point& dst)
+{
+    assert(!_initialised);
+
+    bool isShape = false;
+    _srcVert = new VertInf(VertID(_id, isShape, 1), src);
+    _dstVert = new VertInf(VertID(_id, isShape, 2), dst);
+    vertices.addVertex(_srcVert);
+    vertices.addVertex(_dstVert);
+    makeActive();
+    _initialised = true;
+}
+
+
+VertInf *ConnRef::src(void)
+{
+    return _srcVert;
+}
+
+    
+VertInf *ConnRef::dst(void)
+{
+    return _dstVert;
+}
+
+
+bool ConnRef::isInitialised(void)
+{
+    return _initialised;
+}
+
+
+void ConnRef::unInitialise(void)
+{
+    vertices.removeVertex(_srcVert);
+    vertices.removeVertex(_dstVert);
+    makeInactive();
+    _initialised = false;
+}
+
+
+void ConnRef::removeFromGraph(void)
+{
+    for (VertInf *iter = _srcVert; iter != NULL; )
+    {
+        VertInf *tmp = iter;
+        iter = (iter == _srcVert) ? _dstVert : NULL;
+        
+        // For each vertex.
+        EdgeInfList& visList = tmp->visList;
+        EdgeInfList::iterator finish = visList.end();
+        EdgeInfList::iterator edge;
+        while ((edge = visList.begin()) != finish)
+        {
+            // Remove each visibility edge
+            delete (*edge);
+        }
+
+        EdgeInfList& invisList = tmp->invisList;
+        finish = invisList.end();
+        while ((edge = invisList.begin()) != finish)
+        {
+            // Remove each invisibility edge
+            delete (*edge);
+        }
+    }
+}
+
+
+void ConnRef::setCallback(void (*cb)(void *), void *ptr)
+{
+    _callback = cb;
+    _connector = ptr;
+}
+
+
+void ConnRef::handleInvalid(void)
+{
+    if (_false_path || _needs_reroute_flag) {
+        if (_callback) {
+            _callback(_connector);
+        }
+    }
+}
+
+
+void ConnRef::makePathInvalid(void)
+{
+    _needs_reroute_flag = true;
+}
+
+
+int ConnRef::generatePath(Point p0, Point p1)
+{
+    if (!_false_path && !_needs_reroute_flag) {
+        // This connector is up to date.
+        return (int) false;
+    }
+
+    _false_path = false;
+    _needs_reroute_flag = false;
+    
+    VertInf *src = _srcVert;
+    VertInf *tar = _dstVert;
+   
+    if (!IncludeEndpoints)
+    {
+        lateSetup(p0, p1);
+        
+        // Update as they have just been set by lateSetup.
+        src = _srcVert;
+        tar = _dstVert;
+   
+        bool knownNew = true;
+        vertexVisibility(src, tar, knownNew);
+        vertexVisibility(tar, src, knownNew);
+    }
+
+    bool *flag = &(_needs_reroute_flag);
+    
+    makePath(this, flag);
+    
+    bool result = true;
+    
+    int pathlen = 1;
+    for (VertInf *i = tar; i != src; i = i->pathNext)
+    {
+        pathlen++;
+        if (i == NULL)
+        {
+            db_printf("Warning: Path not found...\n");
+            pathlen = 2;
+            tar->pathNext = src;
+            if (InvisibilityGrph)
+            {
+                // TODO:  Could we know this edge already?
+                EdgeInf *edge = EdgeInf::existingEdge(src, tar);
+                assert(edge != NULL);
+                edge->addCycleBlocker();
+            }
+            result = false;
+            break;
+        }
+        if (pathlen > 100)
+        {
+            fprintf(stderr, "ERROR: Should never be here...\n");
+            exit(1);
+        }
+    }
+    Point *path = (Point *) malloc(pathlen * sizeof(Point));
+
+    int j = pathlen - 1;
+    for (VertInf *i = tar; i != src; i = i->pathNext)
+    {
+        if (InvisibilityGrph)
+        {
+            // TODO: Again, we could know this edge without searching.
+            EdgeInf *edge = EdgeInf::existingEdge(i, i->pathNext);
+            edge->addConn(flag);
+        }
+        else
+        {
+            _false_path = true;
+        }
+        path[j--] = i->point;
+    }
+    path[0] = src->point;
+
+
+    // Would clear visibility for endpoints here if required.
+
+    PolyLine& output_route = route();
+    output_route.pn = pathlen;
+    output_route.ps = path;
+   
+    return (int) result;
+}
+
+
+//============================================================================
+
+
+    // It's intended this function is called after shape movement has 
+    // happened to alert connectors that they need to be rerouted.
+void callbackAllInvalidConnectors(void)
+{
+    ConnRefList::iterator fin = connRefs.end();
+    for (ConnRefList::iterator i = connRefs.begin(); i != fin; ++i) {
+        (*i)->handleInvalid();
+    }
+}
+
+
+}
+
+
diff --git a/src/libavoid/connector.h b/src/libavoid/connector.h
new file mode 100644
index 000000000..6abb01d49
--- /dev/null
+++ b/src/libavoid/connector.h
@@ -0,0 +1,93 @@
+/*
+ * vim: ts=4 sw=4 et tw=0 wm=0
+ *
+ * libavoid - Fast, Incremental, Object-avoiding Line Router
+ * Copyright (C) 2004-2005  Michael Wybrow <mjwybrow@users.sourceforge.net>
+ *
+ * This library is free software; you can redistribute it and/or
+ * modify it under the terms of the GNU Lesser General Public
+ * License as published by the Free Software Foundation; either
+ * version 2.1 of the License, or (at your option) any later version.
+ *
+ * This library is distributed in the hope that it will be useful,
+ * but WITHOUT ANY WARRANTY; without even the implied warranty of
+ * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU
+ * Lesser General Public License for more details.
+ *
+ * You should have received a copy of the GNU Lesser General Public
+ * License along with this library; if not, write to the Free Software
+ * Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA  02111-1307  USA
+ * 
+*/
+
+#ifndef AVOID_CONNECTOR_H
+#define AVOID_CONNECTOR_H
+
+#include "libavoid/geometry.h"
+#include "libavoid/shape.h"
+#include <list>
+
+
+namespace Avoid {
+
+typedef unsigned int uint;
+    
+class ConnRef;
+
+typedef std::list<ConnRef *> ConnRefList;
+
+
+class ConnRef
+{
+    public:
+        ConnRef(const uint id);
+        ConnRef(const uint id, const Point& src, const Point& dst);
+        ~ConnRef();
+        
+        PolyLine& route(void);
+        bool needsReroute(void);
+        void moveRoute(const int& diff_x, const int& diff_y);
+        void freeRoute(void);
+        void calcRouteDist(void);
+        void updateEndPoint(const uint type, const Point& point);
+        void makeActive(void);
+        void makeInactive(void);
+        void lateSetup(const Point& src, const Point& dst);
+        VertInf *src(void);
+        VertInf *dst(void);
+        void removeFromGraph(void);
+        bool isInitialised(void);
+        void unInitialise(void);
+        void setCallback(void (*cb)(void *), void *ptr);
+        void handleInvalid(void);
+        int generatePath(Point p0, Point p1);
+        void makePathInvalid(void);
+        
+        friend void markConnectors(ShapeRef *shape);
+
+    private:
+        uint _id;
+        bool _needs_reroute_flag;
+        bool _false_path;
+        bool _active;
+        PolyLine _route;
+        double _route_dist;
+        ConnRefList::iterator _pos;
+        VertInf *_srcVert;
+        VertInf *_dstVert;
+        bool _initialised;
+        void (*_callback)(void *);
+        void *_connector;
+};
+
+
+extern ConnRefList connRefs;
+
+extern void callbackAllInvalidConnectors(void);
+
+}
+
+
+#endif
+
+
diff --git a/src/libavoid/debug.h b/src/libavoid/debug.h
new file mode 100644
index 000000000..0b182d442
--- /dev/null
+++ b/src/libavoid/debug.h
@@ -0,0 +1,61 @@
+/*
+ * vim: ts=4 sw=4 et tw=0 wm=0
+ *
+ * libavoid - Fast, Incremental, Object-avoiding Line Router
+ * Copyright (C) 2004-2005  Michael Wybrow <mjwybrow@users.sourceforge.net>
+ *
+ * This library is free software; you can redistribute it and/or
+ * modify it under the terms of the GNU Lesser General Public
+ * License as published by the Free Software Foundation; either
+ * version 2.1 of the License, or (at your option) any later version.
+ *
+ * This library is distributed in the hope that it will be useful,
+ * but WITHOUT ANY WARRANTY; without even the implied warranty of
+ * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU
+ * Lesser General Public License for more details.
+ *
+ * You should have received a copy of the GNU Lesser General Public
+ * License along with this library; if not, write to the Free Software
+ * Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA  02111-1307  USA
+ * 
+*/
+
+#ifndef AVOID_DEBUG_H
+#define AVOID_DEBUG_H
+
+
+
+#ifndef NDEBUG
+  //#define DBPRINTF_DEBUG
+#endif
+
+
+#ifdef DBPRINTF_DEBUG
+
+#include <stdarg.h>
+#include <iostream>
+
+#endif
+
+namespace Avoid {
+
+#ifdef DBPRINTF_DEBUG
+inline void db_printf(const char *fmt, ...)
+{
+    va_list ap;
+    va_start(ap, fmt);
+    vfprintf(stdout, fmt, ap);
+    va_end(ap);
+}
+#else
+inline void db_printf(const char *fmt, ...)
+{
+}
+#endif
+
+}
+
+
+#endif
+
+
diff --git a/src/libavoid/geometry.cpp b/src/libavoid/geometry.cpp
new file mode 100644
index 000000000..d720693ac
--- /dev/null
+++ b/src/libavoid/geometry.cpp
@@ -0,0 +1,260 @@
+/*
+ * vim: ts=4 sw=4 et tw=0 wm=0
+ *
+ * libavoid - Fast, Incremental, Object-avoiding Line Router
+ * Copyright (C) 2004-2005  Michael Wybrow <mjwybrow@users.sourceforge.net>
+ *
+ * --------------------------------------------------------------------
+ * Much of the code in this module is based on code published with
+ * and/or described in "Computational Geometry in C" (Second Edition),
+ * Copyright (C) 1998  Joseph O'Rourke <orourke@cs.smith.edu>
+ * --------------------------------------------------------------------
+ *
+ * This library is free software; you can redistribute it and/or
+ * modify it under the terms of the GNU Lesser General Public
+ * License as published by the Free Software Foundation; either
+ * version 2.1 of the License, or (at your option) any later version.
+ *
+ * This library is distributed in the hope that it will be useful,
+ * but WITHOUT ANY WARRANTY; without even the implied warranty of
+ * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU
+ * Lesser General Public License for more details.
+ *
+ * You should have received a copy of the GNU Lesser General Public
+ * License along with this library; if not, write to the Free Software
+ * Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA  02111-1307  USA
+ *
+*/
+
+#include "libavoid/graph.h"
+#include "libavoid/polyutil.h"
+
+#include <math.h>
+
+namespace Avoid {
+
+
+// Returns true iff the point c lies on the closed segment ab.
+//
+// Based on the code of 'Between'.
+//
+static const bool inBetween(const Point& a, const Point& b, const Point& c)
+{
+    // We only call this when we know the points are collinear,
+    // otherwise we should be checking this here.
+    assert(vecDir(a, b, c) == 0);
+
+    if (a.x != b.x)
+    {
+        // not vertical
+        return (((a.x < c.x) && (c.x < b.x)) ||
+                ((b.x < c.x) && (c.x < a.x)));
+    }
+    else
+    {
+        return (((a.y < c.y) && (c.y < b.y)) ||
+                ((b.y < c.y) && (c.y < a.y)));
+    }
+}
+
+
+// Returns true if the segment cd intersects the segment ab, blocking
+// visibility.
+//
+// Based on the code of 'IntersectProp' and 'Intersect'.
+//
+bool segmentIntersect(const Point& a, const Point& b, const Point& c,
+        const Point& d)
+{
+    int ab_c = vecDir(a, b, c);
+    if ((ab_c == 0) && inBetween(a, b, c))
+    {
+        return true;
+    }
+
+    int ab_d = vecDir(a, b, d);
+    if ((ab_d == 0) && inBetween(a, b, d))
+    {
+        return true;
+    }
+
+    // It's ok for either of the points a or b to be on the line cd,
+    // so we don't have to check the other two cases.
+
+    int cd_a = vecDir(c, d, a);
+    int cd_b = vecDir(c, d, b);
+
+    // Is an intersection if a and b are on opposite sides of cd,
+    // and c and d are on opposite sides of the line ab.
+    //
+    // Note: this is safe even though the textbook warns about it
+    // since, unlike them, out vecDir is equivilent to 'AreaSign'
+    // rather than 'Area2'.
+    return (((ab_c * ab_d) < 0) && ((cd_a * cd_b) < 0));
+}
+
+
+// Returns true iff the point p in a valid region that can contain
+// shortest paths.  a0, a1, a2 are ordered vertices of a shape.
+// This function may seem 'backwards' to the user due to some of
+// the code being reversed due to screen cooridinated being the
+// opposite of graph paper coords.
+// TODO: Rewrite this after checking whether it works for Inkscape.
+//
+// Based on the code of 'InCone'.
+//
+bool inValidRegion(const Point& a0, const Point& a1, const Point& a2,
+        const Point& b)
+{
+    int rSide = vecDir(b, a0, a1);
+    int sSide = vecDir(b, a1, a2);
+
+    bool rOutOn = (rSide >= 0);
+    bool sOutOn = (sSide >= 0);
+
+    bool rOut = (rSide > 0);
+    bool sOut = (sSide > 0);
+
+    if (vecDir(a0, a1, a2) > 0)
+    {
+        // Concave at a1:
+        //
+        //   !rO      rO
+        //   !sO     !sO
+        //
+        //        +---s---
+        //        |
+        //   !rO  r   rO
+        //    sO  |   sO
+        //
+        //
+        return (IgnoreRegions ? false : (rOutOn && sOutOn));
+    }
+    else
+    {
+        // Convex at a1:
+        //
+        //   !rO      rO
+        //    sO      sO
+        //
+        // ---s---+
+        //        |
+        //   !rO  r   rO
+        //   !sO  |  !sO
+        //
+        //
+        if (IgnoreRegions)
+        {
+            return (rOutOn && !sOut) || (!rOut && sOutOn);
+        }
+        return (rOutOn || sOutOn);
+    }
+}
+
+
+// Returns the distance between points a and b.
+//
+double dist(const Point& a, const Point& b)
+{
+    double xdiff = a.x - b.x;
+    double ydiff = a.y - b.y;
+
+    return sqrt((xdiff * xdiff) + (ydiff * ydiff));
+}
+
+
+// Returns true iff the point q is inside (or on the edge of) the
+// polygon argpoly.
+//
+// Based on the code of 'InPoly'.
+//
+bool inPoly(const Polygn& argpoly, const Point& q)
+{
+    // Numbers of right and left edge/ray crossings.
+    int Rcross = 0;
+    int Lcross = 0;
+
+    // Copy the argument polygon
+    Polygn poly = copyPoly(argpoly);
+    Point *P = poly.ps;
+    int    n = poly.pn;
+
+    // Shift so that q is the origin. This is done for pedogical clarity.
+    for (int i = 0; i < n; ++i)
+    {
+        P[i].x = P[i].x - q.x;
+        P[i].y = P[i].y - q.y;
+    }
+
+    // For each edge e=(i-1,i), see if crosses ray.
+    for (int i = 0; i < n; ++i)
+    {
+        // First see if q=(0,0) is a vertex.
+        if ((P[i].x == 0) && (P[i].y == 0))
+        {
+            // We count a vertex as inside.
+            freePoly(poly);
+            return true;
+        }
+
+        // point index; i1 = i-1 mod n
+        int i1 = ( i + n - 1 ) % n;
+
+        // if e "straddles" the x-axis...
+        // The commented-out statement is logically equivalent to the one
+        // following.
+        // if( ((P[i].y > 0) && (P[i1].y <= 0)) ||
+        //         ((P[i1].y > 0) && (P[i].y <= 0)) )
+
+        if ((P[i].y > 0) != (P[i1].y > 0))
+        {
+            // e straddles ray, so compute intersection with ray.
+            double x = (P[i].x * P[i1].y - P[i1].x * P[i].y)
+                    / (P[i1].y - P[i].y);
+
+            // crosses ray if strictly positive intersection.
+            if (x > 0)
+            {
+                Rcross++;
+            }
+        }
+
+        // if e straddles the x-axis when reversed...
+        // if( ((P[i].y < 0) && (P[i1].y >= 0)) ||
+        //         ((P[i1].y < 0) && (P[i].y >= 0)) )
+
+        if ((P[i].y < 0) != (P[i1].y < 0))
+        {
+            // e straddles ray, so compute intersection with ray.
+            double x = (P[i].x * P[i1].y - P[i1].x * P[i].y)
+                    / (P[i1].y - P[i].y);
+
+            // crosses ray if strictly positive intersection.
+            if (x < 0)
+            {
+                Lcross++;
+            }
+        }
+    }
+    freePoly(poly);
+
+    // q on the edge if left and right cross are not the same parity.
+    if ( (Rcross % 2) != (Lcross % 2) )
+    {
+        // We count the edge as inside.
+        return true;
+    }
+
+    // Inside iff an odd number of crossings.
+    if ((Rcross % 2) == 1)
+    {
+        return true;
+    }
+
+    // Outside.
+    return false;
+}
+
+
+}
+
diff --git a/src/libavoid/geometry.h b/src/libavoid/geometry.h
new file mode 100644
index 000000000..500da6273
--- /dev/null
+++ b/src/libavoid/geometry.h
@@ -0,0 +1,75 @@
+/*
+ * vim: ts=4 sw=4 et tw=0 wm=0
+ *
+ * libavoid - Fast, Incremental, Object-avoiding Line Router
+ * Copyright (C) 2004-2005  Michael Wybrow <mjwybrow@users.sourceforge.net>
+ *
+ * --------------------------------------------------------------------
+ * Much of the code in this module is based on code published with
+ * and/or described in "Computational Geometry in C" (Second Edition),
+ * Copyright (C) 1998  Joseph O'Rourke <orourke@cs.smith.edu>
+ * --------------------------------------------------------------------
+ *
+ * This library is free software; you can redistribute it and/or
+ * modify it under the terms of the GNU Lesser General Public
+ * License as published by the Free Software Foundation; either
+ * version 2.1 of the License, or (at your option) any later version.
+ *
+ * This library is distributed in the hope that it will be useful,
+ * but WITHOUT ANY WARRANTY; without even the implied warranty of
+ * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU
+ * Lesser General Public License for more details.
+ *
+ * You should have received a copy of the GNU Lesser General Public
+ * License along with this library; if not, write to the Free Software
+ * Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA  02111-1307  USA
+ * 
+*/
+
+
+#ifndef _GEOMETRY_H
+#define _GEOMETRY_H
+
+#include "libavoid/geomtypes.h"
+
+namespace Avoid {
+
+
+extern double dist(const Point& a, const Point& b);
+extern bool segmentIntersect(const Point& a, const Point& b,
+        const Point& c, const Point& d);
+extern bool inPoly(const Polygn& poly, const Point& q);
+extern bool inValidRegion(const Point& a0, const Point& a1, const Point& a2,
+        const Point& b);
+
+
+// Direction from vector.
+// Looks at the position of point c from the directed segment ab and
+// returns the following:
+//      1   counterclockwise
+//      0   collinear
+//     -1   clockwise
+//
+// Based on the code of 'AreaSign'.
+//
+static inline int vecDir(const Point& a, const Point& b, const Point& c)
+{
+    double area2 = ((b.x - a.x) * (c.y - a.y)) -
+                   ((c.x - a.x) * (b.y - a.y));
+    
+    if (area2 < -0.001)
+    {
+        return -1;
+    }
+    else if (area2 > 0.001)
+    {
+        return 1;
+    }
+    return 0;
+}
+
+
+}
+
+
+#endif
diff --git a/src/libavoid/geomtypes.h b/src/libavoid/geomtypes.h
new file mode 100644
index 000000000..9b682759a
--- /dev/null
+++ b/src/libavoid/geomtypes.h
@@ -0,0 +1,61 @@
+/*
+ * vim: ts=4 sw=4 et tw=0 wm=0
+ *
+ * libavoid - Fast, Incremental, Object-avoiding Line Router
+ * Copyright (C) 2004-2005  Michael Wybrow <mjwybrow@users.sourceforge.net>
+ *
+ * This library is free software; you can redistribute it and/or
+ * modify it under the terms of the GNU Lesser General Public
+ * License as published by the Free Software Foundation; either
+ * version 2.1 of the License, or (at your option) any later version.
+ *
+ * This library is distributed in the hope that it will be useful,
+ * but WITHOUT ANY WARRANTY; without even the implied warranty of
+ * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU
+ * Lesser General Public License for more details.
+ *
+ * You should have received a copy of the GNU Lesser General Public
+ * License along with this library; if not, write to the Free Software
+ * Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA  02111-1307  USA
+ * 
+*/
+
+
+#ifndef AVOID_GEOMTYPES_H
+#define AVOID_GEOMTYPES_H
+
+
+namespace Avoid
+{
+
+    
+typedef struct
+{
+    double x;
+    double y;
+} Point;
+
+
+typedef Point Vector;
+
+
+typedef struct
+{
+    int id;
+    Point *ps;
+    int pn;
+} Polygn;
+
+typedef Polygn PolyLine;
+
+
+typedef struct
+{
+    Point a;
+    Point b;
+} Edge;
+
+
+}
+
+#endif
diff --git a/src/libavoid/graph.cpp b/src/libavoid/graph.cpp
new file mode 100644
index 000000000..9b1d602be
--- /dev/null
+++ b/src/libavoid/graph.cpp
@@ -0,0 +1,986 @@
+/*
+ * vim: ts=4 sw=4 et tw=0 wm=0
+ *
+ * libavoid - Fast, Incremental, Object-avoiding Line Router
+ * Copyright (C) 2004-2005  Michael Wybrow <mjwybrow@users.sourceforge.net>
+ *
+ * This library is free software; you can redistribute it and/or
+ * modify it under the terms of the GNU Lesser General Public
+ * License as published by the Free Software Foundation; either
+ * version 2.1 of the License, or (at your option) any later version.
+ *
+ * This library is distributed in the hope that it will be useful,
+ * but WITHOUT ANY WARRANTY; without even the implied warranty of
+ * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU
+ * Lesser General Public License for more details.
+ *
+ * You should have received a copy of the GNU Lesser General Public
+ * License along with this library; if not, write to the Free Software
+ * Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA  02111-1307  USA
+ *
+*/
+
+#include "libavoid/debug.h"
+#include "libavoid/graph.h"
+#include "libavoid/connector.h"
+#include "libavoid/polyutil.h"
+#include "libavoid/timer.h"
+
+#include <math.h>
+
+namespace Avoid {
+
+
+static int st_checked_edges = 0;
+
+EdgeList visGraph;
+EdgeList invisGraph;
+
+
+EdgeInf::EdgeInf(VertInf *v1, VertInf *v2)
+    : lstPrev(NULL)
+    , lstNext(NULL)
+    , _added(false)
+    , _visible(false)
+    , _v1(v1)
+    , _v2(v2)
+    , _dist(-1)
+{
+    _blockers.clear();
+    _conns.clear();
+}
+
+
+EdgeInf::~EdgeInf()
+{
+    if (_added)
+    {
+        makeInactive();
+    }
+}
+
+
+void EdgeInf::makeActive(void)
+{
+    assert(_added == false);
+
+    if (_visible)
+    {
+        visGraph.addEdge(this);
+        _pos1 = _v1->visList.insert(_v1->visList.begin(), this);
+        _v1->visListSize++;
+        _pos2 = _v2->visList.insert(_v2->visList.begin(), this);
+        _v2->visListSize++;
+    }
+    else // if (invisible)
+    {
+        invisGraph.addEdge(this);
+        _pos1 = _v1->invisList.insert(_v1->invisList.begin(), this);
+        _v1->invisListSize++;
+        _pos2 = _v2->invisList.insert(_v2->invisList.begin(), this);
+        _v2->invisListSize++;
+    }
+    _added = true;
+}
+
+
+void EdgeInf::makeInactive(void)
+{
+    assert(_added == true);
+
+    if (_visible)
+    {
+        visGraph.removeEdge(this);
+        _v1->visList.erase(_pos1);
+        _v1->visListSize--;
+        _v2->visList.erase(_pos2);
+        _v2->visListSize--;
+    }
+    else // if (invisible)
+    {
+        invisGraph.removeEdge(this);
+        _v1->invisList.erase(_pos1);
+        _v1->invisListSize--;
+        _v2->invisList.erase(_pos2);
+        _v2->invisListSize--;
+    }
+    _blockers.clear();
+    _conns.clear();
+    _added = false;
+}
+
+
+double EdgeInf::getDist(void)
+{
+    return _dist;
+}
+
+
+void EdgeInf::setDist(double dist)
+{
+    //assert(dist != 0);
+
+    if (_added && !_visible)
+    {
+        makeInactive();
+    }
+    if (!_added)
+    {
+        _visible = true;
+        makeActive();
+    }
+    _dist = dist;
+    _blockers.clear();
+}
+
+
+void EdgeInf::alertConns(void)
+{
+    for (FlagList::iterator i = _conns.begin(); i != _conns.end(); ++i)
+    {
+        *(*i) = true;
+    }
+    _conns.clear();
+}
+
+
+void EdgeInf::addConn(bool *flag)
+{
+    _conns.push_back(flag);
+}
+
+
+void EdgeInf::addCycleBlocker(void)
+{
+    // Needs to be in invisibility graph.
+    addBlocker(-1);
+}
+
+
+void EdgeInf::addBlocker(int b)
+{
+    assert(InvisibilityGrph);
+
+    if (_added && _visible)
+    {
+        makeInactive();
+    }
+    if (!_added)
+    {
+        _visible = false;
+        makeActive();
+    }
+    _dist = 0;
+    _blockers.clear();
+    _blockers.push_back(b);
+}
+
+
+bool EdgeInf::hasBlocker(int b)
+{
+    assert(InvisibilityGrph);
+
+    ShapeList::iterator finish = _blockers.end();
+    for (ShapeList::iterator it = _blockers.begin(); it != finish; ++it)
+    {
+        if ((*it) == -1)
+        {
+            alertConns();
+            return true;
+        }
+        else if ((*it) == b)
+        {
+            return true;
+        }
+    }
+    return false;
+}
+
+
+pair<VertID, VertID> EdgeInf::ids(void)
+{
+    return std::make_pair(_v1->id, _v2->id);
+}
+
+
+pair<Point, Point> EdgeInf::points(void)
+{
+    return std::make_pair(_v1->point, _v2->point);
+}
+
+
+void EdgeInf::db_print(void)
+{
+    db_printf("Edge(");
+    _v1->id.db_print();
+    db_printf(",");
+    _v2->id.db_print();
+    db_printf(")\n");
+}
+
+
+void EdgeInf::checkVis(void)
+{
+    if (_added && !_visible)
+    {
+        db_printf("\tChecking visibility for existing invisibility edge..."
+                "\n\t\t");
+        db_print();
+    }
+    else if (_added && _visible)
+    {
+        db_printf("\tChecking visibility for existing visibility edge..."
+                "\n\t\t");
+        db_print();
+    }
+
+    int blocker = 0;
+    bool cone1 = true;
+    bool cone2 = true;
+
+    VertInf *i = _v1;
+    VertInf *j = _v2;
+    const VertID& iID = i->id;
+    const VertID& jID = j->id;
+    const Point& iPoint = i->point;
+    const Point& jPoint = j->point;
+
+    st_checked_edges++;
+
+    if (iID.isShape)
+    {
+        cone1 = inValidRegion(i->shPrev->point, iPoint, i->shNext->point,
+                jPoint);
+    }
+    else
+    {
+        ShapeSet& ss = contains[iID];
+
+        if ((jID.isShape) && (ss.find(jID.objID) != ss.end()))
+        {
+            db_printf("1: Edge of bounding shape\n");
+            // Don't even check this edge, it should be zero,
+            // since a point in a shape can't see it's corners
+            cone1 = false;
+        }
+    }
+
+    if (cone1)
+    {
+        // If outside the first cone, don't even bother checking.
+        if (jID.isShape)
+        {
+            cone2 = inValidRegion(j->shPrev->point, jPoint, j->shNext->point,
+                    iPoint);
+        }
+        else
+        {
+            ShapeSet& ss = contains[jID];
+
+            if ((iID.isShape) && (ss.find(iID.objID) != ss.end()))
+            {
+                db_printf("2: Edge of bounding shape\n");
+                // Don't even check this edge, it should be zero,
+                // since a point in a shape can't see it's corners
+                cone2 = false;
+            }
+        }
+    }
+
+    if (cone1 && cone2 && ((blocker = firstBlocker()) == 0))
+    {
+
+        // if i and j see each other, add edge
+        db_printf("\tSetting visibility edge... \n\t\t");
+        db_print();
+
+        double d = dist(iPoint, jPoint);
+
+        setDist(d);
+
+    }
+    else if (InvisibilityGrph)
+    {
+#if 0
+        db_printf("%d, %d, %d\n", cone1, cone2, blocker);
+        db_printf("\t(%d, %d)--(%d, %d)\n", (int) iInfo.point.x,
+                (int) iInfo.point.y, (int) jInfo.point.x,
+                (int) jInfo.point.y);
+#endif
+
+        // if i and j can't see each other, add blank edge
+        db_printf("\tSetting invisibility edge... \n\t\t");
+        db_print();
+        addBlocker(blocker);
+    }
+}
+
+
+int EdgeInf::firstBlocker(void)
+{
+    ShapeSet ss = ShapeSet();
+
+    Point& pti = _v1->point;
+    Point& ptj = _v2->point;
+    VertID& iID = _v1->id;
+    VertID& jID = _v2->id;
+
+    if (!(iID.isShape))
+    {
+        ss.insert(contains[iID].begin(), contains[iID].end());
+    }
+    if (!(jID.isShape))
+    {
+        ss.insert(contains[jID].begin(), contains[jID].end());
+    }
+
+    VertInf *last = vertices.end();
+    for (VertInf *k = vertices.shapesBegin(); k != last; )
+    {
+        VertID kID = k->id;
+        if ((ss.find(kID.objID) != ss.end()))
+        {
+            uint shapeID = kID.objID;
+            db_printf("Endpoint is inside shape %u so ignore shape edges.\n",
+                    kID.objID);
+            // One of the endpoints is inside this shape so ignore it.
+            while ((k != last) && (k->id.objID == shapeID))
+            {
+                // And skip the other vertices from this shape.
+                k = k->lstNext;
+            }
+            continue;
+        }
+        Point& kPoint = k->point;
+        Point& kPrevPoint = k->shPrev->point;
+
+        if (segmentIntersect(pti, ptj, kPrevPoint, kPoint))
+        {
+            ss.clear();
+            return kID.objID;
+        }
+        k = k->lstNext;
+    }
+    ss.clear();
+    return 0;
+}
+
+
+bool EdgeInf::isBetween(VertInf *i, VertInf *j)
+{
+    if ( ((i == _v1) && (j == _v2)) ||
+         ((i == _v2) && (j == _v1)) )
+    {
+        return true;
+    }
+    return false;
+}
+
+
+VertInf *EdgeInf::otherVert(VertInf *vert)
+{
+    assert((vert == _v1) || (vert == _v2));
+
+    if (vert == _v1)
+    {
+        return _v2;
+    }
+    return _v1;
+}
+
+
+EdgeInf *EdgeInf::checkEdgeVisibility(VertInf *i, VertInf *j, bool knownNew)
+{
+    EdgeInf *edge = NULL;
+
+    if (knownNew)
+    {
+        assert(existingEdge(i, j) == NULL);
+        edge = new EdgeInf(i, j);
+    }
+    else
+    {
+        edge = existingEdge(i, j);
+        if (edge == NULL)
+        {
+            edge = new EdgeInf(i, j);
+        }
+    }
+    edge->checkVis();
+    if (!(edge->_added) && !InvisibilityGrph)
+    {
+        delete edge;
+        edge = NULL;
+    }
+
+    return edge;
+}
+
+
+EdgeInf *EdgeInf::existingEdge(VertInf *i, VertInf *j)
+{
+    VertInf *selected = NULL;
+
+    if (i->visListSize <= j->visListSize)
+    {
+        selected = i;
+    }
+    else
+    {
+        selected = j;
+    }
+
+    EdgeInfList& visList = selected->visList;
+    EdgeInfList::iterator finish = visList.end();
+    for (EdgeInfList::iterator edge = visList.begin(); edge != finish;
+            ++edge)
+    {
+        if ((*edge)->isBetween(i, j))
+        {
+            return (*edge);
+        }
+    }
+
+    if (i->invisListSize <= j->invisListSize)
+    {
+        selected = i;
+    }
+    else
+    {
+        selected = j;
+    }
+
+    EdgeInfList& invisList = selected->invisList;
+    finish = invisList.end();
+    for (EdgeInfList::iterator edge = invisList.begin(); edge != finish;
+            ++edge)
+    {
+        if ((*edge)->isBetween(i, j))
+        {
+            return (*edge);
+        }
+    }
+
+    return NULL;
+}
+
+
+//===========================================================================
+
+
+EdgeList::EdgeList()
+    : _firstEdge(NULL)
+    , _lastEdge(NULL)
+    , _count(0)
+{
+}
+
+
+void EdgeList::addEdge(EdgeInf *edge)
+{
+    if (_firstEdge == NULL)
+    {
+        assert(_lastEdge == NULL);
+
+        _lastEdge = edge;
+        _firstEdge = edge;
+
+        edge->lstPrev = NULL;
+        edge->lstNext = NULL;
+    }
+    else
+    {
+        assert(_lastEdge != NULL);
+
+        _lastEdge->lstNext = edge;
+        edge->lstPrev = _lastEdge;
+
+        _lastEdge = edge;
+
+        edge->lstNext = NULL;
+    }
+    _count++;
+}
+
+
+void EdgeList::removeEdge(EdgeInf *edge)
+{
+    if (edge->lstPrev)
+    {
+        edge->lstPrev->lstNext = edge->lstNext;
+    }
+    if (edge->lstNext)
+    {
+        edge->lstNext->lstPrev = edge->lstPrev;
+    }
+    if (edge == _lastEdge)
+    {
+        _lastEdge = edge->lstPrev;
+        if (edge == _firstEdge)
+        {
+            _firstEdge = NULL;
+        }
+    }
+    else if (edge == _firstEdge)
+    {
+        _firstEdge = edge->lstNext;
+    }
+
+
+    edge->lstPrev = NULL;
+    edge->lstNext = NULL;
+
+    _count--;
+}
+
+
+EdgeInf *EdgeList::begin(void)
+{
+    return _firstEdge;
+}
+
+
+EdgeInf *EdgeList::end(void)
+{
+    return NULL;
+}
+
+
+// General visibility graph utility functions
+
+
+void newBlockingShape(Polygn *poly, int pid)
+{
+    // o  Check all visibility edges to see if this one shape
+    //    blocks them.
+    EdgeInf *finish = visGraph.end();
+    for (EdgeInf *iter = visGraph.begin(); iter != finish ; )
+    {
+        EdgeInf *tmp = iter;
+        iter = iter->lstNext;
+
+        if (tmp->getDist() != 0)
+        {
+            pair<VertID, VertID> ids(tmp->ids());
+            VertID eID1 = ids.first;
+            VertID eID2 = ids.second;
+            pair<Point, Point> points(tmp->points());
+            Point e1 = points.first;
+            Point e2 = points.second;
+            bool blocked = false;
+
+            bool ep_in_poly1 = !(eID1.isShape) ? inPoly(*poly, e1) : false;
+            bool ep_in_poly2 = !(eID2.isShape) ? inPoly(*poly, e2) : false;
+            if (ep_in_poly1 || ep_in_poly2)
+            {
+                // Don't check edges that have a connector endpoint
+                // and are inside the shape being added.
+                continue;
+            }
+
+            for (int pt_i = 0; pt_i < poly->pn; pt_i++)
+            {
+                int pt_n = (pt_i == (poly->pn - 1)) ? 0 : pt_i + 1;
+                if (segmentIntersect(e1, e2, poly->ps[pt_i], poly->ps[pt_n]))
+                {
+                    blocked = true;
+                    break;
+                }
+            }
+            if (blocked)
+            {
+                db_printf("\tRemoving newly blocked edge (by shape %3d)"
+                        "... \n\t\t", pid);
+                tmp->alertConns();
+                tmp->db_print();
+                if (InvisibilityGrph)
+                {
+                    tmp->addBlocker(pid);
+                }
+                else
+                {
+                    delete tmp;
+                }
+            }
+        }
+    }
+}
+
+
+void checkAllBlockedEdges(int pid)
+{
+    assert(InvisibilityGrph);
+
+    for (EdgeInf *iter = invisGraph.begin(); iter != invisGraph.end() ; )
+    {
+        EdgeInf *tmp = iter;
+        iter = iter->lstNext;
+
+        if (tmp->hasBlocker(pid))
+        {
+            tmp->checkVis();
+        }
+    }
+}
+
+
+void checkAllMissingEdges(void)
+{
+    assert(!InvisibilityGrph);
+
+    VertInf *first = NULL;
+
+    if (IncludeEndpoints)
+    {
+        first = vertices.connsBegin();
+    }
+    else
+    {
+        first = vertices.shapesBegin();
+    }
+
+    VertInf *pend = vertices.end();
+    for (VertInf *i = first; i != pend; i = i->lstNext)
+    {
+        VertID iID = i->id;
+
+        // Check remaining, earlier vertices
+        for (VertInf *j = first ; j != i; j = j->lstNext)
+        {
+            VertID jID = j->id;
+            if (!(iID.isShape) && (iID.objID != jID.objID))
+            {
+                // Don't keep visibility between edges of different conns
+                continue;
+            }
+
+            // See if the edge is already there?
+            bool found = (EdgeInf::existingEdge(i, j) != NULL);
+
+            if (!found)
+            {
+                // Didn't already exist, check.
+                bool knownNew = true;
+                EdgeInf::checkEdgeVisibility(i, j, knownNew);
+            }
+        }
+    }
+}
+
+
+void generateContains(VertInf *pt)
+{
+    contains[pt->id].clear();
+
+    ShapeRefList::iterator finish = shapeRefs.end();
+    for (ShapeRefList::iterator i = shapeRefs.begin(); i != finish; ++i)
+    {
+        Polygn poly = copyPoly(*i);
+        if (inPoly(poly, pt->point))
+        {
+            contains[pt->id].insert((*i)->id());
+        }
+        freePoly(poly);
+    }
+}
+
+
+void adjustContainsWithAdd(const Polygn& poly, const int p_shape)
+{
+    for (VertInf *k = vertices.connsBegin(); k != vertices.shapesBegin();
+            k = k->lstNext)
+    {
+        if (inPoly(poly, k->point))
+        {
+            contains[k->id].insert(p_shape);
+        }
+    }
+}
+
+
+void adjustContainsWithDel(const int p_shape)
+{
+    for (VertInf *k = vertices.connsBegin(); k != vertices.shapesBegin();
+            k = k->lstNext)
+    {
+        contains[k->id].erase(p_shape);
+    }
+}
+
+
+// Maybe this one should be in with the connector stuff, but it may later
+// need to operate on a particular section of the visibility graph so it
+// may have to stay here.
+//
+#define MIN(a, b) (((a) <= (b)) ? (a) : (b))
+#define MAX(a, b) (((a) >= (b)) ? (a) : (b))
+
+#ifdef SELECTIVE_DEBUG
+static double AngleAFromThreeSides(const double a, const double b,
+        const double c)
+{
+    // returns angle A, the angle opposite from side a, in radians
+    return acos((pow(b, 2) + pow(c, 2) - pow(a, 2)) / (2 * b * c));
+}
+#endif
+
+void markConnectors(ShapeRef *shape)
+{
+    assert(SelectiveReroute);
+
+    ConnRefList::iterator end = connRefs.end();
+    for (ConnRefList::iterator it = connRefs.begin(); it != end; ++it)
+    {
+        ConnRef *conn = (*it);
+
+        if (conn->_route.pn == 0)
+        {
+            // Ignore uninitialised connectors.
+            continue;
+        }
+
+        Point start = conn->_route.ps[0];
+        Point end = conn->_route.ps[conn->_route.pn - 1];
+
+        double conndist = conn->_route_dist;
+
+        double estdist;
+        double e1, e2;
+
+        VertInf *beginV = shape->firstVert();
+        VertInf *endV = shape->lastVert()->lstNext;
+        for (VertInf *i = beginV; i != endV; i = i->lstNext)
+        {
+            const Point& p1 = i->point;
+            const Point& p2 = i->shNext->point;
+
+            double offy;
+            double a;
+            double b;
+            double c;
+            double d;
+
+            double min;
+            double max;
+
+            if (p1.y == p2.y)
+            {
+                // Standard case
+                offy = p1.y;
+                a = start.x;
+                b = start.y - offy;
+                c = end.x;
+                d = end.y - offy;
+
+                min = MIN(p1.x, p2.x);
+                max = MAX(p1.x, p2.x);
+            }
+            else if (p1.x == p2.x)
+            {
+                // Other Standard case
+                offy = p1.x;
+                a = start.y;
+                b = start.x - offy;
+                c = end.y;
+                d = end.x - offy;
+
+                min = MIN(p1.y, p2.y);
+                max = MAX(p1.y, p2.y);
+            }
+            else
+            {
+                // Need to do rotation
+                Point n_p2 = { p2.x - p1.x, p2.y - p1.y };
+                Point n_start = { start.x - p1.x, start.y - p1.y };
+                Point n_end = { end.x - p1.x, end.y - p1.y };
+                //printf("n_p2:    (%.1f, %.1f)\n", n_p2.x, n_p2.y);
+                //printf("n_start: (%.1f, %.1f)\n", n_start.x, n_start.y);
+                //printf("n_end:   (%.1f, %.1f)\n", n_end.x, n_end.y);
+
+                double theta = 0 - atan2(n_p2.y, n_p2.x);
+                //printf("theta = %.2f\n", theta * (180 / PI));
+
+                Point r_p1 = {0, 0};
+                Point r_p2 = n_p2;
+                start = n_start;
+                end = n_end;
+
+                double cosv = cos(theta);
+                double sinv = sin(theta);
+
+                r_p2.x = cosv * n_p2.x - sinv * n_p2.y;
+                r_p2.y = cosv * n_p2.y + sinv * n_p2.x;
+                start.x = cosv * n_start.x - sinv * n_start.y;
+                start.y = cosv * n_start.y + sinv * n_start.x;
+                end.x = cosv * n_end.x - sinv * n_end.y;
+                end.y = cosv * n_end.y + sinv * n_end.x;
+                //printf("r_p2:    (%.1f, %.1f)\n", r_p2.x, r_p2.y);
+                //printf("r_start: (%.1f, %.1f)\n", start.x, start.y);
+                //printf("r_end:   (%.1f, %.1f)\n", end.x, end.y);
+
+                if (((int) r_p2.y) != 0)
+                {
+                    printf("r_p2.y: %f != 0\n", r_p2.y);
+                    abort();
+                }
+                // This might be slightly off.
+                r_p2.y = 0;
+
+                offy = r_p1.y;
+                a = start.x;
+                b = start.y - offy;
+                c = end.x;
+                d = end.y - offy;
+
+                min = MIN(r_p1.x, r_p2.x);
+                max = MAX(r_p1.x, r_p2.x);
+
+            }
+
+            double x;
+            if ((b + d) == 0)
+            {
+                db_printf("WARNING: (b + d) == 0\n");
+                d = d * -1;
+            }
+
+            if ((b == 0) && (d == 0))
+            {
+                db_printf("WARNING: b == d == 0\n");
+                if (((a < min) && (c < min)) ||
+                        ((a > max) && (c > max)))
+                {
+                    // It's going to get adjusted.
+                    x = a;
+                }
+                else
+                {
+                    continue;
+                }
+            }
+            else
+            {
+                x = ((b*c) + (a*d)) / (b + d);
+            }
+
+            //printf("%.1f, %.1f, %.1f, %.1f\n", a, b, c, d);
+            //printf("x = %.1f\n", x);
+
+            // XXX: Use MAX and MIN
+            x = (x < min) ? min : x;
+            x = (x > max) ? max : x;
+
+            //printf("x = %.1f\n", x);
+
+            Point xp;
+            if (p1.x == p2.x)
+            {
+                xp.x = offy;
+                xp.y = x;
+            }
+            else
+            {
+                xp.x = x;
+                xp.y = offy;
+            }
+            //printf("(%.1f, %.1f)\n", xp.x, xp.y);
+
+            e1 = dist(start, xp);
+            e2 = dist(xp, end);
+            estdist = e1 + e2;
+
+
+            //printf("is %.1f < %.1f\n", estdist, conndist);
+            if (estdist < conndist)
+            {
+#ifdef SELECTIVE_DEBUG
+                //double angle = AngleAFromThreeSides(dist(start, end),
+                //        e1, e2);
+                printf("[%3d] - Possible better path found (%.1f < %.1f)\n",
+                        conn->_id, estdist, conndist);
+#endif
+                conn->_needs_reroute_flag = true;
+                break;
+            }
+
+        }
+    }
+}
+
+
+void printInfo(void)
+{
+    FILE *fp = stdout;
+    fprintf(fp, "\nVisibility Graph info:\n");
+    fprintf(fp, "----------------------\n");
+
+    uint currshape = 0;
+    int st_shapes = 0;
+    int st_vertices = 0;
+    int st_endpoints = 0;
+    int st_valid_shape_visedges = 0;
+    int st_valid_endpt_visedges = 0;
+    int st_invalid_visedges = 0;
+    VertInf *finish = vertices.end();
+    for (VertInf *t = vertices.connsBegin(); t != finish; t = t->lstNext)
+    {
+        VertID pID = t->id;
+
+        if ((pID.isShape) && (pID.objID != currshape))
+        {
+            currshape = pID.objID;
+            st_shapes++;
+        }
+        if (pID.isShape)
+        {
+            st_vertices++;
+        }
+        else
+        {
+            // The shape 0 ones are temporary and not considered.
+            st_endpoints++;
+        }
+    }
+    for (EdgeInf *t = visGraph.begin(); t != visGraph.end();
+            t = t->lstNext)
+    {
+        std::pair<VertID, VertID> idpair = t->ids();
+
+        if (!(idpair.first.isShape) || !(idpair.second.isShape))
+        {
+            st_valid_endpt_visedges++;
+        }
+        else
+        {
+            st_valid_shape_visedges++;
+        }
+    }
+    for (EdgeInf *t = invisGraph.begin(); t != invisGraph.end();
+            t = t->lstNext)
+    {
+        st_invalid_visedges++;
+    }
+    fprintf(fp, "Number of shapes: %d\n", st_shapes);
+    fprintf(fp, "Number of vertices: %d (%d real, %d endpoints)\n",
+            st_vertices + st_endpoints, st_vertices, st_endpoints);
+    fprintf(fp, "Number of vis_edges: %d (%d valid [%d normal, %d endpt], "
+            "%d invalid)\n", st_valid_shape_visedges + st_invalid_visedges +
+            st_valid_endpt_visedges, st_valid_shape_visedges +
+            st_valid_endpt_visedges, st_valid_shape_visedges,
+            st_valid_endpt_visedges, st_invalid_visedges);
+    fprintf(fp, "----------------------\n");
+    fprintf(fp, "checkVisEdge tally: %d\n", st_checked_edges);
+    fprintf(fp, "----------------------\n");
+
+    fprintf(fp, "ADDS:  "); timers.Print(tmAdd);
+    fprintf(fp, "DELS:  "); timers.Print(tmDel);
+    fprintf(fp, "MOVS:  "); timers.Print(tmMov);
+    fprintf(fp, "***S:  "); timers.Print(tmSev);
+    fprintf(fp, "PTHS:  "); timers.Print(tmPth);
+    fprintf(fp, "\n");
+}
+
+
+}
+
+
diff --git a/src/libavoid/graph.h b/src/libavoid/graph.h
new file mode 100644
index 000000000..d30f394cf
--- /dev/null
+++ b/src/libavoid/graph.h
@@ -0,0 +1,127 @@
+/*
+ * vim: ts=4 sw=4 et tw=0 wm=0
+ *
+ * libavoid - Fast, Incremental, Object-avoiding Line Router
+ * Copyright (C) 2004-2005  Michael Wybrow <mjwybrow@users.sourceforge.net>
+ *
+ * This library is free software; you can redistribute it and/or
+ * modify it under the terms of the GNU Lesser General Public
+ * License as published by the Free Software Foundation; either
+ * version 2.1 of the License, or (at your option) any later version.
+ *
+ * This library is distributed in the hope that it will be useful,
+ * but WITHOUT ANY WARRANTY; without even the implied warranty of
+ * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU
+ * Lesser General Public License for more details.
+ *
+ * You should have received a copy of the GNU Lesser General Public
+ * License along with this library; if not, write to the Free Software
+ * Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA  02111-1307  USA
+ *
+*/
+
+#ifndef AVOID_GRAPH_H
+#define AVOID_GRAPH_H
+
+
+#include <cassert>
+#include <list>
+#include <utility>
+using std::pair;
+
+#include "libavoid/vertices.h"
+
+
+namespace Avoid {
+
+
+extern bool UseAStarSearch;
+extern bool IgnoreRegions;
+extern bool SelectiveReroute;
+extern bool IncludeEndpoints;
+extern bool UseLeesAlgorithm;
+extern bool InvisibilityGrph;
+extern bool PartialFeedback;
+
+
+typedef std::list<int> ShapeList;
+typedef std::list<bool *> FlagList;
+
+
+class EdgeInf
+{
+    public:
+        EdgeInf(VertInf *v1, VertInf *v2);
+        ~EdgeInf();
+        double getDist(void);
+        void setDist(double dist);
+        void alertConns(void);
+        void addConn(bool *flag);
+        void addCycleBlocker(void);
+        void addBlocker(int b);
+        bool hasBlocker(int b);
+        pair<VertID, VertID> ids(void);
+        pair<Point, Point> points(void);
+        void db_print(void);
+        void checkVis(void);
+        VertInf *otherVert(VertInf *vert);
+        static EdgeInf *checkEdgeVisibility(VertInf *i, VertInf *j,
+                bool knownNew = false);
+        static EdgeInf *existingEdge(VertInf *i, VertInf *j);
+
+        EdgeInf *lstPrev;
+        EdgeInf *lstNext;
+    private:
+        bool _added;
+        bool _visible;
+        VertInf *_v1;
+        VertInf *_v2;
+        EdgeInfList::iterator _pos1;
+        EdgeInfList::iterator _pos2;
+        ShapeList _blockers;
+        FlagList  _conns;
+        double  _dist;
+
+        void makeActive(void);
+        void makeInactive(void);
+        int firstBlocker(void);
+        bool isBetween(VertInf *i, VertInf *j);
+};
+
+
+class EdgeList
+{
+    public:
+        EdgeList();
+        void addEdge(EdgeInf *edge);
+        void removeEdge(EdgeInf *edge);
+        EdgeInf *begin(void);
+        EdgeInf *end(void);
+    private:
+        EdgeInf *_firstEdge;
+        EdgeInf *_lastEdge;
+        unsigned int _count;
+};
+
+
+extern EdgeList visGraph;
+extern EdgeList invisGraph;
+
+class ShapeRef;
+
+extern void newBlockingShape(Polygn *poly, int pid);
+extern void checkAllBlockedEdges(int pid);
+extern void checkAllMissingEdges(void);
+extern void generateContains(VertInf *pt);
+extern void adjustContainsWithAdd(const Polygn& poly, const int p_shape);
+extern void adjustContainsWithDel(const int p_shape);
+extern void markConnectors(ShapeRef *shape);
+extern void printInfo(void);
+
+
+}
+
+
+#endif
+
+
diff --git a/src/libavoid/incremental.cpp b/src/libavoid/incremental.cpp
new file mode 100644
index 000000000..3830c70ee
--- /dev/null
+++ b/src/libavoid/incremental.cpp
@@ -0,0 +1,139 @@
+/*
+ * vim: ts=4 sw=4 et tw=0 wm=0
+ *
+ * libavoid - Fast, Incremental, Object-avoiding Line Router
+ * Copyright (C) 2004-2005  Michael Wybrow <mjwybrow@users.sourceforge.net>
+ *
+ * This library is free software; you can redistribute it and/or
+ * modify it under the terms of the GNU Lesser General Public
+ * License as published by the Free Software Foundation; either
+ * version 2.1 of the License, or (at your option) any later version.
+ *
+ * This library is distributed in the hope that it will be useful,
+ * but WITHOUT ANY WARRANTY; without even the implied warranty of
+ * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU
+ * Lesser General Public License for more details.
+ *
+ * You should have received a copy of the GNU Lesser General Public
+ * License along with this library; if not, write to the Free Software
+ * Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA  02111-1307  USA
+ * 
+*/
+
+#include "libavoid/connector.h"
+#include "libavoid/graph.h"
+#include "libavoid/visibility.h"
+
+namespace Avoid {
+
+
+void addShape(ShapeRef *shape)
+{
+    uint pid = shape->id();
+    Polygn poly = shape->poly();
+    
+    adjustContainsWithAdd(poly, pid);
+    
+    // o  Check all visibility edges to see if this one shape
+    //    blocks them.
+    newBlockingShape(&poly, pid);
+
+    // o  Calculate visibility for the new vertices.
+    if (UseLeesAlgorithm)
+    {
+        shapeVisSweep(shape);
+    }
+    else
+    {
+        shapeVis(shape);
+    }
+    callbackAllInvalidConnectors();
+}
+
+
+void delShape(ShapeRef *shape)
+{
+    uint pid = shape->id();
+
+    // o  Remove entries related to this shape's vertices
+    shape->removeFromGraph();
+    
+    if (SelectiveReroute)
+    {
+        markConnectors(shape);
+    }
+
+    adjustContainsWithDel(pid);
+    
+    delete shape;
+    
+    // o  Check all edges that were blocked by this shape.
+    if (InvisibilityGrph)
+    {
+        checkAllBlockedEdges(pid);
+    }
+    else
+    {
+        // check all edges not in graph
+        checkAllMissingEdges();
+    }
+    callbackAllInvalidConnectors();
+}
+
+
+ShapeRef *moveShape(ShapeRef *oldShape, Polygn *newPoly)
+{
+    uint pid = oldShape->id();
+    
+    // o  Remove entries related to this shape's vertices
+    oldShape->removeFromGraph();
+    
+    if (SelectiveReroute && !(PartialFeedback && PartialTime))
+    {
+        markConnectors(oldShape);
+    }
+
+    adjustContainsWithDel(pid);
+    
+    delete oldShape;
+    oldShape = NULL;
+
+    adjustContainsWithAdd(*newPoly, pid);
+    
+    // o  Check all edges that were blocked by this shape.
+    if (InvisibilityGrph)
+    {
+        checkAllBlockedEdges(pid);
+    }
+    else
+    {
+        // check all edges not in graph
+        checkAllMissingEdges();
+    }
+    
+    ShapeRef *newShape = new ShapeRef(pid, *newPoly);
+
+    // o  Check all visibility edges to see if this one shape
+    //    blocks them.
+    if (!(PartialFeedback && PartialTime))
+    {
+        newBlockingShape(newPoly, pid);
+    }
+
+    // o  Calculate visibility for the new vertices.
+    if (UseLeesAlgorithm)
+    {
+        shapeVisSweep(newShape);
+    }
+    else
+    {
+        shapeVis(newShape);
+    }
+    callbackAllInvalidConnectors();
+
+    return newShape;
+}
+
+
+}
+
diff --git a/src/libavoid/incremental.h b/src/libavoid/incremental.h
new file mode 100644
index 000000000..50ef8f7dc
--- /dev/null
+++ b/src/libavoid/incremental.h
@@ -0,0 +1,39 @@
+/*
+ * vim: ts=4 sw=4 et tw=0 wm=0
+ *
+ * libavoid - Fast, Incremental, Object-avoiding Line Router
+ * Copyright (C) 2004-2005  Michael Wybrow <mjwybrow@users.sourceforge.net>
+ *
+ * This library is free software; you can redistribute it and/or
+ * modify it under the terms of the GNU Lesser General Public
+ * License as published by the Free Software Foundation; either
+ * version 2.1 of the License, or (at your option) any later version.
+ *
+ * This library is distributed in the hope that it will be useful,
+ * but WITHOUT ANY WARRANTY; without even the implied warranty of
+ * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU
+ * Lesser General Public License for more details.
+ *
+ * You should have received a copy of the GNU Lesser General Public
+ * License along with this library; if not, write to the Free Software
+ * Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA  02111-1307  USA
+ * 
+*/
+
+
+#ifndef AVOID_INCREMENTAL_H
+#define AVOID_INCREMENTAL_H
+
+#include "libavoid/shape.h"
+
+
+namespace Avoid {
+
+extern void addShape(ShapeRef *shape);
+extern void delShape(ShapeRef *shape);
+extern ShapeRef *moveShape(ShapeRef *oldShape, Polygn *newPoly);
+
+}
+
+
+#endif
diff --git a/src/libavoid/libavoid.h b/src/libavoid/libavoid.h
new file mode 100644
index 000000000..0b6c7a819
--- /dev/null
+++ b/src/libavoid/libavoid.h
@@ -0,0 +1,40 @@
+/*
+ * vim: ts=4 sw=4 et tw=0 wm=0
+ *
+ * libavoid - Fast, Incremental, Object-avoiding Line Router
+ * Copyright (C) 2004-2005  Michael Wybrow <mjwybrow@users.sourceforge.net>
+ *
+ * This library is free software; you can redistribute it and/or
+ * modify it under the terms of the GNU Lesser General Public
+ * License as published by the Free Software Foundation; either
+ * version 2.1 of the License, or (at your option) any later version.
+ *
+ * This library is distributed in the hope that it will be useful,
+ * but WITHOUT ANY WARRANTY; without even the implied warranty of
+ * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU
+ * Lesser General Public License for more details.
+ *
+ * You should have received a copy of the GNU Lesser General Public
+ * License along with this library; if not, write to the Free Software
+ * Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA  02111-1307  USA
+ * 
+*/
+
+#ifndef AVOID_LIBAVOID_H
+#define AVOID_LIBAVOID_H
+
+#include "libavoid/geomtypes.h"
+#include "libavoid/polyutil.h"
+#include "libavoid/connector.h"
+#include "libavoid/graph.h"
+#include "libavoid/debug.h"
+#include "libavoid/timer.h"
+#include "libavoid/makepath.h"
+#include "libavoid/vertices.h"
+#include "libavoid/visibility.h"
+#include "libavoid/static.h"
+#include "libavoid/incremental.h"
+
+#endif
+
+
diff --git a/src/libavoid/makefile.in b/src/libavoid/makefile.in
new file mode 100644
index 000000000..e651e0ef1
--- /dev/null
+++ b/src/libavoid/makefile.in
@@ -0,0 +1,17 @@
+# Convenience stub makefile to call the real Makefile.
+
+@SET_MAKE@
+
+# Explicit so that it's the default rule.
+all:
+	cd .. && $(MAKE) libavoid/all
+
+clean %.a %.o:
+	cd .. && $(MAKE) libavoid/$@
+
+.PHONY: all clean
+
+OBJEXT = @OBJEXT@
+
+.SUFFIXES:
+.SUFFIXES: .a .$(OBJEXT)
diff --git a/src/libavoid/makepath.cpp b/src/libavoid/makepath.cpp
new file mode 100644
index 000000000..776ffd307
--- /dev/null
+++ b/src/libavoid/makepath.cpp
@@ -0,0 +1,462 @@
+/*
+ * vim: ts=4 sw=4 et tw=0 wm=0
+ *
+ * libavoid - Fast, Incremental, Object-avoiding Line Router
+ * Copyright (C) 2004-2005  Michael Wybrow <mjwybrow@users.sourceforge.net>
+ *
+ * --------------------------------------------------------------------
+ * The dijkstraPath function is based on code published and described
+ * in "Algorithms in C" (Second Edition), 1990, by Robert Sedgewick.
+ * --------------------------------------------------------------------
+ *
+ * This library is free software; you can redistribute it and/or
+ * modify it under the terms of the GNU Lesser General Public
+ * License as published by the Free Software Foundation; either
+ * version 2.1 of the License, or (at your option) any later version.
+ *
+ * This library is distributed in the hope that it will be useful,
+ * but WITHOUT ANY WARRANTY; without even the implied warranty of
+ * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU
+ * Lesser General Public License for more details.
+ *
+ * You should have received a copy of the GNU Lesser General Public
+ * License along with this library; if not, write to the Free Software
+ * Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA  02111-1307  USA
+ *
+*/
+
+#include "libavoid/connector.h"
+#include "libavoid/graph.h"
+#include <vector>
+#include <math.h>
+
+namespace Avoid {
+
+
+double segmt_penalty = 0;
+double angle_penalty = 0;
+
+
+static double Dot(const Point& l, const Point& r)
+{
+    return (l.x * r.x) + (l.y * r.y);
+}
+
+static double CrossLength(const Point& l, const Point& r)
+{
+    return (l.x * r.y) - (l.y * r.x);
+}
+
+
+// Return the angle between the two line segments made by the
+// points p1--p2 and p2--p3.  Return value is in radians.
+//
+static double angleBetween(const Point& p1, const Point& p2, const Point& p3)
+{
+    Point v1 = { p1.x - p2.x, p1.y - p2.y };
+    Point v2 = { p3.x - p2.x, p3.y - p2.y };
+
+    return fabs(atan2(CrossLength(v1, v2), Dot(v1, v2)));
+}
+
+
+// Given the two points for a new segment of a path (inf2 & inf3)
+// as well as the distance between these points (dist), as well as
+// possibly the previous point (inf1) [from inf1--inf2], return a
+// cost associated with this route.
+//
+double cost(const double dist, VertInf *inf1,
+        VertInf *inf2, VertInf *inf3)
+{
+    double result = dist;
+
+    if (inf2->pathNext != NULL)
+    {
+        // This is not the first segment, so there is a bend
+        // between it and the last one in the existing path.
+        if ((angle_penalty > 0) || (segmt_penalty > 0))
+        {
+            Point p1 = inf1->point;
+            Point p2 = inf2->point;
+            Point p3 = inf3->point;
+
+            double rad = M_PI - angleBetween(p1, p2, p3);
+
+            // Make `rad' between 0--10 then take its log so small
+            // angles are not penalised as much as large ones.
+            result += (angle_penalty * log((rad * 10 / M_PI) + 1));
+
+            // Don't penalise as an extra segment if there is no turn.
+            if (rad > 0.0005)
+            {
+                result += segmt_penalty;
+            }
+        }
+
+    }
+
+    return result;
+}
+
+
+// Returns the best path from src to tar using the cost function.
+//
+// The path is worked out via Dijkstra's algorithm, and is encoded via
+// pathNext links in each of the VerInfs along the path.
+//
+// Based on the code of 'matrixpfs'.
+//
+static void dijkstraPath(VertInf *src, VertInf *tar)
+{
+    double unseen = (double) INT_MAX;
+
+    // initialize arrays
+    VertInf *finish = vertices.end();
+    for (VertInf *t = vertices.connsBegin(); t != finish; t = t->lstNext)
+    {
+        t->pathNext = NULL;
+        t->pathDist = -unseen;
+    }
+
+    VertInf *min = src;
+    while (min != tar)
+    {
+        VertInf *k = min;
+        min = NULL;
+
+        k->pathDist *= -1;
+        if (k->pathDist == unseen)
+        {
+            k->pathDist = 0;
+        }
+
+        EdgeInfList& visList = k->visList;
+        EdgeInfList::iterator finish = visList.end();
+        for (EdgeInfList::iterator edge = visList.begin(); edge != finish;
+                ++edge)
+        {
+            VertInf *t = (*edge)->otherVert(k);
+            VertID tID = t->id;
+
+            // Only check shape verticies, or endpoints.
+            if ((t->pathDist < 0) &&
+                    ((tID.objID == src->id.objID) || tID.isShape))
+            {
+                double kt_dist = (*edge)->getDist();
+                double priority = k->pathDist +
+                        cost(kt_dist, k->pathNext, k, t);
+
+                if ((kt_dist != 0) && (t->pathDist < -priority))
+                {
+                    t->pathDist = -priority;
+                    t->pathNext = k;
+                }
+                if ((min == NULL) || (t->pathDist > min->pathDist))
+                {
+                    min = t;
+                }
+            }
+        }
+        EdgeInfList& invisList = k->invisList;
+        finish = invisList.end();
+        for (EdgeInfList::iterator edge = invisList.begin(); edge != finish;
+                ++edge)
+        {
+            VertInf *t = (*edge)->otherVert(k);
+            VertID tID = t->id;
+
+            // Only check shape verticies, or endpoints.
+            if ((t->pathDist < 0) &&
+                    ((tID.objID == src->id.objID) || tID.isShape > 0))
+            {
+                if ((min == NULL) || (t->pathDist > min->pathDist))
+                {
+                    min = t;
+                }
+            }
+        }
+    }
+}
+
+
+class ANode
+{
+    public:
+        VertInf* inf;
+        double g;        // Gone
+        double h;        // Heuristic
+        double f;        // Formula f = g + h
+        VertInf *pp;
+
+        ANode(VertInf *vinf)
+            : inf(vinf)
+            , g(0)
+            , h(0)
+            , f(0)
+            , pp(NULL)
+        {
+        }
+        ANode()
+            : inf(NULL)
+            , g(0)
+            , h(0)
+            , f(0)
+            , pp(NULL)
+        {
+        }
+};
+
+bool operator<(const ANode &a, const ANode &b)
+{
+    return a.f < b.f;
+}
+
+
+bool operator>(const ANode &a, const ANode &b)
+{
+    return a.f > b.f;
+}
+
+
+// Returns the best path from src to tar using the cost function.
+//
+// The path is worked out using the aStar algorithm, and is encoded via
+// pathNext links in each of the VerInfs along the path.
+//
+// The aStar STL code is based on public domain code available on the
+// internet.
+//
+static void aStarPath(VertInf *src, VertInf *tar)
+{
+    std::vector<ANode> PENDING;     // STL Vectors chosen because of rapid
+    std::vector<ANode> DONE;        // insertions/deletions at back,
+    ANode Node, BestNode;           // Temporary Node and BestNode
+    bool bNodeFound = false;        // Flag if node is found in container
+
+    tar->pathNext = NULL;
+
+    // Create the start node
+    Node = ANode(src);
+    Node.g = 0;
+    Node.h = dist(Node.inf->point, tar->point);
+    Node.f = Node.g + Node.h;
+    // Set a null parent, so cost function knows this is the first segment.
+    Node.pp = NULL;
+
+    // Populate the PENDING container with the first location
+    PENDING.push_back(Node);
+    // Create a heap from PENDING for sorting
+    using std::make_heap; using std::push_heap; using std::pop_heap;
+    make_heap( PENDING.begin(), PENDING.end() );
+
+    while (!PENDING.empty())
+    {
+        // Ascending sort based on overloaded operators below
+        sort_heap(PENDING.begin(), PENDING.end());
+
+        // Set the Node with lowest f value to BESTNODE
+        BestNode = PENDING.front();
+
+        // Pop off the heap.  Actually this moves the
+        // far left value to the far right.  The node
+        // is not actually removed since the pop is to
+        // the heap and not the container.
+        pop_heap(PENDING.begin(), PENDING.end());
+
+
+        // Remove node from right (the value we pop_heap'd)
+        PENDING.pop_back();
+
+        // Push the BestNode onto DONE
+        BestNode.inf->pathNext = BestNode.pp;
+        DONE.push_back(BestNode);
+
+#if 0
+        printf("Considering... ");
+        BestNode.ID->print(stdout);
+        printf(" - g: %3.1f h: %3.1f f: %3.1f back: ", BestNode.g, BestNode.h,
+                BestNode.f);
+        BestNode.pp.print(stdout);
+        printf("\n");
+#endif
+
+        // If at destination, break and create path below
+        if (BestNode.inf == tar)
+        {
+            //bPathFound = true; // arrived at destination...
+            break;
+        }
+
+        // Check adjacent points in graph
+        EdgeInfList& visList = BestNode.inf->visList;
+        EdgeInfList::iterator finish = visList.end();
+        for (EdgeInfList::iterator edge = visList.begin(); edge != finish;
+                ++edge)
+        {
+            Node.inf = (*edge)->otherVert(BestNode.inf);
+
+            // Only check shape verticies, or the tar endpoint.
+            if (!(Node.inf->id.isShape) && (Node.inf != tar))
+            {
+                continue;
+            }
+
+            double edgeDist = (*edge)->getDist();
+
+            if (edgeDist == 0)
+            {
+                continue;
+            }
+
+            VertInf *prevInf = BestNode.inf->pathNext;
+
+            Node.g = BestNode.g + cost(edgeDist, prevInf,
+                    BestNode.inf, Node.inf);
+
+            // Calculate the Heuristic.
+            Node.h = dist(Node.inf->point, tar->point);
+
+            // The A* formula
+            Node.f = Node.g + Node.h;
+            // Point parent to last BestNode (pushed onto DONE)
+            Node.pp = BestNode.inf;
+
+            bNodeFound = false;
+
+            // Check to see if already on PENDING
+            for (unsigned int i = 0; i < PENDING.size(); i++)
+            {
+                if (Node.inf == PENDING.at(i).inf)
+                {   // If already on PENDING
+                    if (Node.g < PENDING.at(i).g)
+                    {
+                        PENDING.at(i).g = Node.g;
+                        PENDING.at(i).f = Node.g + PENDING.at(i).h;
+                        PENDING.at(i).pp = Node.pp;
+                    }
+                    bNodeFound = true;
+                    break;
+                }
+            }
+            if (!bNodeFound ) // If Node NOT found on PENDING
+            {
+                // Check to see if already on DONE
+                for (unsigned int i = 0; i < DONE.size(); i++)
+                {
+                    if (Node.inf == DONE.at(i).inf)
+                    {
+                        // If on DONE, Which has lower gone?
+                        if (Node.g < DONE.at(i).g)
+                        {
+                            DONE.at(i).g = Node.g;
+                            DONE.at(i).f = Node.g + DONE.at(i).h;
+                            DONE.at(i).pp = Node.pp;
+                            DONE.at(i).inf->pathNext = Node.pp;
+                        }
+                        bNodeFound = true;
+                        break;
+                    }
+                }
+            }
+
+            if (!bNodeFound ) // If Node NOT found on PENDING or DONE
+            {
+                // Push NewNode onto PENDING
+                PENDING.push_back(Node);
+                // Push NewNode onto heap
+                push_heap( PENDING.begin(), PENDING.end() );
+                // Re-Assert heap, or will be short by one
+                make_heap( PENDING.begin(), PENDING.end() );
+
+#if 0
+                // Display PENDING and DONE containers (For Debugging)
+                cout << "PENDING:   ";
+                for (int i = 0; i < PENDING.size(); i++)
+                {
+                    cout << PENDING.at(i).x << "," << PENDING.at(i).y << ",";
+                    cout << PENDING.at(i).g << "," << PENDING.at(i).h << "  ";
+                }
+                cout << endl;
+                cout << "DONE:   ";
+                for (int i = 0; i < DONE.size(); i++)
+                {
+                    cout << DONE.at(i).x << "," << DONE.at(i).y << ",";
+                    cout << DONE.at(i).g << "," << DONE.at(i).h << "  ";
+                }
+                cout << endl << endl;
+                int ch = _getch();
+#endif
+            }
+        }
+    }
+}
+
+
+// Returns the best path for the connector referred to by lineRef.
+//
+// The path encoded in the pathNext links in each of the VerInfs
+// backwards along the path, from the tar back to the source.
+//
+void makePath(ConnRef *lineRef, bool *flag)
+{
+    VertInf *src = lineRef->src();
+    VertInf *tar = lineRef->dst();
+
+    // TODO: Could be more efficient here.
+    EdgeInf *directEdge = EdgeInf::existingEdge(src, tar);
+    if (!IncludeEndpoints && directVis(src, tar))
+    {
+        Point p = src->point;
+        Point q = tar->point;
+
+        assert(directEdge == NULL);
+
+        directEdge = new EdgeInf(src, tar);
+        tar->pathNext = src;
+        directEdge->setDist(dist(p, q));
+        directEdge->addConn(flag);
+
+        return;
+    }
+    else if (IncludeEndpoints && directEdge && (directEdge->getDist() > 0))
+    {
+        tar->pathNext = src;
+        directEdge->addConn(flag);
+    }
+    else
+    {
+        // Mark the path endpoints as not being able to see
+        // each other.  This is true if we are here.
+        if (!IncludeEndpoints && InvisibilityGrph)
+        {
+            directEdge->addBlocker(0);
+        }
+
+        if (UseAStarSearch)
+        {
+            aStarPath(src, tar);
+        }
+        else
+        {
+            dijkstraPath(src, tar);
+        }
+
+#if 0
+        PointMap::iterator t;
+        for (VertInf *t = vertices.connsBegin(); t != vertices.end();
+                t = t->lstNext)
+        {
+
+            t->id.print();
+            printf(" -> ");
+            t->pathNext->id.print();
+            printf("\n");
+        }
+#endif
+    }
+}
+
+
+}
+
+
diff --git a/src/libavoid/makepath.h b/src/libavoid/makepath.h
new file mode 100644
index 000000000..5ab21b993
--- /dev/null
+++ b/src/libavoid/makepath.h
@@ -0,0 +1,42 @@
+/*
+ * vim: ts=4 sw=4 et tw=0 wm=0
+ *
+ * libavoid - Fast, Incremental, Object-avoiding Line Router
+ * Copyright (C) 2004-2005  Michael Wybrow <mjwybrow@users.sourceforge.net>
+ *
+ * This library is free software; you can redistribute it and/or
+ * modify it under the terms of the GNU Lesser General Public
+ * License as published by the Free Software Foundation; either
+ * version 2.1 of the License, or (at your option) any later version.
+ *
+ * This library is distributed in the hope that it will be useful,
+ * but WITHOUT ANY WARRANTY; without even the implied warranty of
+ * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU
+ * Lesser General Public License for more details.
+ *
+ * You should have received a copy of the GNU Lesser General Public
+ * License along with this library; if not, write to the Free Software
+ * Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA  02111-1307  USA
+ * 
+*/
+
+#ifndef AVOID_MAKEPATH_H
+#define AVOID_MAKEPATH_H
+
+#include "libavoid/connector.h"
+
+namespace Avoid {
+
+
+extern double segmt_penalty;
+extern double angle_penalty;
+
+extern void makePath(ConnRef *lineRef, bool *flag);
+
+
+}
+
+
+#endif
+
+
diff --git a/src/libavoid/polyutil.cpp b/src/libavoid/polyutil.cpp
new file mode 100644
index 000000000..6ece50e63
--- /dev/null
+++ b/src/libavoid/polyutil.cpp
@@ -0,0 +1,86 @@
+/*
+ * vim: ts=4 sw=4 et tw=0 wm=0
+ *
+ * libavoid - Fast, Incremental, Object-avoiding Line Router
+ * Copyright (C) 2004-2005  Michael Wybrow <mjwybrow@users.sourceforge.net>
+ *
+ * This library is free software; you can redistribute it and/or
+ * modify it under the terms of the GNU Lesser General Public
+ * License as published by the Free Software Foundation; either
+ * version 2.1 of the License, or (at your option) any later version.
+ *
+ * This library is distributed in the hope that it will be useful,
+ * but WITHOUT ANY WARRANTY; without even the implied warranty of
+ * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU
+ * Lesser General Public License for more details.
+ *
+ * You should have received a copy of the GNU Lesser General Public
+ * License along with this library; if not, write to the Free Software
+ * Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA  02111-1307  USA
+ * 
+*/
+
+
+#include "libavoid/shape.h"
+
+namespace Avoid {
+
+
+Polygn newPoly(int size)
+{
+    Polygn newpoly;
+
+    newpoly.pn = size;
+    newpoly.ps = (Point *) calloc(size, sizeof(Point));
+    if (!newpoly.ps)
+    {
+        fprintf(stderr,
+                "Error: Unable to allocate Point array in Avoid::newPoly\n");
+        abort();
+    }
+    return newpoly;
+}
+
+
+Polygn copyPoly(Polygn poly)
+{
+    Polygn newpoly = newPoly(poly.pn);
+
+    newpoly.id = poly.id;
+    for (int i = 0; i < poly.pn; i++)
+    {
+        newpoly.ps[i] = poly.ps[i];
+    }
+    return newpoly;
+}
+
+
+Polygn copyPoly(ShapeRef *shape)
+{
+    Polygn poly = shape->poly();
+    Polygn newpoly = newPoly(poly.pn);
+
+    newpoly.id = poly.id;
+    for (int i = 0; i < poly.pn; i++)
+    {
+        newpoly.ps[i] = poly.ps[i];
+    }
+    return newpoly;
+}
+
+
+void freePoly(Polygn& poly)
+{
+    std::free(poly.ps);
+}
+
+
+void freePtrPoly(Polygn *poly)
+{
+    std::free(poly->ps);
+    std::free(poly);
+}
+
+
+}
+
diff --git a/src/libavoid/polyutil.h b/src/libavoid/polyutil.h
new file mode 100644
index 000000000..456e190fb
--- /dev/null
+++ b/src/libavoid/polyutil.h
@@ -0,0 +1,41 @@
+/*
+ * vim: ts=4 sw=4 et tw=0 wm=0
+ *
+ * libavoid - Fast, Incremental, Object-avoiding Line Router
+ * Copyright (C) 2004-2005  Michael Wybrow <mjwybrow@users.sourceforge.net>
+ *
+ * This library is free software; you can redistribute it and/or
+ * modify it under the terms of the GNU Lesser General Public
+ * License as published by the Free Software Foundation; either
+ * version 2.1 of the License, or (at your option) any later version.
+ *
+ * This library is distributed in the hope that it will be useful,
+ * but WITHOUT ANY WARRANTY; without even the implied warranty of
+ * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU
+ * Lesser General Public License for more details.
+ *
+ * You should have received a copy of the GNU Lesser General Public
+ * License along with this library; if not, write to the Free Software
+ * Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA  02111-1307  USA
+ * 
+*/
+
+#include "libavoid/geometry.h"
+#include "libavoid/shape.h"
+
+#ifndef AVOID_POLYUTIL_H
+#define AVOID_POLYUTIL_H
+
+namespace Avoid {
+
+
+extern Polygn newPoly(int size);
+extern Polygn copyPoly(Polygn);
+extern Polygn copyPoly(ShapeRef *shape);
+extern void freePoly(Polygn&);
+extern void freePtrPoly(Polygn *argpoly);
+
+
+}
+
+#endif
diff --git a/src/libavoid/shape.cpp b/src/libavoid/shape.cpp
new file mode 100644
index 000000000..b08e75f3e
--- /dev/null
+++ b/src/libavoid/shape.cpp
@@ -0,0 +1,176 @@
+/*
+ * vim: ts=4 sw=4 et tw=0 wm=0
+ *
+ * libavoid - Fast, Incremental, Object-avoiding Line Router
+ * Copyright (C) 2004-2005  Michael Wybrow <mjwybrow@users.sourceforge.net>
+ *
+ * This library is free software; you can redistribute it and/or
+ * modify it under the terms of the GNU Lesser General Public
+ * License as published by the Free Software Foundation; either
+ * version 2.1 of the License, or (at your option) any later version.
+ *
+ * This library is distributed in the hope that it will be useful,
+ * but WITHOUT ANY WARRANTY; without even the implied warranty of
+ * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU
+ * Lesser General Public License for more details.
+ *
+ * You should have received a copy of the GNU Lesser General Public
+ * License along with this library; if not, write to the Free Software
+ * Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA  02111-1307  USA
+ * 
+*/
+
+
+#include "libavoid/graph.h"  // For alertConns
+#include "libavoid/polyutil.h"
+
+
+namespace Avoid {
+
+
+ShapeRefList shapeRefs;
+
+
+ShapeRef::ShapeRef(uint id, Polygn& ply)
+    : _id(id)
+    , _poly(copyPoly(ply))
+    , _active(false)
+    , _firstVert(NULL)
+    , _lastVert(NULL)
+{
+    bool isShape = true;
+    VertID i = VertID(id, isShape, 0);
+    
+    VertInf *last = NULL;
+    VertInf *node = NULL;
+    for (int pt_i = 0; pt_i < _poly.pn; pt_i++)
+    {
+        node = new VertInf(i, _poly.ps[pt_i]);
+
+        if (!_firstVert)
+        {
+            _firstVert = node;
+        }
+        else
+        {
+            node->shPrev = last;
+            last->shNext = node;
+            //node->lstPrev = last;
+            //last->lstNext = node;
+        }
+        vertices.addVertex(node);
+        
+        last = node;
+        i++;
+        // Increase total vertices count ++;
+    }
+    _lastVert = node;
+    
+    _lastVert->shNext = _firstVert;
+    _firstVert->shPrev = _lastVert;
+    
+    // Increase total shape count ++;
+    makeActive();
+}
+
+
+ShapeRef::~ShapeRef()
+{
+    assert(_firstVert != NULL);
+    
+    VertInf *it = _firstVert;
+    do
+    {
+        VertInf *tmp = it;
+        it = it->shNext;
+
+        // XXX: This could possibly be done less
+        //      safely but faster, all at once.
+        vertices.removeVertex(tmp);
+        delete tmp;
+    }
+    while (it != _firstVert);
+    _firstVert = _lastVert = NULL;
+
+    freePoly(_poly);
+    
+    makeInactive();
+}
+
+
+void ShapeRef::makeActive(void)
+{
+    assert(!_active);
+    
+    // Add to connRefs list.
+    _pos = shapeRefs.insert(shapeRefs.begin(), this);
+    _active = true;
+}
+
+
+void ShapeRef::makeInactive(void)
+{
+    assert(_active);
+    
+    // Remove from connRefs list.
+    shapeRefs.erase(_pos);
+    _active = false;
+}
+    
+
+VertInf *ShapeRef::firstVert(void)
+{
+    return _firstVert;
+}
+
+
+VertInf *ShapeRef::lastVert(void)
+{
+    return _lastVert;
+}
+
+
+uint ShapeRef::id(void)
+{
+    return _id;
+}
+
+
+Polygn ShapeRef::poly(void)
+{
+    return _poly;
+}
+
+
+void ShapeRef::removeFromGraph(void)
+{
+    for (VertInf *iter = firstVert(); iter != lastVert()->lstNext; )
+    {
+        VertInf *tmp = iter;
+        iter = iter->lstNext;
+        
+        // For each vertex.
+        EdgeInfList& visList = tmp->visList;
+        EdgeInfList::iterator finish = visList.end();
+        EdgeInfList::iterator edge;
+        while ((edge = visList.begin()) != finish)
+        {
+            // Remove each visibility edge
+            (*edge)->alertConns();
+            delete (*edge);
+        }
+
+        EdgeInfList& invisList = tmp->invisList;
+        finish = invisList.end();
+        while ((edge = invisList.begin()) != finish)
+        {
+            // Remove each invisibility edge
+            delete (*edge);
+        }
+    }
+}
+
+
+}
+
+
diff --git a/src/libavoid/shape.h b/src/libavoid/shape.h
new file mode 100644
index 000000000..acdb36983
--- /dev/null
+++ b/src/libavoid/shape.h
@@ -0,0 +1,73 @@
+/*
+ * vim: ts=4 sw=4 et tw=0 wm=0
+ *
+ * libavoid - Fast, Incremental, Object-avoiding Line Router
+ * Copyright (C) 2004-2005  Michael Wybrow <mjwybrow@users.sourceforge.net>
+ *
+ * This library is free software; you can redistribute it and/or
+ * modify it under the terms of the GNU Lesser General Public
+ * License as published by the Free Software Foundation; either
+ * version 2.1 of the License, or (at your option) any later version.
+ *
+ * This library is distributed in the hope that it will be useful,
+ * but WITHOUT ANY WARRANTY; without even the implied warranty of
+ * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU
+ * Lesser General Public License for more details.
+ *
+ * You should have received a copy of the GNU Lesser General Public
+ * License along with this library; if not, write to the Free Software
+ * Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA  02111-1307  USA
+ * 
+*/
+
+#ifndef AVOID_SHAPE_H
+#define AVOID_SHAPE_H
+
+#include "libavoid/geometry.h"
+#include <list>
+
+
+namespace Avoid {
+
+typedef unsigned int uint;
+    
+class ShapeRef;
+class VertInf;
+
+typedef std::list<ShapeRef *> ShapeRefList;
+
+    
+class ShapeRef
+{
+    public:
+        ShapeRef(uint id, Polygn& poly);
+        ~ShapeRef();
+        VertInf *firstVert(void);
+        VertInf *lastVert(void);
+        uint id(void);
+        Polygn poly(void);
+        
+        void makeActive(void);
+        void makeInactive(void);
+
+        void removeFromGraph(void);
+        
+    private:
+        uint _id;
+        Polygn _poly;
+        bool _active;
+        ShapeRefList::iterator _pos;
+        VertInf *_firstVert;
+        VertInf *_lastVert;
+};
+
+
+extern ShapeRefList shapeRefs;
+
+
+}
+
+
+#endif
+
+
diff --git a/src/libavoid/static.cpp b/src/libavoid/static.cpp
new file mode 100644
index 000000000..d424a2e7f
--- /dev/null
+++ b/src/libavoid/static.cpp
@@ -0,0 +1,76 @@
+/*
+ * vim: ts=4 sw=4 et tw=0 wm=0
+ *
+ * libavoid - Fast, Incremental, Object-avoiding Line Router
+ * Copyright (C) 2004-2005  Michael Wybrow <mjwybrow@users.sourceforge.net>
+ *
+ * This library is free software; you can redistribute it and/or
+ * modify it under the terms of the GNU Lesser General Public
+ * License as published by the Free Software Foundation; either
+ * version 2.1 of the License, or (at your option) any later version.
+ *
+ * This library is distributed in the hope that it will be useful,
+ * but WITHOUT ANY WARRANTY; without even the implied warranty of
+ * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU
+ * Lesser General Public License for more details.
+ *
+ * You should have received a copy of the GNU Lesser General Public
+ * License along with this library; if not, write to the Free Software
+ * Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA  02111-1307  USA
+ * 
+*/
+
+#include <cassert>
+#include "libavoid/connector.h"
+#include "libavoid/visibility.h"
+
+namespace Avoid {
+
+
+// This should only be used for the static algorithm.
+//
+// XXX: If to set up the vis graph for incremental it would need 
+//      the shapeRef ppinters in obs.
+//
+void CreateVisGraph(Polygn **obs, int n_obs)
+{
+    for (int poly_i = 0; poly_i < n_obs; poly_i++)
+    {
+        uint id = obs[poly_i]->id;
+        
+        new ShapeRef(id, *(obs[poly_i]));
+    }
+    computeCompleteVis();
+}
+
+
+void DestroyVisGraph(void)
+{
+    ShapeRefList::iterator sFinish = shapeRefs.end();
+    ShapeRefList::iterator sCurr;
+    
+    while ((sCurr = shapeRefs.begin()) != sFinish)
+    {
+        ShapeRef *shape = (*sCurr);
+
+        shape->removeFromGraph();
+        delete shape;
+    }
+    
+    ConnRefList::iterator cFinish = connRefs.end();
+    ConnRefList::iterator cCurr;
+    
+    while ((cCurr = connRefs.begin())!= cFinish)
+    {
+        ConnRef *conn = (*cCurr);
+
+        conn->removeFromGraph();
+        conn->unInitialise();
+    }
+
+    assert(vertices.connsBegin() == NULL);
+}
+
+
+}
+
diff --git a/src/libavoid/static.h b/src/libavoid/static.h
new file mode 100644
index 000000000..c02c6be2f
--- /dev/null
+++ b/src/libavoid/static.h
@@ -0,0 +1,38 @@
+/*
+ * vim: ts=4 sw=4 et tw=0 wm=0
+ *
+ * libavoid - Fast, Incremental, Object-avoiding Line Router
+ * Copyright (C) 2004-2005  Michael Wybrow <mjwybrow@users.sourceforge.net>
+ *
+ * This library is free software; you can redistribute it and/or
+ * modify it under the terms of the GNU Lesser General Public
+ * License as published by the Free Software Foundation; either
+ * version 2.1 of the License, or (at your option) any later version.
+ *
+ * This library is distributed in the hope that it will be useful,
+ * but WITHOUT ANY WARRANTY; without even the implied warranty of
+ * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU
+ * Lesser General Public License for more details.
+ *
+ * You should have received a copy of the GNU Lesser General Public
+ * License along with this library; if not, write to the Free Software
+ * Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA  02111-1307  USA
+ * 
+*/
+
+
+#ifndef AVOID_STATIC_H
+#define AVOID_STATIC_H
+
+#include "libavoid/geomtypes.h"
+
+
+namespace Avoid {
+
+extern void CreateVisGraph(Polygn **obstacles, int n_obstacles);
+extern void DestroyVisGraph(void);
+
+}
+
+
+#endif
diff --git a/src/libavoid/timer.cpp b/src/libavoid/timer.cpp
new file mode 100644
index 000000000..7e930d011
--- /dev/null
+++ b/src/libavoid/timer.cpp
@@ -0,0 +1,168 @@
+/*
+ * vim: ts=4 sw=4 et tw=0 wm=0
+ *
+ * libavoid - Fast, Incremental, Object-avoiding Line Router
+ * Copyright (C) 2004-2005  Michael Wybrow <mjwybrow@users.sourceforge.net>
+ *
+ * This library is free software; you can redistribute it and/or
+ * modify it under the terms of the GNU Lesser General Public
+ * License as published by the Free Software Foundation; either
+ * version 2.1 of the License, or (at your option) any later version.
+ *
+ * This library is distributed in the hope that it will be useful,
+ * but WITHOUT ANY WARRANTY; without even the implied warranty of
+ * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU
+ * Lesser General Public License for more details.
+ *
+ * You should have received a copy of the GNU Lesser General Public
+ * License along with this library; if not, write to the Free Software
+ * Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA  02111-1307  USA
+ * 
+*/
+
+#include <cstdio>
+#include <cstdlib>
+#include <cassert>
+using std::abort;
+#include <climits>
+
+#include "libavoid/timer.h"
+
+namespace Avoid {
+
+
+Timer timers = Timer();
+
+
+Timer::Timer()
+{
+    Reset();
+}
+
+
+void Timer::Reset(void)
+{
+    for (int i = 0; i < tmCount; i++)
+    {
+        //tTotal[i] = 0;
+        cTotal[i] = cPath[i] = 0;
+        cTally[i] = cPathTally[i] = 0;
+        cMax[i] = cPathMax[i] = 0;
+    }
+    running = false;
+    count  = 0;
+    type = lasttype = tmNon;
+}
+
+
+void Timer::Register(const int t, const bool start)
+{
+    assert(t != tmNon);
+
+    if (type == tmNon)
+    {
+        type = t;
+    }
+    else
+    {
+        type = tmSev;
+    }
+
+    if (start)
+    {
+        Start();
+    }
+}
+
+void Timer::Start(void)
+{
+    if (running)
+    {
+        fprintf(stderr, "ERROR: Timer already running in Timer::Start()\n");
+        abort();
+    }
+    cStart[type] = clock();  // CPU time
+    running = true;
+}
+
+
+void Timer::Stop(void)
+{
+    if (!running)
+    {
+        fprintf(stderr, "ERROR: Timer not running in Timer::Stop()\n");
+        abort();
+    }
+    clock_t cStop = clock();      // CPU time
+    running = false;
+
+    bigclock_t cDiff;
+    if (cStop < cStart[type])
+    {
+        // Uh-oh, the clock value has wrapped around.
+        //
+        bigclock_t realStop = ((bigclock_t) cStop) + ULONG_MAX + 1;
+        cDiff = realStop - cStart[type];
+    }
+    else
+    {
+        cDiff = cStop - cStart[type];
+    }
+    
+    if (cDiff > LONG_MAX)
+    {
+        fprintf(stderr, "Error: cDiff overflow in Timer:Stop()\n");
+        abort();
+    }
+
+    if (type == tmPth)
+    {
+        cPath[lasttype] += cDiff;
+        cPathTally[lasttype]++;
+        if (((clock_t) cDiff) > cPathMax[lasttype])
+        {
+            cPathMax[lasttype] = (clock_t) cDiff;
+        }
+    }
+    else
+    {
+        cTotal[type] += cDiff;
+        cTally[type]++;
+        if (((clock_t) cDiff) > cMax[type])
+        {
+            cMax[type] = (clock_t) cDiff;
+        }
+        lasttype = type;
+    }
+
+    type = tmNon;
+}
+
+
+void Timer::PrintAll(void)
+{
+    for (int i = 0; i < tmCount; i++)
+    {
+        Print(i);
+    }
+}
+
+
+#define toMsec(tot) ((bigclock_t) ((tot) / (((double) CLOCKS_PER_SEC) / 1000)))
+#define toAvg(tot, cnt) ((((cnt) > 0) ? ((long double) (tot)) / (cnt) : 0))
+
+void Timer::Print(const int t)
+{
+   bigclock_t avg = toMsec(toAvg(cTotal[t], cTally[t]));
+   bigclock_t pind = toMsec(toAvg(cPath[t], cPathTally[t]));
+   bigclock_t pavg = toMsec(toAvg(cPath[t], cTally[t]));
+   double max = toMsec(cMax[t]); 
+   double pmax = toMsec(cPathMax[t]);
+   printf("\t%lld %d %lld %.0f %lld %d %lld %.0f %lld\n",
+           cTotal[t], cTally[t], avg, max,
+           cPath[t], cPathTally[t], pavg, pmax, pind);
+}
+
+
+}
+
diff --git a/src/libavoid/timer.h b/src/libavoid/timer.h
new file mode 100644
index 000000000..9446ecc51
--- /dev/null
+++ b/src/libavoid/timer.h
@@ -0,0 +1,92 @@
+/*
+ * vim: ts=4 sw=4 et tw=0 wm=0
+ *
+ * libavoid - Fast, Incremental, Object-avoiding Line Router
+ * Copyright (C) 2004-2005  Michael Wybrow <mjwybrow@users.sourceforge.net>
+ *
+ * This library is free software; you can redistribute it and/or
+ * modify it under the terms of the GNU Lesser General Public
+ * License as published by the Free Software Foundation; either
+ * version 2.1 of the License, or (at your option) any later version.
+ *
+ * This library is distributed in the hope that it will be useful,
+ * but WITHOUT ANY WARRANTY; without even the implied warranty of
+ * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU
+ * Lesser General Public License for more details.
+ *
+ * You should have received a copy of the GNU Lesser General Public
+ * License along with this library; if not, write to the Free Software
+ * Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA  02111-1307  USA
+ * 
+*/
+
+#ifndef PROFILE_H
+#define PROFILE_H
+
+#include <ctime>
+
+namespace Avoid {
+
+
+#ifdef NOTIMERS
+
+  #define register_timer(t) do {} while(0)
+  #define regstart_timer(t) do {} while(0)
+  #define start_timer() do {} while(0)
+  #define stop_timer() do {} while(0)
+
+#else
+   
+  #define register_timer(t) timers.Register(t)
+  #define regstart_timer(t) timers.Register(t, timerStart)
+  #define start_timer() timers.Start()
+  #define stop_timer() timers.Stop()
+
+#endif
+
+typedef unsigned long long int bigclock_t;
+
+static const int tmCount = 5;
+
+static const int tmNon = -1;
+static const int tmAdd = 0;
+static const int tmDel = 1;
+static const int tmMov = 2;
+static const int tmPth = 3;
+static const int tmSev = 4;
+
+
+static const bool timerStart = true;
+static const bool timerDelay = false;
+
+
+class Timer
+{
+    public:
+        Timer();
+        void Register(const int t, const bool start = timerDelay);
+        void Start(void);
+        void Stop(void);
+        void Reset(void);
+        void Print(const int t);
+        void PrintAll(void);
+
+    private:
+        clock_t cStart[tmCount];
+        bigclock_t cTotal[tmCount];
+        bigclock_t cPath[tmCount];
+        int cTally[tmCount];
+        int cPathTally[tmCount];
+        clock_t cMax[tmCount];
+        clock_t cPathMax[tmCount];
+
+        bool running;
+        long count;
+        int type, lasttype;
+};
+
+extern Timer timers;
+
+}
+
+#endif
diff --git a/src/libavoid/vertices.cpp b/src/libavoid/vertices.cpp
new file mode 100644
index 000000000..7e74509f0
--- /dev/null
+++ b/src/libavoid/vertices.cpp
@@ -0,0 +1,438 @@
+/*
+ * vim: ts=4 sw=4 et tw=0 wm=0
+ *
+ * libavoid - Fast, Incremental, Object-avoiding Line Router
+ * Copyright (C) 2004-2005  Michael Wybrow <mjwybrow@users.sourceforge.net>
+ *
+ * This library is free software; you can redistribute it and/or
+ * modify it under the terms of the GNU Lesser General Public
+ * License as published by the Free Software Foundation; either
+ * version 2.1 of the License, or (at your option) any later version.
+ *
+ * This library is distributed in the hope that it will be useful,
+ * but WITHOUT ANY WARRANTY; without even the implied warranty of
+ * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU
+ * Lesser General Public License for more details.
+ *
+ * You should have received a copy of the GNU Lesser General Public
+ * License along with this library; if not, write to the Free Software
+ * Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA  02111-1307  USA
+ *
+*/
+
+#include "libavoid/geometry.h"
+#include "libavoid/graph.h"  // For alertConns
+#include "libavoid/debug.h"
+
+
+
+namespace Avoid {
+
+
+ContainsMap contains;
+
+
+VertID::VertID()
+{
+}
+
+
+VertID::VertID(unsigned int id, bool s, int n)
+    : objID(id)
+    , isShape(s)
+    , vn(n)
+{
+}
+
+
+VertID::VertID(const VertID& other)
+    : objID(other.objID)
+    , isShape(other.isShape)
+    , vn(other.vn)
+{
+}
+
+
+VertID& VertID::operator= (const VertID& rhs)
+{
+    // Gracefully handle self assignment
+    //if (this == &rhs) return *this;
+
+    objID = rhs.objID;
+    isShape = rhs.isShape;
+    vn = rhs.vn;
+
+    return *this;
+}
+
+
+bool VertID::operator==(const VertID& rhs) const
+{
+    if ((objID != rhs.objID) || (vn != rhs.vn))
+    {
+        return false;
+    }
+    assert(isShape == rhs.isShape);
+    return true;
+}
+
+
+bool VertID::operator!=(const VertID& rhs) const
+{
+    if ((objID != rhs.objID) || (vn != rhs.vn))
+    {
+        return true;
+    }
+    assert(isShape == rhs.isShape);
+    return false;
+}
+
+
+bool VertID::operator<(const VertID& rhs) const
+{
+    if ((objID < rhs.objID) ||
+            ((objID == rhs.objID) && (vn < rhs.vn)))
+    {
+        return true;
+    }
+    return false;
+}
+
+
+VertID VertID::operator+(const int& rhs) const
+{
+    return VertID(objID, isShape, vn + rhs);
+}
+
+
+VertID VertID::operator-(const int& rhs) const
+{
+    return VertID(objID, isShape, vn - rhs);
+}
+
+
+VertID& VertID::operator++(int)
+{
+    vn += 1;
+    return *this;
+}
+
+
+void VertID::print(FILE *file) const
+{
+    fprintf(file, "[%u,%d]", objID, vn);
+}
+
+
+void VertID::db_print(void) const
+{
+    db_printf("[%u,%d]", objID, vn);
+}
+
+
+const int VertID::src = 1;
+const int VertID::tar = 2;
+
+
+VertInf::VertInf(const VertID& vid, const Point& vpoint)
+    : id(vid)
+    , point(vpoint)
+    , lstPrev(NULL)
+    , lstNext(NULL)
+    , shPrev(NULL)
+    , shNext(NULL)
+    , visListSize(0)
+    , invisListSize(0)
+    , pathNext(NULL)
+    , pathDist(0)
+{
+}
+
+
+void VertInf::Reset(const Point& vpoint)
+{
+    point = vpoint;
+}
+
+
+void VertInf::removeFromGraph(const bool isConnVert)
+{
+    if (isConnVert)
+    {
+        assert(!(id.isShape));
+    }
+
+    VertInf *tmp = this;
+
+    // For each vertex.
+    EdgeInfList& visList = tmp->visList;
+    EdgeInfList::iterator finish = visList.end();
+    EdgeInfList::iterator edge;
+    while ((edge = visList.begin()) != finish)
+    {
+        // Remove each visibility edge
+        (*edge)->alertConns();
+        delete (*edge);
+    }
+
+    EdgeInfList& invisList = tmp->invisList;
+    finish = invisList.end();
+    while ((edge = invisList.begin()) != finish)
+    {
+        // Remove each invisibility edge
+        delete (*edge);
+    }
+}
+
+
+bool directVis(VertInf *src, VertInf *dst)
+{
+    ShapeSet ss = ShapeSet();
+
+    Point& p = src->point;
+    Point& q = dst->point;
+
+    VertID& pID = src->id;
+    VertID& qID = dst->id;
+
+    if (!(pID.isShape))
+    {
+        ss.insert(contains[pID].begin(), contains[pID].end());
+    }
+    if (!(qID.isShape))
+    {
+        ss.insert(contains[qID].begin(), contains[qID].end());
+    }
+
+    // The "beginning" should be the first shape vertex, rather
+    // than an endpoint, which are also stored in "vertices".
+    VertInf *endVert = vertices.end();
+    for (VertInf *k = vertices.shapesBegin(); k != endVert; k = k->lstNext)
+    {
+        if ((ss.find(k->id.objID) == ss.end()))
+        {
+            if (segmentIntersect(p, q, k->point, k->shNext->point))
+            {
+                return false;
+            }
+        }
+    }
+    return true;
+}
+
+
+VertInfList::VertInfList()
+    : _firstShapeVert(NULL)
+    , _firstConnVert(NULL)
+    , _lastShapeVert(NULL)
+    , _lastConnVert(NULL)
+    , _shapeVertices(0)
+    , _connVertices(0)
+{
+}
+
+
+#define checkVertInfListConditions() \
+        do { \
+            assert((!_firstConnVert && (_connVertices == 0)) || \
+                    ((_firstConnVert->lstPrev == NULL) && (_connVertices > 0))); \
+            assert((!_firstShapeVert && (_shapeVertices == 0)) || \
+                    ((_firstShapeVert->lstPrev == NULL) && (_shapeVertices > 0))); \
+            assert(!_lastShapeVert || (_lastShapeVert->lstNext == NULL)); \
+            assert(!_lastConnVert || (_lastConnVert->lstNext == _firstShapeVert)); \
+            assert((!_firstConnVert && !_lastConnVert) || \
+                    (_firstConnVert &&  _lastConnVert) ); \
+            assert((!_firstShapeVert && !_lastShapeVert) || \
+                    (_firstShapeVert &&  _lastShapeVert) ); \
+            assert(!_firstShapeVert || _firstShapeVert->id.isShape); \
+            assert(!_lastShapeVert || _lastShapeVert->id.isShape); \
+            assert(!_firstConnVert || !(_firstConnVert->id.isShape)); \
+            assert(!_lastConnVert || !(_lastConnVert->id.isShape)); \
+        } while(0)
+
+
+void VertInfList::addVertex(VertInf *vert)
+{
+    checkVertInfListConditions();
+    assert(vert->lstPrev == NULL);
+    assert(vert->lstNext == NULL);
+
+    if (!(vert->id.isShape))
+    {
+        // A Connector vertex
+        if (_firstConnVert)
+        {
+            // Join with previous front
+            vert->lstNext = _firstConnVert;
+            _firstConnVert->lstPrev = vert;
+
+            // Make front
+            _firstConnVert = vert;
+        }
+        else
+        {
+            // Make front and back
+            _firstConnVert = vert;
+            _lastConnVert = vert;
+
+            // Link to front of shapes list
+            vert->lstNext = _firstShapeVert;
+        }
+        _connVertices++;
+    }
+    else // if (vert->id.shape > 0)
+    {
+        // A Shape vertex
+        if (_lastShapeVert)
+        {
+            // Join with previous back
+            vert->lstPrev = _lastShapeVert;
+            _lastShapeVert->lstNext = vert;
+
+            // Make back
+            _lastShapeVert = vert;
+        }
+        else
+        {
+            // Make first and last
+            _firstShapeVert = vert;
+            _lastShapeVert = vert;
+
+            // Join with conns list
+            if (_lastConnVert)
+            {
+                assert (_lastConnVert->lstNext == NULL);
+
+                _lastConnVert->lstNext = vert;
+            }
+        }
+        _shapeVertices++;
+    }
+    checkVertInfListConditions();
+}
+
+
+void VertInfList::removeVertex(VertInf *vert)
+{
+    // Conditions for correct data structure
+    checkVertInfListConditions();
+
+    if (!(vert->id.isShape))
+    {
+        // A Connector vertex
+        if (vert == _firstConnVert)
+        {
+
+            if (vert == _lastConnVert)
+            {
+                _firstConnVert = NULL;
+                _lastConnVert = NULL;
+            }
+            else
+            {
+                // Set new first
+                _firstConnVert = _firstConnVert->lstNext;
+
+                if (_firstConnVert)
+                {
+                    // Set previous
+                    _firstConnVert->lstPrev = NULL;
+                }
+            }
+        }
+        else if (vert == _lastConnVert)
+        {
+            // Set new last
+            _lastConnVert = _lastConnVert->lstPrev;
+
+            // Make last point to shapes list
+            _lastConnVert->lstNext = _firstShapeVert;
+        }
+        else
+        {
+            vert->lstNext->lstPrev = vert->lstPrev;
+            vert->lstPrev->lstNext = vert->lstNext;
+        }
+        _connVertices--;
+    }
+    else // if (vert->id.shape > 0)
+    {
+        // A Shape vertex
+        if (vert == _lastShapeVert)
+        {
+            // Set new last
+            _lastShapeVert = _lastShapeVert->lstPrev;
+
+            if (vert == _firstShapeVert)
+            {
+                _firstShapeVert = NULL;
+                if (_lastConnVert)
+                {
+                    _lastConnVert->lstNext = NULL;
+                }
+            }
+
+            if (_lastShapeVert)
+            {
+                _lastShapeVert->lstNext = NULL;
+            }
+        }
+        else if (vert == _firstShapeVert)
+        {
+            // Set new first
+            _firstShapeVert = _firstShapeVert->lstNext;
+
+            // Correct the last conn vertex
+            if (_lastConnVert)
+            {
+                _lastConnVert->lstNext = _firstShapeVert;
+            }
+
+            if (_firstShapeVert)
+            {
+                _firstShapeVert->lstPrev = NULL;
+            }
+        }
+        else
+        {
+            vert->lstNext->lstPrev = vert->lstPrev;
+            vert->lstPrev->lstNext = vert->lstNext;
+        }
+        _shapeVertices--;
+    }
+    vert->lstPrev = NULL;
+    vert->lstNext = NULL;
+
+    checkVertInfListConditions();
+}
+
+
+VertInf *VertInfList::shapesBegin(void)
+{
+    return _firstShapeVert;
+}
+
+
+VertInf *VertInfList::connsBegin(void)
+{
+    if (_firstConnVert)
+    {
+        return _firstConnVert;
+    }
+    // No connector vertices
+    return _firstShapeVert;
+}
+
+
+VertInf *VertInfList::end(void)
+{
+    return NULL;
+}
+
+
+VertInfList vertices;
+
+
+}
+
+
diff --git a/src/libavoid/vertices.h b/src/libavoid/vertices.h
new file mode 100644
index 000000000..c2ff6977f
--- /dev/null
+++ b/src/libavoid/vertices.h
@@ -0,0 +1,124 @@
+/*
+ * vim: ts=4 sw=4 et tw=0 wm=0
+ *
+ * libavoid - Fast, Incremental, Object-avoiding Line Router
+ * Copyright (C) 2004-2005  Michael Wybrow <mjwybrow@users.sourceforge.net>
+ *
+ * This library is free software; you can redistribute it and/or
+ * modify it under the terms of the GNU Lesser General Public
+ * License as published by the Free Software Foundation; either
+ * version 2.1 of the License, or (at your option) any later version.
+ *
+ * This library is distributed in the hope that it will be useful,
+ * but WITHOUT ANY WARRANTY; without even the implied warranty of
+ * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU
+ * Lesser General Public License for more details.
+ *
+ * You should have received a copy of the GNU Lesser General Public
+ * License along with this library; if not, write to the Free Software
+ * Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA  02111-1307  USA
+ *
+*/
+
+#ifndef AVOID_VERTICES_H
+#define AVOID_VERTICES_H
+
+#include <list>
+#include <set>
+#include <map>
+#include <iostream>
+#include "libavoid/geomtypes.h"
+
+namespace Avoid {
+
+class EdgeInf;
+
+typedef std::list<EdgeInf *> EdgeInfList;
+
+
+class VertID
+{
+    public:
+        unsigned int objID;
+        bool isShape;
+        int vn;
+
+        static const int src;
+        static const int tar;
+
+        VertID();
+        VertID(unsigned int id, bool s, int n);
+        VertID(const VertID& other);
+        VertID& operator= (const VertID& rhs);
+        bool operator==(const VertID& rhs) const;
+        bool operator!=(const VertID& rhs) const;
+        bool operator<(const VertID& rhs) const;
+        VertID operator+(const int& rhs) const;
+        VertID operator-(const int& rhs) const;
+        VertID& operator++(int);
+        void print(FILE *file = stdout) const;
+        void db_print(void) const;
+};
+
+
+class VertInf
+{
+    public:
+        VertInf(const VertID& vid, const Point& vpoint);
+        void Reset(const Point& vpoint);
+        void removeFromGraph(const bool isConnVert = true);
+
+        VertID id;
+        Point  point;
+        VertInf *lstPrev;
+        VertInf *lstNext;
+        VertInf *shPrev;
+        VertInf *shNext;
+        EdgeInfList visList;
+        unsigned int visListSize;
+        EdgeInfList invisList;
+        unsigned int invisListSize;
+        VertInf *pathNext;
+        double pathDist;
+};
+
+
+bool directVis(VertInf *src, VertInf *dst);
+
+
+class VertInfList
+{
+    public:
+        VertInfList();
+        void addVertex(VertInf *vert);
+        void removeVertex(VertInf *vert);
+        VertInf *shapesBegin(void);
+        VertInf *connsBegin(void);
+        VertInf *end(void);
+        void stats(void)
+        {
+            printf("Conns %d, shapes %d\n", _connVertices, _shapeVertices);
+        }
+    private:
+        VertInf *_firstShapeVert;
+        VertInf *_firstConnVert;
+        VertInf *_lastShapeVert;
+        VertInf *_lastConnVert;
+        unsigned int _shapeVertices;
+        unsigned int _connVertices;
+};
+
+
+typedef std::set<unsigned int> ShapeSet;
+typedef std::map<VertID, ShapeSet> ContainsMap;
+
+extern ContainsMap contains;
+extern VertInfList vertices;
+
+
+}
+
+
+#endif
+
+
diff --git a/src/libavoid/visibility.cpp b/src/libavoid/visibility.cpp
new file mode 100644
index 000000000..e13656f5f
--- /dev/null
+++ b/src/libavoid/visibility.cpp
@@ -0,0 +1,653 @@
+/*
+ * vim: ts=4 sw=4 et tw=0 wm=0
+ *
+ * libavoid - Fast, Incremental, Object-avoiding Line Router
+ * Copyright (C) 2004-2005  Michael Wybrow <mjwybrow@users.sourceforge.net>
+ *
+ * This library is free software; you can redistribute it and/or
+ * modify it under the terms of the GNU Lesser General Public
+ * License as published by the Free Software Foundation; either
+ * version 2.1 of the License, or (at your option) any later version.
+ *
+ * This library is distributed in the hope that it will be useful,
+ * but WITHOUT ANY WARRANTY; without even the implied warranty of
+ * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU
+ * Lesser General Public License for more details.
+ *
+ * You should have received a copy of the GNU Lesser General Public
+ * License along with this library; if not, write to the Free Software
+ * Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA  02111-1307  USA
+ *
+*/
+
+
+#include <cfloat>
+
+#include "libavoid/shape.h"
+#include "libavoid/debug.h"
+#include "libavoid/visibility.h"
+#include "libavoid/graph.h"
+
+#include <math.h>
+
+#ifdef LINEDEBUG
+  #include "SDL_gfxPrimitives.h"
+#endif
+
+namespace Avoid {
+
+
+bool UseAStarSearch   = true;
+bool IgnoreRegions    = true;
+bool SelectiveReroute = true;
+bool IncludeEndpoints = true;
+bool UseLeesAlgorithm = false;
+bool InvisibilityGrph = true;
+bool PartialFeedback  = false;
+
+bool PartialTime = false;
+
+
+void computeCompleteVis(void)
+{
+    VertInf *beginVert = vertices.shapesBegin();
+    VertInf *endVert = vertices.end();
+    for (VertInf *i = beginVert; i != endVert; i = i->lstNext)
+    {
+        db_printf("-- CONSIDERING --\n");
+        i->id.db_print();
+
+        for (VertInf *j = i->lstPrev ; j != NULL; j = j->lstPrev)
+        {
+            bool knownNew = true;
+            EdgeInf::checkEdgeVisibility(i, j, knownNew);
+        }
+    }
+}
+
+
+void shapeVis(ShapeRef *shape)
+{
+    if (!InvisibilityGrph)
+    {
+        // Clear shape from graph.
+        shape->removeFromGraph();
+    }
+
+    VertInf *shapeBegin = shape->firstVert();
+    VertInf *shapeEnd = shape->lastVert()->lstNext;
+
+    VertInf *pointsBegin = NULL;
+    if (IncludeEndpoints)
+    {
+        pointsBegin = vertices.connsBegin();
+    }
+    else
+    {
+        pointsBegin = vertices.shapesBegin();
+    }
+
+    for (VertInf *curr = shapeBegin; curr != shapeEnd; curr = curr->lstNext)
+    {
+        bool knownNew = true;
+
+        db_printf("-- CONSIDERING --\n");
+        curr->id.db_print();
+
+        db_printf("\tFirst Half:\n");
+        for (VertInf *j = pointsBegin ; j != curr; j = j->lstNext)
+        {
+            EdgeInf::checkEdgeVisibility(curr, j, knownNew);
+        }
+
+        db_printf("\tSecond Half:\n");
+        VertInf *pointsEnd = vertices.end();
+        for (VertInf *k = shapeEnd; k != pointsEnd; k = k->lstNext)
+        {
+            EdgeInf::checkEdgeVisibility(curr, k, knownNew);
+        }
+    }
+}
+
+
+void shapeVisSweep(ShapeRef *shape)
+{
+    if (!InvisibilityGrph)
+    {
+        // Clear shape from graph.
+        shape->removeFromGraph();
+    }
+
+    VertInf *startIter = shape->firstVert();
+    VertInf *endIter = shape->lastVert()->lstNext;
+
+    for (VertInf *i = startIter; i != endIter; i = i->lstNext)
+    {
+        vertexSweep(i);
+    }
+}
+
+
+void vertexVisibility(VertInf *point, VertInf *partner, bool knownNew,
+        const bool gen_contains)
+{
+    const VertID& pID = point->id;
+
+    // Make sure we're only doing ptVis for endpoints.
+    assert(!(pID.isShape));
+
+    if (!InvisibilityGrph)
+    {
+        point->removeFromGraph();
+    }
+
+    if (gen_contains && !(pID.isShape))
+    {
+        generateContains(point);
+    }
+
+    if (UseLeesAlgorithm)
+    {
+        vertexSweep(point);
+    }
+    else
+    {
+        VertInf *shapesEnd = vertices.end();
+        for (VertInf *k = vertices.shapesBegin(); k != shapesEnd;
+                k = k->lstNext)
+        {
+            EdgeInf::checkEdgeVisibility(point, k, knownNew);
+        }
+        if (IncludeEndpoints && partner)
+        {
+            EdgeInf::checkEdgeVisibility(point, partner, knownNew);
+        }
+    }
+}
+
+
+//============================================================================
+//  SWEEP CODE
+//
+
+static VertInf *centerInf;
+static Point centerPoint;
+static VertID centerID;
+static double centerAngle;
+
+#ifdef LINEDEBUG
+    SDL_Surface *avoid_screen = NULL;
+#endif
+
+
+class PointPair
+{
+    public:
+        PointPair(VertInf *inf)
+            : vInf(inf)
+        {
+            double x = vInf->point.x - centerPoint.x;
+            double y = vInf->point.y - centerPoint.y;
+
+            angle = pos_to_angle(x, y);
+        }
+        bool operator==(const PointPair& rhs) const
+        {
+            if (vInf->id == rhs.vInf->id)
+            {
+                return true;
+            }
+            return false;
+        }
+        static double pos_to_angle(double x, double y)
+        {
+            double ang = atan(y / x);
+            ang = (ang * 180) / M_PI;
+            if (x < 0)
+            {
+                ang += 180;
+            }
+            else if (y < 0)
+            {
+                ang += 360;
+            }
+            return ang;
+        }
+
+        VertInf    *vInf;
+        double     angle;
+};
+
+
+typedef std::list<PointPair > VertList;
+
+
+class EdgePair
+{
+    public:
+        EdgePair(VertInf *v1, VertInf *v2, double d, double a)
+            : vInf1(v1), vInf2(v2), initdist(d), initangle(a)
+        {
+            currdist  = initdist;
+            currangle = initangle;
+        }
+        bool operator<(const EdgePair& rhs) const
+        {
+            if (initdist == rhs.initdist)
+            {
+                // TODO: This is a bit of a hack, should be
+                //       set by the call to the constructor.
+                return dist(centerPoint, vInf2->point) <
+                        dist(centerPoint, rhs.vInf2->point);
+            }
+            return (initdist < rhs.initdist);
+        }
+        bool operator==(const EdgePair& rhs) const
+        {
+            if (((vInf1->id == rhs.vInf1->id) &&
+                        (vInf2->id == rhs.vInf2->id)) ||
+                ((vInf1->id == rhs.vInf2->id) &&
+                        (vInf2->id == rhs.vInf1->id)))
+            {
+                return true;
+            }
+            return false;
+        }
+        bool operator!=(const EdgePair& rhs) const
+        {
+            if (((vInf1->id == rhs.vInf1->id) &&
+                        (vInf2->id == rhs.vInf2->id)) ||
+                ((vInf1->id == rhs.vInf2->id) &&
+                        (vInf2->id == rhs.vInf1->id)))
+            {
+                return false;
+            }
+            return true;
+        }
+        void SetObsAng(double a)
+        {
+            obsAngle = fmod(initangle - (a - 180), 360);
+
+            //db_printf("SetObsAng: %.2f  (from init %.2f, a %.2f)\n",
+            //      obsAngle, initangle, a);
+        }
+
+        VertInf *vInf1;
+        VertInf *vInf2;
+        double  initdist;
+        double  initangle;
+        double  currdist;
+        double  currangle;
+        double  obsAngle;
+};
+
+typedef std::set<EdgePair> EdgeSet;
+
+
+static bool ppCompare(PointPair& pp1, PointPair& pp2)
+{
+    if (pp1.angle == pp2.angle)
+    {
+        // If the points are colinear, then order them in increasing
+        // distance from the point we are sweeping around.
+        return dist(centerPoint, pp1.vInf->point) <
+                dist(centerPoint, pp2.vInf->point);
+    }
+    return pp1.angle < pp2.angle;
+}
+
+
+#define AHEAD    1
+#define BEHIND  -1
+
+class isBoundingShape
+{
+    public:
+        // constructor remembers the value provided
+        isBoundingShape(ShapeSet& set)
+        : ss(set)
+        { }
+        // the following is an overloading of the function call operator
+        bool operator () (const PointPair& pp)
+        {
+            if (pp.vInf->id.isShape &&
+                    (ss.find(pp.vInf->id.objID) != ss.end()))
+            {
+                return true;
+            }
+            return false;
+        }
+    private:
+        ShapeSet& ss;
+};
+
+
+static bool sweepVisible(EdgeSet& T, VertInf *currInf, VertInf *lastInf,
+        bool lastVisible, double lastAngle, int *blocker)
+{
+
+    if (!lastInf || (lastAngle != centerAngle))
+    {
+        // Nothing before it on the current ray
+        EdgeSet::iterator closestIt = T.begin();
+        if (closestIt != T.end())
+        {
+
+            Point &e1 = (*closestIt).vInf1->point;
+            Point &e2 = (*closestIt).vInf2->point;
+
+            if (segmentIntersect(centerInf->point, currInf->point, e1, e2))
+            {
+                *blocker = (*closestIt).vInf1->id.objID;
+                return false;
+            }
+            else
+            {
+                return true;
+            }
+        }
+        else
+        {
+            return true;
+        }
+    }
+    else
+    {
+        // There was another point before this on the ray (lastInf)
+        if (!lastVisible)
+        {
+            *blocker = -1;
+            return false;
+        }
+        else
+        {
+            // Check if there is an edge in T that blocks the ray
+            // between lastInf and currInf.
+            EdgeSet::iterator tfin = T.end();
+            for (EdgeSet::iterator l = T.begin(); l != tfin; ++l)
+            {
+                Point &e1 = (*l).vInf1->point;
+                Point &e2 = (*l).vInf2->point;
+
+                if (segmentIntersect(lastInf->point, currInf->point, e1, e2))
+                {
+                    *blocker = (*l).vInf1->id.objID;
+                    return false;
+                }
+            }
+            return true;
+        }
+    }
+}
+
+
+void vertexSweep(VertInf *vert)
+{
+    VertID& pID = vert->id;
+    Point& pPoint = vert->point;
+
+    centerInf = vert;
+    centerID = pID;
+    centerPoint = pPoint;
+    Point centerPt = pPoint;
+    centerAngle = -1;
+
+    // List of shape (and maybe endpt) vertices, except p
+    // Sort list, around
+    VertList v;
+
+    // Initialise the vertex list
+    VertInf *beginVert = vertices.connsBegin();
+    VertInf *endVert = vertices.end();
+    for (VertInf *inf = beginVert; inf != endVert; inf = inf->lstNext)
+    {
+        if (inf->id == centerID)
+        {
+            // Don't include the center point
+            continue;
+        }
+
+        if (inf->id.isShape)
+        {
+            // Add shape vertex
+            v.push_back(inf);
+        }
+        else
+        {
+            if (IncludeEndpoints)
+            {
+                if (centerID.isShape)
+                {
+                    // Add endpoint vertex
+                    v.push_back(inf);
+                }
+                else
+                {
+                    // Center is an endpoint, so only include the other
+                    // endpoint from the matching connector.
+                    VertID partnerID = VertID(centerID.objID, false,
+                            (centerID.vn == 1) ? 2 : 1);
+                    if (inf->id == partnerID)
+                    {
+                        v.push_back(inf);
+                    }
+                }
+            }
+        }
+    }
+    // TODO: This should be done with a sorted data type and insertion sort.
+    v.sort(ppCompare);
+
+    EdgeSet e;
+    ShapeSet& ss = contains[centerID];
+
+    // And edge to T that intersect the initial ray.
+    VertInf *last = vertices.end();
+    for (VertInf *k = vertices.shapesBegin(); k != last; )
+    {
+        VertID kID = k->id;
+        if (!(centerID.isShape) && (ss.find(kID.objID) != ss.end()))
+        {
+            uint shapeID = kID.objID;
+            db_printf("Center is inside shape %u so ignore shape edges.\n",
+                    shapeID);
+            // One of the endpoints is inside this shape so ignore it.
+            while ((k != last) && (k->id.objID == shapeID))
+            {
+                // And skip the other vertices from this shape.
+                k = k->lstNext;
+            }
+            continue;
+        }
+
+        VertInf *kPrev = k->shPrev;
+        if ((centerInf == k) || (centerInf == kPrev))
+        {
+            k = k->lstNext;
+            continue;
+        }
+
+        Point xaxis = { DBL_MAX, centerInf->point.y };
+
+        if (segmentIntersect(centerInf->point, xaxis, kPrev->point, k->point))
+        {
+            double distance;
+            if (vecDir(centerInf->point, xaxis, kPrev->point) == BEHIND)
+            {
+                distance = dist(centerInf->point, kPrev->point);
+            }
+            else
+            {
+                distance = dist(centerInf->point, k->point);
+            }
+
+            EdgePair intPair = EdgePair(k, kPrev, distance, 0.0);
+            e.insert(intPair).first;
+        }
+        k = k->lstNext;
+    }
+
+    // Start the actual sweep.
+    db_printf("SWEEP: "); centerID.db_print(); db_printf("\n");
+
+    VertInf *lastInf     = NULL;
+    double   lastAngle   = 0;
+    bool     lastVisible = false;
+    int      lastBlocker = 0;
+
+    isBoundingShape isBounding(contains[centerID]);
+    VertList::iterator vfst = v.begin();
+    VertList::iterator vfin = v.end();
+    for (VertList::iterator t = vfst; t != vfin; ++t)
+    {
+        VertInf *currInf = (*t).vInf;
+        VertID& currID = currInf->id;
+        Point&  currPt = currInf->point;
+        centerAngle = (*t).angle;
+
+#ifdef LINEDEBUG
+        Sint16 ppx = (int) centerPt.x;
+        Sint16 ppy = (int) centerPt.y;
+
+        Sint16 cx = (int) currPt.x;
+        Sint16 cy = (int) currPt.y;
+#endif
+
+        double currDist = dist(centerPt, currPt);
+        db_printf("Dist: %.1f.\n", currDist);
+
+        EdgeInf *edge = EdgeInf::existingEdge(centerInf, currInf);
+        if (edge == NULL)
+        {
+            edge = new EdgeInf(centerInf, currInf);
+        }
+        // Ignore vertices from bounding shapes, if sweeping round an endpoint.
+        if (!(centerID.isShape) && isBounding(*t))
+        {
+            if (InvisibilityGrph)
+            {
+                // if p and t can't see each other, add blank edge
+                db_printf("\tSkipping visibility edge... \n\t\t");
+                edge->addBlocker(currInf->id.objID);
+                edge->db_print();
+            }
+            continue;
+        }
+
+
+        bool cone1 = true, cone2 = true;
+        if (centerID.isShape)
+        {
+            cone1 = inValidRegion(centerInf->shPrev->point, centerPoint,
+                    centerInf->shNext->point, currInf->point);
+        }
+        if (currInf->id.isShape)
+        {
+            cone2 = inValidRegion(currInf->shPrev->point, currInf->point,
+                    currInf->shNext->point, centerPoint);
+        }
+
+        if (!cone1 || !cone2)
+        {
+            lastInf = NULL;
+            if (InvisibilityGrph)
+            {
+                db_printf("\tSetting invisibility edge... \n\t\t");
+                edge->addBlocker(0);
+                edge->db_print();
+            }
+        }
+        else
+        {
+            int blocker = 0;
+            // Check visibility.
+            bool currVisible = sweepVisible(e, currInf,
+                    lastInf, lastVisible, lastAngle, &blocker);
+            if (blocker == -1)
+            {
+                blocker = lastBlocker;
+            }
+            if (currVisible)
+            {
+#ifdef LINEDEBUG
+                lineRGBA(avoid_screen, ppx, ppy, cx, cy, 255, 0, 0, 32);
+#endif
+                db_printf("\tSetting visibility edge... \n\t\t");
+                edge->setDist(currDist);
+                edge->db_print();
+            }
+            else if (InvisibilityGrph)
+            {
+                db_printf("\tSetting invisibility edge... \n\t\t");
+                edge->addBlocker(blocker);
+                edge->db_print();
+            }
+
+            lastVisible = currVisible;
+            lastInf     = currInf;
+            lastAngle   = centerAngle;
+            lastBlocker = blocker;
+        }
+
+        if (currID.isShape)
+        {
+            // This is a shape edge
+            Point& prevPt = currInf->shPrev->point;
+            Point& nextPt = currInf->shNext->point;
+
+            int prevDir = vecDir(centerPt, currPt, prevPt);
+            EdgePair prevPair = EdgePair(currInf, currInf->shPrev,
+                    currDist, centerAngle);
+
+            EdgeSet::iterator ePtr;
+            if (prevDir == BEHIND)
+            {
+                ePtr = e.find(prevPair);
+                if (ePtr != e.end())
+                {
+                    e.erase(ePtr);
+                }
+            }
+            else if ((prevDir == AHEAD) && (currInf->shPrev != centerInf))
+            {
+                double x = prevPt.x - currPt.x;
+                double y = prevPt.y - currPt.y;
+                double angle = PointPair::pos_to_angle(x, y);
+                prevPair.SetObsAng(angle);
+
+                ePtr = e.insert(prevPair).first;
+            }
+
+
+            int nextDir = vecDir(centerPt, currPt, nextPt);
+            EdgePair nextPair = EdgePair(currInf, currInf->shNext,
+                    currDist, centerAngle);
+
+            if (nextDir == BEHIND)
+            {
+                ePtr = e.find(nextPair);
+                if (ePtr != e.end())
+                {
+                    e.erase(ePtr);
+                }
+            }
+            else if ((nextDir == AHEAD) && (currInf->shNext != centerInf))
+            {
+                double x = nextPt.x - currPt.x;
+                double y = nextPt.y - currPt.y;
+                double angle = PointPair::pos_to_angle(x, y);
+                nextPair.SetObsAng(angle);
+
+                ePtr = e.insert(nextPair).first;
+            }
+        }
+
+#ifdef LINEDEBUG
+        SDL_Flip(avoid_screen);
+#endif
+    }
+}
+
+
+}
+
diff --git a/src/libavoid/visibility.h b/src/libavoid/visibility.h
new file mode 100644
index 000000000..edfc3b16c
--- /dev/null
+++ b/src/libavoid/visibility.h
@@ -0,0 +1,57 @@
+/*
+ * vim: ts=4 sw=4 et tw=0 wm=0
+ *
+ * libavoid - Fast, Incremental, Object-avoiding Line Router
+ * Copyright (C) 2004-2005  Michael Wybrow <mjwybrow@users.sourceforge.net>
+ *
+ * This library is free software; you can redistribute it and/or
+ * modify it under the terms of the GNU Lesser General Public
+ * License as published by the Free Software Foundation; either
+ * version 2.1 of the License, or (at your option) any later version.
+ *
+ * This library is distributed in the hope that it will be useful,
+ * but WITHOUT ANY WARRANTY; without even the implied warranty of
+ * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU
+ * Lesser General Public License for more details.
+ *
+ * You should have received a copy of the GNU Lesser General Public
+ * License along with this library; if not, write to the Free Software
+ * Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA  02111-1307  USA
+ * 
+*/
+
+#ifndef AVOID_VISIBILITY_H
+#define AVOID_VISIBILITY_H
+
+#include "libavoid/vertices.h"
+
+
+//#define LINEDEBUG
+
+#ifdef LINEDEBUG       
+    #include <SDL.h>
+#endif
+    
+
+namespace Avoid {
+
+extern bool PartialTime;
+#ifdef LINEDEBUG       
+    extern SDL_Surface *avoid_screen;
+#endif
+
+    
+extern void vertexVisibility(VertInf *point, VertInf *partner, bool knownNew,
+            const bool gen_contains = false);
+extern void vertexSweep(VertInf *point);
+extern void computeCompleteVis(void);
+extern void shapeVis(ShapeRef *shape);
+extern void shapeVisSweep(ShapeRef *shape);
+
+
+}
+
+
+#endif
+
+