X-Git-Url: https://gerrit.simantics.org/r/gitweb?a=blobdiff_plain;f=bundles%2Forg.simantics.g2d%2Fsrc%2Forg%2Fsimantics%2Fg2d%2Frouting%2Fspatial%2FRTree.java;fp=bundles%2Forg.simantics.g2d%2Fsrc%2Forg%2Fsimantics%2Fg2d%2Frouting%2Fspatial%2FRTree.java;h=ed3cfd3ac74a8bdf7a9063243915bd51506866fe;hb=969bd23cab98a79ca9101af33334000879fb60c5;hp=0000000000000000000000000000000000000000;hpb=866dba5cd5a3929bbeae85991796acb212338a08;p=simantics%2Fplatform.git

diff --git a/bundles/org.simantics.g2d/src/org/simantics/g2d/routing/spatial/RTree.java b/bundles/org.simantics.g2d/src/org/simantics/g2d/routing/spatial/RTree.java
new file mode 100644
index 000000000..ed3cfd3ac
--- /dev/null
+++ b/bundles/org.simantics.g2d/src/org/simantics/g2d/routing/spatial/RTree.java
@@ -0,0 +1,635 @@
+/*******************************************************************************
+ * 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]);
+		}
+	}
+
+}