Mercurial > projects > dwt-addons

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

Find changesets by keywords (author, files, the commit message), revision number or hash, or revset expression.
Added Draw2d code, still work in progress
author Frank Benoit <benoit@tionex.de>
date Sun, 03 Aug 2008 00:52:14 +0200
parents
children 2d6540440fe6
comparison
equal deleted inserted replaced
96:b492ba44e44d 98:95307ad235d9
1 /*******************************************************************************
2 * Copyright (c) 2004, 2005 IBM Corporation and others.
3 * All rights reserved. This program and the accompanying materials
4 * are made available under the terms of the Eclipse Public License v1.0
5 * which accompanies this distribution, and is available at
6 * http://www.eclipse.org/legal/epl-v10.html
7 *
8 * Contributors:
9 * IBM Corporation - initial API and implementation
10 * Port to the D programming language:
11 * Frank Benoit <benoit@tionex.de>
12 *******************************************************************************/
13 module dwtx.draw2d.graph.Path;
14
15 import dwt.dwthelper.utils;
16 import dwtx.dwtxhelper.Collection;
17
18 import dwtx.draw2d.PositionConstants;
19 import dwtx.draw2d.geometry.Point;
20 import dwtx.draw2d.geometry.PointList;
21 import dwtx.draw2d.graph.Segment;
22 import dwtx.draw2d.graph.Vertex;
23 import dwtx.draw2d.graph.Obstacle;
24
25 /**
26 * A Path representation for the ShortestPathRouting. A Path has a start and end point
27 * and may have bendpoints. The output of a path is accessed via the method
28 * <code>getPoints()</code>.
29 *
30 * This class is for internal use only.
31 * @author Whitney Sorenson
32 * @since 3.0
33 */
34 public class Path {
35
36 /**
37 * A Stack of segments.
38 */
39 private static class SegmentStack : ArrayList {
40
41 Segment pop() {
42 return cast(Segment)remove(size() - 1);
43 }
44
45 Obstacle popObstacle() {
46 return cast(Obstacle)remove(size() - 1);
47 }
48
49 void push(Object obj) {
50 add(obj);
51 }
52
53 }
54
55 private static const Point CURRENT;
56 private static const double EPSILON = 1.04;
57 private static const Point NEXT;
58 private static const double OVAL_CONSTANT = 1.13;
59
60 static this(){
61 CURRENT = new Point();
62 NEXT = new Point();
63 }
64
65 /**
66 * The bendpoint constraints. The path must go through these bendpoints.
67 */
68 PointList bendpoints;
69 /**
70 * An arbitrary data field which can be used to map a Path back to some client object.
71 */
72 public Object data;
73 List excludedObstacles;
74 List grownSegments;
75 /**
76 * this field is for internal use only. It is true whenever a property has been changed
77 * which requires the solver to resolve this path.
78 */
79 public bool isDirty = true;
80
81 bool isInverted = false;
82 bool isMarked = false;
83 PointList points;
84
85 /**
86 * The previous cost ratio of the path. The cost ratio is the actual path length divided
87 * by the length from the start to the end.
88 */
89 private double prevCostRatio;
90 List segments;
91
92 private SegmentStack stack;
93 Vertex start, end;
94 private Path subPath;
95 double threshold;
96 Set visibleObstacles;
97 Set visibleVertices;
98
99 /**
100 * Constructs a new path.
101 * @since 3.0
102 */
103 public this() {
104 segments = new ArrayList();
105 grownSegments = new ArrayList();
106 points = new PointList();
107 visibleVertices = new HashSet();
108 stack = new SegmentStack();
109 visibleObstacles = new HashSet();
110 excludedObstacles = new ArrayList();
111 }
112
113 /**
114 * Constructs a new path with the given data.
115 * @since 3.0
116 * @param data an arbitrary data field
117 */
118 public this(Object data) {
119 this();
120 this.data = data;
121 }
122
123 /**
124 * Constructs a new path with the given data, start and end point.
125 *
126 * @param start the start point for this path
127 * @param end the end point for this path
128 */
129 public this(Point start, Point end) {
130 this(new Vertex(start, null), new Vertex(end, null));
131 }
132
133 /**
134 * Creates a path between the given vertices.
135 *
136 * @param start start vertex
137 * @param end end vertex
138 */
139 this(Vertex start, Vertex end) {
140 this();
141 this.start = start;
142 this.end = end;
143 }
144
145 /**
146 * Attempts to add all segments between the given obstacles to the visibility graph.
147 * @param source the source obstacle
148 * @param target the target obstacle
149 */
150 private void addAllSegmentsBetween(Obstacle source, Obstacle target) {
151 addConnectingSegment(new Segment(source.bottomLeft, target.bottomLeft),
152 source, target, false, false);
153 addConnectingSegment(new Segment(source.bottomRight, target.bottomRight),
154 source, target, true, true);
155 addConnectingSegment(new Segment(source.topLeft, target.topLeft),
156 source, target, true, true);
157 addConnectingSegment(new Segment(source.topRight, target.topRight),
158 source, target, false, false);
159
160 if (source.bottom() is target.bottom()) {
161 addConnectingSegment(new Segment(source.bottomLeft, target.bottomRight),
162 source, target, false, true);
163 addConnectingSegment(new Segment(source.bottomRight, target.bottomLeft),
164 source, target, true, false);
165 }
166 if (source.y is target.y) {
167 addConnectingSegment(new Segment(source.topLeft, target.topRight),
168 source, target, true, false);
169 addConnectingSegment(new Segment(source.topRight, target.topLeft),
170 source, target, false, true);
171 }
172 if (source.x is target.x) {
173 addConnectingSegment(new Segment(source.bottomLeft, target.topLeft),
174 source, target, false, true);
175 addConnectingSegment(new Segment(source.topLeft, target.bottomLeft),
176 source, target, true, false);
177 }
178 if (source.right() is target.right()) {
179 addConnectingSegment(new Segment(source.bottomRight, target.topRight),
180 source, target, true, false);
181 addConnectingSegment(new Segment(source.topRight, target.bottomRight),
182 source, target, false, true);
183 }
184 }
185
186 /**
187 * Attempts to add a segment between the given obstacles to the visibility graph. This
188 * method is specifically written for the case where the two obstacles intersect and contains
189 * a bool as to whether to check the diagonal that includes the top right point of the
190 * other obstacle.
191 *
192 * @param segment the segment to check
193 * @param o1 the first obstacle
194 * @param o2 the second obstacle
195 * @param checkTopRight1 whether or not to check the diagonal containing top right point
196 */
197 private void addConnectingSegment(Segment segment, Obstacle o1, Obstacle o2,
198 bool checkTopRight1, bool checkTopRight2) {
199 if (threshold !is 0
200 && (segment.end.getDistance(end) + segment.end.getDistance(start) > threshold
201 || segment.start.getDistance(end) + segment.start.getDistance(start) > threshold))
202 return;
203
204 if (o2.containsProper(segment.start) || o1.containsProper(segment.end))
205 return;
206
207 if (checkTopRight1 && segment.intersects(o1.x, o1.bottom() - 1, o1.right() - 1, o1.y))
208 return;
209 if (checkTopRight2 && segment.intersects(o2.x, o2.bottom() - 1, o2.right() - 1, o2.y))
210 return;
211 if (!checkTopRight1 && segment.intersects(o1.x, o1.y, o1.right() - 1, o1.bottom() - 1))
212 return;
213 if (!checkTopRight2 && segment.intersects(o2.x, o2.y, o2.right() - 1, o2.bottom() - 1))
214 return;
215
216 stack.push(o1);
217 stack.push(o2);
218 stack.push(segment);
219 }
220
221 /**
222 * Adds an obstacle to the visibility graph and generates new segments
223 * @param newObs the new obstacle, should not be in the graph already
224 */
225 private void addObstacle(Obstacle newObs) {
226 visibleObstacles.add(newObs);
227 Iterator oItr = (new HashSet(visibleObstacles)).iterator();
228 while (oItr.hasNext()) {
229 Obstacle currObs = cast(Obstacle)oItr.next();
230 if (newObs !is currObs)
231 addSegmentsFor(newObs, currObs);
232 }
233 addPerimiterSegments(newObs);
234 addSegmentsFor(start, newObs);
235 addSegmentsFor(end, newObs);
236 }
237
238 /**
239 * Adds the segments along the perimiter of an obstacle to the visiblity graph queue.
240 * @param obs the obstacle
241 */
242 private void addPerimiterSegments(Obstacle obs) {
243 Segment seg = new Segment(obs.topLeft, obs.topRight);
244 stack.push(obs);
245 stack.push(null);
246 stack.push(seg);
247 seg = new Segment(obs.topRight, obs.bottomRight);
248 stack.push(obs);
249 stack.push(null);
250 stack.push(seg);
251 seg = new Segment(obs.bottomRight, obs.bottomLeft);
252 stack.push(obs);
253 stack.push(null);
254 stack.push(seg);
255 seg = new Segment(obs.bottomLeft, obs.topLeft);
256 stack.push(obs);
257 stack.push(null);
258 stack.push(seg);
259 }
260
261 /**
262 * Attempts to add a segment to the visibility graph.
263 * First checks to see if the segment is outside the threshold oval. Then it compares the segment
264 * against all obstacles. If it is clean, the segment is finally added to the graph.
265 *
266 * @param segment the segment
267 * @param exclude1 an obstacle to exclude from the search
268 * @param exclude2 another obstacle to exclude from the search
269 * @param allObstacles the list of all obstacles
270 */
271 private void addSegment(Segment segment, Obstacle exclude1, Obstacle exclude2, List allObstacles) {
272 if (threshold !is 0
273 && (segment.end.getDistance(end) + segment.end.getDistance(start) > threshold
274 || segment.start.getDistance(end) + segment.start.getDistance(start) > threshold))
275 return;
276
277 for (int i = 0; i < allObstacles.size(); i++) {
278 Obstacle obs = cast(Obstacle)allObstacles.get(i);
279
280 if (obs is exclude1 || obs is exclude2 || obs.exclude)
281 continue;
282
283 if (segment.intersects(obs.x, obs.y, obs.right() - 1, obs.bottom() - 1)
284 || segment.intersects(obs.x, obs.bottom() - 1, obs.right() - 1, obs.y)
285 || obs.containsProper(segment.start)
286 || obs.containsProper(segment.end)) {
287 if (!visibleObstacles.contains(obs))
288 addObstacle(obs);
289 return;
290 }
291 }
292
293 linkVertices(segment);
294 }
295
296 /**
297 * Adds the segments between the given obstacles.
298 * @param source source obstacle
299 * @param target target obstacle
300 */
301 private void addSegmentsFor(Obstacle source, Obstacle target) {
302 if (source.intersects(target))
303 addAllSegmentsBetween(source, target);
304 else if (target.bottom() - 1 < source.y)
305 addSegmentsTargetAboveSource(source, target);
306 else if (source.bottom() - 1 < target.y)
307 addSegmentsTargetAboveSource(target, source);
308 else if (target.right() - 1 < source.x)
309 addSegmentsTargetBesideSource(source, target);
310 else
311 addSegmentsTargetBesideSource(target, source);
312 }
313
314 /**
315 * Adds the segments between the given obstacles.
316 * @param source source obstacle
317 * @param target target obstacle
318 */
319 private void addSegmentsFor(Vertex vertex, Obstacle obs) {
320 Segment seg = null;
321 Segment seg2 = null;
322
323 switch (obs.getPosition(vertex)) {
324 case PositionConstants.SOUTH_WEST :
325 case PositionConstants.NORTH_EAST :
326 seg = new Segment(vertex, obs.topLeft);
327 seg2 = new Segment(vertex, obs.bottomRight);
328 break;
329 case PositionConstants.SOUTH_EAST :
330 case PositionConstants.NORTH_WEST :
331 seg = new Segment(vertex, obs.topRight);
332 seg2 = new Segment(vertex, obs.bottomLeft);
333 break;
334 case PositionConstants.NORTH :
335 seg = new Segment(vertex, obs.topLeft);
336 seg2 = new Segment(vertex, obs.topRight);
337 break;
338 case PositionConstants.EAST :
339 seg = new Segment(vertex, obs.bottomRight);
340 seg2 = new Segment(vertex, obs.topRight);
341 break;
342 case PositionConstants.SOUTH :
343 seg = new Segment(vertex, obs.bottomRight);
344 seg2 = new Segment(vertex, obs.bottomLeft);
345 break;
346 case PositionConstants.WEST :
347 seg = new Segment(vertex, obs.topLeft);
348 seg2 = new Segment(vertex, obs.bottomLeft);
349 break;
350 default:
351 if (vertex.x is obs.x) {
352 seg = new Segment(vertex, obs.topLeft);
353 seg2 = new Segment(vertex, obs.bottomLeft);
354 } else if (vertex.y is obs.y) {
355 seg = new Segment(vertex, obs.topLeft);
356 seg2 = new Segment(vertex, obs.topRight);
357 } else if (vertex.y is obs.bottom() - 1) {
358 seg = new Segment(vertex, obs.bottomLeft);
359 seg2 = new Segment(vertex, obs.bottomRight);
360 } else if (vertex.x is obs.right() - 1) {
361 seg = new Segment(vertex, obs.topRight);
362 seg2 = new Segment(vertex, obs.bottomRight);
363 } else {
364 throw new RuntimeException("Unexpected vertex conditions"); //$NON-NLS-1$
365 }
366 }
367
368 stack.push(obs);
369 stack.push(null);
370 stack.push(seg);
371 stack.push(obs);
372 stack.push(null);
373 stack.push(seg2);
374 }
375
376 private void addSegmentsTargetAboveSource(Obstacle source, Obstacle target) {
377 //target located above source
378 Segment seg = null;
379 Segment seg2 = null;
380 if (target.x > source.x) {
381 seg = new Segment(source.topLeft, target.topLeft);
382 if (target.x < source.right() - 1)
383 seg2 = new Segment(source.topRight, target.bottomLeft);
384 else
385 seg2 = new Segment(source.bottomRight, target.topLeft);
386 } else if (source.x is target.x) {
387 seg = new Segment(source.topLeft, target.bottomLeft);
388 seg2 = new Segment(source.topRight, target.bottomLeft);
389 } else {
390 seg = new Segment(source.bottomLeft, target.bottomLeft);
391 seg2 = new Segment(source.topRight, target.bottomLeft);
392 }
393
394 stack.push(source);
395 stack.push(target);
396 stack.push(seg);
397 stack.push(source);
398 stack.push(target);
399 stack.push(seg2);
400 seg = null;
401 seg2 = null;
402
403 if (target.right() < source.right()) {
404 seg = new Segment(source.topRight, target.topRight);
405 if (target.right() - 1 > source.x)
406 seg2 = new Segment(source.topLeft, target.bottomRight);
407 else
408 seg2 = new Segment(source.bottomLeft, target.topRight);
409 } else if (source.right() is target.right()) {
410 seg = new Segment(source.topRight, target.bottomRight);
411 seg2 = new Segment(source.topLeft, target.bottomRight);
412 } else {
413 seg = new Segment(source.bottomRight, target.bottomRight);
414 seg2 = new Segment(source.topLeft, target.bottomRight);
415 }
416
417 stack.push(source);
418 stack.push(target);
419 stack.push(seg);
420 stack.push(source);
421 stack.push(target);
422 stack.push(seg2);
423 }
424
425 private void addSegmentsTargetBesideSource(Obstacle source, Obstacle target) {
426 //target located above source
427 Segment seg = null;
428 Segment seg2 = null;
429 if (target.y > source.y) {
430 seg = new Segment(source.topLeft, target.topLeft);
431 if (target.y < source.bottom() - 1)
432 seg2 = new Segment(source.bottomLeft, target.topRight);
433 else
434 seg2 = new Segment(source.bottomRight, target.topLeft);
435 } else if (source.y is target.y) {
436 //degenerate case
437 seg = new Segment(source.topLeft, target.topRight);
438 seg2 = new Segment(source.bottomLeft, target.topRight);
439 } else {
440 seg = new Segment(source.topRight, target.topRight);
441 seg2 = new Segment(source.bottomLeft, target.topRight);
442 }
443 stack.push(source);
444 stack.push(target);
445 stack.push(seg);
446 stack.push(source);
447 stack.push(target);
448 stack.push(seg2);
449 seg = null;
450 seg2 = null;
451
452 if (target.bottom() < source.bottom()) {
453 seg = new Segment(source.bottomLeft, target.bottomLeft);
454 if (target.bottom() - 1 > source.y)
455 seg2 = new Segment(source.topLeft, target.bottomRight);
456 else
457 seg2 = new Segment(source.topRight, target.bottomLeft);
458 } else if (source.bottom() is target.bottom()) {
459 seg = new Segment(source.bottomLeft, target.bottomRight);
460 seg2 = new Segment(source.topLeft, target.bottomRight);
461 } else {
462 seg = new Segment(source.bottomRight, target.bottomRight);
463 seg2 = new Segment(source.topLeft, target.bottomRight);
464 }
465 stack.push(source);
466 stack.push(target);
467 stack.push(seg);
468 stack.push(source);
469 stack.push(target);
470 stack.push(seg2);
471 }
472
473 /**
474 *
475 */
476 void cleanup() {
477 //segments.clear();
478 visibleVertices.clear();
479 }
480
481 /**
482 * Begins the creation of the visibility graph with the first segment
483 * @param allObstacles list of all obstacles
484 */
485 private void createVisibilityGraph(List allObstacles) {
486 stack.push(null);
487 stack.push(null);
488 stack.push(new Segment(start, end));
489
490 while (!stack.isEmpty())
491 addSegment(stack.pop(), stack.popObstacle(), stack.popObstacle(), allObstacles);
492 }
493
494 /**
495 * Once the visibility graph is constructed, this is called to label the graph and
496 * determine the shortest path. Returns false if no path can be found.
497 *
498 * @return true if a path can be found.
499 */
500 private bool determineShortestPath() {
501 if (!labelGraph())
502 return false;
503 Vertex vertex = end;
504 prevCostRatio = end.cost / start.getDistance(end);
505
506 Vertex nextVertex;
507 while (!vertex.opEquals(start)) {
508 nextVertex = vertex.label;
509 if (nextVertex is null)
510 return false;
511 Segment s = new Segment(nextVertex, vertex);
512 segments.add(s);
513 vertex = nextVertex;
514 }
515
516 Collections.reverse(segments);
517 return true;
518 }
519
520 /**
521 * Resets all necessary fields for a solve.
522 */
523 void fullReset() {
524 visibleVertices.clear();
525 segments.clear();
526 if (prevCostRatio is 0) {
527 double distance = start.getDistance(end);
528 threshold = distance * OVAL_CONSTANT;
529 } else
530 threshold = prevCostRatio * EPSILON * start.getDistance(end);
531 visibleObstacles.clear();
532 resetPartial();
533 }
534
535 /**
536 * Creates the visibility graph and returns whether or not a shortest path could be
537 * determined.
538 *
539 * @param allObstacles the list of all obstacles
540 * @return true if a shortest path was found
541 */
542 bool generateShortestPath(List allObstacles) {
543 createVisibilityGraph(allObstacles);
544
545 if (visibleVertices.size() is 0)
546 return false;
547
548 return determineShortestPath();
549 }
550
551 /**
552 * Returns the list of constrained points through which this path must pass or
553 * <code>null</code>.
554 * @see #setBendPoints(PointList)
555 * @return list of bend points
556 */
557 public PointList getBendPoints() {
558 return bendpoints;
559 }
560
561 /**
562 * Returns the end point for this path
563 * @return end point for this path
564 */
565 public Point getEndPoint() {
566 return end;
567 }
568
569 /**
570 * Returns the solution to this path.
571 *
572 * @return the points for this path.
573 */
574 public PointList getPoints() {
575 return points;
576 }
577
578 /**
579 * Returns the start point for this path
580 * @return start point for this path
581 */
582 public Point getStartPoint() {
583 return start;
584 }
585
586 /**
587 * Returns a subpath for this path at the given segment
588 *
589 * @param currentSegment the segment at which the subpath should be created
590 * @return the new path
591 */
592 Path getSubPath(Segment currentSegment) {
593 // ready new path
594 Path newPath = new Path(currentSegment.start, end);
595 newPath.grownSegments = new ArrayList(grownSegments.subList(
596 grownSegments.indexOf(currentSegment),
597 grownSegments.size()));
598
599 // fix old path
600 grownSegments = new ArrayList(grownSegments.subList(
601 0, grownSegments.indexOf(currentSegment) + 1));
602 end = currentSegment.end;
603
604 subPath = newPath;
605 return newPath;
606 }
607
608 /**
609 * Resets the vertices that this path has traveled prior to this segment. This is called
610 * when the path has become inverted and needs to rectify any labeling mistakes it made
611 * before it knew it was inverted.
612 * @param currentSegment the segment at which the path found it was inverted
613 */
614 void invertPriorVertices(Segment currentSegment) {
615 int stop = grownSegments.indexOf(currentSegment);
616 for (int i = 0; i < stop; i++) {
617 Vertex vertex = (cast(Segment)grownSegments.get(i)).end;
618 if (vertex.type is Vertex.INNIE)
619 vertex.type = Vertex.OUTIE;
620 else
621 vertex.type = Vertex.INNIE;
622 }
623 }
624
625 /**
626 * Returns true if this obstacle is in the visibility graph
627 * @param obs the obstacle
628 * @return true if obstacle is in the visibility graph
629 */
630 bool isObstacleVisible(Obstacle obs) {
631 return visibleObstacles.contains(obs);
632 }
633
634 /**
635 * Labels the visibility graph to assist in finding the shortest path
636 * @return false if there was a gap in the visibility graph
637 */
638 private bool labelGraph() {
639 int numPermanentNodes = 1;
640 Vertex vertex = start;
641 Vertex neighborVertex = null;
642 vertex.isPermanent = true;
643 double newCost;
644 while (numPermanentNodes !is visibleVertices.size()) {
645 List neighbors = vertex.neighbors;
646 if (neighbors is null)
647 return false;
648 // label neighbors if they have a new shortest path
649 for (int i = 0; i < neighbors.size(); i++) {
650 neighborVertex = cast(Vertex)neighbors.get(i);
651 if (!neighborVertex.isPermanent) {
652 newCost = vertex.cost + vertex.getDistance(neighborVertex);
653 if (neighborVertex.label is null) {
654 neighborVertex.label = vertex;
655 neighborVertex.cost = newCost;
656 } else if (neighborVertex.cost > newCost) {
657 neighborVertex.label = vertex;
658 neighborVertex.cost = newCost;
659 }
660 }
661 }
662 // find the next none-permanent, labeled vertex with smallest cost
663 double smallestCost = 0;
664 Vertex tempVertex = null;
665 Iterator v = visibleVertices.iterator();
666 while (v.hasNext()) {
667 tempVertex = cast(Vertex)v.next();
668 if (!tempVertex.isPermanent && tempVertex.label !is null
669 && (tempVertex.cost < smallestCost || smallestCost is 0)) {
670 smallestCost = tempVertex.cost;
671 vertex = tempVertex;
672 }
673 }
674 // set the new vertex to permanent.
675 vertex.isPermanent = true;
676 numPermanentNodes++;
677 }
678 return true;
679 }
680
681 /**
682 * Links two vertices together in the visibility graph
683 * @param segment the segment to add
684 */
685 private void linkVertices(Segment segment) {
686 if (segment.start.neighbors is null)
687 segment.start.neighbors = new ArrayList();
688 if (segment.end.neighbors is null)
689 segment.end.neighbors = new ArrayList();
690
691 if (!segment.start.neighbors.contains(segment.end)) {
692 segment.start.neighbors.add(segment.end);
693 segment.end.neighbors.add(segment.start);
694 }
695
696 visibleVertices.add(segment.start);
697 visibleVertices.add(segment.end);
698 }
699
700 /**
701 * Called to reconnect a subpath back onto this path. Does a depth-first search to
702 * reconnect all paths. Should be called after sorting.
703 */
704 void reconnectSubPaths() {
705 if (subPath !is null) {
706 subPath.reconnectSubPaths();
707
708 Segment changedSegment = cast(Segment)subPath.grownSegments.remove(0);
709 Segment oldSegment = cast(Segment)grownSegments.get(grownSegments.size() - 1);
710
711 oldSegment.end = changedSegment.end;
712 grownSegments.addAll(subPath.grownSegments);
713
714 subPath.points.removePoint(0);
715 points.removePoint(points.size() - 1);
716 points.addAll(subPath.points);
717
718 visibleObstacles.addAll(subPath.visibleObstacles);
719
720 end = subPath.end;
721 subPath = null;
722 }
723 }
724
725
726 /**
727 * Refreshes the exclude field on the obstacles in the list. Excludes all obstacles
728 * that contain the start or end point for this path.
729 * @param allObstacles list of all obstacles
730 */
731 void refreshExcludedObstacles(List allObstacles) {
732 excludedObstacles.clear();
733
734 for (int i = 0; i < allObstacles.size(); i++) {
735 Obstacle o = cast(Obstacle)allObstacles.get(i);
736 o.exclude = false;
737
738 if (o.contains(start)) {
739 if (o.containsProper(start))
740 o.exclude = true;
741 else {
742 /*
743 * $TODO Check for corners. If the path begins exactly at the corner of
744 * an obstacle, the exclude should also be true.
745 *
746 * Or, change segment intersection so that two segments that share an
747 * endpoint do not intersect.
748 */
749 }
750 }
751
752 if (o.contains(end)) {
753 if (o.containsProper(end))
754 o.exclude = true;
755 else {
756 //check for corners. See above statement.
757 }
758 }
759
760 if (o.exclude && !excludedObstacles.contains(o))
761 excludedObstacles.add(o);
762 }
763 }
764
765 /**
766 * Resets the fields for everything in the solve after the visibility graph steps.
767 */
768 void resetPartial() {
769 isMarked = false;
770 isInverted = false;
771 subPath = null;
772 isDirty = false;
773 grownSegments.clear();
774 points.removeAllPoints();
775 }
776
777 /**
778 * Sets the list of bend points to the given list and dirties the path.
779 * @param bendPoints the list of bend points
780 */
781 public void setBendPoints(PointList bendPoints) {
782 this.bendpoints = bendPoints;
783 isDirty = true;
784 }
785
786 /**
787 * Sets the end point for this path to the given point.
788 * @param end the new end point for this path
789 */
790 public void setEndPoint(Point end) {
791 if (end.opEquals(this.end))
792 return;
793 this.end = new Vertex(end, null);
794 isDirty = true;
795 }
796
797 /**
798 * Sets the start point for this path to the given point.
799 * @param start the new start point for this path
800 */
801 public void setStartPoint(Point start) {
802 if (start.opEquals(this.start))
803 return;
804 this.start = new Vertex(start, null);
805 isDirty = true;
806 }
807
808 /**
809 * Returns <code>true</code> if the path is clean and intersects the given obstacle. Also
810 * dirties the path in the process.
811 * @since 3.0
812 * @param obs the obstacle
813 * @return <code>true</code> if a clean path touches the obstacle
814 */
815 bool testAndSet(Obstacle obs) {
816 if (isDirty)
817 return false;
818 //This will never actually happen because obstacles are not stored by identity
819 if (excludedObstacles.contains(obs))
820 return false;
821
822 Segment seg1 = new Segment(obs.topLeft, obs.bottomRight);
823 Segment seg2 = new Segment(obs.topRight, obs.bottomLeft);
824
825 for (int s = 0; s < points.size() - 1; s++) {
826 points.getPoint(CURRENT, s);
827 points.getPoint(NEXT, s + 1);
828
829 if (seg1.intersects(CURRENT, NEXT) || seg2.intersects(CURRENT, NEXT)
830 || obs.contains(CURRENT) || obs.contains(NEXT)) {
831 isDirty = true;
832 return true;
833 }
834 }
835 return false;
836 }
837
838 }