001: /*
002: * The JTS Topology Suite is a collection of Java classes that
003: * implement the fundamental operations required to validate a given
004: * geo-spatial data set to a known topological specification.
005: *
006: * Copyright (C) 2001 Vivid Solutions
007: *
008: * This library is free software; you can redistribute it and/or
009: * modify it under the terms of the GNU Lesser General Public
010: * License as published by the Free Software Foundation; either
011: * version 2.1 of the License, or (at your option) any later version.
012: *
013: * This library is distributed in the hope that it will be useful,
014: * but WITHOUT ANY WARRANTY; without even the implied warranty of
015: * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU
016: * Lesser General Public License for more details.
017: *
018: * You should have received a copy of the GNU Lesser General Public
019: * License along with this library; if not, write to the Free Software
020: * Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA 02111-1307 USA
021: *
022: * For more information, contact:
023: *
024: * Vivid Solutions
025: * Suite #1A
026: * 2328 Government Street
027: * Victoria BC V8T 5G5
028: * Canada
029: *
030: * (250)385-6040
031: * www.vividsolutions.com
032: */
033: package com.vividsolutions.jts.index.bintree;
034:
035: import java.util.ArrayList;
036: import java.util.Collection;
037: import java.util.Iterator;
038: import java.util.List;
039:
040: /**
041: * An <code>BinTree</code> (or "Binary Interval Tree")
042: * is a 1-dimensional version of a quadtree.
043: * It indexes 1-dimensional intervals (which of course may
044: * be the projection of 2-D objects on an axis).
045: * It supports range searching
046: * (where the range may be a single point).
047: * <p>
048: * This implementation does not require specifying the extent of the inserted
049: * items beforehand. It will automatically expand to accomodate any extent
050: * of dataset.
051: * <p>
052: * The bintree structure is used to provide a primary filter
053: * for interval queries. The query() method returns a list of
054: * all objects which <i>may</i> intersect the query interval.
055: * Note that it may return objects which do not in fact intersect.
056: * A secondary filter is required to test for exact intersection.
057: * Of course, this secondary filter may consist of other tests besides
058: * intersection, such as testing other kinds of spatial relationships.
059: * <p>
060: * This index is different to the Interval Tree of Edelsbrunner
061: * or the Segment Tree of Bentley.
062: *
063: * @version 1.7
064: */
065: public class Bintree {
066: /**
067: * Ensure that the Interval for the inserted item has non-zero extents.
068: * Use the current minExtent to pad it, if necessary
069: */
070: public static Interval ensureExtent(Interval itemInterval,
071: double minExtent) {
072: double min = itemInterval.getMin();
073: double max = itemInterval.getMax();
074: // has a non-zero extent
075: if (min != max)
076: return itemInterval;
077:
078: // pad extent
079: if (min == max) {
080: min = min - minExtent / 2.0;
081: max = min + minExtent / 2.0;
082: }
083: return new Interval(min, max);
084: }
085:
086: private Root root;
087: /**
088: * Statistics
089: *
090: * minExtent is the minimum extent of all items
091: * inserted into the tree so far. It is used as a heuristic value
092: * to construct non-zero extents for features with zero extent.
093: * Start with a non-zero extent, in case the first feature inserted has
094: * a zero extent in both directions. This value may be non-optimal, but
095: * only one feature will be inserted with this value.
096: **/
097: private double minExtent = 1.0;
098:
099: public Bintree() {
100: root = new Root();
101: }
102:
103: public int depth() {
104: if (root != null)
105: return root.depth();
106: return 0;
107: }
108:
109: public int size() {
110: if (root != null)
111: return root.size();
112: return 0;
113: }
114:
115: /**
116: * Compute the total number of nodes in the tree
117: *
118: * @return the number of nodes in the tree
119: */
120: public int nodeSize() {
121: if (root != null)
122: return root.nodeSize();
123: return 0;
124: }
125:
126: public void insert(Interval itemInterval, Object item) {
127: collectStats(itemInterval);
128: Interval insertInterval = ensureExtent(itemInterval, minExtent);
129: //int oldSize = size();
130: root.insert(insertInterval, item);
131: /* DEBUG
132: int newSize = size();
133: System.out.println("BinTree: size = " + newSize + " node size = " + nodeSize());
134: if (newSize <= oldSize) {
135: System.out.println("Lost item!");
136: root.insert(insertInterval, item);
137: System.out.println("reinsertion size = " + size());
138: }
139: */
140: }
141:
142: public Iterator iterator() {
143: List foundItems = new ArrayList();
144: root.addAllItems(foundItems);
145: return foundItems.iterator();
146: }
147:
148: public List query(double x) {
149: return query(new Interval(x, x));
150: }
151:
152: /**
153: * min and max may be the same value
154: */
155: public List query(Interval interval) {
156: /**
157: * the items that are matched are all items in intervals
158: * which overlap the query interval
159: */
160: List foundItems = new ArrayList();
161: query(interval, foundItems);
162: return foundItems;
163: }
164:
165: public void query(Interval interval, Collection foundItems) {
166: root.addAllItemsFromOverlapping(interval, foundItems);
167: }
168:
169: private void collectStats(Interval interval) {
170: double del = interval.getWidth();
171: if (del < minExtent && del > 0.0)
172: minExtent = del;
173: }
174:
175: }
|