1 /*******************************************************************************
\r
2 * Copyright (c) 2007, 2010 Association for Decentralized Information Management
\r
3 * in Industry THTH ry.
\r
4 * All rights reserved. This program and the accompanying materials
\r
5 * are made available under the terms of the Eclipse Public License v1.0
\r
6 * which accompanies this distribution, and is available at
\r
7 * http://www.eclipse.org/legal/epl-v10.html
\r
10 * VTT Technical Research Centre of Finland - initial API and implementation
\r
11 *******************************************************************************/
\r
12 package org.simantics.g2d.routing.spatial;
\r
14 import java.util.ArrayList;
\r
15 import java.util.Collection;
\r
16 import java.util.Random;
\r
18 import org.simantics.g2d.routing.algorithm1.Rectangle;
\r
21 * 2-dimensional R-tree
\r
23 public class RTree {
\r
25 public static final int MAX_ENTRIES = 7;
\r
26 public static final int MIN_ENTRIES = 3;
\r
27 public static final int MAX_ENTRIES_AFTER_SPLIT = MAX_ENTRIES - MIN_ENTRIES + 1;
\r
29 static interface INode {
\r
30 void search(Rectangle rect, IRectangleProcedure proc);
\r
31 boolean intersects(Rectangle rect);
\r
32 Split add(Rectangle rect, Object value);
\r
34 double[] getRectangles();
\r
35 Object[] getChildren();
\r
36 void setCount(int count);
\r
38 Rectangle findBounds();
\r
41 static class Split {
\r
42 double oldX0, oldY0, oldX1, oldY1;
\r
43 double newX0, newY0, newX1, newY1;
\r
46 public Split(double oldX0, double oldY0, double oldX1, double oldY1,
\r
47 double newX0, double newY0, double newX1, double newY1,
\r
57 this.newNode = newNode;
\r
62 class Node implements INode {
\r
63 double[] rectangles = new double[MAX_ENTRIES*4];
\r
64 INode[] children = new INode[MAX_ENTRIES];
\r
67 public void search(Rectangle rect, IRectangleProcedure proc) {
\r
68 double x0 = rect.x0;
\r
69 double y0 = rect.y0;
\r
70 double x1 = rect.x1;
\r
71 double y1 = rect.y1;
\r
72 for(int i=0,ad=0;i<count;++i,ad+=4)
\r
73 if(x1 >= rectangles[ad] && x0 <= rectangles[ad+2] &&
\r
74 y1 >= rectangles[ad+1] && y0 <= rectangles[ad+3])
\r
75 children[i].search(rect, proc);
\r
78 public boolean intersects(Rectangle rect) {
\r
79 double x0 = rect.x0;
\r
80 double y0 = rect.y0;
\r
81 double x1 = rect.x1;
\r
82 double y1 = rect.y1;
\r
83 for(int i=0,ad=0;i<count;++i,ad+=4)
\r
84 if(x1 >= rectangles[ad] && x0 <= rectangles[ad+2] &&
\r
85 y1 >= rectangles[ad+1] && y0 <= rectangles[ad+3])
\r
86 if(children[i].intersects(rect))
\r
92 public Split add(Rectangle rect, Object value) {
\r
93 double x0 = rect.x0;
\r
94 double y0 = rect.y0;
\r
95 double x1 = rect.x1;
\r
96 double y1 = rect.y1;
\r
99 double bestArea = 0.0;
\r
100 double bestAddition = Double.POSITIVE_INFINITY;
\r
101 for(int i=0,ad=0;i<count;++i) {
\r
102 double x0b = rectangles[ad++];
\r
103 double y0b = rectangles[ad++];
\r
104 double x1b = rectangles[ad++];
\r
105 double y1b = rectangles[ad++];
\r
106 double area = (x1b-x0b)*(y1b-y0b);
\r
107 if(x0 < x0b) x0b = x0;
\r
108 if(y0 < y0b) y0b = y0;
\r
109 if(x1 > x1b) x1b = x1;
\r
110 if(y1 > y1b) y1b = y1;
\r
111 double addition = (x1b-x0b)*(y1b-y0b) - area;
\r
112 if(addition < bestAddition || (addition==bestAddition && area < bestArea)) {
\r
115 bestAddition = addition;
\r
118 Split split = children[bestId].add(rect, value);
\r
119 if(split == null) {
\r
120 if(bestAddition > 0.0) {
\r
121 int ad = bestId * 4;
\r
122 rectangles[ad] = Math.min(rectangles[ad], x0); ++ad;
\r
123 rectangles[ad] = Math.min(rectangles[ad], y0); ++ad;
\r
124 rectangles[ad] = Math.max(rectangles[ad], x1); ++ad;
\r
125 rectangles[ad] = Math.max(rectangles[ad], y1);
\r
129 int ad = bestId * 4;
\r
130 rectangles[ad] = split.oldX0; ++ad;
\r
131 rectangles[ad] = split.oldY0; ++ad;
\r
132 rectangles[ad] = split.oldX1; ++ad;
\r
133 rectangles[ad] = split.oldY1;
\r
134 if(count < children.length) {
\r
136 rectangles[ad] = split.newX0; ++ad;
\r
137 rectangles[ad] = split.newY0; ++ad;
\r
138 rectangles[ad] = split.newX1; ++ad;
\r
139 rectangles[ad] = split.newY1;
\r
140 children[count++] = split.newNode;
\r
143 Node newNode = new Node();
\r
144 findNodeSeeds(rectangles, children,
\r
145 new Rectangle(split.newX0, split.newY0, split.newX1, split.newY1),
\r
146 split.newNode, newNode.rectangles, newNode.children);
\r
147 return splitNode(this, newNode);
\r
155 public Object[] getChildren() {
\r
160 public double[] getRectangles() {
\r
165 public void setCount(int count) {
\r
166 this.count = count;
\r
170 public Rectangle findBounds() {
\r
171 double x0 = Double.POSITIVE_INFINITY;
\r
172 double y0 = Double.POSITIVE_INFINITY;
\r
173 double x1 = Double.NEGATIVE_INFINITY;
\r
174 double y1 = Double.NEGATIVE_INFINITY;
\r
175 for(int i=0;i<count;++i) {
\r
177 double x0a = rectangles[ad++];
\r
178 double y0a = rectangles[ad++];
\r
179 double x1a = rectangles[ad++];
\r
180 double y1a = rectangles[ad++];
\r
181 Rectangle rect = children[i].findBounds();
\r
183 throw new RuntimeException("x0");
\r
185 throw new RuntimeException("y0");
\r
187 throw new RuntimeException("x1");
\r
189 throw new RuntimeException("y1");
\r
190 x0 = Math.min(x0, x0a);
\r
191 y0 = Math.min(y0, y0a);
\r
192 x1 = Math.max(x1, x1a);
\r
193 y1 = Math.max(y1, y1a);
\r
195 return new Rectangle(x0, y0, x1, y1);
\r
199 class Leaf implements INode {
\r
200 double[] rectangles = new double[MAX_ENTRIES*4];
\r
201 Object[] children = new Object[MAX_ENTRIES];
\r
204 public void search(Rectangle rect, IRectangleProcedure proc) {
\r
205 double x0 = rect.x0;
\r
206 double y0 = rect.y0;
\r
207 double x1 = rect.x1;
\r
208 double y1 = rect.y1;
\r
209 for(int i=0,ad=0;i<count;++i,ad+=4)
\r
210 if(x1 >= rectangles[ad] && x0 <= rectangles[ad+2] &&
\r
211 y1 >= rectangles[ad+1] && y0 <= rectangles[ad+3])
\r
213 rectangles[ad], rectangles[ad+1],
\r
214 rectangles[ad+2], rectangles[ad+3],
\r
218 public boolean intersects(Rectangle rect) {
\r
219 double x0 = rect.x0;
\r
220 double y0 = rect.y0;
\r
221 double x1 = rect.x1;
\r
222 double y1 = rect.y1;
\r
223 for(int i=0,ad=0;i<count;++i,ad+=4)
\r
224 if(x1 >= rectangles[ad] && x0 <= rectangles[ad+2] &&
\r
225 y1 >= rectangles[ad+1] && y0 <= rectangles[ad+3])
\r
231 public Split add(Rectangle rect, Object value) {
\r
232 if(count < children.length) {
\r
234 rectangles[ad++] = rect.x0;
\r
235 rectangles[ad++] = rect.y0;
\r
236 rectangles[ad++] = rect.x1;
\r
237 rectangles[ad] = rect.y1;
\r
238 children[count++] = value;
\r
242 Leaf newLeaf = new Leaf();
\r
243 findNodeSeeds(rectangles, children, rect, value, newLeaf.rectangles, newLeaf.children);
\r
244 return splitNode(this, newLeaf);
\r
249 public Object[] getChildren() {
\r
254 public double[] getRectangles() {
\r
259 public void setCount(int count) {
\r
260 this.count = count;
\r
264 public Rectangle findBounds() {
\r
265 double x0 = Double.POSITIVE_INFINITY;
\r
266 double y0 = Double.POSITIVE_INFINITY;
\r
267 double x1 = Double.NEGATIVE_INFINITY;
\r
268 double y1 = Double.NEGATIVE_INFINITY;
\r
269 for(int i=0;i<count;++i) {
\r
271 double x0a = rectangles[ad++];
\r
272 double y0a = rectangles[ad++];
\r
273 double x1a = rectangles[ad++];
\r
274 double y1a = rectangles[ad++];
\r
275 x0 = Math.min(x0, x0a);
\r
276 y0 = Math.min(y0, y0a);
\r
277 x1 = Math.max(x1, x1a);
\r
278 y1 = Math.max(y1, y1a);
\r
280 return new Rectangle(x0, y0, x1, y1);
\r
284 static Split splitNode(INode a, INode b) {
\r
285 double[] aRectangles = a.getRectangles();
\r
286 Object[] aValues = a.getChildren();
\r
287 double[] bRectangles = b.getRectangles();
\r
288 Object[] bValues = b.getChildren();
\r
289 double x0a = aRectangles[0];
\r
290 double y0a = aRectangles[1];
\r
291 double x1a = aRectangles[2];
\r
292 double y1a = aRectangles[3];
\r
293 double areaA = (x1a-x0a) * (y1a-y0a);
\r
294 double x0b = bRectangles[0];
\r
295 double y0b = bRectangles[1];
\r
296 double x1b = bRectangles[2];
\r
297 double y1b = bRectangles[3];
\r
298 double areaB = (x1b-x0b) * (y1b-y0b);
\r
299 int aCount = 1, bCount = 1;
\r
301 int firstUnassigned = 1;
\r
303 while(firstUnassigned < aValues.length) {
\r
305 double bestDiff = Double.NEGATIVE_INFINITY;
\r
306 boolean bestToB = false;
\r
307 for(int i=firstUnassigned,ad=firstUnassigned*4;i<aValues.length;++i) {
\r
308 double x0 = aRectangles[ad++];
\r
309 double y0 = aRectangles[ad++];
\r
310 double x1 = aRectangles[ad++];
\r
311 double y1 = aRectangles[ad++];
\r
313 (Math.max(x1a, x1) - Math.min(x0a, x0)) * (Math.max(y1a, y1) - Math.min(y0a, y0)) - areaA;
\r
315 (Math.max(x1b, x1) - Math.min(x0b, x0)) * (Math.max(y1b, y1) - Math.min(y0b, y0)) - areaB;
\r
316 double diff = Math.abs(da-db);
\r
317 if(diff > bestDiff) {
\r
320 bestToB = db < da || (db==da && bCount < aCount);
\r
325 rotate2(bRectangles, bValues, bCount, aRectangles, aValues, firstUnassigned, bestI);
\r
326 x0b = Math.min(x0b, bRectangles[4*bCount]);
\r
327 y0b = Math.min(y0b, bRectangles[4*bCount+1]);
\r
328 x1b = Math.max(x1b, bRectangles[4*bCount+2]);
\r
329 y1b = Math.max(y1b, bRectangles[4*bCount+3]);
\r
332 if(bCount == MAX_ENTRIES_AFTER_SPLIT) {
\r
333 while(firstUnassigned < aValues.length) {
\r
334 move(aRectangles, aValues, aCount, firstUnassigned);
\r
335 x0a = Math.min(x0a, aRectangles[4*aCount]);
\r
336 y0a = Math.min(y0a, aRectangles[4*aCount+1]);
\r
337 x1a = Math.max(x1a, aRectangles[4*aCount+2]);
\r
338 y1a = Math.max(y1a, aRectangles[4*aCount+3]);
\r
346 //System.out.println(aRectangles.length + " " + aValues.length + " " + aCount + " " + bCount + " " + firstUnassigned + " " + bestI);
\r
347 rotate(aRectangles, aValues, aCount, firstUnassigned, bestI);
\r
348 x0a = Math.min(x0a, aRectangles[4*aCount]);
\r
349 y0a = Math.min(y0a, aRectangles[4*aCount+1]);
\r
350 x1a = Math.max(x1a, aRectangles[4*aCount+2]);
\r
351 y1a = Math.max(y1a, aRectangles[4*aCount+3]);
\r
354 if(aCount == MAX_ENTRIES_AFTER_SPLIT) {
\r
355 while(firstUnassigned < aValues.length) {
\r
356 move2(bRectangles, bValues, bCount, aRectangles, aValues, firstUnassigned);
\r
357 x0b = Math.min(x0b, bRectangles[4*bCount]);
\r
358 y0b = Math.min(y0b, bRectangles[4*bCount+1]);
\r
359 x1b = Math.max(x1b, bRectangles[4*bCount+2]);
\r
360 y1b = Math.max(y1b, bRectangles[4*bCount+3]);
\r
369 a.setCount(aCount);
\r
370 b.setCount(bCount);
\r
371 return new Split(x0a, y0a, x1a, y1a, x0b, y0b, x1b, y1b, b);
\r
374 static void move(double[] array, Object[] oArray, int a, int b) {
\r
376 oArray[a] = oArray[b];
\r
380 for(int i=0;i<4;++i)
\r
381 array[a++] = array[b++];
\r
384 static void move2(double[] array, Object[] oArray, int a, double[] array2, Object[] oArray2, int b) {
\r
385 oArray[a] = oArray2[b];
\r
389 for(int i=0;i<4;++i)
\r
390 array[a++] = array2[b++];
\r
393 static void rotate(double[] array, Object[] oArray, int a, int b, int c) {
\r
398 Object temp = oArray[a];
\r
399 oArray[a] = oArray[c];
\r
405 for(int i=0;i<4;++i) {
\r
406 double temp = array[a];
\r
407 array[a] = array[c];
\r
415 Object temp = oArray[a];
\r
416 oArray[a] = oArray[c];
\r
422 for(int i=0;i<4;++i) {
\r
423 double temp = array[a];
\r
424 array[a] = array[c];
\r
431 Object temp = oArray[b];
\r
432 oArray[b] = oArray[a];
\r
433 oArray[a] = oArray[c];
\r
440 for(int i=0;i<4;++i) {
\r
441 double temp = array[b];
\r
442 array[b] = array[a];
\r
443 array[a] = array[c];
\r
450 static void rotate2(double[] array, Object[] oArray, int a, double[] array2, Object[] oArray2, int b, int c) {
\r
452 oArray[a] = oArray2[c];
\r
453 oArray2[c] = oArray2[b];
\r
460 for(int i=0;i<4;++i) {
\r
461 array[a] = array2[c];
\r
462 array2[c] = array2[b];
\r
468 static void findNodeSeeds(double[] rectangles, Object[] values, Rectangle rect, Object value,
\r
469 double[] newRectangles, Object[] newValues) {
\r
472 double bestInefficiency = Double.NEGATIVE_INFINITY;
\r
473 for(int j=0;j<=rectangles.length;j+=4) {
\r
474 double x0b, y0b, x1b, y1b;
\r
475 if(j < rectangles.length) {
\r
476 x0b = rectangles[j];
\r
477 y0b = rectangles[j+1];
\r
478 x1b = rectangles[j+2];
\r
479 y1b = rectangles[j+3];
\r
487 double areaB = (x1b-x0b) * (y1b-y0b);
\r
488 for(int i=0;i<j;) {
\r
489 double x0a = rectangles[i++];
\r
490 double y0a = rectangles[i++];
\r
491 double x1a = rectangles[i++];
\r
492 double y1a = rectangles[i++];
\r
493 double inefficiency =
\r
494 (Math.max(x1a, x1b) - Math.min(x0a, x0b)) * (Math.max(y1a, y1b) - Math.min(y0a, y0b))
\r
495 - (x1a-x0a) * (y1a-y0a) - areaB;
\r
496 if(inefficiency > bestInefficiency) {
\r
499 bestInefficiency = inefficiency;
\r
503 if(bestJ==rectangles.length) {
\r
504 newRectangles[0] = rect.x0;
\r
505 newRectangles[1] = rect.y0;
\r
506 newRectangles[2] = rect.x1;
\r
507 newRectangles[3] = rect.y1;
\r
508 newValues[0] = value;
\r
511 newValues[0] = values[bestJ/4];
\r
512 values[bestJ/4] = value;
\r
514 newRectangles[0] = rectangles[bestJ++];
\r
515 newRectangles[1] = rectangles[bestJ++];
\r
516 newRectangles[2] = rectangles[bestJ++];
\r
517 newRectangles[3] = rectangles[bestJ];
\r
520 rectangles[bestJ++] = rect.x0;
\r
521 rectangles[bestJ++] = rect.y0;
\r
522 rectangles[bestJ++] = rect.x1;
\r
523 rectangles[bestJ] = rect.y1;
\r
528 Object temp2 = values[0];
\r
529 values[0] = values[bestI/4];
\r
530 values[bestI/4] = temp2;
\r
533 temp = rectangles[0];
\r
534 rectangles[0] = rectangles[bestI];
\r
535 rectangles[bestI++] = temp;
\r
536 temp = rectangles[1];
\r
537 rectangles[1] = rectangles[bestI];
\r
538 rectangles[bestI++] = temp;
\r
539 temp = rectangles[2];
\r
540 rectangles[2] = rectangles[bestI];
\r
541 rectangles[bestI++] = temp;
\r
542 temp = rectangles[3];
\r
543 rectangles[3] = rectangles[bestI];
\r
544 rectangles[bestI++] = temp;
\r
548 INode root = new Leaf();
\r
550 public void search(Rectangle rect, IRectangleProcedure proc) {
\r
551 root.search(rect, proc);
\r
554 public boolean intersects(Rectangle rect) {
\r
555 return root.intersects(rect);
\r
558 public void add(Rectangle rect, Object obj) {
\r
559 Split split = root.add(rect, obj);
\r
560 if(split != null) {
\r
561 Node node = new Node();
\r
562 node.rectangles[0] = split.oldX0;
\r
563 node.rectangles[1] = split.oldY0;
\r
564 node.rectangles[2] = split.oldX1;
\r
565 node.rectangles[3] = split.oldY1;
\r
566 node.rectangles[4] = split.newX0;
\r
567 node.rectangles[5] = split.newY0;
\r
568 node.rectangles[6] = split.newX1;
\r
569 node.rectangles[7] = split.newY1;
\r
570 node.children[0] = root;
\r
571 node.children[1] = split.newNode;
\r
578 static Random random = new Random();
\r
580 public static Rectangle randomRectangle() {
\r
581 double x = random.nextDouble();
\r
582 double y = random.nextDouble();
\r
583 double w = random.nextDouble()*0.1;
\r
584 double h = random.nextDouble()*0.1;
\r
585 return new Rectangle(x, y, x+w, y+h);
\r
588 public static void main(String[] args) {
\r
589 Collection<Rectangle> rects = new ArrayList<Rectangle>();
\r
591 for(int i=0;i<1000;++i)
\r
592 rects.add(randomRectangle());
\r
594 RTree tree = new RTree();
\r
595 for(Rectangle rect : rects) {
\r
596 tree.add(rect, rect);
\r
597 tree.root.findBounds();
\r
602 for(int i=0;i<100;++i) {
\r
603 final Rectangle q = randomRectangle();
\r
606 for(Rectangle rect : rects)
\r
607 if(q.intersects(rect))
\r
610 final int[] iCount2 = new int[] { 0 };
\r
611 tree.search(q, new IRectangleProcedure() {
\r
614 public void call(double x0, double y0, double x1, double y1,
\r
617 Rectangle r = (Rectangle)value;
\r
618 if(!r.intersects(q))
\r
619 System.out.println("Not really intersecting!");
\r
624 System.out.println("Value and key differ!" +
\r
625 "(" + x0 + " " + y0 + " " + x1 + " " + y1 + ") " +
\r
626 "(" + r.x0 + " " + r.y0 + " " + r.x1 + " " + r.y1 + ")");
\r
630 if(iCount != iCount2[0])
\r
631 System.out.println("Different iCount: " + iCount + " " + iCount2[0]);
\r