bundles/org.simantics.g2d/src/org/simantics/g2d/routing/spatial/RTree.java

   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
   8  *\r
   9  * Contributors:\r
  10  *     VTT Technical Research Centre of Finland - initial API and implementation\r
  11  *******************************************************************************/\r
  12 package org.simantics.g2d.routing.spatial;\r
  13 \r
  14 import java.util.ArrayList;\r
  15 import java.util.Collection;\r
  16 import java.util.Random;\r
  17 \r
  18 import org.simantics.g2d.routing.algorithm1.Rectangle;\r
  19 \r
  20 /*\r
  21  * 2-dimensional R-tree\r
  22  */\r
  23 public class RTree {\r
  24 \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
  28         \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
  33                 \r
  34                 double[] getRectangles();\r
  35                 Object[] getChildren();\r
  36                 void setCount(int count);\r
  37                 \r
  38                 Rectangle findBounds();\r
  39         }\r
  40         \r
  41         static class Split {            \r
  42                 double oldX0, oldY0, oldX1, oldY1;\r
  43                 double newX0, newY0, newX1, newY1;\r
  44                 INode newNode;\r
  45                 \r
  46                 public Split(double oldX0, double oldY0, double oldX1, double oldY1,\r
  47                         double newX0, double newY0, double newX1, double newY1,\r
  48                         INode newNode) {\r
  49                         this.oldX0 = oldX0;\r
  50                         this.oldY0 = oldY0;\r
  51                         this.oldX1 = oldX1;\r
  52                         this.oldY1 = oldY1;\r
  53                         this.newX0 = newX0;\r
  54                         this.newY0 = newY0;\r
  55                         this.newX1 = newX1;\r
  56                         this.newY1 = newY1;\r
  57                         this.newNode = newNode;\r
  58                 }                               \r
  59                 \r
  60         }\r
  61         \r
  62         class Node implements INode {\r
  63                 double[] rectangles = new double[MAX_ENTRIES*4];\r
  64                 INode[] children = new INode[MAX_ENTRIES];\r
  65                 int count = 0;\r
  66                 \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
  76                 }\r
  77                 \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
  87                                                 return true;\r
  88                         return false;\r
  89                 }\r
  90 \r
  91                 @Override\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
  97                         \r
  98                         int bestId = -1;\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
 113                                         bestId = i;\r
 114                                         bestArea = area;\r
 115                                         bestAddition = addition;                                        \r
 116                                 }\r
 117                         }\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
 126                                 }\r
 127                         }\r
 128                         else { \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
 135                                         ad = count * 4;\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
 141                                 }\r
 142                                 else {\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
 148                                 }\r
 149                                 \r
 150                         }\r
 151                         return null;\r
 152                 }\r
 153 \r
 154                 @Override\r
 155                 public Object[] getChildren() {\r
 156                         return children;\r
 157                 }\r
 158 \r
 159                 @Override\r
 160                 public double[] getRectangles() {\r
 161                         return rectangles;\r
 162                 }\r
 163 \r
 164                 @Override\r
 165                 public void setCount(int count) {\r
 166                         this.count = count;                     \r
 167                 }\r
 168 \r
 169                 @Override\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
 176                                 int ad = i * 4;\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
 182                                 if(rect.x0 != x0a)\r
 183                                         throw new RuntimeException("x0");\r
 184                                 if(rect.y0 != y0a)\r
 185                                         throw new RuntimeException("y0");\r
 186                                 if(rect.x1 != x1a)\r
 187                                         throw new RuntimeException("x1");\r
 188                                 if(rect.y1 != y1a)\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
 194                         }\r
 195                         return new Rectangle(x0, y0, x1, y1);\r
 196                 }\r
 197         }\r
 198         \r
 199         class Leaf implements INode {\r
 200                 double[] rectangles = new double[MAX_ENTRIES*4];\r
 201                 Object[] children = new Object[MAX_ENTRIES];\r
 202                 int count = 0;\r
 203                 \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
 212                                         proc.call(\r
 213                                                 rectangles[ad], rectangles[ad+1], \r
 214                                                 rectangles[ad+2], rectangles[ad+3], \r
 215                                                 children[i]);                   \r
 216                 }\r
 217                 \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
 226                                         return true;\r
 227                         return false;\r
 228                 }\r
 229 \r
 230                 @Override\r
 231                 public Split add(Rectangle rect, Object value) {\r
 232                         if(count < children.length) {\r
 233                                 int ad = count*4;\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
 239                                 return null;\r
 240                         }\r
 241                         else {\r
 242                                 Leaf newLeaf = new Leaf();\r
 243                                 findNodeSeeds(rectangles, children, rect, value, newLeaf.rectangles, newLeaf.children);\r
 244                                 return splitNode(this, newLeaf);\r
 245                         }\r
 246                 }\r
 247                 \r
 248                 @Override\r
 249                 public Object[] getChildren() {\r
 250                         return children;\r
 251                 }\r
 252 \r
 253                 @Override\r
 254                 public double[] getRectangles() {\r
 255                         return rectangles;\r
 256                 }\r
 257                 \r
 258                 @Override\r
 259                 public void setCount(int count) {\r
 260                         this.count = count;                     \r
 261                 }\r
 262                 \r
 263                 @Override\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
 270                                 int ad = i * 4;\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
 279                         }\r
 280                         return new Rectangle(x0, y0, x1, y1);\r
 281                 }\r
 282         }                               \r
 283         \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
 300                 \r
 301                 int firstUnassigned = 1;\r
 302                 loop:\r
 303                 while(firstUnassigned < aValues.length) {\r
 304                         int bestI = -1;\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
 312                                 double da = \r
 313                                         (Math.max(x1a, x1) - Math.min(x0a, x0)) * (Math.max(y1a, y1) - Math.min(y0a, y0)) - areaA;\r
 314                                 double db = \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
 318                                         bestI = i;\r
 319                                         bestDiff = diff;\r
 320                                         bestToB = db < da || (db==da && bCount < aCount);\r
 321                                 }\r
 322                         }\r
 323                 \r
 324                         if(bestToB) {                           \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
 330                                 ++bCount;\r
 331                                 ++firstUnassigned;\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
 339                                                 ++aCount;\r
 340                                                 ++firstUnassigned;\r
 341                                         }\r
 342                                         break loop;\r
 343                                 }                               \r
 344                         }\r
 345                         else {                          \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
 352                                 ++aCount;\r
 353                                 ++firstUnassigned;\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
 361                                                 ++bCount;\r
 362                                                 ++firstUnassigned;\r
 363                                         }\r
 364                                         break loop;\r
 365                                 }\r
 366                         }\r
 367                         \r
 368                 }\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
 372         }\r
 373         \r
 374         static void move(double[] array, Object[] oArray, int a, int b) {\r
 375                 assert(a != b);\r
 376                 oArray[a] = oArray[b];\r
 377                 oArray[b] = null;\r
 378                 a *= 4;\r
 379                 b *= 4;\r
 380                 for(int i=0;i<4;++i)\r
 381                         array[a++] = array[b++];\r
 382         }\r
 383         \r
 384         static void move2(double[] array, Object[] oArray, int a, double[] array2, Object[] oArray2, int b) {\r
 385                 oArray[a] = oArray2[b];\r
 386                 oArray2[b] = null;\r
 387                 a *= 4;\r
 388                 b *= 4;\r
 389                 for(int i=0;i<4;++i)\r
 390                         array[a++] = array2[b++];\r
 391         }\r
 392         \r
 393         static void rotate(double[] array, Object[] oArray, int a, int b, int c) {\r
 394                 if(a==b) {\r
 395                         if(b==c)\r
 396                                 return;\r
 397                         {\r
 398                                 Object temp = oArray[a];\r
 399                                 oArray[a] = oArray[c]; \r
 400                                 oArray[c] = temp;\r
 401                         }\r
 402                         \r
 403                         a *= 4;\r
 404                         c *= 4;\r
 405                         for(int i=0;i<4;++i) {\r
 406                                 double temp = array[a];\r
 407                                 array[a] = array[c];\r
 408                                 array[c] = temp;\r
 409                                 ++a; ++c;\r
 410                         }\r
 411 \r
 412                 }\r
 413                 else if(b==c) {\r
 414                         {\r
 415                                 Object temp = oArray[a];\r
 416                                 oArray[a] = oArray[c]; \r
 417                                 oArray[c] = temp;\r
 418                         }\r
 419                         \r
 420                         a *= 4;\r
 421                         c *= 4;\r
 422                         for(int i=0;i<4;++i) {\r
 423                                 double temp = array[a];\r
 424                                 array[a] = array[c];\r
 425                                 array[c] = temp;\r
 426                                 ++a; ++c;\r
 427                         }\r
 428                 }\r
 429                 else {          \r
 430                         {\r
 431                                 Object temp = oArray[b];                \r
 432                                 oArray[b] = oArray[a];\r
 433                                 oArray[a] = oArray[c];\r
 434                                 oArray[c] = temp;\r
 435                         }\r
 436                         \r
 437                         a *= 4;\r
 438                         b *= 4;\r
 439                         c *= 4;\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
 444                                 array[c] = temp;\r
 445                                 ++a; ++b; ++c;\r
 446                         }\r
 447                 }\r
 448         }       \r
 449         \r
 450         static void rotate2(double[] array, Object[] oArray, int a, double[] array2, Object[] oArray2, int b, int c) {\r
 451                 {               \r
 452                         oArray[a] = oArray2[c];\r
 453                         oArray2[c] = oArray2[b];\r
 454                         oArray2[b] = null;\r
 455                 }\r
 456                 \r
 457                 a *= 4;\r
 458                 b *= 4;\r
 459                 c *= 4;\r
 460                 for(int i=0;i<4;++i) {                  \r
 461                         array[a] = array2[c];\r
 462                         array2[c] = array2[b];\r
 463                         array2[b] = 0.0;\r
 464                         ++a; ++b; ++c;\r
 465                 }\r
 466         }       \r
 467         \r
 468         static void findNodeSeeds(double[] rectangles, Object[] values, Rectangle rect, Object value,\r
 469                                                   double[] newRectangles, Object[] newValues) {\r
 470                 int bestI = -1;\r
 471                 int bestJ = -1;\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
 480                         }\r
 481                         else {\r
 482                                 x0b = rect.x0;\r
 483                                 y0b = rect.y0;\r
 484                                 x1b = rect.x1;\r
 485                                 y1b = rect.y1;\r
 486                         }\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
 497                                         bestI = i-4;\r
 498                                         bestJ = j;\r
 499                                         bestInefficiency = inefficiency;\r
 500                                 }                                       \r
 501                         }\r
 502                 }\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
 509                 }\r
 510                 else {\r
 511                         newValues[0] = values[bestJ/4];\r
 512                         values[bestJ/4] = value;\r
 513                         \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
 518                                               \r
 519                         bestJ -= 3;\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
 524                         \r
 525                 }\r
 526                 \r
 527                 if(bestI > 0) {                 \r
 528                         Object temp2 = values[0];\r
 529                         values[0] = values[bestI/4];\r
 530                         values[bestI/4] = temp2;\r
 531                         \r
 532                         double temp;\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
 545                 }\r
 546         }       \r
 547         \r
 548         INode root = new Leaf();\r
 549         \r
 550         public void search(Rectangle rect, IRectangleProcedure proc) {\r
 551                 root.search(rect, proc);\r
 552         }\r
 553         \r
 554         public boolean intersects(Rectangle rect) {\r
 555                 return root.intersects(rect);\r
 556         }\r
 557         \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
 572                         node.count = 2;\r
 573                         \r
 574                         root = node;\r
 575                 }\r
 576         }\r
 577         \r
 578         static Random random = new Random();\r
 579                 \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
 586         }\r
 587         \r
 588         public static void main(String[] args) {\r
 589                 Collection<Rectangle> rects = new ArrayList<Rectangle>();\r
 590                 \r
 591                 for(int i=0;i<1000;++i)                 \r
 592                         rects.add(randomRectangle());\r
 593                 \r
 594                 RTree tree = new RTree();\r
 595                 for(Rectangle rect : rects) {\r
 596                         tree.add(rect, rect);\r
 597                         tree.root.findBounds();\r
 598                 }\r
 599                 \r
 600                 \r
 601                 \r
 602                 for(int i=0;i<100;++i) {\r
 603                         final Rectangle q = randomRectangle();\r
 604                         \r
 605                         int iCount = 0;\r
 606                         for(Rectangle rect : rects)\r
 607                                 if(q.intersects(rect))\r
 608                                         ++iCount;\r
 609                         \r
 610                         final int[] iCount2 = new int[] { 0 };\r
 611                         tree.search(q, new IRectangleProcedure() {\r
 612 \r
 613                                 @Override\r
 614                                 public void call(double x0, double y0, double x1, double y1,\r
 615                                         Object value) {\r
 616                                         ++iCount2[0];\r
 617                                         Rectangle r = (Rectangle)value;\r
 618                                         if(!r.intersects(q))\r
 619                                                 System.out.println("Not really intersecting!");\r
 620                                         if( x0 != r.x0\r
 621                                           ||y0 != r.y0\r
 622                                           ||x1 != r.x1\r
 623                                           ||y1 != r.y1)\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
 627                                 }\r
 628                                 \r
 629                         });\r
 630                         if(iCount != iCount2[0])\r
 631                                 System.out.println("Different iCount: " + iCount + " " + iCount2[0]);\r
 632                 }\r
 633         }\r
 634 \r
 635 }\r