org.spf4j.ds

Class RTree<T>

java.lang.Object

org.spf4j.ds.RTree<T>

Type Parameters:

T - the type of entry to store in this RTree.

public final class RTree<T>
extends Object

Implementation of an arbitrary-dimension RTree. Based on R-Trees: A Dynamic Index Structure for Spatial Searching (Antonn Guttmann, 1984) This class is not thread-safe. Z TODO: I have cleaned up a bit this class, but there is a lot more to do here this class implementation is not clean in several places. (see findbugs supressions)

Nested Class Summary

Nested Classes

Modifier and Type	Class and Description
static class	RTree.SeedPicker

Constructor Summary

Constructors

Constructor and Description
RTree() Builds a new RTree using default parameters: maximum 50 entries per node minimum 2 entries per node 2 dimensions
RTree(int numDimensions)
RTree(int maxEntries, int minEntries, int numDims)
RTree(int maxEntries, int minEntries, int numDims, RTree.SeedPicker seedPicker) Creates a new RTree.

Method Summary

Methods

Modifier and Type	Method and Description
void	clear() Empties the RTree
boolean	delete(float[] coords, float[] dimensions, T entry) Deletes the entry associated with the given rectangle from the RTree
boolean	delete(float[] coords, T entry)
int	getMaxEntries()
int	getMinEntries()
int	getNumDims()
void	insert(float[] coords, float[] dimensions, T entry) Inserts the given entry into the RTree, associated with the given rectangle.
void	insert(float[] coords, T entry) Convenience method for inserting a point
List<T>	search(float[] coords, float[] dimensions) Searches the RTree for objects overlapping with the given rectangle.
int	size()
String	visualize()

Methods inherited from class java.lang.Object

clone, equals, finalize, getClass, hashCode, notify, notifyAll, toString, wait, wait, wait

Constructor Detail

RTree

public RTree(int maxEntries,
     int minEntries,
     int numDims,
     RTree.SeedPicker seedPicker)

Creates a new RTree.

Parameters:

maxEntries - maximum number of entries per node

minEntries - minimum number of entries per node (except for the root node)

numDims - the number of dimensions of the RTree.

RTree

public RTree(int maxEntries,
     int minEntries,
     int numDims)

RTree

public RTree()

Builds a new RTree using default parameters: maximum 50 entries per node minimum 2 entries per node 2 dimensions

RTree

public RTree(int numDimensions)

Method Detail

getMaxEntries

public int getMaxEntries()

Returns:

the maximum number of entries per node

getMinEntries

public int getMinEntries()

Returns:

the minimum number of entries per node for all nodes except the root.

getNumDims

public int getNumDims()

Returns:

the number of dimensions of the tree

size

public int size()

Returns:

the number of items in this tree.

search

@Nonnull
public List<T> search(float[] coords,
                     float[] dimensions)

Searches the RTree for objects overlapping with the given rectangle.

Parameters:

coords - the corner of the rectangle that is the lower bound of every dimension (eg. the top-left corner)

dimensions - the dimensions of the rectangle.

Returns:

a list of objects whose rectangles overlap with the given rectangle.

delete

public boolean delete(float[] coords,
             float[] dimensions,
             T entry)

Deletes the entry associated with the given rectangle from the RTree

Parameters:

coords - the corner of the rectangle that is the lower bound in every dimension

dimensions - the dimensions of the rectangle

entry - the entry to delete

Returns:

true iff the entry was deleted from the RTree.

delete

public boolean delete(float[] coords,
             T entry)

clear

public void clear()

Empties the RTree

insert

public void insert(float[] coords,
          float[] dimensions,
          T entry)

Inserts the given entry into the RTree, associated with the given rectangle.

Parameters:

coords - the corner of the rectangle that is the lower bound in every dimension

dimensions - the dimensions of the rectangle

entry - the entry to insert

insert

public void insert(float[] coords,
          T entry)

Convenience method for inserting a point

Parameters:

coords -

entry -

visualize

public String visualize()