public class Bintree
extends java.lang.Object
BinTree
(or "Binary Interval Tree")
is a 1-dimensional version of a quadtree.
It indexes 1-dimensional intervals (which may
be the projection of 2-D objects on an axis).
It supports range searching
(where the range may be a single point).
This structure is dynamic -
new items can be added at any time,
and it will support deletion of items
(although this is not currently implemented).
This implementation does not require specifying the extent of the inserted items beforehand. It will automatically expand to accommodate any extent of dataset.
The bintree structure is used to provide a primary filter for interval queries. The query() method returns a list of all objects which may intersect the query interval. Note that it may return objects which do not in fact intersect. A secondary filter is required to test for exact intersection. Of course, this secondary filter may consist of other tests besides intersection, such as testing other kinds of spatial relationships.
This index is different to the Interval Tree of Edelsbrunner or the Segment Tree of Bentley.
Constructor | Description |
---|---|
Bintree() |
Modifier and Type | Method | Description |
---|---|---|
int |
depth() |
|
static Interval |
ensureExtent(Interval itemInterval,
double minExtent) |
Ensure that the Interval for the inserted item has non-zero extents.
|
void |
insert(Interval itemInterval,
java.lang.Object item) |
|
java.util.Iterator |
iterator() |
|
int |
nodeSize() |
Compute the total number of nodes in the tree
|
java.util.List |
query(double x) |
|
java.util.List |
query(Interval interval) |
Queries the tree to find all candidate items which
may overlap the query interval.
|
void |
query(Interval interval,
java.util.Collection foundItems) |
Adds items in the tree which potentially overlap the query interval
to the given collection.
|
boolean |
remove(Interval itemInterval,
java.lang.Object item) |
Removes a single item from the tree.
|
int |
size() |
public static Interval ensureExtent(Interval itemInterval, double minExtent)
public int depth()
public int size()
public int nodeSize()
public void insert(Interval itemInterval, java.lang.Object item)
public boolean remove(Interval itemInterval, java.lang.Object item)
itemEnv
- the Envelope of the item to be removeditem
- the item to removetrue
if the item was found (and thus removed)public java.util.Iterator iterator()
public java.util.List query(double x)
public java.util.List query(Interval interval)
public void query(Interval interval, java.util.Collection foundItems)
interval
- a query interval, or nullresultItems
- the candidate items foundCopyright © 2018. All rights reserved.