001: /*
002: * DO NOT ALTER OR REMOVE COPYRIGHT NOTICES OR THIS HEADER.
003: *
004: * Copyright 1997-2007 Sun Microsystems, Inc. All rights reserved.
005: *
006: * The contents of this file are subject to the terms of either the GNU
007: * General Public License Version 2 only ("GPL") or the Common
008: * Development and Distribution License("CDDL") (collectively, the
009: * "License"). You may not use this file except in compliance with the
010: * License. You can obtain a copy of the License at
011: * http://www.netbeans.org/cddl-gplv2.html
012: * or nbbuild/licenses/CDDL-GPL-2-CP. See the License for the
013: * specific language governing permissions and limitations under the
014: * License. When distributing the software, include this License Header
015: * Notice in each file and include the License file at
016: * nbbuild/licenses/CDDL-GPL-2-CP. Sun designates this
017: * particular file as subject to the "Classpath" exception as provided
018: * by Sun in the GPL Version 2 section of the License file that
019: * accompanied this code. If applicable, add the following below the
020: * License Header, with the fields enclosed by brackets [] replaced by
021: * your own identifying information:
022: * "Portions Copyrighted [year] [name of copyright owner]"
023: *
024: * Contributor(s):
025: *
026: * The Original Software is NetBeans. The Initial Developer of the Original
027: * Software is Sun Microsystems, Inc. Portions Copyright 1997-2007 Sun
028: * Microsystems, Inc. All Rights Reserved.
029: *
030: * If you wish your version of this file to be governed by only the CDDL
031: * or only the GPL Version 2, indicate your decision by adding
032: * "[Contributor] elects to include this software in this distribution
033: * under the [CDDL or GPL Version 2] license." If you do not indicate a
034: * single choice of license, a recipient has the option to distribute
035: * your version of this file under either the CDDL, the GPL Version 2 or
036: * to extend the choice of license to its licensees as provided above.
037: * However, if you add GPL Version 2 code and therefore, elected the GPL
038: * Version 2 license, then the option applies only if the new code is
039: * made subject to such option by the copyright holder.
040: */
041: package org.netbeans.modules.visual.router;
042:
043: import org.netbeans.api.visual.anchor.Anchor;
044: import org.netbeans.api.visual.widget.Scene;
045:
046: import java.awt.*;
047: import java.util.ArrayList;
048: import java.util.Arrays;
049: import java.util.List;
050:
051: /**
052: * @author David Kaspar
053: */
054: final class OrthogonalSearchRouterCore {
055:
056: private static final int MAXIMAL_DEPTH = 5; // 6 is too slow for 10+ nodes and 10+ links
057: private static final int CORNER_LENGTH = 200;
058: private static final boolean UPDATE_COLLISION_LISTS = true; // set true for faster computation but not optimal results
059: private static final boolean UPDATE_COLLISION_LISTS_REMOVE = true;
060: static final boolean IGNORE_LINKS_WITH_ACTUAL_PORTS = false; // cause links to try to merge as a bus, multilinks are merged too
061: private static final boolean OPTIMALIZE_REGIONS = false;
062:
063: private Scene scene;
064: private ArrayList<Rectangle> verticalCollisions;
065: private ArrayList<Rectangle> horizontalCollisions;
066: private Point sourcePoint;
067: private Anchor.Direction sourceDirection;
068: private Point targetPoint;
069: private Anchor.Direction targetDirection;
070:
071: private Point sourceBoundaryPoint;
072: private Point targetBoundaryPoint;
073: private final OrthogonalSearchRouterRegion[] regions = new OrthogonalSearchRouterRegion[MAXIMAL_DEPTH + 1];
074:
075: private Point[] bestControlPoints;
076: private int bestControlPointsPrice;
077:
078: public OrthogonalSearchRouterCore(Scene scene,
079: ArrayList<Rectangle> verticalCollisions,
080: ArrayList<Rectangle> horizontalCollisions,
081: Point sourcePoint, Anchor.Direction sourceDirection,
082: Point targetPoint, Anchor.Direction targetDirection) {
083: this .scene = scene;
084: this .verticalCollisions = verticalCollisions;
085: this .horizontalCollisions = horizontalCollisions;
086: this .sourcePoint = sourcePoint;
087: this .sourceDirection = sourceDirection;
088: this .targetPoint = targetPoint;
089: this .targetDirection = targetDirection;
090: }
091:
092: public OrthogonalSearchRouter.Solution route() {
093: sourceBoundaryPoint = findBoundaryPoint(sourcePoint,
094: sourceDirection);
095: targetBoundaryPoint = findBoundaryPoint(targetPoint,
096: targetDirection);
097:
098: search(new OrthogonalSearchRouterRegion(
099: /*null, */sourceBoundaryPoint.x,
100: sourceBoundaryPoint.y, 0, 0, sourceDirection, 0));
101:
102: return bestControlPoints != null ? new OrthogonalSearchRouter.Solution(
103: bestControlPointsPrice, Arrays
104: .asList(bestControlPoints))
105: : null;
106: }
107:
108: private Point findBoundaryPoint(Point point,
109: Anchor.Direction direction) {
110: point = new Point(point);
111: ArrayList<Rectangle> collisions;
112: switch (direction) {
113: case LEFT:
114: case RIGHT:
115: collisions = horizontalCollisions;
116: break;
117: case BOTTOM:
118: case TOP:
119: collisions = verticalCollisions;
120: break;
121: default:
122: return point;
123: }
124:
125: boolean changed = true;
126: while (changed) {
127: changed = false;
128:
129: switch (direction) {
130: case LEFT:
131: for (Rectangle rectangle : collisions) {
132: if (rectangle.contains(point)) {
133: point.x = rectangle.x - 1;
134: changed = true;
135: }
136: }
137: break;
138: case RIGHT:
139: for (Rectangle rectangle : collisions) {
140: if (rectangle.contains(point)) {
141: point.x = rectangle.x + rectangle.width;
142: changed = true;
143: }
144: }
145: break;
146: case BOTTOM:
147: for (Rectangle rectangle : collisions) {
148: if (rectangle.contains(point)) {
149: point.y = rectangle.y + rectangle.height;
150: changed = true;
151: }
152: }
153: break;
154: case TOP:
155: for (Rectangle rectangle : collisions) {
156: if (rectangle.contains(point)) {
157: point.y = rectangle.y - 1;
158: changed = true;
159: }
160: }
161: break;
162: }
163: }
164: return point;
165: }
166:
167: private void search(OrthogonalSearchRouterRegion region) {
168: Rectangle inter = region.intersection(scene.getMaximumBounds());
169: region = new OrthogonalSearchRouterRegion(inter.x, inter.y,
170: inter.width, inter.height, region.getDirection(),
171: region.getDepth());
172:
173: if (region.width < 0 || region.height < 0)
174: return;
175: assert region.x >= OrthogonalSearchRouterRegion.MIN_INT_REGION;
176: assert region.y >= OrthogonalSearchRouterRegion.MIN_INT_REGION;
177: assert region.x + region.width <= OrthogonalSearchRouterRegion.MAX_INT_REGION;
178: assert region.y + region.height <= OrthogonalSearchRouterRegion.MAX_INT_REGION;
179: // System.out.println ("REG: " + region);
180:
181: int depth = region.getDepth();
182: if (depth >= MAXIMAL_DEPTH) // too deeply
183: return;
184:
185: region.extendToInfinity();
186: regions[depth] = region;
187:
188: List<Rectangle> collisions = region.isHorizontal() ? horizontalCollisions
189: : verticalCollisions;
190:
191: ArrayList<OrthogonalSearchRouterRegion> subRegions = region
192: .parseSubRegions(collisions);
193:
194: boolean updatedCollissions = false;
195: if (!region.isEmpty()) {
196: // addRectangle (link, region);
197: if (UPDATE_COLLISION_LISTS) {
198: Rectangle updateCollisionsRect = new Rectangle(region);
199: horizontalCollisions.add(updateCollisionsRect);
200: verticalCollisions.add(updateCollisionsRect);
201: updatedCollissions = true;
202: }
203: }
204:
205: if (region.containsInsideEdges(targetBoundaryPoint)) {
206: // TODO - not true - point could lay on right or bottom edge ! - this is not checked yet
207: // System.out.println ("FOUND");
208: constructControlPoints(depth);
209: // TODO
210: // if not correct direction then
211: // reuse the same pathRegion rectangle and correct the direction
212: // return the path as the best
213: } else {
214:
215: // try left and/or right
216: if (region.getLength() > 0) {
217: search(region.cloneWithCounterClockwiseEdge());
218: search(region.cloneWithClockwiseEdge());
219: }
220:
221: // tryNearestSubRegion and maybeOthersSubRegions
222: if (!subRegions.isEmpty()) {
223: // OrthogonalLinkRouterRegion r0 = (OrthogonalLinkRouterRegion) subRegions.get (0);
224: // if (subRegions.size () > 1) {
225: // int dist0 = r0.getDistance (targetBoundaryPoint);
226: // final OrthogonalLinkRouterRegion r1 = (OrthogonalLinkRouterRegion) subRegions.get (subRegions.size () - 1);
227: // int dist1 = r1.getDistance (targetBoundaryPoint);
228: // if (dist1 < dist0)
229: // r0 = r1;
230: // search (r0);
231: for (OrthogonalSearchRouterRegion subRegion : subRegions) {
232: // if (subRegion != r0)
233: search(subRegion);
234: }
235: // } else
236: // search (r0);
237: }
238: }
239:
240: if (updatedCollissions && UPDATE_COLLISION_LISTS_REMOVE) {
241: horizontalCollisions
242: .remove(horizontalCollisions.size() - 1);
243: verticalCollisions.remove(verticalCollisions.size() - 1);
244: }
245: }
246:
247: private void constructControlPoints(int depth) {
248: Anchor.Direction desiredDirection;
249: switch (targetDirection) {
250: case LEFT:
251: desiredDirection = Anchor.Direction.RIGHT;
252: break;
253: case RIGHT:
254: desiredDirection = Anchor.Direction.LEFT;
255: break;
256: case TOP:
257: desiredDirection = Anchor.Direction.BOTTOM;
258: break;
259: case BOTTOM:
260: desiredDirection = Anchor.Direction.TOP;
261: break;
262: default:
263: throw new IllegalArgumentException();
264: }
265: if (desiredDirection != regions[depth].getDirection()) {
266: final OrthogonalSearchRouterRegion region = regions[depth];
267: depth++;
268: regions[depth] = new OrthogonalSearchRouterRegion(region.x,
269: region.y, region.width, region.height,
270: desiredDirection, depth);
271: }
272:
273: Point[] controlPoints = new Point[depth + 4];
274: controlPoints[0] = new Point(sourcePoint);
275: controlPoints[1] = new Point(sourceBoundaryPoint);
276: for (int a = 2; a < depth + 2; a++)
277: controlPoints[a] = new Point();
278: controlPoints[depth + 2] = new Point(targetBoundaryPoint);
279: controlPoints[depth + 3] = new Point(targetPoint);
280:
281: for (int a = 0; a < depth; a++) {
282: final OrthogonalSearchRouterRegion region = regions[a];
283: Point previousPoint = controlPoints[a + 1];
284: Point currentPoint = controlPoints[a + 2];
285: if (region.isHorizontal()) {
286: int yy;
287: if (a > 0) {
288: final int y1 = region.y;
289: final int y2 = region.y + region.height;
290: if (y1 <= OrthogonalSearchRouterRegion.MIN_INT_REGION
291: && y2 < OrthogonalSearchRouterRegion.MAX_INT_REGION)
292: yy = y2 - OrthogonalSearchRouter.SPACING_EDGE;
293: else if (y1 > OrthogonalSearchRouterRegion.MIN_INT_REGION
294: && y2 >= OrthogonalSearchRouterRegion.MAX_INT_REGION)
295: yy = y1 + OrthogonalSearchRouter.SPACING_EDGE;
296: else
297: yy = region.y + region.height / 2;
298: } else
299: yy = previousPoint.y;
300: previousPoint.y = currentPoint.y = yy;
301: } else {
302: int xx;
303: if (a > 0) {
304: final int x1 = region.x;
305: final int x2 = region.x + region.width;
306: if (x1 <= OrthogonalSearchRouterRegion.MIN_INT_REGION
307: && x2 < OrthogonalSearchRouterRegion.MAX_INT_REGION)
308: xx = x2 - OrthogonalSearchRouter.SPACING_EDGE;
309: else if (x1 > OrthogonalSearchRouterRegion.MIN_INT_REGION
310: && x2 >= OrthogonalSearchRouterRegion.MAX_INT_REGION)
311: xx = x1 + OrthogonalSearchRouter.SPACING_EDGE;
312: else
313: xx = region.x + region.width / 2;
314: } else
315: xx = previousPoint.x;
316: previousPoint.x = currentPoint.x = xx;
317: }
318: }
319:
320: if (regions[depth].isHorizontal())
321: controlPoints[depth + 1].y = controlPoints[depth + 2].y;
322: else
323: controlPoints[depth + 1].x = controlPoints[depth + 2].x;
324:
325: if (OPTIMALIZE_REGIONS) {
326: for (int a = depth; a > 0; a--) {
327: // if (infiniteY[a]) {
328: final int newY = controlPoints[a + 3].y;
329: final OrthogonalSearchRouterRegion regionY = regions[a];
330: final OrthogonalSearchRouterRegion regionY1 = regions[a - 1];
331: if (newY >= regionY.y
332: && newY < regionY.y + regionY.height
333: && newY >= regionY1.y
334: && newY < regionY1.y + regionY1.height)
335: controlPoints[a + 1].y = controlPoints[a + 2].y = newY;
336: // }
337: // if (infiniteX[a]) {
338: final int newX = controlPoints[a + 3].x;
339: final OrthogonalSearchRouterRegion regionX = regions[a];
340: final OrthogonalSearchRouterRegion regionX1 = regions[a - 1];
341: if (newX >= regionX.x
342: && newX < regionX.x + regionX.width
343: && newX >= regionX1.x
344: && newX < regionX1.x + regionX1.width)
345: controlPoints[a + 1].x = controlPoints[a + 2].x = newX;
346: // }
347: }
348: }
349:
350: int controlPointsLength = removeDuplicateControlPoints(controlPoints);
351:
352: int price = calculatePrice(controlPointsLength, controlPoints);
353:
354: if (bestControlPoints == null || bestControlPointsPrice > price) {
355: if (controlPointsLength < controlPoints.length) {
356: bestControlPoints = new Point[controlPointsLength];
357: System.arraycopy(controlPoints, 0, bestControlPoints,
358: 0, controlPointsLength);
359: } else
360: bestControlPoints = controlPoints;
361: bestControlPointsPrice = price;
362: // System.out.println ("BEST");
363: // DEBUG
364: // if (SHOW_DEBUG_REGIONS) {
365: // clearRectangle ();
366: // for (int i = 0; i <= depth; i++)
367: // addRectangle (regions[i]);
368: // }
369: }
370: }
371:
372: private int removeDuplicateControlPoints(Point[] controlPoints) {
373: int newPointsLength = 0;
374: for (int a = 1; a < controlPoints.length - 1; a++) {
375: Point p0 = controlPoints[newPointsLength];
376: Point p1 = controlPoints[a];
377: Point p2 = controlPoints[a + 1];
378:
379: if (p0.x == p1.x && p1.x == p2.x)
380: continue;
381: if (p0.y == p1.y && p1.y == p2.y)
382: continue;
383:
384: newPointsLength++;
385: if (newPointsLength != a)
386: controlPoints[newPointsLength] = p1;
387: }
388: newPointsLength++;
389: if (newPointsLength < controlPoints.length - 1)
390: controlPoints[newPointsLength++] = controlPoints[controlPoints.length - 1];
391: return newPointsLength;
392: }
393:
394: private int calculatePrice(int controlPointsLength,
395: Point[] controlPoints) {
396: int price = 0;
397: for (int a = 1; a < controlPointsLength; a++) {
398: final Point p1 = controlPoints[a - 1];
399: final Point p2 = controlPoints[a];
400: price += Math.abs(p2.y - p1.y) + Math.abs(p2.x - p1.x)
401: + CORNER_LENGTH;
402: }
403: if (controlPointsLength > 0) {
404: int average = price / controlPointsLength;
405: int diff = 0;
406: for (int a = 1; a < controlPointsLength; a++) {
407: final Point p1 = controlPoints[a - 1];
408: final Point p2 = controlPoints[a];
409: diff += Math.abs(Math.abs(p2.y - p1.y)
410: + Math.abs(p2.x - p1.x) - average);
411: }
412: diff /= controlPointsLength;
413: price += diff;
414: }
415: // price += depth * CORNER_LENGTH;
416: return price;
417: }
418:
419: }
|