bundles/org.simantics.scenegraph/src/com/infomatiq/jsi/rtree/Node.java

   1 //   Node.java\r
   2 //   Java Spatial Index Library\r
   3 //   Copyright (C) 2002-2005 Infomatiq Limited\r
   4 //   Copyright (C) 2008-2010 aled@sourceforge.net\r
   5 //  \r
   6 //  This library is free software; you can redistribute it and/or\r
   7 //  modify it under the terms of the GNU Lesser General Public\r
   8 //  License as published by the Free Software Foundation; either\r
   9 //  version 2.1 of the License, or (at your option) any later version.\r
  10 //  \r
  11 //  This library is distributed in the hope that it will be useful,\r
  12 //  but WITHOUT ANY WARRANTY; without even the implied warranty of\r
  13 //  MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU\r
  14 //  Lesser General Public License for more details.\r
  15 //  \r
  16 //  You should have received a copy of the GNU Lesser General Public\r
  17 //  License along with this library; if not, write to the Free Software\r
  18 //  Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA  02111-1307  USA\r
  19 \r
  20 package com.infomatiq.jsi.rtree;\r
  21 \r
  22 /**\r
  23  * <p>Used by RTree. There are no public methods in this class.</p>\r
  24  * \r
  25  * @author aled.morris@infomatiq.co.uk\r
  26  * @version 1.0b8\r
  27  */\r
  28 public class Node {\r
  29   int nodeId = 0;\r
  30   float mbrMinX = Float.MAX_VALUE;\r
  31   float mbrMinY = Float.MAX_VALUE;\r
  32   float mbrMaxX = -Float.MAX_VALUE;\r
  33   float mbrMaxY = -Float.MAX_VALUE;\r
  34   \r
  35   float[] entriesMinX = null;\r
  36   float[] entriesMinY = null;\r
  37   float[] entriesMaxX = null;\r
  38   float[] entriesMaxY = null;\r
  39   \r
  40   int[] ids = null;\r
  41   int level;\r
  42   int entryCount;\r
  43 \r
  44   Node(int nodeId, int level, int maxNodeEntries) {\r
  45     this.nodeId = nodeId;\r
  46     this.level = level;\r
  47     entriesMinX = new float[maxNodeEntries];\r
  48     entriesMinY = new float[maxNodeEntries];\r
  49     entriesMaxX = new float[maxNodeEntries];\r
  50     entriesMaxY = new float[maxNodeEntries];\r
  51     ids = new int[maxNodeEntries];\r
  52   }\r
  53    \r
  54   void addEntry(float minX, float minY, float maxX, float maxY, int id) {\r
  55     ids[entryCount] = id;\r
  56     entriesMinX[entryCount] = minX;\r
  57     entriesMinY[entryCount] = minY;\r
  58     entriesMaxX[entryCount] = maxX;\r
  59     entriesMaxY[entryCount] = maxY;\r
  60    \r
  61     if (minX < mbrMinX) mbrMinX = minX;\r
  62     if (minY < mbrMinY) mbrMinY = minY;\r
  63     if (maxX > mbrMaxX) mbrMaxX = maxX;\r
  64     if (maxY > mbrMaxY) mbrMaxY = maxY;\r
  65     \r
  66     entryCount++;\r
  67   }\r
  68   \r
  69   // Return the index of the found entry, or -1 if not found\r
  70   int findEntry(float minX, float minY, float maxX, float maxY, int id) {\r
  71     for (int i = 0; i < entryCount; i++) {\r
  72         if (id == ids[i] && \r
  73           entriesMinX[i] == minX && entriesMinY[i] == minY &&\r
  74           entriesMaxX[i] == maxX && entriesMaxY[i] == maxY) {\r
  75           return i;     \r
  76         }\r
  77     }\r
  78     return -1;\r
  79   }\r
  80   \r
  81   // delete entry. This is done by setting it to null and copying the last entry into its space.\r
  82   void deleteEntry(int i) {\r
  83           int lastIndex = entryCount - 1;\r
  84     float deletedMinX = entriesMinX[i];\r
  85     float deletedMinY = entriesMinY[i];\r
  86     float deletedMaxX = entriesMaxX[i];\r
  87     float deletedMaxY = entriesMaxY[i];\r
  88     \r
  89     if (i != lastIndex) {\r
  90       entriesMinX[i] = entriesMinX[lastIndex];\r
  91       entriesMinY[i] = entriesMinY[lastIndex];\r
  92       entriesMaxX[i] = entriesMaxX[lastIndex];\r
  93       entriesMaxY[i] = entriesMaxY[lastIndex];\r
  94         ids[i] = ids[lastIndex];\r
  95           }\r
  96     entryCount--;\r
  97     \r
  98     // adjust the MBR\r
  99     recalculateMBRIfInfluencedBy(deletedMinX, deletedMinY, deletedMaxX, deletedMaxY);\r
 100   } \r
 101   \r
 102   // deletedMin/MaxX/Y is a rectangle that has just been deleted or made smaller.\r
 103   // Thus, the MBR is only recalculated if the deleted rectangle influenced the old MBR\r
 104   void recalculateMBRIfInfluencedBy(float deletedMinX, float deletedMinY, float deletedMaxX, float deletedMaxY) {\r
 105     if (mbrMinX == deletedMinX || mbrMinY == deletedMinY || mbrMaxX == deletedMaxX || mbrMaxY == deletedMaxY) { \r
 106       recalculateMBR();   \r
 107     }\r
 108   }\r
 109    \r
 110   void recalculateMBR() {\r
 111     mbrMinX = entriesMinX[0];\r
 112     mbrMinY = entriesMinY[0];\r
 113     mbrMaxX = entriesMaxX[0];\r
 114     mbrMaxY = entriesMaxY[0];\r
 115 \r
 116     for (int i = 1; i < entryCount; i++) {\r
 117       if (entriesMinX[i] < mbrMinX) mbrMinX = entriesMinX[i];\r
 118       if (entriesMinY[i] < mbrMinY) mbrMinY = entriesMinY[i];\r
 119       if (entriesMaxX[i] > mbrMaxX) mbrMaxX = entriesMaxX[i];\r
 120       if (entriesMaxY[i] > mbrMaxY) mbrMaxY = entriesMaxY[i];\r
 121     }\r
 122   }\r
 123     \r
 124   /**\r
 125    * eliminate null entries, move all entries to the start of the source node\r
 126    */\r
 127   void reorganize(RTree rtree) {\r
 128     int countdownIndex = rtree.maxNodeEntries - 1; \r
 129     for (int index = 0; index < entryCount; index++) {\r
 130       if (ids[index] == -1) {\r
 131          while (ids[countdownIndex] == -1 && countdownIndex > index) {\r
 132            countdownIndex--;\r
 133          }\r
 134          entriesMinX[index] = entriesMinX[countdownIndex];\r
 135          entriesMinY[index] = entriesMinY[countdownIndex];\r
 136          entriesMaxX[index] = entriesMaxX[countdownIndex];\r
 137          entriesMaxY[index] = entriesMaxY[countdownIndex];\r
 138          ids[index] = ids[countdownIndex];    \r
 139          ids[countdownIndex] = -1;\r
 140       }\r
 141     }\r
 142   }\r
 143   \r
 144   public int getEntryCount() {\r
 145     return entryCount;\r
 146   }\r
 147  \r
 148   public int getId(int index) {\r
 149     if (index < entryCount) {\r
 150       return ids[index];\r
 151     }\r
 152     return -1;\r
 153   }\r
 154   \r
 155   boolean isLeaf() {\r
 156     return (level == 1);\r
 157   }\r
 158   \r
 159   public int getLevel() {\r
 160     return level; \r
 161   }\r
 162 }\r