001: // Spatial Index Library
002: //
003: // Copyright (C) 2002 Navel Ltd.
004: //
005: // This library is free software; you can redistribute it and/or
006: // modify it under the terms of the GNU Lesser General Public
007: // License as published by the Free Software Foundation; either
008: // version 2.1 of the License, or (at your option) any later version.
009: //
010: // This library is distributed in the hope that it will be useful,
011: // but WITHOUT ANY WARRANTY; without even the implied warranty of
012: // MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU
013: // Lesser General Public License for more details.
014: //
015: // You should have received a copy of the GNU Lesser General Public
016: // License aint with this library; if not, write to the Free Software
017: // Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA 02111-1307 USA
018: //
019: // Contact information:
020: // Mailing address:
021: // Marios Hadjieleftheriou
022: // University of California, Riverside
023: // Department of Computer Science
024: // Surge Building, Room 310
025: // Riverside, CA 92521
026: //
027: // Email:
028: // marioh@cs.ucr.edu
029: package org.geotools.caching.spatialindex.rtree;
030:
031: import org.geotools.caching.spatialindex.spatialindex.*;
032:
033: import java.util.*;
034:
035: public class Index extends Node {
036: public Index(RTree pTree, int id, int level) {
037: super (pTree, id, level, pTree.m_indexCapacity);
038: }
039:
040: protected Node chooseSubtree(Region mbr, int level, Stack pathBuffer) {
041: if (m_level == level) {
042: return this ;
043: }
044:
045: pathBuffer.push(new Integer(m_identifier));
046:
047: int child = 0;
048:
049: switch (m_pTree.m_treeVariant) {
050: case SpatialIndex.RtreeVariantLinear:
051: case SpatialIndex.RtreeVariantQuadratic:
052: child = findLeastEnlargement(mbr);
053:
054: break;
055:
056: case SpatialIndex.RtreeVariantRstar:
057:
058: if (m_level == 1) {
059: // if this node points to leaves...
060: child = findLeastOverlap(mbr);
061: } else {
062: child = findLeastEnlargement(mbr);
063: }
064:
065: break;
066:
067: default:
068: throw new IllegalStateException("Unknown RTree variant.");
069: }
070:
071: Node n = m_pTree.readNode(m_pIdentifier[child]);
072: Node ret = n.chooseSubtree(mbr, level, pathBuffer);
073:
074: return ret;
075: }
076:
077: protected Leaf findLeaf(Region mbr, int id, Stack pathBuffer) {
078: pathBuffer.push(new Integer(m_identifier));
079:
080: for (int cChild = 0; cChild < m_children; cChild++) {
081: if (m_pMBR[cChild].contains(mbr)) {
082: Node n = m_pTree.readNode(m_pIdentifier[cChild]);
083: Leaf l = n.findLeaf(mbr, id, pathBuffer);
084:
085: if (l != null) {
086: return l;
087: }
088: }
089: }
090:
091: pathBuffer.pop();
092:
093: return null;
094: }
095:
096: protected Node[] split(byte[] pData, Region mbr, int id) {
097: m_pTree.m_stats.m_splits++;
098:
099: ArrayList g1 = new ArrayList();
100: ArrayList g2 = new ArrayList();
101:
102: switch (m_pTree.m_treeVariant) {
103: case SpatialIndex.RtreeVariantLinear:
104: case SpatialIndex.RtreeVariantQuadratic:
105: rtreeSplit(pData, mbr, id, g1, g2);
106:
107: break;
108:
109: case SpatialIndex.RtreeVariantRstar:
110: rstarSplit(pData, mbr, id, g1, g2);
111:
112: break;
113:
114: default:
115: throw new IllegalStateException("Unknown RTree variant.");
116: }
117:
118: Node left = new Index(m_pTree, m_identifier, m_level);
119: Node right = new Index(m_pTree, -1, m_level);
120:
121: int cIndex;
122:
123: for (cIndex = 0; cIndex < g1.size(); cIndex++) {
124: int i = ((Integer) g1.get(cIndex)).intValue();
125: left.insertEntry(null, m_pMBR[i], m_pIdentifier[i]);
126: }
127:
128: for (cIndex = 0; cIndex < g2.size(); cIndex++) {
129: int i = ((Integer) g2.get(cIndex)).intValue();
130: right.insertEntry(null, m_pMBR[i], m_pIdentifier[i]);
131: }
132:
133: Node[] ret = new Node[2];
134: ret[0] = left;
135: ret[1] = right;
136:
137: return ret;
138: }
139:
140: protected int findLeastEnlargement(Region r) {
141: double area = Double.POSITIVE_INFINITY;
142: int best = -1;
143:
144: for (int cChild = 0; cChild < m_children; cChild++) {
145: Region t = m_pMBR[cChild].combinedRegion(r);
146:
147: double a = m_pMBR[cChild].getArea();
148: double enl = t.getArea() - a;
149:
150: if (enl < area) {
151: area = enl;
152: best = cChild;
153: } else if (enl == area) {
154: if (a < m_pMBR[best].getArea()) {
155: best = cChild;
156: }
157: }
158: }
159:
160: return best;
161: }
162:
163: protected int findLeastOverlap(Region r) {
164: OverlapEntry[] entries = new OverlapEntry[m_children];
165:
166: double leastOverlap = Double.POSITIVE_INFINITY;
167: double me = Double.POSITIVE_INFINITY;
168: int best = -1;
169:
170: // find combined region and enlargement of every entry and store it.
171: for (int cChild = 0; cChild < m_children; cChild++) {
172: OverlapEntry e = new OverlapEntry();
173:
174: e.m_id = cChild;
175: e.m_original = m_pMBR[cChild];
176: e.m_combined = m_pMBR[cChild].combinedRegion(r);
177: e.m_oa = e.m_original.getArea();
178: e.m_ca = e.m_combined.getArea();
179: e.m_enlargement = e.m_ca - e.m_oa;
180: entries[cChild] = e;
181:
182: if (e.m_enlargement < me) {
183: me = e.m_enlargement;
184: best = cChild;
185: } else if ((e.m_enlargement == me)
186: && (e.m_oa < entries[best].m_oa)) {
187: best = cChild;
188: }
189: }
190:
191: if ((me < SpatialIndex.EPSILON) || (me > SpatialIndex.EPSILON)) {
192: int cIterations;
193:
194: if (m_children > m_pTree.m_nearMinimumOverlapFactor) {
195: // sort entries in increasing order of enlargement.
196: Arrays.sort(entries, new OverlapEntryComparator());
197: cIterations = m_pTree.m_nearMinimumOverlapFactor;
198: } else {
199: cIterations = m_children;
200: }
201:
202: // calculate overlap of most important original entries (near minimum overlap cost).
203: for (int cIndex = 0; cIndex < cIterations; cIndex++) {
204: double dif = 0.0;
205: OverlapEntry e = entries[cIndex];
206:
207: for (int cChild = 0; cChild < m_children; cChild++) {
208: if (e.m_id != cChild) {
209: double f = e.m_combined
210: .getIntersectingArea(m_pMBR[cChild]);
211:
212: if (f != 0.0) {
213: dif += (f - e.m_original
214: .getIntersectingArea(m_pMBR[cChild]));
215: }
216: }
217: } // for (cChild)
218:
219: if (dif < leastOverlap) {
220: leastOverlap = dif;
221: best = cIndex;
222: } else if (dif == leastOverlap) {
223: if (e.m_enlargement == entries[best].m_enlargement) {
224: // keep the one with least area.
225: if (e.m_original.getArea() < entries[best].m_original
226: .getArea()) {
227: best = cIndex;
228: }
229: } else {
230: // keep the one with least enlargement.
231: if (e.m_enlargement < entries[best].m_enlargement) {
232: best = cIndex;
233: }
234: }
235: }
236: } // for (cIndex)
237: }
238:
239: return entries[best].m_id;
240: }
241:
242: protected void adjustTree(Node n, Stack pathBuffer) {
243: m_pTree.m_stats.m_adjustments++;
244:
245: // find entry pointing to old node;
246: int child;
247:
248: for (child = 0; child < m_children; child++) {
249: if (m_pIdentifier[child] == n.m_identifier) {
250: break;
251: }
252: }
253:
254: // MBR needs recalculation if either:
255: // 1. the NEW child MBR is not contained.
256: // 2. the OLD child MBR is touching.
257: boolean b = m_nodeMBR.contains(n.m_nodeMBR);
258: boolean recalc = (!b) ? true : m_nodeMBR.touches(m_pMBR[child]);
259:
260: m_pMBR[child] = (Region) n.m_nodeMBR.clone();
261:
262: if (recalc) {
263: for (int cDim = 0; cDim < m_pTree.m_dimension; cDim++) {
264: m_nodeMBR.m_pLow[cDim] = Double.POSITIVE_INFINITY;
265: m_nodeMBR.m_pHigh[cDim] = Double.NEGATIVE_INFINITY;
266:
267: for (int cChild = 0; cChild < m_children; cChild++) {
268: m_nodeMBR.m_pLow[cDim] = Math.min(
269: m_nodeMBR.m_pLow[cDim],
270: m_pMBR[cChild].m_pLow[cDim]);
271: m_nodeMBR.m_pHigh[cDim] = Math.max(
272: m_nodeMBR.m_pHigh[cDim],
273: m_pMBR[cChild].m_pHigh[cDim]);
274: }
275: }
276: }
277:
278: m_pTree.writeNode(this );
279:
280: if (recalc && !pathBuffer.empty()) {
281: int cParent = ((Integer) pathBuffer.pop()).intValue();
282: Index p = (Index) m_pTree.readNode(cParent);
283: p.adjustTree(this , pathBuffer);
284: }
285: }
286:
287: protected void adjustTree(Node n1, Node n2, Stack pathBuffer,
288: boolean[] overflowTable) {
289: m_pTree.m_stats.m_adjustments++;
290:
291: // find entry pointing to old node;
292: int child;
293:
294: for (child = 0; child < m_children; child++) {
295: if (m_pIdentifier[child] == n1.m_identifier) {
296: break;
297: }
298: }
299:
300: // MBR needs recalculation if either:
301: // 1. the NEW child MBR is not contained.
302: // 2. the OLD child MBR is touching.
303: boolean b = m_nodeMBR.contains(n1.m_nodeMBR);
304: boolean recalc = (!b) ? true : m_nodeMBR.touches(m_pMBR[child]);
305:
306: m_pMBR[child] = (Region) n1.m_nodeMBR.clone();
307:
308: if (recalc) {
309: for (int cDim = 0; cDim < m_pTree.m_dimension; cDim++) {
310: m_nodeMBR.m_pLow[cDim] = Double.POSITIVE_INFINITY;
311: m_nodeMBR.m_pHigh[cDim] = Double.NEGATIVE_INFINITY;
312:
313: for (int cChild = 0; cChild < m_children; cChild++) {
314: m_nodeMBR.m_pLow[cDim] = Math.min(
315: m_nodeMBR.m_pLow[cDim],
316: m_pMBR[cChild].m_pLow[cDim]);
317: m_nodeMBR.m_pHigh[cDim] = Math.max(
318: m_nodeMBR.m_pHigh[cDim],
319: m_pMBR[cChild].m_pHigh[cDim]);
320: }
321: }
322: }
323:
324: // No write necessary here. insertData will write the node if needed.
325: //m_pTree.writeNode(this);
326: boolean adjusted = insertData(null, (Region) n2.m_nodeMBR
327: .clone(), n2.m_identifier, pathBuffer, overflowTable);
328:
329: // if n2 is contained in the node and there was no split or reinsert,
330: // we need to adjust only if recalculation took place.
331: // In all other cases insertData above took care of adjustment.
332: if (!adjusted && recalc && !pathBuffer.empty()) {
333: int cParent = ((Integer) pathBuffer.pop()).intValue();
334: Index p = (Index) m_pTree.readNode(cParent);
335: p.adjustTree(this , pathBuffer);
336: }
337: }
338:
339: class OverlapEntry {
340: int m_id;
341: double m_enlargement;
342: Region m_original;
343: Region m_combined;
344: double m_oa;
345: double m_ca;
346: }
347:
348: class OverlapEntryComparator implements Comparator {
349: public int compare(Object o1, Object o2) {
350: OverlapEntry e1 = (OverlapEntry) o1;
351: OverlapEntry e2 = (OverlapEntry) o2;
352:
353: if (e1.m_enlargement < e2.m_enlargement) {
354: return -1;
355: }
356:
357: if (e1.m_enlargement > e2.m_enlargement) {
358: return 1;
359: }
360:
361: return 0;
362: }
363: }
364: }
|