projects/dwt2: org.eclipse.draw2d/src/org/eclipse/draw2d/graph/Path.d annotate

annotate org.eclipse.draw2d/src/org/eclipse/draw2d/graph/Path.d @ 16:dbfb303e8fb0

first complete successful compile (win-only)

author	Frank Benoit <benoit@tionex.de>
date	Wed, 18 Mar 2009 08:56:47 +0100
parents	bc29606a740c
children

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

Mercurial > projects > dwt2

annotate org.eclipse.draw2d/src/org/eclipse/draw2d/graph/Path.d @ 16:dbfb303e8fb0