projects/dwt-addons: dwtx/draw2d/graph/ShortestPathRouter.d comparison

comparison dwtx/draw2d/graph/ShortestPathRouter.d @ 98:95307ad235d9

Added Draw2d code, still work in progress

author	Frank Benoit <benoit@tionex.de>
date	Sun, 03 Aug 2008 00:52:14 +0200
parents
children

comparison

equal deleted inserted replaced

-:b492ba44e44d
+:95307ad235d9
+/*******************************************************************************
+* 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;
+}
+}

Mercurial > projects > dwt-addons

comparison dwtx/draw2d/graph/ShortestPathRouter.d @ 98:95307ad235d9