--- /dev/null	Thu Jan 01 00:00:00 1970 +0000
+++ b/dwtx/draw2d/graph/ShortestPathRouter.d	Sun Aug 03 00:52:14 2008 +0200
@@ -0,0 +1,909 @@
+/*******************************************************************************
+ * Copyright (c) 2004, 2005 IBM Corporation and others.
+ * All rights reserved. This program and the accompanying materials
+ * are made available under the terms of the Eclipse Public License v1.0
+ * which accompanies this distribution, and is available at
+ * http://www.eclipse.org/legal/epl-v10.html
+ *
+ * Contributors:
+ * IBM Corporation - initial API and implementation
+ * Port to the D programming language:
+ *     Frank Benoit <benoit@tionex.de>
+ *******************************************************************************/
+module dwtx.draw2d.graph.ShortestPathRouter;
+
+import dwt.dwthelper.utils;
+import dwtx.dwtxhelper.Collection;
+
+import dwtx.draw2d.PositionConstants;
+import dwtx.draw2d.geometry.Point;
+import dwtx.draw2d.geometry.PointList;
+import dwtx.draw2d.geometry.Rectangle;
+import dwtx.draw2d.graph.Path;
+import dwtx.draw2d.graph.Vertex;
+import dwtx.draw2d.graph.Segment;
+import dwtx.draw2d.graph.Obstacle;
+
+/**
+ * Bends a collection of {@link Path Paths} around rectangular obstacles. This class
+ * maintains a list of paths and obstacles. Updates can be made to the paths and/or
+ * obstacles, and then an incremental solve can be invoked.
+ * <P>
+ * The algorithm will attempt to find the shortest non-intersecting path between each
+ * path's start and end points. Once all paths have been found, they will be offset based
+ * on how many paths bend around the same corner of each obstacle.
+ * <P>
+ * The worst-case performance of this algorithm is p * s * n^2, where p is the number of
+ * paths, n is the number of obstacles, and s is the average number of segments in each
+ * path's final solution.
+ * <P>
+ * This class is not intended to be subclassed.
+ * @author Whitney Sorenson
+ * @author Randy Hudson
+ * @since 3.0
+ */
+public class ShortestPathRouter {
+
+/**
+ * A stack of Paths.
+ */
+static class PathStack : ArrayList {
+
+    Path pop() {
+        return cast(Path)remove(size() - 1);
+    }
+
+    void push(Path path) {
+        add(path);
+    }
+}
+
+/**
+ * The number of times to grow obstacles and test for intersections. This is a tradeoff
+ * between performance and quality of output.
+ */
+private static const int NUM_GROW_PASSES = 2;
+
+private int spacing = 4;
+private bool growPassChangedObstacles;
+private List orderedPaths;
+private Map pathsToChildPaths;
+
+private PathStack stack;
+private List subPaths;
+
+private List userObstacles;
+private List userPaths;
+private List workingPaths;
+
+/**
+ * Creates a new shortest path routing.
+ */
+public this() {
+    userPaths = new ArrayList();
+    workingPaths = new ArrayList();
+    pathsToChildPaths = new HashMap();
+    userObstacles = new ArrayList();
+}
+
+/**
+ * Adds an obstacle with the given bounds to the obstacles.
+ *
+ * @param rect the bounds of this obstacle
+ * @return <code>true</code> if the added obstacle has dirtied one or more paths
+ */
+public bool addObstacle(Rectangle rect) {
+    return internalAddObstacle(new Obstacle(rect, this));
+}
+
+/**
+ * Adds a path to the routing.
+ * @param path the path to add.
+ */
+public void addPath(Path path) {
+    userPaths.add(path);
+    workingPaths.add(path);
+}
+
+/**
+ * Fills the point lists of the Paths to the correct bent points.
+ */
+private void bendPaths() {
+    for (int i = 0; i < orderedPaths.size(); i++) {
+        Path path = cast(Path) orderedPaths.get(i);
+        Segment segment = null;
+        path.points.addPoint(new Point(path.start.x, path.start.y));
+        for (int v = 0; v < path.grownSegments.size(); v++) {
+            segment = cast(Segment) path.grownSegments.get(v);
+            Vertex vertex = segment.end;
+
+            if (vertex !is null && v < path.grownSegments.size() - 1) {
+                if (vertex.type is Vertex.INNIE) {
+                    vertex.count++;
+                    path.points.addPoint(vertex.bend(vertex.count));
+                } else {
+                    path.points.addPoint(vertex.bend(vertex.totalCount));
+                    vertex.totalCount--;
+                }
+            }
+        }
+        path.points.addPoint(new Point(path.end.x, path.end.y));
+    }
+}
+
+/**
+ * Checks a vertex to see if its offset should shrink
+ * @param vertex the vertex to check
+ */
+private void checkVertexForIntersections(Vertex vertex) {
+    if (vertex.nearestObstacle !is 0 || vertex.nearestObstacleChecked)
+        return;
+    int sideLength, x, y;
+
+    sideLength = 2 * (vertex.totalCount * getSpacing()) + 1;
+
+    if ((vertex.positionOnObstacle & PositionConstants.NORTH) > 0)
+        y = vertex.y - sideLength;
+    else
+        y = vertex.y;
+    if ((vertex.positionOnObstacle & PositionConstants.EAST) > 0)
+        x = vertex.x;
+    else
+        x = vertex.x - sideLength;
+
+    Rectangle r = new Rectangle(x, y, sideLength, sideLength);
+
+    int xDist, yDist;
+
+    for (int o = 0; o < userObstacles.size(); o++) {
+        Obstacle obs = cast(Obstacle)userObstacles.get(o);
+        if (obs !is vertex.obs && r.intersects(obs)) {
+            int pos = obs.getPosition(vertex);
+            if (pos is 0)
+                continue;
+
+            if ((pos & PositionConstants.NORTH) > 0)
+                //   use top
+                yDist = obs.y - vertex.y;
+            else
+                // use bottom
+                yDist = vertex.y - obs.bottom() + 1;
+            if ((pos & PositionConstants.EAST) > 0)
+                //   use right
+                xDist = vertex.x - obs.right() + 1;
+            else
+                //   use left
+                xDist = obs.x - vertex.x;
+
+            if (Math.max(xDist, yDist) < vertex.nearestObstacle
+                    || vertex.nearestObstacle is 0) {
+                vertex.nearestObstacle = Math.max(xDist, yDist);
+                vertex.updateOffset();
+            }
+
+        }
+    }
+
+    vertex.nearestObstacleChecked = true;
+}
+
+/**
+ * Checks all vertices along paths for intersections
+ */
+private void checkVertexIntersections() {
+    for (int i = 0; i < workingPaths.size(); i++) {
+        Path path = cast(Path)workingPaths.get(i);
+
+        for (int s = 0; s < path.segments.size() - 1; s++) {
+            Vertex vertex = (cast(Segment)path.segments.get(s)).end;
+            checkVertexForIntersections(vertex);
+        }
+    }
+}
+
+/**
+ * Frees up fields which aren't needed between invocations.
+ */
+private void cleanup() {
+    for (int i = 0; i < workingPaths.size(); i++) {
+        Path path = cast(Path)workingPaths.get(i);
+        path.cleanup();
+    }
+}
+
+/**
+ * Counts how many paths are on given vertices in order to increment their total count.
+ */
+private void countVertices() {
+    for (int i = 0; i < workingPaths.size(); i++) {
+        Path path = cast(Path) workingPaths.get(i);
+        for (int v = 0; v < path.segments.size() - 1; v++)
+            (cast(Segment)path.segments.get(v)).end.totalCount++;
+    }
+}
+
+/**
+ * Dirties the paths that are on the given vertex
+ * @param vertex the vertex that has the paths
+ */
+private bool dirtyPathsOn(Vertex vertex) {
+    List paths = vertex.paths;
+    if (paths !is null && paths.size() !is 0) {
+        for (int i = 0; i < paths.size(); i++)
+            (cast(Path)paths.get(i)).isDirty = true;
+        return true;
+    }
+    return false;
+}
+
+/**
+ * Resyncs the parent paths with any new child paths that are necessary because bendpoints
+ * have been added to the parent path.
+ *
+private void generateChildPaths() {
+    for (int i = 0; i < userPaths.size(); i++) {
+        Path path = (Path)userPaths.get(i);
+        PointList bendPoints = path.bendpoints;
+        if (bendPoints !is null && bendPoints.size() !is 0) {
+            List childPaths = new ArrayList(bendPoints.size() + 1);
+            Path child = null;
+            Vertex prevVertex = path.start;
+            Vertex currVertex = null;
+
+            for (int b = 0; b < bendPoints.size(); b++) {
+                Point bp = (Point)bendPoints.getPoint(b);
+                currVertex = new Vertex(bp, null);
+                child = new Path(prevVertex, currVertex);
+                childPaths.add(child);
+                workingPaths.add(child);
+                prevVertex = currVertex;
+            }
+
+            child = new Path(prevVertex, path.end);
+            childPaths.add(child);
+            workingPaths.add(child);
+            pathsToChildPaths.put(path, childPaths);
+        } else
+            workingPaths.add(path);
+    } //End FOR
+}*/
+
+/**
+ * Returns the closest vertex to the given segment.
+ * @param v1 the first vertex
+ * @param v2 the second vertex
+ * @param segment the segment
+ * @return v1, or v2 whichever is closest to the segment
+ */
+private Vertex getNearestVertex(Vertex v1, Vertex v2, Segment segment) {
+    if (segment.start.getDistance(v1) + segment.end.getDistance(v1)
+            > segment.start.getDistance(v2) + segment.end.getDistance(v2))
+        return v2;
+    else
+        return v1;
+}
+
+/**
+ * Returns the spacing maintained between paths.
+ * @return the default path spacing
+ * @see #setSpacing(int)
+ * @since 3.2
+ */
+public int getSpacing() {
+    return spacing;
+}
+
+/**
+ * Returns the subpath for a split on the given path at the given segment.
+ * @param path the path
+ * @param segment the segment
+ * @return the new subpath
+ */
+private Path getSubpathForSplit(Path path, Segment segment) {
+    Path newPath = path.getSubPath(segment);
+    workingPaths.add(newPath);
+    subPaths.add(newPath);
+    return newPath;
+}
+
+/**
+ * Grows all obstacles in in routing and tests for new intersections
+ */
+private void growObstacles() {
+    growPassChangedObstacles = false;
+    for (int i = 0; i < NUM_GROW_PASSES; i++) {
+        if (i is 0 || growPassChangedObstacles)
+            growObstaclesPass();
+    }
+}
+
+/**
+ * Performs a single pass of the grow obstacles step, this can be repeated as desired.
+ * Grows obstacles, then tests paths against the grown obstacles.
+ */
+private void growObstaclesPass() {
+    // grow obstacles
+    for (int i = 0; i < userObstacles.size(); i++)
+        (cast(Obstacle)userObstacles.get(i)).growVertices();
+
+    // go through paths and test segments
+    for (int i = 0; i < workingPaths.size(); i++) {
+        Path path = cast(Path) workingPaths.get(i);
+
+        for (int e = 0; e < path.excludedObstacles.size(); e++)
+            (cast(Obstacle)path.excludedObstacles.get(e)).exclude = true;
+
+        if (path.grownSegments.size() is 0) {
+            for (int s = 0; s < path.segments.size(); s++)
+                testOffsetSegmentForIntersections(cast(Segment)path.segments.get(s), -1, path);
+        } else {
+            int counter = 0;
+            List currentSegments = new ArrayList(path.grownSegments);
+            for (int s = 0; s < currentSegments.size(); s++)
+                counter += testOffsetSegmentForIntersections(cast(Segment)currentSegments.get(s), s + counter, path);
+        }
+
+        for (int e = 0; e < path.excludedObstacles.size(); e++)
+            (cast(Obstacle)path.excludedObstacles.get(e)).exclude = false;
+
+    }
+
+    // revert obstacles
+    for (int i = 0; i < userObstacles.size(); i++)
+        (cast(Obstacle)userObstacles.get(i)).shrinkVertices();
+}
+
+/**
+ * Adds an obstacle to the routing
+ * @param obs the obstacle
+ */
+private bool internalAddObstacle(Obstacle obs) {
+    userObstacles.add(obs);
+    return testAndDirtyPaths(obs);
+}
+
+/**
+ * Removes an obstacle from the routing.
+ * @param rect the bounds of the obstacle
+ * @return the obstacle removed
+ */
+private bool internalRemoveObstacle(Rectangle rect) {
+    Obstacle obs = null;
+    int index = -1;
+    for (int i = 0; i < userObstacles.size(); i++) {
+        obs = cast(Obstacle)userObstacles.get(i);
+        if (obs.opEquals(rect)) {
+            index = i;
+            break;
+        }
+    }
+
+    userObstacles.remove(index);
+
+    bool result = false;
+    result |= dirtyPathsOn(obs.bottomLeft);
+    result |= dirtyPathsOn(obs.topLeft);
+    result |= dirtyPathsOn(obs.bottomRight);
+    result |= dirtyPathsOn(obs.topRight);
+
+    for (int p = 0; p < workingPaths.size(); p++) {
+        Path path = cast(Path)workingPaths.get(p);
+        if (path.isDirty)
+            continue;
+        if (path.isObstacleVisible(obs))
+            path.isDirty = result = true;
+    }
+
+    return result;
+}
+
+/**
+ * Labels the given path's vertices as innies, or outies, as well as determining if this
+ * path is inverted.
+ * @param path the path
+ */
+private void labelPath(Path path) {
+    Segment segment = null;
+    Segment nextSegment = null;
+    Vertex vertex = null;
+    bool agree = false;
+    for (int v = 0; v < path.grownSegments.size() - 1; v++) {
+        segment = cast(Segment) path.grownSegments.get(v);
+        nextSegment = cast(Segment) path.grownSegments.get(v + 1);
+        vertex = segment.end;
+        long crossProduct = segment.crossProduct(new Segment(vertex, vertex.obs.center));
+
+        if (vertex.type is Vertex.NOT_SET) {
+            labelVertex(segment, crossProduct, path);
+        } else if (!path.isInverted
+                && ((crossProduct > 0 && vertex.type is Vertex.OUTIE)
+                        || (crossProduct < 0 && vertex.type is Vertex.INNIE))) {
+            if (agree) {
+                // split detected.
+                stack.push(getSubpathForSplit(path, segment));
+                return;
+            } else {
+                path.isInverted = true;
+                path.invertPriorVertices(segment);
+            }
+        } else if (path.isInverted
+                && ((crossProduct < 0 && vertex.type is Vertex.OUTIE)
+                        || (crossProduct > 0 && vertex.type is Vertex.INNIE))) {
+            // split detected.
+            stack.push(getSubpathForSplit(path, segment));
+            return;
+        } else
+            agree = true;
+
+        if (vertex.paths !is null) {
+            for (int i = 0;i < vertex.paths.size();i++) {
+                Path nextPath = cast(Path)vertex.paths.get(i);
+                if (!nextPath.isMarked) {
+                    nextPath.isMarked = true;
+                    stack.push(nextPath);
+                }
+            }
+        }
+
+        vertex.addPath(path, segment, nextSegment);
+    }
+}
+
+/**
+ * Labels all path's vertices in the routing.
+ */
+private void labelPaths() {
+    Path path = null;
+    for (int i = 0; i < workingPaths.size(); i++) {
+        path = cast(Path) workingPaths.get(i);
+        stack.push(path);
+    }
+
+    while (!stack.isEmpty()) {
+        path = stack.pop();
+        if (!path.isMarked) {
+            path.isMarked = true;
+            labelPath(path);
+        }
+    }
+
+    // revert is marked so we can use it again in ordering.
+    for (int i = 0;i < workingPaths.size(); i++) {
+        path = cast(Path)workingPaths.get(i);
+        path.isMarked = false;
+    }
+}
+
+/**
+ * Labels the vertex at the end of the semgent based on the cross product.
+ * @param segment the segment to this vertex
+ * @param crossProduct the cross product of this segment and a segment to the obstacles center
+ * @param path the path
+ */
+private void labelVertex(Segment segment, long crossProduct, Path path) {
+//   assumes vertex in question is segment.end
+    if (crossProduct > 0) {
+        if (path.isInverted)
+            segment.end.type = Vertex.OUTIE;
+        else
+            segment.end.type = Vertex.INNIE;
+    } else if (crossProduct < 0) {
+        if (path.isInverted)
+            segment.end.type = Vertex.INNIE;
+        else
+            segment.end.type = Vertex.OUTIE;
+    } else if (segment.start.type !is Vertex.NOT_SET)
+        segment.end.type = segment.start.type;
+    else
+        segment.end.type = Vertex.INNIE;
+}
+
+/**
+ * Orders the path by comparing its angle at shared vertices with other paths.
+ * @param path the path
+ */
+private void orderPath(Path path) {
+    if (path.isMarked)
+        return;
+    path.isMarked = true;
+    Segment segment = null;
+    Vertex vertex = null;
+    for (int v = 0; v < path.grownSegments.size() - 1; v++) {
+        segment = cast(Segment) path.grownSegments.get(v);
+        vertex = segment.end;
+        double thisAngle = (cast(Double)vertex.cachedCosines.get(path)).doubleValue();
+        if (path.isInverted)
+            thisAngle = -thisAngle;
+
+        for (int i = 0; i < vertex.paths.size(); i++) {
+            Path vPath = cast(Path)vertex.paths.get(i);
+            if (!vPath.isMarked) {
+                double otherAngle = (cast(Double)vertex.cachedCosines.get(vPath)).doubleValue();
+
+                if (vPath.isInverted)
+                    otherAngle = -otherAngle;
+
+                if (otherAngle < thisAngle)
+                    orderPath(vPath);
+            }
+        }
+    }
+
+    orderedPaths.add(path);
+}
+
+/**
+ * Orders all paths in the graph.
+ */
+private void orderPaths() {
+    for (int i = 0; i < workingPaths.size(); i++) {
+        Path path = cast(Path) workingPaths.get(i);
+        orderPath(path);
+    }
+}
+
+/**
+ * Populates the parent paths with all the child paths that were created to represent
+ * bendpoints.
+ */
+private void recombineChildrenPaths() {
+    // only populate those paths with children paths.
+    Iterator keyItr = pathsToChildPaths.keySet().iterator();
+    while (keyItr.hasNext()) {
+        Path path = cast(Path)keyItr.next();
+
+        path.fullReset();
+
+        List childPaths = cast(List)pathsToChildPaths.get(path);
+        Path childPath = null;
+
+        for (int i = 0; i < childPaths.size(); i++) {
+            childPath = cast(Path)childPaths.get(i);
+            path.points.addAll(childPath.getPoints());
+            // path will overlap
+            path.points.removePoint(path.points.size() - 1);
+            //path.grownSegments.addAll(childPath.grownSegments);
+            path.segments.addAll(childPath.segments);
+            path.visibleObstacles.addAll(childPath.visibleObstacles);
+        }
+
+        // add last point.
+        path.points.addPoint(childPath.points.getLastPoint());
+    }
+}
+
+/**
+ * Reconnects all subpaths.
+ */
+private void recombineSubpaths() {
+    for (int p = 0; p < orderedPaths.size(); p++) {
+        Path path = cast(Path)orderedPaths.get(p);
+        path.reconnectSubPaths();
+    }
+
+    orderedPaths.removeAll(subPaths);
+    workingPaths.removeAll(subPaths);
+    subPaths = null;
+}
+
+/**
+ * Removes the obstacle with the rectangle's bounds from the routing.
+ *
+ * @param rect the bounds of the obstacle to remove
+ * @return <code>true</code> if the removal has dirtied one or more paths
+ */
+public bool removeObstacle(Rectangle rect) {
+    return internalRemoveObstacle(rect);
+}
+
+/**
+ * Removes the given path from the routing.
+ *
+ * @param path the path to remove.
+ * @return <code>true</code> if the removal may have affected one of the remaining paths
+ */
+public bool removePath(Path path) {
+    userPaths.remove(path);
+    List children = cast(List)pathsToChildPaths.get(path);
+    if (children is null)
+        workingPaths.remove(path);
+    else
+        workingPaths.removeAll(children);
+    return true;
+}
+
+/**
+ * Resets exclude field on all obstacles
+ */
+private void resetObstacleExclusions() {
+    for (int i = 0; i < userObstacles.size(); i++)
+        (cast(Obstacle)userObstacles.get(i)).exclude = false;
+}
+
+/**
+ * Resets all vertices found on paths and obstacles.
+ */
+private void resetVertices() {
+    for (int i = 0; i < userObstacles.size(); i++) {
+        Obstacle obs = cast(Obstacle)userObstacles.get(i);
+        obs.reset();
+    }
+    for (int i = 0; i < workingPaths.size(); i++) {
+        Path path = cast(Path)workingPaths.get(i);
+        path.start.fullReset();
+        path.end.fullReset();
+    }
+}
+
+/**
+ * Sets the default spacing between paths. The spacing is the minimum distance that path
+ * should be offset from other paths or obstacles. The default value is 4. When this value
+ * can not be satisfied, paths will be squeezed together uniformly.
+ * @param spacing the path spacing
+ * @since 3.2
+ */
+public void setSpacing(int spacing) {
+    this.spacing = spacing;
+}
+
+/**
+ * Updates the points in the paths in order to represent the current solution
+ * with the given paths and obstacles.
+ *
+ * @return returns the list of paths which were updated.
+ */
+public List solve() {
+
+    solveDirtyPaths();
+
+    countVertices();
+    checkVertexIntersections();
+    growObstacles();
+
+    subPaths = new ArrayList();
+    stack = new PathStack();
+    labelPaths();
+    stack = null;
+
+    orderedPaths = new ArrayList();
+    orderPaths();
+    bendPaths();
+
+    recombineSubpaths();
+    orderedPaths = null;
+    subPaths = null;
+
+    recombineChildrenPaths();
+    cleanup();
+
+    return Collections.unmodifiableList(userPaths);
+}
+
+/**
+ * Solves paths that are dirty.
+ * @return number of dirty paths
+ */
+private int solveDirtyPaths() {
+    int numSolved = 0;
+
+    for (int i = 0; i < userPaths.size(); i++) {
+        Path path = cast(Path)userPaths.get(i);
+        if (!path.isDirty)
+            continue;
+        List children = cast(List)pathsToChildPaths.get(path);
+        int prevCount = 1, newCount = 1;
+        if (children is null)
+            children = Collections.EMPTY_LIST;
+        else
+            prevCount = children.size();
+
+        if (path.getBendPoints() !is null)
+            newCount = path.getBendPoints().size() + 1;
+
+        if (prevCount !is newCount)
+            children = regenerateChildPaths(path, children, prevCount, newCount);
+        refreshChildrenEndpoints(path, children);
+    }
+
+    for (int i = 0; i < workingPaths.size(); i++) {
+        Path path = cast(Path)workingPaths.get(i);
+        path.refreshExcludedObstacles(userObstacles);
+        if (!path.isDirty) {
+            path.resetPartial();
+            continue;
+        }
+
+        numSolved++;
+        path.fullReset();
+
+        bool pathFoundCheck = path.generateShortestPath(userObstacles);
+        if (!pathFoundCheck || path.end.cost > path.threshold) {
+            // path not found, or path found was too long
+            resetVertices();
+            path.fullReset();
+            path.threshold = 0;
+            pathFoundCheck = path.generateShortestPath(userObstacles);
+        }
+
+        resetVertices();
+    }
+
+    resetObstacleExclusions();
+
+    if (numSolved is 0)
+        resetVertices();
+
+    return numSolved;
+}
+
+/**
+ * @since 3.0
+ * @param path
+ * @param children
+ */
+private void refreshChildrenEndpoints(Path path, List children) {
+    Point previous = path.getStartPoint();
+    Point next;
+    PointList bendpoints = path.getBendPoints();
+    Path child;
+
+    for (int i = 0; i < children.size(); i++) {
+        if (i < bendpoints.size())
+            next = bendpoints.getPoint(i);
+        else
+            next = path.getEndPoint();
+        child = cast(Path)children.get(i);
+        child.setStartPoint(previous);
+        child.setEndPoint(next);
+        previous = next;
+    }
+}
+
+/**
+ * @since 3.0
+ * @param path
+ * @param children
+ */
+private List regenerateChildPaths(Path path, List children, int currentSize, int newSize) {
+    //Path used to be simple but now is compound, children is EMPTY.
+    if (currentSize is 1) {
+        workingPaths.remove(path);
+        currentSize = 0;
+        children = new ArrayList(newSize);
+        pathsToChildPaths.put(path, cast(Object)children);
+    } else
+    //Path is becoming simple but was compound.  children becomes empty.
+    if (newSize is 1) {
+        workingPaths.removeAll(children);
+        workingPaths.add(path);
+        pathsToChildPaths.remove(path);
+        return Collections.EMPTY_LIST;
+    }
+
+    //Add new working paths until the sizes are the same
+    while (currentSize < newSize) {
+        Path child = new Path();
+        workingPaths.add(child);
+        children.add(child);
+        currentSize++;
+    }
+
+    while (currentSize > newSize) {
+        Path child = cast(Path)children.remove(children.size() - 1);
+        workingPaths.remove(child);
+        currentSize--;
+    }
+
+    return children;
+}
+
+/**
+ * Tests a segment that has been offset for new intersections
+ * @param segment the segment
+ * @param index the index of the segment along the path
+ * @param path the path
+ * @return 1 if new segments have been inserted
+ */
+private int testOffsetSegmentForIntersections(Segment segment, int index, Path path) {
+    for (int i = 0; i < userObstacles.size(); i++) {
+        Obstacle obs = cast(Obstacle) userObstacles.get(i);
+
+        if (segment.end.obs is obs || segment.start.obs is obs || obs.exclude)
+            continue;
+        Vertex vertex = null;
+
+        int offset = getSpacing();
+        if (segment.getSlope() < 0) {
+            if (segment.intersects(obs.topLeft.x - offset,
+                    obs.topLeft.y - offset,
+                    obs.bottomRight.x + offset,
+                    obs.bottomRight.y + offset))
+                vertex = getNearestVertex(obs.topLeft, obs.bottomRight, segment);
+            else if (segment.intersects(obs.bottomLeft.x - offset,
+                    obs.bottomLeft.y + offset,
+                    obs.topRight.x + offset,
+                    obs.topRight.y - offset))
+                vertex = getNearestVertex(obs.bottomLeft, obs.topRight, segment);
+        } else {
+            if (segment.intersects(obs.bottomLeft.x - offset,
+                    obs.bottomLeft.y + offset,
+                    obs.topRight.x + offset,
+                    obs.topRight.y - offset))
+                vertex = getNearestVertex(obs.bottomLeft, obs.topRight, segment);
+            else if (segment.intersects(obs.topLeft.x - offset,
+                    obs.topLeft.y - offset,
+                    obs.bottomRight.x + offset,
+                    obs.bottomRight.y + offset))
+                vertex = getNearestVertex(obs.topLeft, obs.bottomRight, segment);
+        }
+
+        if (vertex !is null) {
+            Rectangle vRect = vertex.getDeformedRectangle(offset);
+            if (segment.end.obs !is null) {
+                Rectangle endRect = segment.end.getDeformedRectangle(offset);
+                if (vRect.intersects(endRect))
+                    continue;
+            }
+            if (segment.start.obs !is null) {
+                Rectangle startRect = segment.start.getDeformedRectangle(offset);
+                if (vRect.intersects(startRect))
+                    continue;
+            }
+
+            Segment newSegmentStart = new Segment(segment.start, vertex);
+            Segment newSegmentEnd = new Segment(vertex, segment.end);
+
+            vertex.totalCount++;
+            vertex.nearestObstacleChecked = false;
+
+            vertex.shrink();
+            checkVertexForIntersections(vertex);
+            vertex.grow();
+
+            if (vertex.nearestObstacle !is 0)
+                vertex.updateOffset();
+
+            growPassChangedObstacles = true;
+
+            if (index !is -1) {
+                path.grownSegments.remove(segment);
+                path.grownSegments.add(index, newSegmentStart);
+                path.grownSegments.add(index + 1, newSegmentEnd);
+            } else {
+                path.grownSegments.add(newSegmentStart);
+                path.grownSegments.add(newSegmentEnd);
+            }
+            return 1;
+        }
+    }
+    if (index is -1)
+        path.grownSegments.add(segment);
+    return 0;
+}
+
+/**
+ * Tests all paths against the given obstacle
+ * @param obs the obstacle
+ */
+private bool testAndDirtyPaths(Obstacle obs) {
+    bool result = false;
+    for (int i = 0; i < workingPaths.size(); i++) {
+        Path path = cast(Path)workingPaths.get(i);
+        result |= path.testAndSet(obs);
+    }
+    return result;
+}
+
+/**
+ * Updates the position of an existing obstacle.
+ * @param oldBounds the old bounds(used to find the obstacle)
+ * @param newBounds the new bounds
+ * @return <code>true</code> if the change the current results to become stale
+ */
+public bool updateObstacle(Rectangle oldBounds, Rectangle newBounds) {
+    bool result = internalRemoveObstacle(oldBounds);
+    result |= addObstacle(newBounds);
+    return result;
+}
+
+}