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

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