public class RTree
extends java.util.AbstractSet<java.lang.Object>
An R-tree facilitates a variety of queries, such as a search for all objects with bounds that overlap a specified box, or a search for the k objects nearest to a specified point. An R-tree is also dynamic; objects may be efficiently added and removed from the tree at any time.
An R-tree uses the N-dimensional coordinate bounds of each object to build a hierarchy (a tree) of internal nodes. Each node contains a list of child nodes or objects. Each node maintains bounds that tightly contain its children. The R-tree attempts to minimize any overlap of these internal nodes, so that objects can be quickly found, added, or removed.
An R-tree is a set; it contains no duplicate objects. Specifically, an R-tree contains no objects b1 and b2 such that b1.equals(b2). Also, an R-tree contains no null objects.
To reduce memory consumption, an object's bounds are not stored in the R-tree. These bounds may be either computed on demand or cached by the object itself. However, while an object is in an R-tree, it should not be changed in any way that would affect its equality comparison or its bounds. The result of such a change is undefined.
References:
Modifier and Type | Class and Description |
---|---|
static class |
RTree.Box
A simple N-dimensional box.
|
static interface |
RTree.Boxed
An N-dimensional object in a box defined by N min/max coordinates.
|
static interface |
RTree.Boxer
Gets bounds and computes distances for objects added to an R-tree.
|
Constructor and Description |
---|
RTree(int ndim,
int nmin,
int nmax)
Constructs an R-tree with specified parameters.
|
RTree(int ndim,
int nmin,
int nmax,
RTree.Boxer boxer)
Constructs an R-tree with specified parameters.
|
Modifier and Type | Method and Description |
---|---|
boolean |
add(java.lang.Object object)
Adds the specified object to this tree, if not already present.
|
int |
addPacked(java.lang.Object[] objects)
Adds the specified objects to this tree, if not already present.
|
void |
clear()
Removes all objects from this tree.
|
boolean |
contains(java.lang.Object object)
Determines whether this tree contains the specified object.
|
void |
dump()
Prints this tree to the standard output stream.
|
java.lang.Object[] |
findInSphere(float[] center,
float radius)
Finds all objects in a specified sphere.
|
java.lang.Object |
findNearest(float[] point)
Finds the object nearest to the specified point.
|
java.lang.Object[] |
findNearest(int k,
float[] point)
Finds the k objects nearest to the specified point.
|
java.lang.Object[] |
findOverlapping(float[] min,
float[] max)
Finds all objects with bounds that overlap the specified bounds.
|
java.lang.Object[] |
findOverlapping(RTree.Box box)
Finds all objects with bounds that overlap the specified box.
|
float |
getLeafArea()
Gets the leaf node area, the sum of the areas of all leaf node boxes.
|
float |
getLeafVolume()
Gets the leaf node volume, the sum of the volumes of all leaf node boxes.
|
int |
getLevels()
Gets the number of levels in this tree.
|
boolean |
isEmpty()
Returns true if this tree contains no objects.
|
java.util.Iterator<java.lang.Object> |
iterator()
Returns an iterator for all objects in this tree.
|
boolean |
remove(java.lang.Object object)
Deletes the specified object from this tree, if present.
|
int |
size()
Returns the size of this tree.
|
void |
validate()
Validates the internal state of this tree.
|
addAll, containsAll, retainAll, toArray, toArray, toString
public RTree(int ndim, int nmin, int nmax)
ndim
- the number of dimensions per object;
equals the number of min/max coordinates per object.nmin
- the minimum number of objects per node;
must not be less than one or greater than nmax/2.nmax
- the maximum number of objects per node;
must not be less than 4.public RTree(int ndim, int nmin, int nmax, RTree.Boxer boxer)
ndim
- the number of dimensions per object;
equals the number of min/max coordinates per object.nmin
- the minimum number of objects per node;
must not be less than one or greater than nmax/2.nmax
- the maximum number of objects per node;
must not be less than 4.boxer
- the RTree.Boxer
used to compute the bounds of
objects added to this tree.public int size()
size
in interface java.util.Collection<java.lang.Object>
size
in interface java.util.Set<java.lang.Object>
size
in class java.util.AbstractCollection<java.lang.Object>
public void clear()
clear
in interface java.util.Collection<java.lang.Object>
clear
in interface java.util.Set<java.lang.Object>
clear
in class java.util.AbstractCollection<java.lang.Object>
public boolean isEmpty()
isEmpty
in interface java.util.Collection<java.lang.Object>
isEmpty
in interface java.util.Set<java.lang.Object>
isEmpty
in class java.util.AbstractCollection<java.lang.Object>
public boolean add(java.lang.Object object)
add
in interface java.util.Collection<java.lang.Object>
add
in interface java.util.Set<java.lang.Object>
add
in class java.util.AbstractCollection<java.lang.Object>
object
- the object.public int addPacked(java.lang.Object[] objects)
objects
- the objects.public boolean remove(java.lang.Object object)
remove
in interface java.util.Collection<java.lang.Object>
remove
in interface java.util.Set<java.lang.Object>
remove
in class java.util.AbstractCollection<java.lang.Object>
object
- the object.public boolean contains(java.lang.Object object)
contains
in interface java.util.Collection<java.lang.Object>
contains
in interface java.util.Set<java.lang.Object>
contains
in class java.util.AbstractCollection<java.lang.Object>
object
- the object.public java.util.Iterator<java.lang.Object> iterator()
The iterator does not support removal. A call to the method
Iterator.remove()
will cause a
UnsupportedOperationException
.
The iterator does not support concurrent modification. If this tree
is modified after the iterator has been returned, a subsequent call
to the method Iterator.next()
will cause a
ConcurrentModificationException
.
iterator
in interface java.lang.Iterable<java.lang.Object>
iterator
in interface java.util.Collection<java.lang.Object>
iterator
in interface java.util.Set<java.lang.Object>
iterator
in class java.util.AbstractCollection<java.lang.Object>
public int getLevels()
public java.lang.Object[] findOverlapping(float[] min, float[] max)
min
- array of bounding min coordinates.max
- array of bounding max coordinates.public java.lang.Object[] findOverlapping(RTree.Box box)
box
- the box.RTree.Box
public java.lang.Object[] findInSphere(float[] center, float radius)
center
- array of sphere center coordinates.radius
- the sphere radius.public java.lang.Object findNearest(float[] point)
point
- array of point coordinates.public java.lang.Object[] findNearest(int k, float[] point)
k
- the number of nearest objects to find.point
- array of point coordinates.public float getLeafArea()
public float getLeafVolume()
public void dump()
public void validate()