-/*******************************************************************************\r
- * Copyright (c) 2007, 2010 Association for Decentralized Information Management\r
- * in Industry THTH ry.\r
- * All rights reserved. This program and the accompanying materials\r
- * are made available under the terms of the Eclipse Public License v1.0\r
- * which accompanies this distribution, and is available at\r
- * http://www.eclipse.org/legal/epl-v10.html\r
- *\r
- * Contributors:\r
- * VTT Technical Research Centre of Finland - initial API and implementation\r
- *******************************************************************************/\r
-package org.simantics.g2d.routing.spatial;\r
-\r
-import java.util.ArrayList;\r
-import java.util.Collection;\r
-import java.util.Random;\r
-\r
-import org.simantics.g2d.routing.algorithm1.Rectangle;\r
-\r
-/*\r
- * 2-dimensional R-tree\r
- */\r
-public class RTree {\r
-\r
- public static final int MAX_ENTRIES = 7;\r
- public static final int MIN_ENTRIES = 3;\r
- public static final int MAX_ENTRIES_AFTER_SPLIT = MAX_ENTRIES - MIN_ENTRIES + 1;\r
- \r
- static interface INode {\r
- void search(Rectangle rect, IRectangleProcedure proc);\r
- boolean intersects(Rectangle rect);\r
- Split add(Rectangle rect, Object value);\r
- \r
- double[] getRectangles();\r
- Object[] getChildren();\r
- void setCount(int count);\r
- \r
- Rectangle findBounds();\r
- }\r
- \r
- static class Split { \r
- double oldX0, oldY0, oldX1, oldY1;\r
- double newX0, newY0, newX1, newY1;\r
- INode newNode;\r
- \r
- public Split(double oldX0, double oldY0, double oldX1, double oldY1,\r
- double newX0, double newY0, double newX1, double newY1,\r
- INode newNode) {\r
- this.oldX0 = oldX0;\r
- this.oldY0 = oldY0;\r
- this.oldX1 = oldX1;\r
- this.oldY1 = oldY1;\r
- this.newX0 = newX0;\r
- this.newY0 = newY0;\r
- this.newX1 = newX1;\r
- this.newY1 = newY1;\r
- this.newNode = newNode;\r
- } \r
- \r
- }\r
- \r
- class Node implements INode {\r
- double[] rectangles = new double[MAX_ENTRIES*4];\r
- INode[] children = new INode[MAX_ENTRIES];\r
- int count = 0;\r
- \r
- public void search(Rectangle rect, IRectangleProcedure proc) {\r
- double x0 = rect.x0;\r
- double y0 = rect.y0;\r
- double x1 = rect.x1;\r
- double y1 = rect.y1;\r
- for(int i=0,ad=0;i<count;++i,ad+=4)\r
- if(x1 >= rectangles[ad] && x0 <= rectangles[ad+2] &&\r
- y1 >= rectangles[ad+1] && y0 <= rectangles[ad+3])\r
- children[i].search(rect, proc); \r
- }\r
- \r
- public boolean intersects(Rectangle rect) {\r
- double x0 = rect.x0;\r
- double y0 = rect.y0;\r
- double x1 = rect.x1;\r
- double y1 = rect.y1;\r
- for(int i=0,ad=0;i<count;++i,ad+=4)\r
- if(x1 >= rectangles[ad] && x0 <= rectangles[ad+2] &&\r
- y1 >= rectangles[ad+1] && y0 <= rectangles[ad+3])\r
- if(children[i].intersects(rect))\r
- return true;\r
- return false;\r
- }\r
-\r
- @Override\r
- public Split add(Rectangle rect, Object value) {\r
- double x0 = rect.x0;\r
- double y0 = rect.y0;\r
- double x1 = rect.x1;\r
- double y1 = rect.y1;\r
- \r
- int bestId = -1;\r
- double bestArea = 0.0;\r
- double bestAddition = Double.POSITIVE_INFINITY;\r
- for(int i=0,ad=0;i<count;++i) {\r
- double x0b = rectangles[ad++];\r
- double y0b = rectangles[ad++];\r
- double x1b = rectangles[ad++];\r
- double y1b = rectangles[ad++];\r
- double area = (x1b-x0b)*(y1b-y0b);\r
- if(x0 < x0b) x0b = x0;\r
- if(y0 < y0b) y0b = y0;\r
- if(x1 > x1b) x1b = x1;\r
- if(y1 > y1b) y1b = y1;\r
- double addition = (x1b-x0b)*(y1b-y0b) - area;\r
- if(addition < bestAddition || (addition==bestAddition && area < bestArea)) {\r
- bestId = i;\r
- bestArea = area;\r
- bestAddition = addition; \r
- }\r
- }\r
- Split split = children[bestId].add(rect, value);\r
- if(split == null) {\r
- if(bestAddition > 0.0) {\r
- int ad = bestId * 4;\r
- rectangles[ad] = Math.min(rectangles[ad], x0); ++ad;\r
- rectangles[ad] = Math.min(rectangles[ad], y0); ++ad;\r
- rectangles[ad] = Math.max(rectangles[ad], x1); ++ad;\r
- rectangles[ad] = Math.max(rectangles[ad], y1);\r
- }\r
- }\r
- else { \r
- int ad = bestId * 4;\r
- rectangles[ad] = split.oldX0; ++ad;\r
- rectangles[ad] = split.oldY0; ++ad;\r
- rectangles[ad] = split.oldX1; ++ad;\r
- rectangles[ad] = split.oldY1;\r
- if(count < children.length) { \r
- ad = count * 4;\r
- rectangles[ad] = split.newX0; ++ad;\r
- rectangles[ad] = split.newY0; ++ad;\r
- rectangles[ad] = split.newX1; ++ad;\r
- rectangles[ad] = split.newY1;\r
- children[count++] = split.newNode;\r
- }\r
- else {\r
- Node newNode = new Node();\r
- findNodeSeeds(rectangles, children, \r
- new Rectangle(split.newX0, split.newY0, split.newX1, split.newY1), \r
- split.newNode, newNode.rectangles, newNode.children);\r
- return splitNode(this, newNode);\r
- }\r
- \r
- }\r
- return null;\r
- }\r
-\r
- @Override\r
- public Object[] getChildren() {\r
- return children;\r
- }\r
-\r
- @Override\r
- public double[] getRectangles() {\r
- return rectangles;\r
- }\r
-\r
- @Override\r
- public void setCount(int count) {\r
- this.count = count; \r
- }\r
-\r
- @Override\r
- public Rectangle findBounds() {\r
- double x0 = Double.POSITIVE_INFINITY;\r
- double y0 = Double.POSITIVE_INFINITY;\r
- double x1 = Double.NEGATIVE_INFINITY;\r
- double y1 = Double.NEGATIVE_INFINITY;\r
- for(int i=0;i<count;++i) {\r
- int ad = i * 4;\r
- double x0a = rectangles[ad++];\r
- double y0a = rectangles[ad++];\r
- double x1a = rectangles[ad++];\r
- double y1a = rectangles[ad++];\r
- Rectangle rect = children[i].findBounds();\r
- if(rect.x0 != x0a)\r
- throw new RuntimeException("x0");\r
- if(rect.y0 != y0a)\r
- throw new RuntimeException("y0");\r
- if(rect.x1 != x1a)\r
- throw new RuntimeException("x1");\r
- if(rect.y1 != y1a)\r
- throw new RuntimeException("y1");\r
- x0 = Math.min(x0, x0a);\r
- y0 = Math.min(y0, y0a);\r
- x1 = Math.max(x1, x1a);\r
- y1 = Math.max(y1, y1a);\r
- }\r
- return new Rectangle(x0, y0, x1, y1);\r
- }\r
- }\r
- \r
- class Leaf implements INode {\r
- double[] rectangles = new double[MAX_ENTRIES*4];\r
- Object[] children = new Object[MAX_ENTRIES];\r
- int count = 0;\r
- \r
- public void search(Rectangle rect, IRectangleProcedure proc) {\r
- double x0 = rect.x0;\r
- double y0 = rect.y0;\r
- double x1 = rect.x1;\r
- double y1 = rect.y1;\r
- for(int i=0,ad=0;i<count;++i,ad+=4)\r
- if(x1 >= rectangles[ad] && x0 <= rectangles[ad+2] &&\r
- y1 >= rectangles[ad+1] && y0 <= rectangles[ad+3])\r
- proc.call(\r
- rectangles[ad], rectangles[ad+1], \r
- rectangles[ad+2], rectangles[ad+3], \r
- children[i]); \r
- }\r
- \r
- public boolean intersects(Rectangle rect) {\r
- double x0 = rect.x0;\r
- double y0 = rect.y0;\r
- double x1 = rect.x1;\r
- double y1 = rect.y1;\r
- for(int i=0,ad=0;i<count;++i,ad+=4)\r
- if(x1 >= rectangles[ad] && x0 <= rectangles[ad+2] &&\r
- y1 >= rectangles[ad+1] && y0 <= rectangles[ad+3])\r
- return true;\r
- return false;\r
- }\r
-\r
- @Override\r
- public Split add(Rectangle rect, Object value) {\r
- if(count < children.length) {\r
- int ad = count*4;\r
- rectangles[ad++] = rect.x0;\r
- rectangles[ad++] = rect.y0;\r
- rectangles[ad++] = rect.x1;\r
- rectangles[ad] = rect.y1;\r
- children[count++] = value;\r
- return null;\r
- }\r
- else {\r
- Leaf newLeaf = new Leaf();\r
- findNodeSeeds(rectangles, children, rect, value, newLeaf.rectangles, newLeaf.children);\r
- return splitNode(this, newLeaf);\r
- }\r
- }\r
- \r
- @Override\r
- public Object[] getChildren() {\r
- return children;\r
- }\r
-\r
- @Override\r
- public double[] getRectangles() {\r
- return rectangles;\r
- }\r
- \r
- @Override\r
- public void setCount(int count) {\r
- this.count = count; \r
- }\r
- \r
- @Override\r
- public Rectangle findBounds() {\r
- double x0 = Double.POSITIVE_INFINITY;\r
- double y0 = Double.POSITIVE_INFINITY;\r
- double x1 = Double.NEGATIVE_INFINITY;\r
- double y1 = Double.NEGATIVE_INFINITY;\r
- for(int i=0;i<count;++i) {\r
- int ad = i * 4;\r
- double x0a = rectangles[ad++];\r
- double y0a = rectangles[ad++];\r
- double x1a = rectangles[ad++];\r
- double y1a = rectangles[ad++]; \r
- x0 = Math.min(x0, x0a);\r
- y0 = Math.min(y0, y0a);\r
- x1 = Math.max(x1, x1a);\r
- y1 = Math.max(y1, y1a);\r
- }\r
- return new Rectangle(x0, y0, x1, y1);\r
- }\r
- } \r
- \r
- static Split splitNode(INode a, INode b) {\r
- double[] aRectangles = a.getRectangles(); \r
- Object[] aValues = a.getChildren(); \r
- double[] bRectangles = b.getRectangles();\r
- Object[] bValues = b.getChildren();\r
- double x0a = aRectangles[0];\r
- double y0a = aRectangles[1];\r
- double x1a = aRectangles[2];\r
- double y1a = aRectangles[3];\r
- double areaA = (x1a-x0a) * (y1a-y0a);\r
- double x0b = bRectangles[0];\r
- double y0b = bRectangles[1];\r
- double x1b = bRectangles[2];\r
- double y1b = bRectangles[3];\r
- double areaB = (x1b-x0b) * (y1b-y0b);\r
- int aCount = 1, bCount = 1; \r
- \r
- int firstUnassigned = 1;\r
- loop:\r
- while(firstUnassigned < aValues.length) {\r
- int bestI = -1;\r
- double bestDiff = Double.NEGATIVE_INFINITY;\r
- boolean bestToB = false;\r
- for(int i=firstUnassigned,ad=firstUnassigned*4;i<aValues.length;++i) {\r
- double x0 = aRectangles[ad++];\r
- double y0 = aRectangles[ad++];\r
- double x1 = aRectangles[ad++];\r
- double y1 = aRectangles[ad++];\r
- double da = \r
- (Math.max(x1a, x1) - Math.min(x0a, x0)) * (Math.max(y1a, y1) - Math.min(y0a, y0)) - areaA;\r
- double db = \r
- (Math.max(x1b, x1) - Math.min(x0b, x0)) * (Math.max(y1b, y1) - Math.min(y0b, y0)) - areaB;\r
- double diff = Math.abs(da-db);\r
- if(diff > bestDiff) {\r
- bestI = i;\r
- bestDiff = diff;\r
- bestToB = db < da || (db==da && bCount < aCount);\r
- }\r
- }\r
- \r
- if(bestToB) { \r
- rotate2(bRectangles, bValues, bCount, aRectangles, aValues, firstUnassigned, bestI);\r
- x0b = Math.min(x0b, bRectangles[4*bCount]);\r
- y0b = Math.min(y0b, bRectangles[4*bCount+1]);\r
- x1b = Math.max(x1b, bRectangles[4*bCount+2]);\r
- y1b = Math.max(y1b, bRectangles[4*bCount+3]);\r
- ++bCount;\r
- ++firstUnassigned;\r
- if(bCount == MAX_ENTRIES_AFTER_SPLIT) {\r
- while(firstUnassigned < aValues.length) {\r
- move(aRectangles, aValues, aCount, firstUnassigned);\r
- x0a = Math.min(x0a, aRectangles[4*aCount]);\r
- y0a = Math.min(y0a, aRectangles[4*aCount+1]);\r
- x1a = Math.max(x1a, aRectangles[4*aCount+2]);\r
- y1a = Math.max(y1a, aRectangles[4*aCount+3]); \r
- ++aCount;\r
- ++firstUnassigned;\r
- }\r
- break loop;\r
- } \r
- }\r
- else { \r
- //System.out.println(aRectangles.length + " " + aValues.length + " " + aCount + " " + bCount + " " + firstUnassigned + " " + bestI);\r
- rotate(aRectangles, aValues, aCount, firstUnassigned, bestI);\r
- x0a = Math.min(x0a, aRectangles[4*aCount]);\r
- y0a = Math.min(y0a, aRectangles[4*aCount+1]);\r
- x1a = Math.max(x1a, aRectangles[4*aCount+2]);\r
- y1a = Math.max(y1a, aRectangles[4*aCount+3]); \r
- ++aCount;\r
- ++firstUnassigned;\r
- if(aCount == MAX_ENTRIES_AFTER_SPLIT) {\r
- while(firstUnassigned < aValues.length) {\r
- move2(bRectangles, bValues, bCount, aRectangles, aValues, firstUnassigned);\r
- x0b = Math.min(x0b, bRectangles[4*bCount]);\r
- y0b = Math.min(y0b, bRectangles[4*bCount+1]);\r
- x1b = Math.max(x1b, bRectangles[4*bCount+2]);\r
- y1b = Math.max(y1b, bRectangles[4*bCount+3]);\r
- ++bCount;\r
- ++firstUnassigned;\r
- }\r
- break loop;\r
- }\r
- }\r
- \r
- }\r
- a.setCount(aCount);\r
- b.setCount(bCount);\r
- return new Split(x0a, y0a, x1a, y1a, x0b, y0b, x1b, y1b, b);\r
- }\r
- \r
- static void move(double[] array, Object[] oArray, int a, int b) {\r
- assert(a != b);\r
- oArray[a] = oArray[b];\r
- oArray[b] = null;\r
- a *= 4;\r
- b *= 4;\r
- for(int i=0;i<4;++i)\r
- array[a++] = array[b++];\r
- }\r
- \r
- static void move2(double[] array, Object[] oArray, int a, double[] array2, Object[] oArray2, int b) {\r
- oArray[a] = oArray2[b];\r
- oArray2[b] = null;\r
- a *= 4;\r
- b *= 4;\r
- for(int i=0;i<4;++i)\r
- array[a++] = array2[b++];\r
- }\r
- \r
- static void rotate(double[] array, Object[] oArray, int a, int b, int c) {\r
- if(a==b) {\r
- if(b==c)\r
- return;\r
- {\r
- Object temp = oArray[a];\r
- oArray[a] = oArray[c]; \r
- oArray[c] = temp;\r
- }\r
- \r
- a *= 4;\r
- c *= 4;\r
- for(int i=0;i<4;++i) {\r
- double temp = array[a];\r
- array[a] = array[c];\r
- array[c] = temp;\r
- ++a; ++c;\r
- }\r
-\r
- }\r
- else if(b==c) {\r
- {\r
- Object temp = oArray[a];\r
- oArray[a] = oArray[c]; \r
- oArray[c] = temp;\r
- }\r
- \r
- a *= 4;\r
- c *= 4;\r
- for(int i=0;i<4;++i) {\r
- double temp = array[a];\r
- array[a] = array[c];\r
- array[c] = temp;\r
- ++a; ++c;\r
- }\r
- }\r
- else { \r
- {\r
- Object temp = oArray[b]; \r
- oArray[b] = oArray[a];\r
- oArray[a] = oArray[c];\r
- oArray[c] = temp;\r
- }\r
- \r
- a *= 4;\r
- b *= 4;\r
- c *= 4;\r
- for(int i=0;i<4;++i) {\r
- double temp = array[b];\r
- array[b] = array[a];\r
- array[a] = array[c];\r
- array[c] = temp;\r
- ++a; ++b; ++c;\r
- }\r
- }\r
- } \r
- \r
- static void rotate2(double[] array, Object[] oArray, int a, double[] array2, Object[] oArray2, int b, int c) {\r
- { \r
- oArray[a] = oArray2[c];\r
- oArray2[c] = oArray2[b];\r
- oArray2[b] = null;\r
- }\r
- \r
- a *= 4;\r
- b *= 4;\r
- c *= 4;\r
- for(int i=0;i<4;++i) { \r
- array[a] = array2[c];\r
- array2[c] = array2[b];\r
- array2[b] = 0.0;\r
- ++a; ++b; ++c;\r
- }\r
- } \r
- \r
- static void findNodeSeeds(double[] rectangles, Object[] values, Rectangle rect, Object value,\r
- double[] newRectangles, Object[] newValues) {\r
- int bestI = -1;\r
- int bestJ = -1;\r
- double bestInefficiency = Double.NEGATIVE_INFINITY;\r
- for(int j=0;j<=rectangles.length;j+=4) {\r
- double x0b, y0b, x1b, y1b;\r
- if(j < rectangles.length) {\r
- x0b = rectangles[j];\r
- y0b = rectangles[j+1];\r
- x1b = rectangles[j+2];\r
- y1b = rectangles[j+3];\r
- }\r
- else {\r
- x0b = rect.x0;\r
- y0b = rect.y0;\r
- x1b = rect.x1;\r
- y1b = rect.y1;\r
- }\r
- double areaB = (x1b-x0b) * (y1b-y0b);\r
- for(int i=0;i<j;) {\r
- double x0a = rectangles[i++];\r
- double y0a = rectangles[i++];\r
- double x1a = rectangles[i++];\r
- double y1a = rectangles[i++];\r
- double inefficiency =\r
- (Math.max(x1a, x1b) - Math.min(x0a, x0b)) * (Math.max(y1a, y1b) - Math.min(y0a, y0b))\r
- - (x1a-x0a) * (y1a-y0a) - areaB;\r
- if(inefficiency > bestInefficiency) {\r
- bestI = i-4;\r
- bestJ = j;\r
- bestInefficiency = inefficiency;\r
- } \r
- }\r
- }\r
- if(bestJ==rectangles.length) { \r
- newRectangles[0] = rect.x0;\r
- newRectangles[1] = rect.y0;\r
- newRectangles[2] = rect.x1;\r
- newRectangles[3] = rect.y1;\r
- newValues[0] = value;\r
- }\r
- else {\r
- newValues[0] = values[bestJ/4];\r
- values[bestJ/4] = value;\r
- \r
- newRectangles[0] = rectangles[bestJ++];\r
- newRectangles[1] = rectangles[bestJ++];\r
- newRectangles[2] = rectangles[bestJ++];\r
- newRectangles[3] = rectangles[bestJ]; \r
- \r
- bestJ -= 3;\r
- rectangles[bestJ++] = rect.x0;\r
- rectangles[bestJ++] = rect.y0;\r
- rectangles[bestJ++] = rect.x1;\r
- rectangles[bestJ] = rect.y1;\r
- \r
- }\r
- \r
- if(bestI > 0) { \r
- Object temp2 = values[0];\r
- values[0] = values[bestI/4];\r
- values[bestI/4] = temp2;\r
- \r
- double temp;\r
- temp = rectangles[0];\r
- rectangles[0] = rectangles[bestI];\r
- rectangles[bestI++] = temp;\r
- temp = rectangles[1];\r
- rectangles[1] = rectangles[bestI];\r
- rectangles[bestI++] = temp;\r
- temp = rectangles[2];\r
- rectangles[2] = rectangles[bestI];\r
- rectangles[bestI++] = temp;\r
- temp = rectangles[3];\r
- rectangles[3] = rectangles[bestI];\r
- rectangles[bestI++] = temp; \r
- }\r
- } \r
- \r
- INode root = new Leaf();\r
- \r
- public void search(Rectangle rect, IRectangleProcedure proc) {\r
- root.search(rect, proc);\r
- }\r
- \r
- public boolean intersects(Rectangle rect) {\r
- return root.intersects(rect);\r
- }\r
- \r
- public void add(Rectangle rect, Object obj) {\r
- Split split = root.add(rect, obj);\r
- if(split != null) {\r
- Node node = new Node();\r
- node.rectangles[0] = split.oldX0;\r
- node.rectangles[1] = split.oldY0;\r
- node.rectangles[2] = split.oldX1;\r
- node.rectangles[3] = split.oldY1;\r
- node.rectangles[4] = split.newX0;\r
- node.rectangles[5] = split.newY0;\r
- node.rectangles[6] = split.newX1;\r
- node.rectangles[7] = split.newY1;\r
- node.children[0] = root;\r
- node.children[1] = split.newNode;\r
- node.count = 2;\r
- \r
- root = node;\r
- }\r
- }\r
- \r
- static Random random = new Random();\r
- \r
- public static Rectangle randomRectangle() {\r
- double x = random.nextDouble();\r
- double y = random.nextDouble();\r
- double w = random.nextDouble()*0.1;\r
- double h = random.nextDouble()*0.1;\r
- return new Rectangle(x, y, x+w, y+h);\r
- }\r
- \r
- public static void main(String[] args) {\r
- Collection<Rectangle> rects = new ArrayList<Rectangle>();\r
- \r
- for(int i=0;i<1000;++i) \r
- rects.add(randomRectangle());\r
- \r
- RTree tree = new RTree();\r
- for(Rectangle rect : rects) {\r
- tree.add(rect, rect);\r
- tree.root.findBounds();\r
- }\r
- \r
- \r
- \r
- for(int i=0;i<100;++i) {\r
- final Rectangle q = randomRectangle();\r
- \r
- int iCount = 0;\r
- for(Rectangle rect : rects)\r
- if(q.intersects(rect))\r
- ++iCount;\r
- \r
- final int[] iCount2 = new int[] { 0 };\r
- tree.search(q, new IRectangleProcedure() {\r
-\r
- @Override\r
- public void call(double x0, double y0, double x1, double y1,\r
- Object value) {\r
- ++iCount2[0];\r
- Rectangle r = (Rectangle)value;\r
- if(!r.intersects(q))\r
- System.out.println("Not really intersecting!");\r
- if( x0 != r.x0\r
- ||y0 != r.y0\r
- ||x1 != r.x1\r
- ||y1 != r.y1)\r
- System.out.println("Value and key differ!" +\r
- "(" + x0 + " " + y0 + " " + x1 + " " + y1 + ") " +\r
- "(" + r.x0 + " " + r.y0 + " " + r.x1 + " " + r.y1 + ")");\r
- }\r
- \r
- });\r
- if(iCount != iCount2[0])\r
- System.out.println("Different iCount: " + iCount + " " + iCount2[0]);\r
- }\r
- }\r
-\r
-}\r
+/*******************************************************************************
+ * Copyright (c) 2007, 2010 Association for Decentralized Information Management
+ * in Industry THTH ry.
+ * All rights reserved. This program and the accompanying materials
+ * are made available under the terms of the Eclipse Public License v1.0
+ * which accompanies this distribution, and is available at
+ * http://www.eclipse.org/legal/epl-v10.html
+ *
+ * Contributors:
+ * VTT Technical Research Centre of Finland - initial API and implementation
+ *******************************************************************************/
+package org.simantics.g2d.routing.spatial;
+
+import java.util.ArrayList;
+import java.util.Collection;
+import java.util.Random;
+
+import org.simantics.g2d.routing.algorithm1.Rectangle;
+
+/*
+ * 2-dimensional R-tree
+ */
+public class RTree {
+
+ public static final int MAX_ENTRIES = 7;
+ public static final int MIN_ENTRIES = 3;
+ public static final int MAX_ENTRIES_AFTER_SPLIT = MAX_ENTRIES - MIN_ENTRIES + 1;
+
+ static interface INode {
+ void search(Rectangle rect, IRectangleProcedure proc);
+ boolean intersects(Rectangle rect);
+ Split add(Rectangle rect, Object value);
+
+ double[] getRectangles();
+ Object[] getChildren();
+ void setCount(int count);
+
+ Rectangle findBounds();
+ }
+
+ static class Split {
+ double oldX0, oldY0, oldX1, oldY1;
+ double newX0, newY0, newX1, newY1;
+ INode newNode;
+
+ public Split(double oldX0, double oldY0, double oldX1, double oldY1,
+ double newX0, double newY0, double newX1, double newY1,
+ INode newNode) {
+ this.oldX0 = oldX0;
+ this.oldY0 = oldY0;
+ this.oldX1 = oldX1;
+ this.oldY1 = oldY1;
+ this.newX0 = newX0;
+ this.newY0 = newY0;
+ this.newX1 = newX1;
+ this.newY1 = newY1;
+ this.newNode = newNode;
+ }
+
+ }
+
+ class Node implements INode {
+ double[] rectangles = new double[MAX_ENTRIES*4];
+ INode[] children = new INode[MAX_ENTRIES];
+ int count = 0;
+
+ public void search(Rectangle rect, IRectangleProcedure proc) {
+ double x0 = rect.x0;
+ double y0 = rect.y0;
+ double x1 = rect.x1;
+ double y1 = rect.y1;
+ for(int i=0,ad=0;i<count;++i,ad+=4)
+ if(x1 >= rectangles[ad] && x0 <= rectangles[ad+2] &&
+ y1 >= rectangles[ad+1] && y0 <= rectangles[ad+3])
+ children[i].search(rect, proc);
+ }
+
+ public boolean intersects(Rectangle rect) {
+ double x0 = rect.x0;
+ double y0 = rect.y0;
+ double x1 = rect.x1;
+ double y1 = rect.y1;
+ for(int i=0,ad=0;i<count;++i,ad+=4)
+ if(x1 >= rectangles[ad] && x0 <= rectangles[ad+2] &&
+ y1 >= rectangles[ad+1] && y0 <= rectangles[ad+3])
+ if(children[i].intersects(rect))
+ return true;
+ return false;
+ }
+
+ @Override
+ public Split add(Rectangle rect, Object value) {
+ double x0 = rect.x0;
+ double y0 = rect.y0;
+ double x1 = rect.x1;
+ double y1 = rect.y1;
+
+ int bestId = -1;
+ double bestArea = 0.0;
+ double bestAddition = Double.POSITIVE_INFINITY;
+ for(int i=0,ad=0;i<count;++i) {
+ double x0b = rectangles[ad++];
+ double y0b = rectangles[ad++];
+ double x1b = rectangles[ad++];
+ double y1b = rectangles[ad++];
+ double area = (x1b-x0b)*(y1b-y0b);
+ if(x0 < x0b) x0b = x0;
+ if(y0 < y0b) y0b = y0;
+ if(x1 > x1b) x1b = x1;
+ if(y1 > y1b) y1b = y1;
+ double addition = (x1b-x0b)*(y1b-y0b) - area;
+ if(addition < bestAddition || (addition==bestAddition && area < bestArea)) {
+ bestId = i;
+ bestArea = area;
+ bestAddition = addition;
+ }
+ }
+ Split split = children[bestId].add(rect, value);
+ if(split == null) {
+ if(bestAddition > 0.0) {
+ int ad = bestId * 4;
+ rectangles[ad] = Math.min(rectangles[ad], x0); ++ad;
+ rectangles[ad] = Math.min(rectangles[ad], y0); ++ad;
+ rectangles[ad] = Math.max(rectangles[ad], x1); ++ad;
+ rectangles[ad] = Math.max(rectangles[ad], y1);
+ }
+ }
+ else {
+ int ad = bestId * 4;
+ rectangles[ad] = split.oldX0; ++ad;
+ rectangles[ad] = split.oldY0; ++ad;
+ rectangles[ad] = split.oldX1; ++ad;
+ rectangles[ad] = split.oldY1;
+ if(count < children.length) {
+ ad = count * 4;
+ rectangles[ad] = split.newX0; ++ad;
+ rectangles[ad] = split.newY0; ++ad;
+ rectangles[ad] = split.newX1; ++ad;
+ rectangles[ad] = split.newY1;
+ children[count++] = split.newNode;
+ }
+ else {
+ Node newNode = new Node();
+ findNodeSeeds(rectangles, children,
+ new Rectangle(split.newX0, split.newY0, split.newX1, split.newY1),
+ split.newNode, newNode.rectangles, newNode.children);
+ return splitNode(this, newNode);
+ }
+
+ }
+ return null;
+ }
+
+ @Override
+ public Object[] getChildren() {
+ return children;
+ }
+
+ @Override
+ public double[] getRectangles() {
+ return rectangles;
+ }
+
+ @Override
+ public void setCount(int count) {
+ this.count = count;
+ }
+
+ @Override
+ public Rectangle findBounds() {
+ double x0 = Double.POSITIVE_INFINITY;
+ double y0 = Double.POSITIVE_INFINITY;
+ double x1 = Double.NEGATIVE_INFINITY;
+ double y1 = Double.NEGATIVE_INFINITY;
+ for(int i=0;i<count;++i) {
+ int ad = i * 4;
+ double x0a = rectangles[ad++];
+ double y0a = rectangles[ad++];
+ double x1a = rectangles[ad++];
+ double y1a = rectangles[ad++];
+ Rectangle rect = children[i].findBounds();
+ if(rect.x0 != x0a)
+ throw new RuntimeException("x0");
+ if(rect.y0 != y0a)
+ throw new RuntimeException("y0");
+ if(rect.x1 != x1a)
+ throw new RuntimeException("x1");
+ if(rect.y1 != y1a)
+ throw new RuntimeException("y1");
+ x0 = Math.min(x0, x0a);
+ y0 = Math.min(y0, y0a);
+ x1 = Math.max(x1, x1a);
+ y1 = Math.max(y1, y1a);
+ }
+ return new Rectangle(x0, y0, x1, y1);
+ }
+ }
+
+ class Leaf implements INode {
+ double[] rectangles = new double[MAX_ENTRIES*4];
+ Object[] children = new Object[MAX_ENTRIES];
+ int count = 0;
+
+ public void search(Rectangle rect, IRectangleProcedure proc) {
+ double x0 = rect.x0;
+ double y0 = rect.y0;
+ double x1 = rect.x1;
+ double y1 = rect.y1;
+ for(int i=0,ad=0;i<count;++i,ad+=4)
+ if(x1 >= rectangles[ad] && x0 <= rectangles[ad+2] &&
+ y1 >= rectangles[ad+1] && y0 <= rectangles[ad+3])
+ proc.call(
+ rectangles[ad], rectangles[ad+1],
+ rectangles[ad+2], rectangles[ad+3],
+ children[i]);
+ }
+
+ public boolean intersects(Rectangle rect) {
+ double x0 = rect.x0;
+ double y0 = rect.y0;
+ double x1 = rect.x1;
+ double y1 = rect.y1;
+ for(int i=0,ad=0;i<count;++i,ad+=4)
+ if(x1 >= rectangles[ad] && x0 <= rectangles[ad+2] &&
+ y1 >= rectangles[ad+1] && y0 <= rectangles[ad+3])
+ return true;
+ return false;
+ }
+
+ @Override
+ public Split add(Rectangle rect, Object value) {
+ if(count < children.length) {
+ int ad = count*4;
+ rectangles[ad++] = rect.x0;
+ rectangles[ad++] = rect.y0;
+ rectangles[ad++] = rect.x1;
+ rectangles[ad] = rect.y1;
+ children[count++] = value;
+ return null;
+ }
+ else {
+ Leaf newLeaf = new Leaf();
+ findNodeSeeds(rectangles, children, rect, value, newLeaf.rectangles, newLeaf.children);
+ return splitNode(this, newLeaf);
+ }
+ }
+
+ @Override
+ public Object[] getChildren() {
+ return children;
+ }
+
+ @Override
+ public double[] getRectangles() {
+ return rectangles;
+ }
+
+ @Override
+ public void setCount(int count) {
+ this.count = count;
+ }
+
+ @Override
+ public Rectangle findBounds() {
+ double x0 = Double.POSITIVE_INFINITY;
+ double y0 = Double.POSITIVE_INFINITY;
+ double x1 = Double.NEGATIVE_INFINITY;
+ double y1 = Double.NEGATIVE_INFINITY;
+ for(int i=0;i<count;++i) {
+ int ad = i * 4;
+ double x0a = rectangles[ad++];
+ double y0a = rectangles[ad++];
+ double x1a = rectangles[ad++];
+ double y1a = rectangles[ad++];
+ x0 = Math.min(x0, x0a);
+ y0 = Math.min(y0, y0a);
+ x1 = Math.max(x1, x1a);
+ y1 = Math.max(y1, y1a);
+ }
+ return new Rectangle(x0, y0, x1, y1);
+ }
+ }
+
+ static Split splitNode(INode a, INode b) {
+ double[] aRectangles = a.getRectangles();
+ Object[] aValues = a.getChildren();
+ double[] bRectangles = b.getRectangles();
+ Object[] bValues = b.getChildren();
+ double x0a = aRectangles[0];
+ double y0a = aRectangles[1];
+ double x1a = aRectangles[2];
+ double y1a = aRectangles[3];
+ double areaA = (x1a-x0a) * (y1a-y0a);
+ double x0b = bRectangles[0];
+ double y0b = bRectangles[1];
+ double x1b = bRectangles[2];
+ double y1b = bRectangles[3];
+ double areaB = (x1b-x0b) * (y1b-y0b);
+ int aCount = 1, bCount = 1;
+
+ int firstUnassigned = 1;
+ loop:
+ while(firstUnassigned < aValues.length) {
+ int bestI = -1;
+ double bestDiff = Double.NEGATIVE_INFINITY;
+ boolean bestToB = false;
+ for(int i=firstUnassigned,ad=firstUnassigned*4;i<aValues.length;++i) {
+ double x0 = aRectangles[ad++];
+ double y0 = aRectangles[ad++];
+ double x1 = aRectangles[ad++];
+ double y1 = aRectangles[ad++];
+ double da =
+ (Math.max(x1a, x1) - Math.min(x0a, x0)) * (Math.max(y1a, y1) - Math.min(y0a, y0)) - areaA;
+ double db =
+ (Math.max(x1b, x1) - Math.min(x0b, x0)) * (Math.max(y1b, y1) - Math.min(y0b, y0)) - areaB;
+ double diff = Math.abs(da-db);
+ if(diff > bestDiff) {
+ bestI = i;
+ bestDiff = diff;
+ bestToB = db < da || (db==da && bCount < aCount);
+ }
+ }
+
+ if(bestToB) {
+ rotate2(bRectangles, bValues, bCount, aRectangles, aValues, firstUnassigned, bestI);
+ x0b = Math.min(x0b, bRectangles[4*bCount]);
+ y0b = Math.min(y0b, bRectangles[4*bCount+1]);
+ x1b = Math.max(x1b, bRectangles[4*bCount+2]);
+ y1b = Math.max(y1b, bRectangles[4*bCount+3]);
+ ++bCount;
+ ++firstUnassigned;
+ if(bCount == MAX_ENTRIES_AFTER_SPLIT) {
+ while(firstUnassigned < aValues.length) {
+ move(aRectangles, aValues, aCount, firstUnassigned);
+ x0a = Math.min(x0a, aRectangles[4*aCount]);
+ y0a = Math.min(y0a, aRectangles[4*aCount+1]);
+ x1a = Math.max(x1a, aRectangles[4*aCount+2]);
+ y1a = Math.max(y1a, aRectangles[4*aCount+3]);
+ ++aCount;
+ ++firstUnassigned;
+ }
+ break loop;
+ }
+ }
+ else {
+ //System.out.println(aRectangles.length + " " + aValues.length + " " + aCount + " " + bCount + " " + firstUnassigned + " " + bestI);
+ rotate(aRectangles, aValues, aCount, firstUnassigned, bestI);
+ x0a = Math.min(x0a, aRectangles[4*aCount]);
+ y0a = Math.min(y0a, aRectangles[4*aCount+1]);
+ x1a = Math.max(x1a, aRectangles[4*aCount+2]);
+ y1a = Math.max(y1a, aRectangles[4*aCount+3]);
+ ++aCount;
+ ++firstUnassigned;
+ if(aCount == MAX_ENTRIES_AFTER_SPLIT) {
+ while(firstUnassigned < aValues.length) {
+ move2(bRectangles, bValues, bCount, aRectangles, aValues, firstUnassigned);
+ x0b = Math.min(x0b, bRectangles[4*bCount]);
+ y0b = Math.min(y0b, bRectangles[4*bCount+1]);
+ x1b = Math.max(x1b, bRectangles[4*bCount+2]);
+ y1b = Math.max(y1b, bRectangles[4*bCount+3]);
+ ++bCount;
+ ++firstUnassigned;
+ }
+ break loop;
+ }
+ }
+
+ }
+ a.setCount(aCount);
+ b.setCount(bCount);
+ return new Split(x0a, y0a, x1a, y1a, x0b, y0b, x1b, y1b, b);
+ }
+
+ static void move(double[] array, Object[] oArray, int a, int b) {
+ assert(a != b);
+ oArray[a] = oArray[b];
+ oArray[b] = null;
+ a *= 4;
+ b *= 4;
+ for(int i=0;i<4;++i)
+ array[a++] = array[b++];
+ }
+
+ static void move2(double[] array, Object[] oArray, int a, double[] array2, Object[] oArray2, int b) {
+ oArray[a] = oArray2[b];
+ oArray2[b] = null;
+ a *= 4;
+ b *= 4;
+ for(int i=0;i<4;++i)
+ array[a++] = array2[b++];
+ }
+
+ static void rotate(double[] array, Object[] oArray, int a, int b, int c) {
+ if(a==b) {
+ if(b==c)
+ return;
+ {
+ Object temp = oArray[a];
+ oArray[a] = oArray[c];
+ oArray[c] = temp;
+ }
+
+ a *= 4;
+ c *= 4;
+ for(int i=0;i<4;++i) {
+ double temp = array[a];
+ array[a] = array[c];
+ array[c] = temp;
+ ++a; ++c;
+ }
+
+ }
+ else if(b==c) {
+ {
+ Object temp = oArray[a];
+ oArray[a] = oArray[c];
+ oArray[c] = temp;
+ }
+
+ a *= 4;
+ c *= 4;
+ for(int i=0;i<4;++i) {
+ double temp = array[a];
+ array[a] = array[c];
+ array[c] = temp;
+ ++a; ++c;
+ }
+ }
+ else {
+ {
+ Object temp = oArray[b];
+ oArray[b] = oArray[a];
+ oArray[a] = oArray[c];
+ oArray[c] = temp;
+ }
+
+ a *= 4;
+ b *= 4;
+ c *= 4;
+ for(int i=0;i<4;++i) {
+ double temp = array[b];
+ array[b] = array[a];
+ array[a] = array[c];
+ array[c] = temp;
+ ++a; ++b; ++c;
+ }
+ }
+ }
+
+ static void rotate2(double[] array, Object[] oArray, int a, double[] array2, Object[] oArray2, int b, int c) {
+ {
+ oArray[a] = oArray2[c];
+ oArray2[c] = oArray2[b];
+ oArray2[b] = null;
+ }
+
+ a *= 4;
+ b *= 4;
+ c *= 4;
+ for(int i=0;i<4;++i) {
+ array[a] = array2[c];
+ array2[c] = array2[b];
+ array2[b] = 0.0;
+ ++a; ++b; ++c;
+ }
+ }
+
+ static void findNodeSeeds(double[] rectangles, Object[] values, Rectangle rect, Object value,
+ double[] newRectangles, Object[] newValues) {
+ int bestI = -1;
+ int bestJ = -1;
+ double bestInefficiency = Double.NEGATIVE_INFINITY;
+ for(int j=0;j<=rectangles.length;j+=4) {
+ double x0b, y0b, x1b, y1b;
+ if(j < rectangles.length) {
+ x0b = rectangles[j];
+ y0b = rectangles[j+1];
+ x1b = rectangles[j+2];
+ y1b = rectangles[j+3];
+ }
+ else {
+ x0b = rect.x0;
+ y0b = rect.y0;
+ x1b = rect.x1;
+ y1b = rect.y1;
+ }
+ double areaB = (x1b-x0b) * (y1b-y0b);
+ for(int i=0;i<j;) {
+ double x0a = rectangles[i++];
+ double y0a = rectangles[i++];
+ double x1a = rectangles[i++];
+ double y1a = rectangles[i++];
+ double inefficiency =
+ (Math.max(x1a, x1b) - Math.min(x0a, x0b)) * (Math.max(y1a, y1b) - Math.min(y0a, y0b))
+ - (x1a-x0a) * (y1a-y0a) - areaB;
+ if(inefficiency > bestInefficiency) {
+ bestI = i-4;
+ bestJ = j;
+ bestInefficiency = inefficiency;
+ }
+ }
+ }
+ if(bestJ==rectangles.length) {
+ newRectangles[0] = rect.x0;
+ newRectangles[1] = rect.y0;
+ newRectangles[2] = rect.x1;
+ newRectangles[3] = rect.y1;
+ newValues[0] = value;
+ }
+ else {
+ newValues[0] = values[bestJ/4];
+ values[bestJ/4] = value;
+
+ newRectangles[0] = rectangles[bestJ++];
+ newRectangles[1] = rectangles[bestJ++];
+ newRectangles[2] = rectangles[bestJ++];
+ newRectangles[3] = rectangles[bestJ];
+
+ bestJ -= 3;
+ rectangles[bestJ++] = rect.x0;
+ rectangles[bestJ++] = rect.y0;
+ rectangles[bestJ++] = rect.x1;
+ rectangles[bestJ] = rect.y1;
+
+ }
+
+ if(bestI > 0) {
+ Object temp2 = values[0];
+ values[0] = values[bestI/4];
+ values[bestI/4] = temp2;
+
+ double temp;
+ temp = rectangles[0];
+ rectangles[0] = rectangles[bestI];
+ rectangles[bestI++] = temp;
+ temp = rectangles[1];
+ rectangles[1] = rectangles[bestI];
+ rectangles[bestI++] = temp;
+ temp = rectangles[2];
+ rectangles[2] = rectangles[bestI];
+ rectangles[bestI++] = temp;
+ temp = rectangles[3];
+ rectangles[3] = rectangles[bestI];
+ rectangles[bestI++] = temp;
+ }
+ }
+
+ INode root = new Leaf();
+
+ public void search(Rectangle rect, IRectangleProcedure proc) {
+ root.search(rect, proc);
+ }
+
+ public boolean intersects(Rectangle rect) {
+ return root.intersects(rect);
+ }
+
+ public void add(Rectangle rect, Object obj) {
+ Split split = root.add(rect, obj);
+ if(split != null) {
+ Node node = new Node();
+ node.rectangles[0] = split.oldX0;
+ node.rectangles[1] = split.oldY0;
+ node.rectangles[2] = split.oldX1;
+ node.rectangles[3] = split.oldY1;
+ node.rectangles[4] = split.newX0;
+ node.rectangles[5] = split.newY0;
+ node.rectangles[6] = split.newX1;
+ node.rectangles[7] = split.newY1;
+ node.children[0] = root;
+ node.children[1] = split.newNode;
+ node.count = 2;
+
+ root = node;
+ }
+ }
+
+ static Random random = new Random();
+
+ public static Rectangle randomRectangle() {
+ double x = random.nextDouble();
+ double y = random.nextDouble();
+ double w = random.nextDouble()*0.1;
+ double h = random.nextDouble()*0.1;
+ return new Rectangle(x, y, x+w, y+h);
+ }
+
+ public static void main(String[] args) {
+ Collection<Rectangle> rects = new ArrayList<Rectangle>();
+
+ for(int i=0;i<1000;++i)
+ rects.add(randomRectangle());
+
+ RTree tree = new RTree();
+ for(Rectangle rect : rects) {
+ tree.add(rect, rect);
+ tree.root.findBounds();
+ }
+
+
+
+ for(int i=0;i<100;++i) {
+ final Rectangle q = randomRectangle();
+
+ int iCount = 0;
+ for(Rectangle rect : rects)
+ if(q.intersects(rect))
+ ++iCount;
+
+ final int[] iCount2 = new int[] { 0 };
+ tree.search(q, new IRectangleProcedure() {
+
+ @Override
+ public void call(double x0, double y0, double x1, double y1,
+ Object value) {
+ ++iCount2[0];
+ Rectangle r = (Rectangle)value;
+ if(!r.intersects(q))
+ System.out.println("Not really intersecting!");
+ if( x0 != r.x0
+ ||y0 != r.y0
+ ||x1 != r.x1
+ ||y1 != r.y1)
+ System.out.println("Value and key differ!" +
+ "(" + x0 + " " + y0 + " " + x1 + " " + y1 + ") " +
+ "(" + r.x0 + " " + r.y0 + " " + r.x1 + " " + r.y1 + ")");
+ }
+
+ });
+ if(iCount != iCount2[0])
+ System.out.println("Different iCount: " + iCount + " " + iCount2[0]);
+ }
+ }
+
+}
Code Review / simantics / platform.git / blobdiff