2 // Java Spatial Index Library
3 // Copyright (C) 2002-2005 Infomatiq Limited
4 // Copyright (C) 2008-2010 aled@sourceforge.net
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.
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.
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
20 package com.infomatiq.jsi.rtree;
23 * <p>Used by RTree. There are no public methods in this class.</p>
25 * @author aled.morris@infomatiq.co.uk
30 float mbrMinX = Float.MAX_VALUE;
31 float mbrMinY = Float.MAX_VALUE;
32 float mbrMaxX = -Float.MAX_VALUE;
33 float mbrMaxY = -Float.MAX_VALUE;
35 float[] entriesMinX = null;
36 float[] entriesMinY = null;
37 float[] entriesMaxX = null;
38 float[] entriesMaxY = null;
44 Node(int nodeId, int level, int maxNodeEntries) {
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];
54 void addEntry(float minX, float minY, float maxX, float maxY, int id) {
56 entriesMinX[entryCount] = minX;
57 entriesMinY[entryCount] = minY;
58 entriesMaxX[entryCount] = maxX;
59 entriesMaxY[entryCount] = maxY;
61 if (minX < mbrMinX) mbrMinX = minX;
62 if (minY < mbrMinY) mbrMinY = minY;
63 if (maxX > mbrMaxX) mbrMaxX = maxX;
64 if (maxY > mbrMaxY) mbrMaxY = maxY;
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++) {
73 entriesMinX[i] == minX && entriesMinY[i] == minY &&
74 entriesMaxX[i] == maxX && entriesMaxY[i] == maxY) {
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];
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];
99 recalculateMBRIfInfluencedBy(deletedMinX, deletedMinY, deletedMaxX, deletedMaxY);
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) {
110 void recalculateMBR() {
111 mbrMinX = entriesMinX[0];
112 mbrMinY = entriesMinY[0];
113 mbrMaxX = entriesMaxX[0];
114 mbrMaxY = entriesMaxY[0];
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];
125 * eliminate null entries, move all entries to the start of the source node
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) {
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;
144 public int getEntryCount() {
148 public int getId(int index) {
149 if (index < entryCount) {
159 public int getLevel() {