edu.mines.jtk.util
Class RTree

java.lang.Object
  java.util.AbstractCollection<E>
      java.util.AbstractSet<java.lang.Object>
          edu.mines.jtk.util.RTree

All Implemented Interfaces:

java.lang.Iterable<java.lang.Object>, java.util.Collection<java.lang.Object>, java.util.Set<java.lang.Object>

public class RTree
extends java.util.AbstractSet<java.lang.Object>

A tree of bounded objects with methods for fast updates and queries. An R-tree's entries are bounded objects with min/max coordinates in N dimensions, where N is a parameter specified when constructing an R-tree. We refer to these N-dimensional bounds as boxes.

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:

• Guttman A., 1984, R-trees - a dynamic index structure for spatial searching: Proceedings of the ACM, SIGMOD, p. 47-57.
• Roussopoulos, N., Kelley, S., and Vincent, F., 1995, Nearest neighbor queries: Proceedings of the ACM, SIGMOD, p. 71-79.
• Cheung, K.L., and Fu, A.W.C., 1998, Enhanced nearest neighbor search on the R-tree: SIGMOD Record, v. 27, n. 3, p. 16-21.

Version:

2003.05.02, 2006.07.13

Author:

Dave Hale and Zach Pember, Colorado School of Mines

Nested Class Summary

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 Summary

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.

Method Summary

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.

Methods inherited from class java.util.AbstractSet

equals, hashCode, removeAll

Methods inherited from class java.util.AbstractCollection

addAll, containsAll, retainAll, toArray, toArray, toString

Methods inherited from class java.lang.Object

clone, finalize, getClass, notify, notifyAll, wait, wait, wait

Methods inherited from interface java.util.Set

addAll, containsAll, retainAll, toArray, toArray

Constructor Detail

RTree

public RTree(int ndim,
             int nmin,
             int nmax)

Constructs an R-tree with specified parameters.

Parameters:

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.

RTree

public RTree(int ndim,
             int nmin,
             int nmax,
             RTree.Boxer boxer)

Constructs an R-tree with specified parameters.

Parameters:

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.

Method Detail

size

public int size()

Returns the size of this tree. The size is the number of objects added minus the number of objects removed from this tree.

Specified by:

size in interface java.util.Collection<java.lang.Object>

Specified by:

size in interface java.util.Set<java.lang.Object>

Specified by:

size in class java.util.AbstractCollection<java.lang.Object>

Returns:

the number of boxed objects.

clear

public void clear()

Removes all objects from this tree.

Specified by:

clear in interface java.util.Collection<java.lang.Object>

Specified by:

clear in interface java.util.Set<java.lang.Object>

Overrides:

clear in class java.util.AbstractCollection<java.lang.Object>

isEmpty

public boolean isEmpty()

Returns true if this tree contains no objects.

Specified by:

isEmpty in interface java.util.Collection<java.lang.Object>

Specified by:

isEmpty in interface java.util.Set<java.lang.Object>

Overrides:

isEmpty in class java.util.AbstractCollection<java.lang.Object>

Returns:

true, if empty; false, otherwise.

add

public boolean add(java.lang.Object object)

Adds the specified object to this tree, if not already present.

Specified by:

add in interface java.util.Collection<java.lang.Object>

Specified by:

add in interface java.util.Set<java.lang.Object>

Overrides:

add in class java.util.AbstractCollection<java.lang.Object>

Parameters:

object - the object.

Returns:

true, if the object was added; false, otherwise.

addPacked

public int addPacked(java.lang.Object[] objects)

Adds the specified objects to this tree, if not already present. This method packs the objects, which means that it adds them in a special order. The goal is to reduce (1) the cost of building the R-tree, (2) the cost of subsequent queries, and (3) the memory consumed by the R-tree. However, depending on the locations and sizes of the added objects, packing may increase these costs. Packing seems to work best for uniformly distributed objects with similar size. Also, packing is best when this method is called for an empty R-tree.

Parameters:

objects - the objects.

Returns:

the number of objects added.

remove

public boolean remove(java.lang.Object object)

Deletes the specified object from this tree, if present.

Specified by:

remove in interface java.util.Collection<java.lang.Object>

Specified by:

remove in interface java.util.Set<java.lang.Object>

Overrides:

remove in class java.util.AbstractCollection<java.lang.Object>

Parameters:

object - the object.

Returns:

true, if the object was removed; false, otherwise.

contains

public boolean contains(java.lang.Object object)

Determines whether this tree contains the specified object.

Specified by:

contains in interface java.util.Collection<java.lang.Object>

Specified by:

contains in interface java.util.Set<java.lang.Object>

Overrides:

contains in class java.util.AbstractCollection<java.lang.Object>

Parameters:

object - the object.

Returns:

true, if the object is in this tree; false, otherwise.

iterator

public java.util.Iterator<java.lang.Object> iterator()

Returns an iterator for all objects in this tree.

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.

Specified by:

iterator in interface java.lang.Iterable<java.lang.Object>

Specified by:

iterator in interface java.util.Collection<java.lang.Object>

Specified by:

iterator in interface java.util.Set<java.lang.Object>

Specified by:

iterator in class java.util.AbstractCollection<java.lang.Object>

Returns:

the iterator.

getLevels

public int getLevels()

Gets the number of levels in this tree.

Returns:

the number of levels.

findOverlapping

public java.lang.Object[] findOverlapping(float[] min,
                                          float[] max)

Finds all objects with bounds that overlap the specified bounds.

Parameters:

min - array of bounding min coordinates.

max - array of bounding max coordinates.

Returns:

the array of objects found.

findOverlapping

public java.lang.Object[] findOverlapping(RTree.Box box)

Finds all objects with bounds that overlap the specified box.

Parameters:

box - the box.

Returns:

the array of objects found.

See Also:

RTree.Box

findInSphere

public java.lang.Object[] findInSphere(float[] center,
                                       float radius)

Finds all objects in a specified sphere. An object is considered in the sphere if the distance from the sphere's center to the object (not its bounds) is less than or equal to the sphere's radius.

Parameters:

center - array of sphere center coordinates.

radius - the sphere radius.

Returns:

the array of objects found.

findNearest

public java.lang.Object findNearest(float[] point)

Finds the object nearest to the specified point.

Parameters:

point - array of point coordinates.

Returns:

the nearest object; null, if this tree is empty.

findNearest

public java.lang.Object[] findNearest(int k,
                                      float[] point)

Finds the k objects nearest to the specified point.

Parameters:

k - the number of nearest objects to find.

point - array of point coordinates.

Returns:

the array of objects, ordered by increasing distance to the point.

getLeafArea

public float getLeafArea()

Gets the leaf node area, the sum of the areas of all leaf node boxes.

Returns:

the area.

getLeafVolume

public float getLeafVolume()

Gets the leaf node volume, the sum of the volumes of all leaf node boxes.

Returns:

the volume.

dump

public void dump()

Prints this tree to the standard output stream. Intended for debugging, only.

validate

public void validate()

Validates the internal state of this tree. Intended for debugging, only, with assertions enabled.