projects/dwt-addons: dwtx/draw2d/graph/Path.d annotate

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

rev	line source
98 95307ad235d9 Added Draw2d code, still work in progress Frank Benoit <benoit@tionex.de> parents: diff changeset	1 /*******************************************************************************
95307ad235d9 Added Draw2d code, still work in progress Frank Benoit <benoit@tionex.de> parents: diff changeset	2 * Copyright (c) 2004, 2005 IBM Corporation and others.
95307ad235d9 Added Draw2d code, still work in progress Frank Benoit <benoit@tionex.de> parents: diff changeset	3 * All rights reserved. This program and the accompanying materials
95307ad235d9 Added Draw2d code, still work in progress Frank Benoit <benoit@tionex.de> parents: diff changeset	4 * are made available under the terms of the Eclipse Public License v1.0
95307ad235d9 Added Draw2d code, still work in progress Frank Benoit <benoit@tionex.de> parents: diff changeset	5 * which accompanies this distribution, and is available at
95307ad235d9 Added Draw2d code, still work in progress Frank Benoit <benoit@tionex.de> parents: diff changeset	6 * http://www.eclipse.org/legal/epl-v10.html
95307ad235d9 Added Draw2d code, still work in progress Frank Benoit <benoit@tionex.de> parents: diff changeset	7 *
95307ad235d9 Added Draw2d code, still work in progress Frank Benoit <benoit@tionex.de> parents: diff changeset	8 * Contributors:
95307ad235d9 Added Draw2d code, still work in progress Frank Benoit <benoit@tionex.de> parents: diff changeset	9 * IBM Corporation - initial API and implementation
95307ad235d9 Added Draw2d code, still work in progress Frank Benoit <benoit@tionex.de> parents: diff changeset	10 * Port to the D programming language:
95307ad235d9 Added Draw2d code, still work in progress Frank Benoit <benoit@tionex.de> parents: diff changeset	11 * Frank Benoit <benoit@tionex.de>
95307ad235d9 Added Draw2d code, still work in progress Frank Benoit <benoit@tionex.de> parents: diff changeset	12 *******************************************************************************/
95307ad235d9 Added Draw2d code, still work in progress Frank Benoit <benoit@tionex.de> parents: diff changeset	13 module dwtx.draw2d.graph.Path;
95307ad235d9 Added Draw2d code, still work in progress Frank Benoit <benoit@tionex.de> parents: diff changeset	14
95307ad235d9 Added Draw2d code, still work in progress Frank Benoit <benoit@tionex.de> parents: diff changeset	15 import dwt.dwthelper.utils;
95307ad235d9 Added Draw2d code, still work in progress Frank Benoit <benoit@tionex.de> parents: diff changeset	16 import dwtx.dwtxhelper.Collection;
95307ad235d9 Added Draw2d code, still work in progress Frank Benoit <benoit@tionex.de> parents: diff changeset	17
95307ad235d9 Added Draw2d code, still work in progress Frank Benoit <benoit@tionex.de> parents: diff changeset	18 import dwtx.draw2d.PositionConstants;
95307ad235d9 Added Draw2d code, still work in progress Frank Benoit <benoit@tionex.de> parents: diff changeset	19 import dwtx.draw2d.geometry.Point;
95307ad235d9 Added Draw2d code, still work in progress Frank Benoit <benoit@tionex.de> parents: diff changeset	20 import dwtx.draw2d.geometry.PointList;
95307ad235d9 Added Draw2d code, still work in progress Frank Benoit <benoit@tionex.de> parents: diff changeset	21 import dwtx.draw2d.graph.Segment;
95307ad235d9 Added Draw2d code, still work in progress Frank Benoit <benoit@tionex.de> parents: diff changeset	22 import dwtx.draw2d.graph.Vertex;
95307ad235d9 Added Draw2d code, still work in progress Frank Benoit <benoit@tionex.de> parents: diff changeset	23 import dwtx.draw2d.graph.Obstacle;
95307ad235d9 Added Draw2d code, still work in progress Frank Benoit <benoit@tionex.de> parents: diff changeset	24
95307ad235d9 Added Draw2d code, still work in progress Frank Benoit <benoit@tionex.de> parents: diff changeset	25 /**
95307ad235d9 Added Draw2d code, still work in progress Frank Benoit <benoit@tionex.de> parents: diff changeset	26 * A Path representation for the ShortestPathRouting. A Path has a start and end point
95307ad235d9 Added Draw2d code, still work in progress Frank Benoit <benoit@tionex.de> parents: diff changeset	27 * and may have bendpoints. The output of a path is accessed via the method
95307ad235d9 Added Draw2d code, still work in progress Frank Benoit <benoit@tionex.de> parents: diff changeset	28 * <code>getPoints()</code>.
95307ad235d9 Added Draw2d code, still work in progress Frank Benoit <benoit@tionex.de> parents: diff changeset	29 *
95307ad235d9 Added Draw2d code, still work in progress Frank Benoit <benoit@tionex.de> parents: diff changeset	30 * This class is for internal use only.
95307ad235d9 Added Draw2d code, still work in progress Frank Benoit <benoit@tionex.de> parents: diff changeset	31 * @author Whitney Sorenson
95307ad235d9 Added Draw2d code, still work in progress Frank Benoit <benoit@tionex.de> parents: diff changeset	32 * @since 3.0
95307ad235d9 Added Draw2d code, still work in progress Frank Benoit <benoit@tionex.de> parents: diff changeset	33 */
95307ad235d9 Added Draw2d code, still work in progress Frank Benoit <benoit@tionex.de> parents: diff changeset	34 public class Path {
95307ad235d9 Added Draw2d code, still work in progress Frank Benoit <benoit@tionex.de> parents: diff changeset	35
95307ad235d9 Added Draw2d code, still work in progress Frank Benoit <benoit@tionex.de> parents: diff changeset	36 /**
95307ad235d9 Added Draw2d code, still work in progress Frank Benoit <benoit@tionex.de> parents: diff changeset	37 * A Stack of segments.
95307ad235d9 Added Draw2d code, still work in progress Frank Benoit <benoit@tionex.de> parents: diff changeset	38 */
95307ad235d9 Added Draw2d code, still work in progress Frank Benoit <benoit@tionex.de> parents: diff changeset	39 private static class SegmentStack : ArrayList {
95307ad235d9 Added Draw2d code, still work in progress Frank Benoit <benoit@tionex.de> parents: diff changeset	40
95307ad235d9 Added Draw2d code, still work in progress Frank Benoit <benoit@tionex.de> parents: diff changeset	41 Segment pop() {
95307ad235d9 Added Draw2d code, still work in progress Frank Benoit <benoit@tionex.de> parents: diff changeset	42 return cast(Segment)remove(size() - 1);
95307ad235d9 Added Draw2d code, still work in progress Frank Benoit <benoit@tionex.de> parents: diff changeset	43 }
95307ad235d9 Added Draw2d code, still work in progress Frank Benoit <benoit@tionex.de> parents: diff changeset	44
95307ad235d9 Added Draw2d code, still work in progress Frank Benoit <benoit@tionex.de> parents: diff changeset	45 Obstacle popObstacle() {
95307ad235d9 Added Draw2d code, still work in progress Frank Benoit <benoit@tionex.de> parents: diff changeset	46 return cast(Obstacle)remove(size() - 1);
95307ad235d9 Added Draw2d code, still work in progress Frank Benoit <benoit@tionex.de> parents: diff changeset	47 }
95307ad235d9 Added Draw2d code, still work in progress Frank Benoit <benoit@tionex.de> parents: diff changeset	48
95307ad235d9 Added Draw2d code, still work in progress Frank Benoit <benoit@tionex.de> parents: diff changeset	49 void push(Object obj) {
95307ad235d9 Added Draw2d code, still work in progress Frank Benoit <benoit@tionex.de> parents: diff changeset	50 add(obj);
95307ad235d9 Added Draw2d code, still work in progress Frank Benoit <benoit@tionex.de> parents: diff changeset	51 }
95307ad235d9 Added Draw2d code, still work in progress Frank Benoit <benoit@tionex.de> parents: diff changeset	52
95307ad235d9 Added Draw2d code, still work in progress Frank Benoit <benoit@tionex.de> parents: diff changeset	53 }
95307ad235d9 Added Draw2d code, still work in progress Frank Benoit <benoit@tionex.de> parents: diff changeset	54
95307ad235d9 Added Draw2d code, still work in progress Frank Benoit <benoit@tionex.de> parents: diff changeset	55 private static const Point CURRENT;
95307ad235d9 Added Draw2d code, still work in progress Frank Benoit <benoit@tionex.de> parents: diff changeset	56 private static const double EPSILON = 1.04;
95307ad235d9 Added Draw2d code, still work in progress Frank Benoit <benoit@tionex.de> parents: diff changeset	57 private static const Point NEXT;
95307ad235d9 Added Draw2d code, still work in progress Frank Benoit <benoit@tionex.de> parents: diff changeset	58 private static const double OVAL_CONSTANT = 1.13;
95307ad235d9 Added Draw2d code, still work in progress Frank Benoit <benoit@tionex.de> parents: diff changeset	59
95307ad235d9 Added Draw2d code, still work in progress Frank Benoit <benoit@tionex.de> parents: diff changeset	60 static this(){
95307ad235d9 Added Draw2d code, still work in progress Frank Benoit <benoit@tionex.de> parents: diff changeset	61 CURRENT = new Point();
95307ad235d9 Added Draw2d code, still work in progress Frank Benoit <benoit@tionex.de> parents: diff changeset	62 NEXT = new Point();
95307ad235d9 Added Draw2d code, still work in progress Frank Benoit <benoit@tionex.de> parents: diff changeset	63 }
95307ad235d9 Added Draw2d code, still work in progress Frank Benoit <benoit@tionex.de> parents: diff changeset	64
95307ad235d9 Added Draw2d code, still work in progress Frank Benoit <benoit@tionex.de> parents: diff changeset	65 /**
95307ad235d9 Added Draw2d code, still work in progress Frank Benoit <benoit@tionex.de> parents: diff changeset	66 * The bendpoint constraints. The path must go through these bendpoints.
95307ad235d9 Added Draw2d code, still work in progress Frank Benoit <benoit@tionex.de> parents: diff changeset	67 */
95307ad235d9 Added Draw2d code, still work in progress Frank Benoit <benoit@tionex.de> parents: diff changeset	68 PointList bendpoints;
95307ad235d9 Added Draw2d code, still work in progress Frank Benoit <benoit@tionex.de> parents: diff changeset	69 /**
95307ad235d9 Added Draw2d code, still work in progress Frank Benoit <benoit@tionex.de> parents: diff changeset	70 * An arbitrary data field which can be used to map a Path back to some client object.
95307ad235d9 Added Draw2d code, still work in progress Frank Benoit <benoit@tionex.de> parents: diff changeset	71 */
95307ad235d9 Added Draw2d code, still work in progress Frank Benoit <benoit@tionex.de> parents: diff changeset	72 public Object data;
95307ad235d9 Added Draw2d code, still work in progress Frank Benoit <benoit@tionex.de> parents: diff changeset	73 List excludedObstacles;
95307ad235d9 Added Draw2d code, still work in progress Frank Benoit <benoit@tionex.de> parents: diff changeset	74 List grownSegments;
95307ad235d9 Added Draw2d code, still work in progress Frank Benoit <benoit@tionex.de> parents: diff changeset	75 /**
95307ad235d9 Added Draw2d code, still work in progress Frank Benoit <benoit@tionex.de> parents: diff changeset	76 * this field is for internal use only. It is true whenever a property has been changed
95307ad235d9 Added Draw2d code, still work in progress Frank Benoit <benoit@tionex.de> parents: diff changeset	77 * which requires the solver to resolve this path.
95307ad235d9 Added Draw2d code, still work in progress Frank Benoit <benoit@tionex.de> parents: diff changeset	78 */
95307ad235d9 Added Draw2d code, still work in progress Frank Benoit <benoit@tionex.de> parents: diff changeset	79 public bool isDirty = true;
95307ad235d9 Added Draw2d code, still work in progress Frank Benoit <benoit@tionex.de> parents: diff changeset	80
95307ad235d9 Added Draw2d code, still work in progress Frank Benoit <benoit@tionex.de> parents: diff changeset	81 bool isInverted = false;
95307ad235d9 Added Draw2d code, still work in progress Frank Benoit <benoit@tionex.de> parents: diff changeset	82 bool isMarked = false;
95307ad235d9 Added Draw2d code, still work in progress Frank Benoit <benoit@tionex.de> parents: diff changeset	83 PointList points;
95307ad235d9 Added Draw2d code, still work in progress Frank Benoit <benoit@tionex.de> parents: diff changeset	84
95307ad235d9 Added Draw2d code, still work in progress Frank Benoit <benoit@tionex.de> parents: diff changeset	85 /**
95307ad235d9 Added Draw2d code, still work in progress Frank Benoit <benoit@tionex.de> parents: diff changeset	86 * The previous cost ratio of the path. The cost ratio is the actual path length divided
95307ad235d9 Added Draw2d code, still work in progress Frank Benoit <benoit@tionex.de> parents: diff changeset	87 * by the length from the start to the end.
95307ad235d9 Added Draw2d code, still work in progress Frank Benoit <benoit@tionex.de> parents: diff changeset	88 */
95307ad235d9 Added Draw2d code, still work in progress Frank Benoit <benoit@tionex.de> parents: diff changeset	89 private double prevCostRatio;
95307ad235d9 Added Draw2d code, still work in progress Frank Benoit <benoit@tionex.de> parents: diff changeset	90 List segments;
95307ad235d9 Added Draw2d code, still work in progress Frank Benoit <benoit@tionex.de> parents: diff changeset	91
95307ad235d9 Added Draw2d code, still work in progress Frank Benoit <benoit@tionex.de> parents: diff changeset	92 private SegmentStack stack;
95307ad235d9 Added Draw2d code, still work in progress Frank Benoit <benoit@tionex.de> parents: diff changeset	93 Vertex start, end;
95307ad235d9 Added Draw2d code, still work in progress Frank Benoit <benoit@tionex.de> parents: diff changeset	94 private Path subPath;
95307ad235d9 Added Draw2d code, still work in progress Frank Benoit <benoit@tionex.de> parents: diff changeset	95 double threshold;
95307ad235d9 Added Draw2d code, still work in progress Frank Benoit <benoit@tionex.de> parents: diff changeset	96 Set visibleObstacles;
95307ad235d9 Added Draw2d code, still work in progress Frank Benoit <benoit@tionex.de> parents: diff changeset	97 Set visibleVertices;
95307ad235d9 Added Draw2d code, still work in progress Frank Benoit <benoit@tionex.de> parents: diff changeset	98
95307ad235d9 Added Draw2d code, still work in progress Frank Benoit <benoit@tionex.de> parents: diff changeset	99 /**
95307ad235d9 Added Draw2d code, still work in progress Frank Benoit <benoit@tionex.de> parents: diff changeset	100 * Constructs a new path.
95307ad235d9 Added Draw2d code, still work in progress Frank Benoit <benoit@tionex.de> parents: diff changeset	101 * @since 3.0
95307ad235d9 Added Draw2d code, still work in progress Frank Benoit <benoit@tionex.de> parents: diff changeset	102 */
95307ad235d9 Added Draw2d code, still work in progress Frank Benoit <benoit@tionex.de> parents: diff changeset	103 public this() {
95307ad235d9 Added Draw2d code, still work in progress Frank Benoit <benoit@tionex.de> parents: diff changeset	104 segments = new ArrayList();
95307ad235d9 Added Draw2d code, still work in progress Frank Benoit <benoit@tionex.de> parents: diff changeset	105 grownSegments = new ArrayList();
95307ad235d9 Added Draw2d code, still work in progress Frank Benoit <benoit@tionex.de> parents: diff changeset	106 points = new PointList();
95307ad235d9 Added Draw2d code, still work in progress Frank Benoit <benoit@tionex.de> parents: diff changeset	107 visibleVertices = new HashSet();
95307ad235d9 Added Draw2d code, still work in progress Frank Benoit <benoit@tionex.de> parents: diff changeset	108 stack = new SegmentStack();
95307ad235d9 Added Draw2d code, still work in progress Frank Benoit <benoit@tionex.de> parents: diff changeset	109 visibleObstacles = new HashSet();
95307ad235d9 Added Draw2d code, still work in progress Frank Benoit <benoit@tionex.de> parents: diff changeset	110 excludedObstacles = new ArrayList();
95307ad235d9 Added Draw2d code, still work in progress Frank Benoit <benoit@tionex.de> parents: diff changeset	111 }
95307ad235d9 Added Draw2d code, still work in progress Frank Benoit <benoit@tionex.de> parents: diff changeset	112
95307ad235d9 Added Draw2d code, still work in progress Frank Benoit <benoit@tionex.de> parents: diff changeset	113 /**
95307ad235d9 Added Draw2d code, still work in progress Frank Benoit <benoit@tionex.de> parents: diff changeset	114 * Constructs a new path with the given data.
95307ad235d9 Added Draw2d code, still work in progress Frank Benoit <benoit@tionex.de> parents: diff changeset	115 * @since 3.0
95307ad235d9 Added Draw2d code, still work in progress Frank Benoit <benoit@tionex.de> parents: diff changeset	116 * @param data an arbitrary data field
95307ad235d9 Added Draw2d code, still work in progress Frank Benoit <benoit@tionex.de> parents: diff changeset	117 */
95307ad235d9 Added Draw2d code, still work in progress Frank Benoit <benoit@tionex.de> parents: diff changeset	118 public this(Object data) {
95307ad235d9 Added Draw2d code, still work in progress Frank Benoit <benoit@tionex.de> parents: diff changeset	119 this();
95307ad235d9 Added Draw2d code, still work in progress Frank Benoit <benoit@tionex.de> parents: diff changeset	120 this.data = data;
95307ad235d9 Added Draw2d code, still work in progress Frank Benoit <benoit@tionex.de> parents: diff changeset	121 }
95307ad235d9 Added Draw2d code, still work in progress Frank Benoit <benoit@tionex.de> parents: diff changeset	122
95307ad235d9 Added Draw2d code, still work in progress Frank Benoit <benoit@tionex.de> parents: diff changeset	123 /**
95307ad235d9 Added Draw2d code, still work in progress Frank Benoit <benoit@tionex.de> parents: diff changeset	124 * Constructs a new path with the given data, start and end point.
95307ad235d9 Added Draw2d code, still work in progress Frank Benoit <benoit@tionex.de> parents: diff changeset	125 *
95307ad235d9 Added Draw2d code, still work in progress Frank Benoit <benoit@tionex.de> parents: diff changeset	126 * @param start the start point for this path
95307ad235d9 Added Draw2d code, still work in progress Frank Benoit <benoit@tionex.de> parents: diff changeset	127 * @param end the end point for this path
95307ad235d9 Added Draw2d code, still work in progress Frank Benoit <benoit@tionex.de> parents: diff changeset	128 */
95307ad235d9 Added Draw2d code, still work in progress Frank Benoit <benoit@tionex.de> parents: diff changeset	129 public this(Point start, Point end) {
95307ad235d9 Added Draw2d code, still work in progress Frank Benoit <benoit@tionex.de> parents: diff changeset	130 this(new Vertex(start, null), new Vertex(end, null));
95307ad235d9 Added Draw2d code, still work in progress Frank Benoit <benoit@tionex.de> parents: diff changeset	131 }
95307ad235d9 Added Draw2d code, still work in progress Frank Benoit <benoit@tionex.de> parents: diff changeset	132
95307ad235d9 Added Draw2d code, still work in progress Frank Benoit <benoit@tionex.de> parents: diff changeset	133 /**
95307ad235d9 Added Draw2d code, still work in progress Frank Benoit <benoit@tionex.de> parents: diff changeset	134 * Creates a path between the given vertices.
95307ad235d9 Added Draw2d code, still work in progress Frank Benoit <benoit@tionex.de> parents: diff changeset	135 *
95307ad235d9 Added Draw2d code, still work in progress Frank Benoit <benoit@tionex.de> parents: diff changeset	136 * @param start start vertex
95307ad235d9 Added Draw2d code, still work in progress Frank Benoit <benoit@tionex.de> parents: diff changeset	137 * @param end end vertex
95307ad235d9 Added Draw2d code, still work in progress Frank Benoit <benoit@tionex.de> parents: diff changeset	138 */
95307ad235d9 Added Draw2d code, still work in progress Frank Benoit <benoit@tionex.de> parents: diff changeset	139 this(Vertex start, Vertex end) {
95307ad235d9 Added Draw2d code, still work in progress Frank Benoit <benoit@tionex.de> parents: diff changeset	140 this();
95307ad235d9 Added Draw2d code, still work in progress Frank Benoit <benoit@tionex.de> parents: diff changeset	141 this.start = start;
95307ad235d9 Added Draw2d code, still work in progress Frank Benoit <benoit@tionex.de> parents: diff changeset	142 this.end = end;
95307ad235d9 Added Draw2d code, still work in progress Frank Benoit <benoit@tionex.de> parents: diff changeset	143 }
95307ad235d9 Added Draw2d code, still work in progress Frank Benoit <benoit@tionex.de> parents: diff changeset	144
95307ad235d9 Added Draw2d code, still work in progress Frank Benoit <benoit@tionex.de> parents: diff changeset	145 /**
95307ad235d9 Added Draw2d code, still work in progress Frank Benoit <benoit@tionex.de> parents: diff changeset	146 * Attempts to add all segments between the given obstacles to the visibility graph.
95307ad235d9 Added Draw2d code, still work in progress Frank Benoit <benoit@tionex.de> parents: diff changeset	147 * @param source the source obstacle
95307ad235d9 Added Draw2d code, still work in progress Frank Benoit <benoit@tionex.de> parents: diff changeset	148 * @param target the target obstacle
95307ad235d9 Added Draw2d code, still work in progress Frank Benoit <benoit@tionex.de> parents: diff changeset	149 */
95307ad235d9 Added Draw2d code, still work in progress Frank Benoit <benoit@tionex.de> parents: diff changeset	150 private void addAllSegmentsBetween(Obstacle source, Obstacle target) {
95307ad235d9 Added Draw2d code, still work in progress Frank Benoit <benoit@tionex.de> parents: diff changeset	151 addConnectingSegment(new Segment(source.bottomLeft, target.bottomLeft),
95307ad235d9 Added Draw2d code, still work in progress Frank Benoit <benoit@tionex.de> parents: diff changeset	152 source, target, false, false);
95307ad235d9 Added Draw2d code, still work in progress Frank Benoit <benoit@tionex.de> parents: diff changeset	153 addConnectingSegment(new Segment(source.bottomRight, target.bottomRight),
95307ad235d9 Added Draw2d code, still work in progress Frank Benoit <benoit@tionex.de> parents: diff changeset	154 source, target, true, true);
95307ad235d9 Added Draw2d code, still work in progress Frank Benoit <benoit@tionex.de> parents: diff changeset	155 addConnectingSegment(new Segment(source.topLeft, target.topLeft),
95307ad235d9 Added Draw2d code, still work in progress Frank Benoit <benoit@tionex.de> parents: diff changeset	156 source, target, true, true);
95307ad235d9 Added Draw2d code, still work in progress Frank Benoit <benoit@tionex.de> parents: diff changeset	157 addConnectingSegment(new Segment(source.topRight, target.topRight),
95307ad235d9 Added Draw2d code, still work in progress Frank Benoit <benoit@tionex.de> parents: diff changeset	158 source, target, false, false);
95307ad235d9 Added Draw2d code, still work in progress Frank Benoit <benoit@tionex.de> parents: diff changeset	159
95307ad235d9 Added Draw2d code, still work in progress Frank Benoit <benoit@tionex.de> parents: diff changeset	160 if (source.bottom() is target.bottom()) {
95307ad235d9 Added Draw2d code, still work in progress Frank Benoit <benoit@tionex.de> parents: diff changeset	161 addConnectingSegment(new Segment(source.bottomLeft, target.bottomRight),
95307ad235d9 Added Draw2d code, still work in progress Frank Benoit <benoit@tionex.de> parents: diff changeset	162 source, target, false, true);
95307ad235d9 Added Draw2d code, still work in progress Frank Benoit <benoit@tionex.de> parents: diff changeset	163 addConnectingSegment(new Segment(source.bottomRight, target.bottomLeft),
95307ad235d9 Added Draw2d code, still work in progress Frank Benoit <benoit@tionex.de> parents: diff changeset	164 source, target, true, false);
95307ad235d9 Added Draw2d code, still work in progress Frank Benoit <benoit@tionex.de> parents: diff changeset	165 }
95307ad235d9 Added Draw2d code, still work in progress Frank Benoit <benoit@tionex.de> parents: diff changeset	166 if (source.y is target.y) {
95307ad235d9 Added Draw2d code, still work in progress Frank Benoit <benoit@tionex.de> parents: diff changeset	167 addConnectingSegment(new Segment(source.topLeft, target.topRight),
95307ad235d9 Added Draw2d code, still work in progress Frank Benoit <benoit@tionex.de> parents: diff changeset	168 source, target, true, false);
95307ad235d9 Added Draw2d code, still work in progress Frank Benoit <benoit@tionex.de> parents: diff changeset	169 addConnectingSegment(new Segment(source.topRight, target.topLeft),
95307ad235d9 Added Draw2d code, still work in progress Frank Benoit <benoit@tionex.de> parents: diff changeset	170 source, target, false, true);
95307ad235d9 Added Draw2d code, still work in progress Frank Benoit <benoit@tionex.de> parents: diff changeset	171 }
95307ad235d9 Added Draw2d code, still work in progress Frank Benoit <benoit@tionex.de> parents: diff changeset	172 if (source.x is target.x) {
95307ad235d9 Added Draw2d code, still work in progress Frank Benoit <benoit@tionex.de> parents: diff changeset	173 addConnectingSegment(new Segment(source.bottomLeft, target.topLeft),
95307ad235d9 Added Draw2d code, still work in progress Frank Benoit <benoit@tionex.de> parents: diff changeset	174 source, target, false, true);
95307ad235d9 Added Draw2d code, still work in progress Frank Benoit <benoit@tionex.de> parents: diff changeset	175 addConnectingSegment(new Segment(source.topLeft, target.bottomLeft),
95307ad235d9 Added Draw2d code, still work in progress Frank Benoit <benoit@tionex.de> parents: diff changeset	176 source, target, true, false);
95307ad235d9 Added Draw2d code, still work in progress Frank Benoit <benoit@tionex.de> parents: diff changeset	177 }
95307ad235d9 Added Draw2d code, still work in progress Frank Benoit <benoit@tionex.de> parents: diff changeset	178 if (source.right() is target.right()) {
95307ad235d9 Added Draw2d code, still work in progress Frank Benoit <benoit@tionex.de> parents: diff changeset	179 addConnectingSegment(new Segment(source.bottomRight, target.topRight),
95307ad235d9 Added Draw2d code, still work in progress Frank Benoit <benoit@tionex.de> parents: diff changeset	180 source, target, true, false);
95307ad235d9 Added Draw2d code, still work in progress Frank Benoit <benoit@tionex.de> parents: diff changeset	181 addConnectingSegment(new Segment(source.topRight, target.bottomRight),
95307ad235d9 Added Draw2d code, still work in progress Frank Benoit <benoit@tionex.de> parents: diff changeset	182 source, target, false, true);
95307ad235d9 Added Draw2d code, still work in progress Frank Benoit <benoit@tionex.de> parents: diff changeset	183 }
95307ad235d9 Added Draw2d code, still work in progress Frank Benoit <benoit@tionex.de> parents: diff changeset	184 }
95307ad235d9 Added Draw2d code, still work in progress Frank Benoit <benoit@tionex.de> parents: diff changeset	185
95307ad235d9 Added Draw2d code, still work in progress Frank Benoit <benoit@tionex.de> parents: diff changeset	186 /**
95307ad235d9 Added Draw2d code, still work in progress Frank Benoit <benoit@tionex.de> parents: diff changeset	187 * Attempts to add a segment between the given obstacles to the visibility graph. This
95307ad235d9 Added Draw2d code, still work in progress Frank Benoit <benoit@tionex.de> parents: diff changeset	188 * method is specifically written for the case where the two obstacles intersect and contains
95307ad235d9 Added Draw2d code, still work in progress Frank Benoit <benoit@tionex.de> parents: diff changeset	189 * a bool as to whether to check the diagonal that includes the top right point of the
95307ad235d9 Added Draw2d code, still work in progress Frank Benoit <benoit@tionex.de> parents: diff changeset	190 * other obstacle.
95307ad235d9 Added Draw2d code, still work in progress Frank Benoit <benoit@tionex.de> parents: diff changeset	191 *
95307ad235d9 Added Draw2d code, still work in progress Frank Benoit <benoit@tionex.de> parents: diff changeset	192 * @param segment the segment to check
95307ad235d9 Added Draw2d code, still work in progress Frank Benoit <benoit@tionex.de> parents: diff changeset	193 * @param o1 the first obstacle
95307ad235d9 Added Draw2d code, still work in progress Frank Benoit <benoit@tionex.de> parents: diff changeset	194 * @param o2 the second obstacle
95307ad235d9 Added Draw2d code, still work in progress Frank Benoit <benoit@tionex.de> parents: diff changeset	195 * @param checkTopRight1 whether or not to check the diagonal containing top right point
95307ad235d9 Added Draw2d code, still work in progress Frank Benoit <benoit@tionex.de> parents: diff changeset	196 */
95307ad235d9 Added Draw2d code, still work in progress Frank Benoit <benoit@tionex.de> parents: diff changeset	197 private void addConnectingSegment(Segment segment, Obstacle o1, Obstacle o2,
95307ad235d9 Added Draw2d code, still work in progress Frank Benoit <benoit@tionex.de> parents: diff changeset	198 bool checkTopRight1, bool checkTopRight2) {
95307ad235d9 Added Draw2d code, still work in progress Frank Benoit <benoit@tionex.de> parents: diff changeset	199 if (threshold !is 0
95307ad235d9 Added Draw2d code, still work in progress Frank Benoit <benoit@tionex.de> parents: diff changeset	200 && (segment.end.getDistance(end) + segment.end.getDistance(start) > threshold
95307ad235d9 Added Draw2d code, still work in progress Frank Benoit <benoit@tionex.de> parents: diff changeset	201 \|\| segment.start.getDistance(end) + segment.start.getDistance(start) > threshold))
95307ad235d9 Added Draw2d code, still work in progress Frank Benoit <benoit@tionex.de> parents: diff changeset	202 return;
95307ad235d9 Added Draw2d code, still work in progress Frank Benoit <benoit@tionex.de> parents: diff changeset	203
95307ad235d9 Added Draw2d code, still work in progress Frank Benoit <benoit@tionex.de> parents: diff changeset	204 if (o2.containsProper(segment.start) \|\| o1.containsProper(segment.end))
95307ad235d9 Added Draw2d code, still work in progress Frank Benoit <benoit@tionex.de> parents: diff changeset	205 return;
95307ad235d9 Added Draw2d code, still work in progress Frank Benoit <benoit@tionex.de> parents: diff changeset	206
95307ad235d9 Added Draw2d code, still work in progress Frank Benoit <benoit@tionex.de> parents: diff changeset	207 if (checkTopRight1 && segment.intersects(o1.x, o1.bottom() - 1, o1.right() - 1, o1.y))
95307ad235d9 Added Draw2d code, still work in progress Frank Benoit <benoit@tionex.de> parents: diff changeset	208 return;
95307ad235d9 Added Draw2d code, still work in progress Frank Benoit <benoit@tionex.de> parents: diff changeset	209 if (checkTopRight2 && segment.intersects(o2.x, o2.bottom() - 1, o2.right() - 1, o2.y))
95307ad235d9 Added Draw2d code, still work in progress Frank Benoit <benoit@tionex.de> parents: diff changeset	210 return;
95307ad235d9 Added Draw2d code, still work in progress Frank Benoit <benoit@tionex.de> parents: diff changeset	211 if (!checkTopRight1 && segment.intersects(o1.x, o1.y, o1.right() - 1, o1.bottom() - 1))
95307ad235d9 Added Draw2d code, still work in progress Frank Benoit <benoit@tionex.de> parents: diff changeset	212 return;
95307ad235d9 Added Draw2d code, still work in progress Frank Benoit <benoit@tionex.de> parents: diff changeset	213 if (!checkTopRight2 && segment.intersects(o2.x, o2.y, o2.right() - 1, o2.bottom() - 1))
95307ad235d9 Added Draw2d code, still work in progress Frank Benoit <benoit@tionex.de> parents: diff changeset	214 return;
95307ad235d9 Added Draw2d code, still work in progress Frank Benoit <benoit@tionex.de> parents: diff changeset	215
95307ad235d9 Added Draw2d code, still work in progress Frank Benoit <benoit@tionex.de> parents: diff changeset	216 stack.push(o1);
95307ad235d9 Added Draw2d code, still work in progress Frank Benoit <benoit@tionex.de> parents: diff changeset	217 stack.push(o2);
95307ad235d9 Added Draw2d code, still work in progress Frank Benoit <benoit@tionex.de> parents: diff changeset	218 stack.push(segment);
95307ad235d9 Added Draw2d code, still work in progress Frank Benoit <benoit@tionex.de> parents: diff changeset	219 }
95307ad235d9 Added Draw2d code, still work in progress Frank Benoit <benoit@tionex.de> parents: diff changeset	220
95307ad235d9 Added Draw2d code, still work in progress Frank Benoit <benoit@tionex.de> parents: diff changeset	221 /**
95307ad235d9 Added Draw2d code, still work in progress Frank Benoit <benoit@tionex.de> parents: diff changeset	222 * Adds an obstacle to the visibility graph and generates new segments
95307ad235d9 Added Draw2d code, still work in progress Frank Benoit <benoit@tionex.de> parents: diff changeset	223 * @param newObs the new obstacle, should not be in the graph already
95307ad235d9 Added Draw2d code, still work in progress Frank Benoit <benoit@tionex.de> parents: diff changeset	224 */
95307ad235d9 Added Draw2d code, still work in progress Frank Benoit <benoit@tionex.de> parents: diff changeset	225 private void addObstacle(Obstacle newObs) {
95307ad235d9 Added Draw2d code, still work in progress Frank Benoit <benoit@tionex.de> parents: diff changeset	226 visibleObstacles.add(newObs);
95307ad235d9 Added Draw2d code, still work in progress Frank Benoit <benoit@tionex.de> parents: diff changeset	227 Iterator oItr = (new HashSet(visibleObstacles)).iterator();
95307ad235d9 Added Draw2d code, still work in progress Frank Benoit <benoit@tionex.de> parents: diff changeset	228 while (oItr.hasNext()) {
95307ad235d9 Added Draw2d code, still work in progress Frank Benoit <benoit@tionex.de> parents: diff changeset	229 Obstacle currObs = cast(Obstacle)oItr.next();
95307ad235d9 Added Draw2d code, still work in progress Frank Benoit <benoit@tionex.de> parents: diff changeset	230 if (newObs !is currObs)
95307ad235d9 Added Draw2d code, still work in progress Frank Benoit <benoit@tionex.de> parents: diff changeset	231 addSegmentsFor(newObs, currObs);
95307ad235d9 Added Draw2d code, still work in progress Frank Benoit <benoit@tionex.de> parents: diff changeset	232 }
95307ad235d9 Added Draw2d code, still work in progress Frank Benoit <benoit@tionex.de> parents: diff changeset	233 addPerimiterSegments(newObs);
95307ad235d9 Added Draw2d code, still work in progress Frank Benoit <benoit@tionex.de> parents: diff changeset	234 addSegmentsFor(start, newObs);
95307ad235d9 Added Draw2d code, still work in progress Frank Benoit <benoit@tionex.de> parents: diff changeset	235 addSegmentsFor(end, newObs);
95307ad235d9 Added Draw2d code, still work in progress Frank Benoit <benoit@tionex.de> parents: diff changeset	236 }
95307ad235d9 Added Draw2d code, still work in progress Frank Benoit <benoit@tionex.de> parents: diff changeset	237
95307ad235d9 Added Draw2d code, still work in progress Frank Benoit <benoit@tionex.de> parents: diff changeset	238 /**
95307ad235d9 Added Draw2d code, still work in progress Frank Benoit <benoit@tionex.de> parents: diff changeset	239 * Adds the segments along the perimiter of an obstacle to the visiblity graph queue.
95307ad235d9 Added Draw2d code, still work in progress Frank Benoit <benoit@tionex.de> parents: diff changeset	240 * @param obs the obstacle
95307ad235d9 Added Draw2d code, still work in progress Frank Benoit <benoit@tionex.de> parents: diff changeset	241 */
95307ad235d9 Added Draw2d code, still work in progress Frank Benoit <benoit@tionex.de> parents: diff changeset	242 private void addPerimiterSegments(Obstacle obs) {
95307ad235d9 Added Draw2d code, still work in progress Frank Benoit <benoit@tionex.de> parents: diff changeset	243 Segment seg = new Segment(obs.topLeft, obs.topRight);
95307ad235d9 Added Draw2d code, still work in progress Frank Benoit <benoit@tionex.de> parents: diff changeset	244 stack.push(obs);
95307ad235d9 Added Draw2d code, still work in progress Frank Benoit <benoit@tionex.de> parents: diff changeset	245 stack.push(null);
95307ad235d9 Added Draw2d code, still work in progress Frank Benoit <benoit@tionex.de> parents: diff changeset	246 stack.push(seg);
95307ad235d9 Added Draw2d code, still work in progress Frank Benoit <benoit@tionex.de> parents: diff changeset	247 seg = new Segment(obs.topRight, obs.bottomRight);
95307ad235d9 Added Draw2d code, still work in progress Frank Benoit <benoit@tionex.de> parents: diff changeset	248 stack.push(obs);
95307ad235d9 Added Draw2d code, still work in progress Frank Benoit <benoit@tionex.de> parents: diff changeset	249 stack.push(null);
95307ad235d9 Added Draw2d code, still work in progress Frank Benoit <benoit@tionex.de> parents: diff changeset	250 stack.push(seg);
95307ad235d9 Added Draw2d code, still work in progress Frank Benoit <benoit@tionex.de> parents: diff changeset	251 seg = new Segment(obs.bottomRight, obs.bottomLeft);
95307ad235d9 Added Draw2d code, still work in progress Frank Benoit <benoit@tionex.de> parents: diff changeset	252 stack.push(obs);
95307ad235d9 Added Draw2d code, still work in progress Frank Benoit <benoit@tionex.de> parents: diff changeset	253 stack.push(null);
95307ad235d9 Added Draw2d code, still work in progress Frank Benoit <benoit@tionex.de> parents: diff changeset	254 stack.push(seg);
95307ad235d9 Added Draw2d code, still work in progress Frank Benoit <benoit@tionex.de> parents: diff changeset	255 seg = new Segment(obs.bottomLeft, obs.topLeft);
95307ad235d9 Added Draw2d code, still work in progress Frank Benoit <benoit@tionex.de> parents: diff changeset	256 stack.push(obs);
95307ad235d9 Added Draw2d code, still work in progress Frank Benoit <benoit@tionex.de> parents: diff changeset	257 stack.push(null);
95307ad235d9 Added Draw2d code, still work in progress Frank Benoit <benoit@tionex.de> parents: diff changeset	258 stack.push(seg);
95307ad235d9 Added Draw2d code, still work in progress Frank Benoit <benoit@tionex.de> parents: diff changeset	259 }
95307ad235d9 Added Draw2d code, still work in progress Frank Benoit <benoit@tionex.de> parents: diff changeset	260
95307ad235d9 Added Draw2d code, still work in progress Frank Benoit <benoit@tionex.de> parents: diff changeset	261 /**
95307ad235d9 Added Draw2d code, still work in progress Frank Benoit <benoit@tionex.de> parents: diff changeset	262 * Attempts to add a segment to the visibility graph.
95307ad235d9 Added Draw2d code, still work in progress Frank Benoit <benoit@tionex.de> parents: diff changeset	263 * First checks to see if the segment is outside the threshold oval. Then it compares the segment
95307ad235d9 Added Draw2d code, still work in progress Frank Benoit <benoit@tionex.de> parents: diff changeset	264 * against all obstacles. If it is clean, the segment is finally added to the graph.
95307ad235d9 Added Draw2d code, still work in progress Frank Benoit <benoit@tionex.de> parents: diff changeset	265 *
95307ad235d9 Added Draw2d code, still work in progress Frank Benoit <benoit@tionex.de> parents: diff changeset	266 * @param segment the segment
95307ad235d9 Added Draw2d code, still work in progress Frank Benoit <benoit@tionex.de> parents: diff changeset	267 * @param exclude1 an obstacle to exclude from the search
95307ad235d9 Added Draw2d code, still work in progress Frank Benoit <benoit@tionex.de> parents: diff changeset	268 * @param exclude2 another obstacle to exclude from the search
95307ad235d9 Added Draw2d code, still work in progress Frank Benoit <benoit@tionex.de> parents: diff changeset	269 * @param allObstacles the list of all obstacles
95307ad235d9 Added Draw2d code, still work in progress Frank Benoit <benoit@tionex.de> parents: diff changeset	270 */
95307ad235d9 Added Draw2d code, still work in progress Frank Benoit <benoit@tionex.de> parents: diff changeset	271 private void addSegment(Segment segment, Obstacle exclude1, Obstacle exclude2, List allObstacles) {
95307ad235d9 Added Draw2d code, still work in progress Frank Benoit <benoit@tionex.de> parents: diff changeset	272 if (threshold !is 0
95307ad235d9 Added Draw2d code, still work in progress Frank Benoit <benoit@tionex.de> parents: diff changeset	273 && (segment.end.getDistance(end) + segment.end.getDistance(start) > threshold
95307ad235d9 Added Draw2d code, still work in progress Frank Benoit <benoit@tionex.de> parents: diff changeset	274 \|\| segment.start.getDistance(end) + segment.start.getDistance(start) > threshold))
95307ad235d9 Added Draw2d code, still work in progress Frank Benoit <benoit@tionex.de> parents: diff changeset	275 return;
95307ad235d9 Added Draw2d code, still work in progress Frank Benoit <benoit@tionex.de> parents: diff changeset	276
95307ad235d9 Added Draw2d code, still work in progress Frank Benoit <benoit@tionex.de> parents: diff changeset	277 for (int i = 0; i < allObstacles.size(); i++) {
95307ad235d9 Added Draw2d code, still work in progress Frank Benoit <benoit@tionex.de> parents: diff changeset	278 Obstacle obs = cast(Obstacle)allObstacles.get(i);
95307ad235d9 Added Draw2d code, still work in progress Frank Benoit <benoit@tionex.de> parents: diff changeset	279
95307ad235d9 Added Draw2d code, still work in progress Frank Benoit <benoit@tionex.de> parents: diff changeset	280 if (obs is exclude1 \|\| obs is exclude2 \|\| obs.exclude)
95307ad235d9 Added Draw2d code, still work in progress Frank Benoit <benoit@tionex.de> parents: diff changeset	281 continue;
95307ad235d9 Added Draw2d code, still work in progress Frank Benoit <benoit@tionex.de> parents: diff changeset	282
95307ad235d9 Added Draw2d code, still work in progress Frank Benoit <benoit@tionex.de> parents: diff changeset	283 if (segment.intersects(obs.x, obs.y, obs.right() - 1, obs.bottom() - 1)
95307ad235d9 Added Draw2d code, still work in progress Frank Benoit <benoit@tionex.de> parents: diff changeset	284 \|\| segment.intersects(obs.x, obs.bottom() - 1, obs.right() - 1, obs.y)
95307ad235d9 Added Draw2d code, still work in progress Frank Benoit <benoit@tionex.de> parents: diff changeset	285 \|\| obs.containsProper(segment.start)
95307ad235d9 Added Draw2d code, still work in progress Frank Benoit <benoit@tionex.de> parents: diff changeset	286 \|\| obs.containsProper(segment.end)) {
95307ad235d9 Added Draw2d code, still work in progress Frank Benoit <benoit@tionex.de> parents: diff changeset	287 if (!visibleObstacles.contains(obs))
95307ad235d9 Added Draw2d code, still work in progress Frank Benoit <benoit@tionex.de> parents: diff changeset	288 addObstacle(obs);
95307ad235d9 Added Draw2d code, still work in progress Frank Benoit <benoit@tionex.de> parents: diff changeset	289 return;
95307ad235d9 Added Draw2d code, still work in progress Frank Benoit <benoit@tionex.de> parents: diff changeset	290 }
95307ad235d9 Added Draw2d code, still work in progress Frank Benoit <benoit@tionex.de> parents: diff changeset	291 }
95307ad235d9 Added Draw2d code, still work in progress Frank Benoit <benoit@tionex.de> parents: diff changeset	292
95307ad235d9 Added Draw2d code, still work in progress Frank Benoit <benoit@tionex.de> parents: diff changeset	293 linkVertices(segment);
95307ad235d9 Added Draw2d code, still work in progress Frank Benoit <benoit@tionex.de> parents: diff changeset	294 }
95307ad235d9 Added Draw2d code, still work in progress Frank Benoit <benoit@tionex.de> parents: diff changeset	295
95307ad235d9 Added Draw2d code, still work in progress Frank Benoit <benoit@tionex.de> parents: diff changeset	296 /**
95307ad235d9 Added Draw2d code, still work in progress Frank Benoit <benoit@tionex.de> parents: diff changeset	297 * Adds the segments between the given obstacles.
95307ad235d9 Added Draw2d code, still work in progress Frank Benoit <benoit@tionex.de> parents: diff changeset	298 * @param source source obstacle
95307ad235d9 Added Draw2d code, still work in progress Frank Benoit <benoit@tionex.de> parents: diff changeset	299 * @param target target obstacle
95307ad235d9 Added Draw2d code, still work in progress Frank Benoit <benoit@tionex.de> parents: diff changeset	300 */
95307ad235d9 Added Draw2d code, still work in progress Frank Benoit <benoit@tionex.de> parents: diff changeset	301 private void addSegmentsFor(Obstacle source, Obstacle target) {
95307ad235d9 Added Draw2d code, still work in progress Frank Benoit <benoit@tionex.de> parents: diff changeset	302 if (source.intersects(target))
95307ad235d9 Added Draw2d code, still work in progress Frank Benoit <benoit@tionex.de> parents: diff changeset	303 addAllSegmentsBetween(source, target);
95307ad235d9 Added Draw2d code, still work in progress Frank Benoit <benoit@tionex.de> parents: diff changeset	304 else if (target.bottom() - 1 < source.y)
95307ad235d9 Added Draw2d code, still work in progress Frank Benoit <benoit@tionex.de> parents: diff changeset	305 addSegmentsTargetAboveSource(source, target);
95307ad235d9 Added Draw2d code, still work in progress Frank Benoit <benoit@tionex.de> parents: diff changeset	306 else if (source.bottom() - 1 < target.y)
95307ad235d9 Added Draw2d code, still work in progress Frank Benoit <benoit@tionex.de> parents: diff changeset	307 addSegmentsTargetAboveSource(target, source);
95307ad235d9 Added Draw2d code, still work in progress Frank Benoit <benoit@tionex.de> parents: diff changeset	308 else if (target.right() - 1 < source.x)
95307ad235d9 Added Draw2d code, still work in progress Frank Benoit <benoit@tionex.de> parents: diff changeset	309 addSegmentsTargetBesideSource(source, target);
95307ad235d9 Added Draw2d code, still work in progress Frank Benoit <benoit@tionex.de> parents: diff changeset	310 else
95307ad235d9 Added Draw2d code, still work in progress Frank Benoit <benoit@tionex.de> parents: diff changeset	311 addSegmentsTargetBesideSource(target, source);
95307ad235d9 Added Draw2d code, still work in progress Frank Benoit <benoit@tionex.de> parents: diff changeset	312 }
95307ad235d9 Added Draw2d code, still work in progress Frank Benoit <benoit@tionex.de> parents: diff changeset	313
95307ad235d9 Added Draw2d code, still work in progress Frank Benoit <benoit@tionex.de> parents: diff changeset	314 /**
95307ad235d9 Added Draw2d code, still work in progress Frank Benoit <benoit@tionex.de> parents: diff changeset	315 * Adds the segments between the given obstacles.
95307ad235d9 Added Draw2d code, still work in progress Frank Benoit <benoit@tionex.de> parents: diff changeset	316 * @param source source obstacle
95307ad235d9 Added Draw2d code, still work in progress Frank Benoit <benoit@tionex.de> parents: diff changeset	317 * @param target target obstacle
95307ad235d9 Added Draw2d code, still work in progress Frank Benoit <benoit@tionex.de> parents: diff changeset	318 */
95307ad235d9 Added Draw2d code, still work in progress Frank Benoit <benoit@tionex.de> parents: diff changeset	319 private void addSegmentsFor(Vertex vertex, Obstacle obs) {
95307ad235d9 Added Draw2d code, still work in progress Frank Benoit <benoit@tionex.de> parents: diff changeset	320 Segment seg = null;
95307ad235d9 Added Draw2d code, still work in progress Frank Benoit <benoit@tionex.de> parents: diff changeset	321 Segment seg2 = null;
95307ad235d9 Added Draw2d code, still work in progress Frank Benoit <benoit@tionex.de> parents: diff changeset	322
95307ad235d9 Added Draw2d code, still work in progress Frank Benoit <benoit@tionex.de> parents: diff changeset	323 switch (obs.getPosition(vertex)) {
95307ad235d9 Added Draw2d code, still work in progress Frank Benoit <benoit@tionex.de> parents: diff changeset	324 case PositionConstants.SOUTH_WEST :
95307ad235d9 Added Draw2d code, still work in progress Frank Benoit <benoit@tionex.de> parents: diff changeset	325 case PositionConstants.NORTH_EAST :
95307ad235d9 Added Draw2d code, still work in progress Frank Benoit <benoit@tionex.de> parents: diff changeset	326 seg = new Segment(vertex, obs.topLeft);
95307ad235d9 Added Draw2d code, still work in progress Frank Benoit <benoit@tionex.de> parents: diff changeset	327 seg2 = new Segment(vertex, obs.bottomRight);
95307ad235d9 Added Draw2d code, still work in progress Frank Benoit <benoit@tionex.de> parents: diff changeset	328 break;
95307ad235d9 Added Draw2d code, still work in progress Frank Benoit <benoit@tionex.de> parents: diff changeset	329 case PositionConstants.SOUTH_EAST :
95307ad235d9 Added Draw2d code, still work in progress Frank Benoit <benoit@tionex.de> parents: diff changeset	330 case PositionConstants.NORTH_WEST :
95307ad235d9 Added Draw2d code, still work in progress Frank Benoit <benoit@tionex.de> parents: diff changeset	331 seg = new Segment(vertex, obs.topRight);
95307ad235d9 Added Draw2d code, still work in progress Frank Benoit <benoit@tionex.de> parents: diff changeset	332 seg2 = new Segment(vertex, obs.bottomLeft);
95307ad235d9 Added Draw2d code, still work in progress Frank Benoit <benoit@tionex.de> parents: diff changeset	333 break;
95307ad235d9 Added Draw2d code, still work in progress Frank Benoit <benoit@tionex.de> parents: diff changeset	334 case PositionConstants.NORTH :
95307ad235d9 Added Draw2d code, still work in progress Frank Benoit <benoit@tionex.de> parents: diff changeset	335 seg = new Segment(vertex, obs.topLeft);
95307ad235d9 Added Draw2d code, still work in progress Frank Benoit <benoit@tionex.de> parents: diff changeset	336 seg2 = new Segment(vertex, obs.topRight);
95307ad235d9 Added Draw2d code, still work in progress Frank Benoit <benoit@tionex.de> parents: diff changeset	337 break;
95307ad235d9 Added Draw2d code, still work in progress Frank Benoit <benoit@tionex.de> parents: diff changeset	338 case PositionConstants.EAST :
95307ad235d9 Added Draw2d code, still work in progress Frank Benoit <benoit@tionex.de> parents: diff changeset	339 seg = new Segment(vertex, obs.bottomRight);
95307ad235d9 Added Draw2d code, still work in progress Frank Benoit <benoit@tionex.de> parents: diff changeset	340 seg2 = new Segment(vertex, obs.topRight);
95307ad235d9 Added Draw2d code, still work in progress Frank Benoit <benoit@tionex.de> parents: diff changeset	341 break;
95307ad235d9 Added Draw2d code, still work in progress Frank Benoit <benoit@tionex.de> parents: diff changeset	342 case PositionConstants.SOUTH :
95307ad235d9 Added Draw2d code, still work in progress Frank Benoit <benoit@tionex.de> parents: diff changeset	343 seg = new Segment(vertex, obs.bottomRight);
95307ad235d9 Added Draw2d code, still work in progress Frank Benoit <benoit@tionex.de> parents: diff changeset	344 seg2 = new Segment(vertex, obs.bottomLeft);
95307ad235d9 Added Draw2d code, still work in progress Frank Benoit <benoit@tionex.de> parents: diff changeset	345 break;
95307ad235d9 Added Draw2d code, still work in progress Frank Benoit <benoit@tionex.de> parents: diff changeset	346 case PositionConstants.WEST :
95307ad235d9 Added Draw2d code, still work in progress Frank Benoit <benoit@tionex.de> parents: diff changeset	347 seg = new Segment(vertex, obs.topLeft);
95307ad235d9 Added Draw2d code, still work in progress Frank Benoit <benoit@tionex.de> parents: diff changeset	348 seg2 = new Segment(vertex, obs.bottomLeft);
95307ad235d9 Added Draw2d code, still work in progress Frank Benoit <benoit@tionex.de> parents: diff changeset	349 break;
95307ad235d9 Added Draw2d code, still work in progress Frank Benoit <benoit@tionex.de> parents: diff changeset	350 default:
95307ad235d9 Added Draw2d code, still work in progress Frank Benoit <benoit@tionex.de> parents: diff changeset	351 if (vertex.x is obs.x) {
95307ad235d9 Added Draw2d code, still work in progress Frank Benoit <benoit@tionex.de> parents: diff changeset	352 seg = new Segment(vertex, obs.topLeft);
95307ad235d9 Added Draw2d code, still work in progress Frank Benoit <benoit@tionex.de> parents: diff changeset	353 seg2 = new Segment(vertex, obs.bottomLeft);
95307ad235d9 Added Draw2d code, still work in progress Frank Benoit <benoit@tionex.de> parents: diff changeset	354 } else if (vertex.y is obs.y) {
95307ad235d9 Added Draw2d code, still work in progress Frank Benoit <benoit@tionex.de> parents: diff changeset	355 seg = new Segment(vertex, obs.topLeft);
95307ad235d9 Added Draw2d code, still work in progress Frank Benoit <benoit@tionex.de> parents: diff changeset	356 seg2 = new Segment(vertex, obs.topRight);
95307ad235d9 Added Draw2d code, still work in progress Frank Benoit <benoit@tionex.de> parents: diff changeset	357 } else if (vertex.y is obs.bottom() - 1) {
95307ad235d9 Added Draw2d code, still work in progress Frank Benoit <benoit@tionex.de> parents: diff changeset	358 seg = new Segment(vertex, obs.bottomLeft);
95307ad235d9 Added Draw2d code, still work in progress Frank Benoit <benoit@tionex.de> parents: diff changeset	359 seg2 = new Segment(vertex, obs.bottomRight);
95307ad235d9 Added Draw2d code, still work in progress Frank Benoit <benoit@tionex.de> parents: diff changeset	360 } else if (vertex.x is obs.right() - 1) {
95307ad235d9 Added Draw2d code, still work in progress Frank Benoit <benoit@tionex.de> parents: diff changeset	361 seg = new Segment(vertex, obs.topRight);
95307ad235d9 Added Draw2d code, still work in progress Frank Benoit <benoit@tionex.de> parents: diff changeset	362 seg2 = new Segment(vertex, obs.bottomRight);
95307ad235d9 Added Draw2d code, still work in progress Frank Benoit <benoit@tionex.de> parents: diff changeset	363 } else {
95307ad235d9 Added Draw2d code, still work in progress Frank Benoit <benoit@tionex.de> parents: diff changeset	364 throw new RuntimeException("Unexpected vertex conditions"); //$NON-NLS-1$
95307ad235d9 Added Draw2d code, still work in progress Frank Benoit <benoit@tionex.de> parents: diff changeset	365 }
95307ad235d9 Added Draw2d code, still work in progress Frank Benoit <benoit@tionex.de> parents: diff changeset	366 }
95307ad235d9 Added Draw2d code, still work in progress Frank Benoit <benoit@tionex.de> parents: diff changeset	367
95307ad235d9 Added Draw2d code, still work in progress Frank Benoit <benoit@tionex.de> parents: diff changeset	368 stack.push(obs);
95307ad235d9 Added Draw2d code, still work in progress Frank Benoit <benoit@tionex.de> parents: diff changeset	369 stack.push(null);
95307ad235d9 Added Draw2d code, still work in progress Frank Benoit <benoit@tionex.de> parents: diff changeset	370 stack.push(seg);
95307ad235d9 Added Draw2d code, still work in progress Frank Benoit <benoit@tionex.de> parents: diff changeset	371 stack.push(obs);
95307ad235d9 Added Draw2d code, still work in progress Frank Benoit <benoit@tionex.de> parents: diff changeset	372 stack.push(null);
95307ad235d9 Added Draw2d code, still work in progress Frank Benoit <benoit@tionex.de> parents: diff changeset	373 stack.push(seg2);
95307ad235d9 Added Draw2d code, still work in progress Frank Benoit <benoit@tionex.de> parents: diff changeset	374 }
95307ad235d9 Added Draw2d code, still work in progress Frank Benoit <benoit@tionex.de> parents: diff changeset	375
95307ad235d9 Added Draw2d code, still work in progress Frank Benoit <benoit@tionex.de> parents: diff changeset	376 private void addSegmentsTargetAboveSource(Obstacle source, Obstacle target) {
95307ad235d9 Added Draw2d code, still work in progress Frank Benoit <benoit@tionex.de> parents: diff changeset	377 //target located above source
95307ad235d9 Added Draw2d code, still work in progress Frank Benoit <benoit@tionex.de> parents: diff changeset	378 Segment seg = null;
95307ad235d9 Added Draw2d code, still work in progress Frank Benoit <benoit@tionex.de> parents: diff changeset	379 Segment seg2 = null;
95307ad235d9 Added Draw2d code, still work in progress Frank Benoit <benoit@tionex.de> parents: diff changeset	380 if (target.x > source.x) {
95307ad235d9 Added Draw2d code, still work in progress Frank Benoit <benoit@tionex.de> parents: diff changeset	381 seg = new Segment(source.topLeft, target.topLeft);
95307ad235d9 Added Draw2d code, still work in progress Frank Benoit <benoit@tionex.de> parents: diff changeset	382 if (target.x < source.right() - 1)
95307ad235d9 Added Draw2d code, still work in progress Frank Benoit <benoit@tionex.de> parents: diff changeset	383 seg2 = new Segment(source.topRight, target.bottomLeft);
95307ad235d9 Added Draw2d code, still work in progress Frank Benoit <benoit@tionex.de> parents: diff changeset	384 else
95307ad235d9 Added Draw2d code, still work in progress Frank Benoit <benoit@tionex.de> parents: diff changeset	385 seg2 = new Segment(source.bottomRight, target.topLeft);
95307ad235d9 Added Draw2d code, still work in progress Frank Benoit <benoit@tionex.de> parents: diff changeset	386 } else if (source.x is target.x) {
95307ad235d9 Added Draw2d code, still work in progress Frank Benoit <benoit@tionex.de> parents: diff changeset	387 seg = new Segment(source.topLeft, target.bottomLeft);
95307ad235d9 Added Draw2d code, still work in progress Frank Benoit <benoit@tionex.de> parents: diff changeset	388 seg2 = new Segment(source.topRight, target.bottomLeft);
95307ad235d9 Added Draw2d code, still work in progress Frank Benoit <benoit@tionex.de> parents: diff changeset	389 } else {
95307ad235d9 Added Draw2d code, still work in progress Frank Benoit <benoit@tionex.de> parents: diff changeset	390 seg = new Segment(source.bottomLeft, target.bottomLeft);
95307ad235d9 Added Draw2d code, still work in progress Frank Benoit <benoit@tionex.de> parents: diff changeset	391 seg2 = new Segment(source.topRight, target.bottomLeft);
95307ad235d9 Added Draw2d code, still work in progress Frank Benoit <benoit@tionex.de> parents: diff changeset	392 }
95307ad235d9 Added Draw2d code, still work in progress Frank Benoit <benoit@tionex.de> parents: diff changeset	393
95307ad235d9 Added Draw2d code, still work in progress Frank Benoit <benoit@tionex.de> parents: diff changeset	394 stack.push(source);
95307ad235d9 Added Draw2d code, still work in progress Frank Benoit <benoit@tionex.de> parents: diff changeset	395 stack.push(target);
95307ad235d9 Added Draw2d code, still work in progress Frank Benoit <benoit@tionex.de> parents: diff changeset	396 stack.push(seg);
95307ad235d9 Added Draw2d code, still work in progress Frank Benoit <benoit@tionex.de> parents: diff changeset	397 stack.push(source);
95307ad235d9 Added Draw2d code, still work in progress Frank Benoit <benoit@tionex.de> parents: diff changeset	398 stack.push(target);
95307ad235d9 Added Draw2d code, still work in progress Frank Benoit <benoit@tionex.de> parents: diff changeset	399 stack.push(seg2);
95307ad235d9 Added Draw2d code, still work in progress Frank Benoit <benoit@tionex.de> parents: diff changeset	400 seg = null;
95307ad235d9 Added Draw2d code, still work in progress Frank Benoit <benoit@tionex.de> parents: diff changeset	401 seg2 = null;
95307ad235d9 Added Draw2d code, still work in progress Frank Benoit <benoit@tionex.de> parents: diff changeset	402
95307ad235d9 Added Draw2d code, still work in progress Frank Benoit <benoit@tionex.de> parents: diff changeset	403 if (target.right() < source.right()) {
95307ad235d9 Added Draw2d code, still work in progress Frank Benoit <benoit@tionex.de> parents: diff changeset	404 seg = new Segment(source.topRight, target.topRight);
95307ad235d9 Added Draw2d code, still work in progress Frank Benoit <benoit@tionex.de> parents: diff changeset	405 if (target.right() - 1 > source.x)
95307ad235d9 Added Draw2d code, still work in progress Frank Benoit <benoit@tionex.de> parents: diff changeset	406 seg2 = new Segment(source.topLeft, target.bottomRight);
95307ad235d9 Added Draw2d code, still work in progress Frank Benoit <benoit@tionex.de> parents: diff changeset	407 else
95307ad235d9 Added Draw2d code, still work in progress Frank Benoit <benoit@tionex.de> parents: diff changeset	408 seg2 = new Segment(source.bottomLeft, target.topRight);
95307ad235d9 Added Draw2d code, still work in progress Frank Benoit <benoit@tionex.de> parents: diff changeset	409 } else if (source.right() is target.right()) {
95307ad235d9 Added Draw2d code, still work in progress Frank Benoit <benoit@tionex.de> parents: diff changeset	410 seg = new Segment(source.topRight, target.bottomRight);
95307ad235d9 Added Draw2d code, still work in progress Frank Benoit <benoit@tionex.de> parents: diff changeset	411 seg2 = new Segment(source.topLeft, target.bottomRight);
95307ad235d9 Added Draw2d code, still work in progress Frank Benoit <benoit@tionex.de> parents: diff changeset	412 } else {
95307ad235d9 Added Draw2d code, still work in progress Frank Benoit <benoit@tionex.de> parents: diff changeset	413 seg = new Segment(source.bottomRight, target.bottomRight);
95307ad235d9 Added Draw2d code, still work in progress Frank Benoit <benoit@tionex.de> parents: diff changeset	414 seg2 = new Segment(source.topLeft, target.bottomRight);
95307ad235d9 Added Draw2d code, still work in progress Frank Benoit <benoit@tionex.de> parents: diff changeset	415 }
95307ad235d9 Added Draw2d code, still work in progress Frank Benoit <benoit@tionex.de> parents: diff changeset	416
95307ad235d9 Added Draw2d code, still work in progress Frank Benoit <benoit@tionex.de> parents: diff changeset	417 stack.push(source);
95307ad235d9 Added Draw2d code, still work in progress Frank Benoit <benoit@tionex.de> parents: diff changeset	418 stack.push(target);
95307ad235d9 Added Draw2d code, still work in progress Frank Benoit <benoit@tionex.de> parents: diff changeset	419 stack.push(seg);
95307ad235d9 Added Draw2d code, still work in progress Frank Benoit <benoit@tionex.de> parents: diff changeset	420 stack.push(source);
95307ad235d9 Added Draw2d code, still work in progress Frank Benoit <benoit@tionex.de> parents: diff changeset	421 stack.push(target);
95307ad235d9 Added Draw2d code, still work in progress Frank Benoit <benoit@tionex.de> parents: diff changeset	422 stack.push(seg2);
95307ad235d9 Added Draw2d code, still work in progress Frank Benoit <benoit@tionex.de> parents: diff changeset	423 }
95307ad235d9 Added Draw2d code, still work in progress Frank Benoit <benoit@tionex.de> parents: diff changeset	424
95307ad235d9 Added Draw2d code, still work in progress Frank Benoit <benoit@tionex.de> parents: diff changeset	425 private void addSegmentsTargetBesideSource(Obstacle source, Obstacle target) {
95307ad235d9 Added Draw2d code, still work in progress Frank Benoit <benoit@tionex.de> parents: diff changeset	426 //target located above source
95307ad235d9 Added Draw2d code, still work in progress Frank Benoit <benoit@tionex.de> parents: diff changeset	427 Segment seg = null;
95307ad235d9 Added Draw2d code, still work in progress Frank Benoit <benoit@tionex.de> parents: diff changeset	428 Segment seg2 = null;
95307ad235d9 Added Draw2d code, still work in progress Frank Benoit <benoit@tionex.de> parents: diff changeset	429 if (target.y > source.y) {
95307ad235d9 Added Draw2d code, still work in progress Frank Benoit <benoit@tionex.de> parents: diff changeset	430 seg = new Segment(source.topLeft, target.topLeft);
95307ad235d9 Added Draw2d code, still work in progress Frank Benoit <benoit@tionex.de> parents: diff changeset	431 if (target.y < source.bottom() - 1)
95307ad235d9 Added Draw2d code, still work in progress Frank Benoit <benoit@tionex.de> parents: diff changeset	432 seg2 = new Segment(source.bottomLeft, target.topRight);
95307ad235d9 Added Draw2d code, still work in progress Frank Benoit <benoit@tionex.de> parents: diff changeset	433 else
95307ad235d9 Added Draw2d code, still work in progress Frank Benoit <benoit@tionex.de> parents: diff changeset	434 seg2 = new Segment(source.bottomRight, target.topLeft);
95307ad235d9 Added Draw2d code, still work in progress Frank Benoit <benoit@tionex.de> parents: diff changeset	435 } else if (source.y is target.y) {
95307ad235d9 Added Draw2d code, still work in progress Frank Benoit <benoit@tionex.de> parents: diff changeset	436 //degenerate case
95307ad235d9 Added Draw2d code, still work in progress Frank Benoit <benoit@tionex.de> parents: diff changeset	437 seg = new Segment(source.topLeft, target.topRight);
95307ad235d9 Added Draw2d code, still work in progress Frank Benoit <benoit@tionex.de> parents: diff changeset	438 seg2 = new Segment(source.bottomLeft, target.topRight);
95307ad235d9 Added Draw2d code, still work in progress Frank Benoit <benoit@tionex.de> parents: diff changeset	439 } else {
95307ad235d9 Added Draw2d code, still work in progress Frank Benoit <benoit@tionex.de> parents: diff changeset	440 seg = new Segment(source.topRight, target.topRight);
95307ad235d9 Added Draw2d code, still work in progress Frank Benoit <benoit@tionex.de> parents: diff changeset	441 seg2 = new Segment(source.bottomLeft, target.topRight);
95307ad235d9 Added Draw2d code, still work in progress Frank Benoit <benoit@tionex.de> parents: diff changeset	442 }
95307ad235d9 Added Draw2d code, still work in progress Frank Benoit <benoit@tionex.de> parents: diff changeset	443 stack.push(source);
95307ad235d9 Added Draw2d code, still work in progress Frank Benoit <benoit@tionex.de> parents: diff changeset	444 stack.push(target);
95307ad235d9 Added Draw2d code, still work in progress Frank Benoit <benoit@tionex.de> parents: diff changeset	445 stack.push(seg);
95307ad235d9 Added Draw2d code, still work in progress Frank Benoit <benoit@tionex.de> parents: diff changeset	446 stack.push(source);
95307ad235d9 Added Draw2d code, still work in progress Frank Benoit <benoit@tionex.de> parents: diff changeset	447 stack.push(target);
95307ad235d9 Added Draw2d code, still work in progress Frank Benoit <benoit@tionex.de> parents: diff changeset	448 stack.push(seg2);
95307ad235d9 Added Draw2d code, still work in progress Frank Benoit <benoit@tionex.de> parents: diff changeset	449 seg = null;
95307ad235d9 Added Draw2d code, still work in progress Frank Benoit <benoit@tionex.de> parents: diff changeset	450 seg2 = null;
95307ad235d9 Added Draw2d code, still work in progress Frank Benoit <benoit@tionex.de> parents: diff changeset	451
95307ad235d9 Added Draw2d code, still work in progress Frank Benoit <benoit@tionex.de> parents: diff changeset	452 if (target.bottom() < source.bottom()) {
95307ad235d9 Added Draw2d code, still work in progress Frank Benoit <benoit@tionex.de> parents: diff changeset	453 seg = new Segment(source.bottomLeft, target.bottomLeft);
95307ad235d9 Added Draw2d code, still work in progress Frank Benoit <benoit@tionex.de> parents: diff changeset	454 if (target.bottom() - 1 > source.y)
95307ad235d9 Added Draw2d code, still work in progress Frank Benoit <benoit@tionex.de> parents: diff changeset	455 seg2 = new Segment(source.topLeft, target.bottomRight);
95307ad235d9 Added Draw2d code, still work in progress Frank Benoit <benoit@tionex.de> parents: diff changeset	456 else
95307ad235d9 Added Draw2d code, still work in progress Frank Benoit <benoit@tionex.de> parents: diff changeset	457 seg2 = new Segment(source.topRight, target.bottomLeft);
95307ad235d9 Added Draw2d code, still work in progress Frank Benoit <benoit@tionex.de> parents: diff changeset	458 } else if (source.bottom() is target.bottom()) {
95307ad235d9 Added Draw2d code, still work in progress Frank Benoit <benoit@tionex.de> parents: diff changeset	459 seg = new Segment(source.bottomLeft, target.bottomRight);
95307ad235d9 Added Draw2d code, still work in progress Frank Benoit <benoit@tionex.de> parents: diff changeset	460 seg2 = new Segment(source.topLeft, target.bottomRight);
95307ad235d9 Added Draw2d code, still work in progress Frank Benoit <benoit@tionex.de> parents: diff changeset	461 } else {
95307ad235d9 Added Draw2d code, still work in progress Frank Benoit <benoit@tionex.de> parents: diff changeset	462 seg = new Segment(source.bottomRight, target.bottomRight);
95307ad235d9 Added Draw2d code, still work in progress Frank Benoit <benoit@tionex.de> parents: diff changeset	463 seg2 = new Segment(source.topLeft, target.bottomRight);
95307ad235d9 Added Draw2d code, still work in progress Frank Benoit <benoit@tionex.de> parents: diff changeset	464 }
95307ad235d9 Added Draw2d code, still work in progress Frank Benoit <benoit@tionex.de> parents: diff changeset	465 stack.push(source);
95307ad235d9 Added Draw2d code, still work in progress Frank Benoit <benoit@tionex.de> parents: diff changeset	466 stack.push(target);
95307ad235d9 Added Draw2d code, still work in progress Frank Benoit <benoit@tionex.de> parents: diff changeset	467 stack.push(seg);
95307ad235d9 Added Draw2d code, still work in progress Frank Benoit <benoit@tionex.de> parents: diff changeset	468 stack.push(source);
95307ad235d9 Added Draw2d code, still work in progress Frank Benoit <benoit@tionex.de> parents: diff changeset	469 stack.push(target);
95307ad235d9 Added Draw2d code, still work in progress Frank Benoit <benoit@tionex.de> parents: diff changeset	470 stack.push(seg2);
95307ad235d9 Added Draw2d code, still work in progress Frank Benoit <benoit@tionex.de> parents: diff changeset	471 }
95307ad235d9 Added Draw2d code, still work in progress Frank Benoit <benoit@tionex.de> parents: diff changeset	472
95307ad235d9 Added Draw2d code, still work in progress Frank Benoit <benoit@tionex.de> parents: diff changeset	473 /**
95307ad235d9 Added Draw2d code, still work in progress Frank Benoit <benoit@tionex.de> parents: diff changeset	474 *
95307ad235d9 Added Draw2d code, still work in progress Frank Benoit <benoit@tionex.de> parents: diff changeset	475 */
95307ad235d9 Added Draw2d code, still work in progress Frank Benoit <benoit@tionex.de> parents: diff changeset	476 void cleanup() {
95307ad235d9 Added Draw2d code, still work in progress Frank Benoit <benoit@tionex.de> parents: diff changeset	477 //segments.clear();
95307ad235d9 Added Draw2d code, still work in progress Frank Benoit <benoit@tionex.de> parents: diff changeset	478 visibleVertices.clear();
95307ad235d9 Added Draw2d code, still work in progress Frank Benoit <benoit@tionex.de> parents: diff changeset	479 }
95307ad235d9 Added Draw2d code, still work in progress Frank Benoit <benoit@tionex.de> parents: diff changeset	480
95307ad235d9 Added Draw2d code, still work in progress Frank Benoit <benoit@tionex.de> parents: diff changeset	481 /**
95307ad235d9 Added Draw2d code, still work in progress Frank Benoit <benoit@tionex.de> parents: diff changeset	482 * Begins the creation of the visibility graph with the first segment
95307ad235d9 Added Draw2d code, still work in progress Frank Benoit <benoit@tionex.de> parents: diff changeset	483 * @param allObstacles list of all obstacles
95307ad235d9 Added Draw2d code, still work in progress Frank Benoit <benoit@tionex.de> parents: diff changeset	484 */
95307ad235d9 Added Draw2d code, still work in progress Frank Benoit <benoit@tionex.de> parents: diff changeset	485 private void createVisibilityGraph(List allObstacles) {
95307ad235d9 Added Draw2d code, still work in progress Frank Benoit <benoit@tionex.de> parents: diff changeset	486 stack.push(null);
95307ad235d9 Added Draw2d code, still work in progress Frank Benoit <benoit@tionex.de> parents: diff changeset	487 stack.push(null);
95307ad235d9 Added Draw2d code, still work in progress Frank Benoit <benoit@tionex.de> parents: diff changeset	488 stack.push(new Segment(start, end));
95307ad235d9 Added Draw2d code, still work in progress Frank Benoit <benoit@tionex.de> parents: diff changeset	489
95307ad235d9 Added Draw2d code, still work in progress Frank Benoit <benoit@tionex.de> parents: diff changeset	490 while (!stack.isEmpty())
95307ad235d9 Added Draw2d code, still work in progress Frank Benoit <benoit@tionex.de> parents: diff changeset	491 addSegment(stack.pop(), stack.popObstacle(), stack.popObstacle(), allObstacles);
95307ad235d9 Added Draw2d code, still work in progress Frank Benoit <benoit@tionex.de> parents: diff changeset	492 }
95307ad235d9 Added Draw2d code, still work in progress Frank Benoit <benoit@tionex.de> parents: diff changeset	493
95307ad235d9 Added Draw2d code, still work in progress Frank Benoit <benoit@tionex.de> parents: diff changeset	494 /**
95307ad235d9 Added Draw2d code, still work in progress Frank Benoit <benoit@tionex.de> parents: diff changeset	495 * Once the visibility graph is constructed, this is called to label the graph and
95307ad235d9 Added Draw2d code, still work in progress Frank Benoit <benoit@tionex.de> parents: diff changeset	496 * determine the shortest path. Returns false if no path can be found.
95307ad235d9 Added Draw2d code, still work in progress Frank Benoit <benoit@tionex.de> parents: diff changeset	497 *
95307ad235d9 Added Draw2d code, still work in progress Frank Benoit <benoit@tionex.de> parents: diff changeset	498 * @return true if a path can be found.
95307ad235d9 Added Draw2d code, still work in progress Frank Benoit <benoit@tionex.de> parents: diff changeset	499 */
95307ad235d9 Added Draw2d code, still work in progress Frank Benoit <benoit@tionex.de> parents: diff changeset	500 private bool determineShortestPath() {

98

95307ad235d9 Added Draw2d code, still work in progress