Package org.khelekore.prtree

Class PRTree<T>

java.lang.Object

org.khelekore.prtree.PRTree<T>

Type Parameters:

T - the data type stored in the PRTree

All Implemented Interfaces:

Serializable

public class PRTree<T>
extends Object
implements Serializable

A Priority R-Tree, a spatial index, for N dimensions. This tree only supports bulk loading.

See Also:

Serialized Form

Constructor Summary

Constructors

Constructor	Description
PRTree(MBRConverter<T> converter, int branchFactor)	Create a new PRTree using the specified branch factor.

Method Summary

Modifier and Type	Method	Description
Iterable<T>	find(double xmin, double ymin, double xmax, double ymax)	Find all objects that intersect the given rectangle.
void	find(double xmin, double ymin, double xmax, double ymax, List<T> resultNodes)	Finds all objects that intersect the given rectangle and stores the found node in the given list.
void	find(double xmin, double ymin, double xmax, double ymax, List<T> resultNodes, NodeFilter<T> filter)	Finds all objects that intersect the given rectangle and stores the found node in the given list.
Iterable<T>	find(double xmin, double ymin, double xmax, double ymax, NodeFilter<T> filter)	Find all objects that intersect the given rectangle.
Iterable<T>	find(MBR query)	Find all objects that intersect the given rectangle.
void	find(MBR query, List<T> resultNodes)	Finds all objects that intersect the given rectangle and stores the found node in the given list.
void	find(MBR query, List<T> resultNodes, NodeFilter<T> filter)	Finds all objects that intersect the given rectangle and stores the found node in the given list.
Iterable<T>	find(MBR query, NodeFilter<T> filter)	Find all objects that intersect the given rectangle.
int	getHeight()	Get the height of this tree.
MBR	getMBR()	Get an N dimensional minimum bounding box of the data stored in this tree.
MBR2D	getMBR2D()	Get a 2 dimensional minimum bounding rectangle of the data stored in this tree.
int	getNumberOfLeaves()	Get the number of data leafs in this tree.
boolean	isEmpty()	Check if this tree is empty
void	load(Collection<? extends T> data)	Bulk load data into this tree.
List<DistanceResult<T>>	nearestNeighbour(DistanceCalculator<T> dc, NodeFilter<T> filter, int maxHits, PointND p)	Get the nearest neighbour of the given point

Methods inherited from class java.lang.Object

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

Constructor Detail

PRTree

public PRTree(MBRConverter<T> converter,
              int branchFactor)

Create a new PRTree using the specified branch factor.

Parameters:

converter - the MBRConverter to use for this tree

branchFactor - the number of child nodes for each internal node.

Method Detail

load

public void load(Collection<? extends T> data)

Bulk load data into this tree. Create the leaf nodes that each hold (up to) branchFactor data entries. Then use the leaf nodes as data until we can fit all nodes into the root node.

Parameters:

data - the collection of data to store in the tree.

Throws:

IllegalStateException - if the tree is already loaded

getMBR2D

public MBR2D getMBR2D()

Get a 2 dimensional minimum bounding rectangle of the data stored in this tree.

Returns:

the MBR of the whole PRTree

getMBR

public MBR getMBR()

Get an N dimensional minimum bounding box of the data stored in this tree.

Returns:

the MBR of the whole PRTree

getNumberOfLeaves

public int getNumberOfLeaves()

Get the number of data leafs in this tree.

Returns:

the total number of leafs in this tree

isEmpty

public boolean isEmpty()

Check if this tree is empty

Returns:

true if the number of leafs is 0, false otherwise

getHeight

public int getHeight()

Get the height of this tree.

Returns:

the total height of this tree

find

public void find(double xmin,
                 double ymin,
                 double xmax,
                 double ymax,
                 List<T> resultNodes)

Finds all objects that intersect the given rectangle and stores the found node in the given list. Note, this find method will only use two dimensions, no matter how many dimensions the PRTree actually has.

Parameters:

xmin - the minimum value of the x coordinate when searching

ymin - the minimum value of the y coordinate when searching

xmax - the maximum value of the x coordinate when searching

ymax - the maximum value of the y coordinate when searching

resultNodes - the list that will be filled with the result

find

public void find(double xmin,
                 double ymin,
                 double xmax,
                 double ymax,
                 List<T> resultNodes,
                 NodeFilter<T> filter)

Finds all objects that intersect the given rectangle and stores the found node in the given list. Note, this find method will only use two dimensions, no matter how many dimensions the PRTree actually has.

Parameters:

xmin - the minimum value of the x coordinate when searching

ymin - the minimum value of the y coordinate when searching

xmax - the maximum value of the x coordinate when searching

ymax - the maximum value of the y coordinate when searching

resultNodes - the list that will be filled with the result

filter - a secondary filter to apply

find

public void find(MBR query,
                 List<T> resultNodes)

Finds all objects that intersect the given rectangle and stores the found node in the given list.

Parameters:

query - the bounds of the query

resultNodes - the list that will be filled with the result

find

public void find(MBR query,
                 List<T> resultNodes,
                 NodeFilter<T> filter)

Finds all objects that intersect the given rectangle and stores the found node in the given list.

Parameters:

query - the bounds of the query

resultNodes - the list that will be filled with the result

filter - a secondary filter to apply to the found nodes

find

public Iterable<T> find(double xmin,
                        double ymin,
                        double xmax,
                        double ymax)

Find all objects that intersect the given rectangle. Note, this find method will only use two dimensions, no matter how many dimensions the PRTree actually has.

Parameters:

xmin - the minimum value of the x coordinate when searching

ymin - the minimum value of the y coordinate when searching

xmax - the maximum value of the x coordinate when searching

ymax - the maximum value of the y coordinate when searching

Returns:

an iterable of the elements inside the query rectangle

Throws:

IllegalArgumentException - if xmin > xmax or ymin > ymax

find

public Iterable<T> find(double xmin,
                        double ymin,
                        double xmax,
                        double ymax,
                        NodeFilter<T> filter)

Find all objects that intersect the given rectangle. Note, this find method will only use two dimensions, no matter how many dimensions the PRTree actually has.

Parameters:

xmin - the minimum value of the x coordinate when searching

ymin - the minimum value of the y coordinate when searching

xmax - the maximum value of the x coordinate when searching

ymax - the maximum value of the y coordinate when searching

filter - a secondary filter to apply to the found nodes

Returns:

an iterable of the elements inside the query rectangle

Throws:

IllegalArgumentException - if xmin > xmax or ymin > ymax

find

public Iterable<T> find(MBR query)

Find all objects that intersect the given rectangle.

Parameters:

query - the bounds of the query

Returns:

an iterable of the elements inside the query rectangle

Throws:

IllegalArgumentException - if xmin > xmax or ymin > ymax

find

public Iterable<T> find(MBR query,
                        NodeFilter<T> filter)

Find all objects that intersect the given rectangle.

Parameters:

query - the bounds of the query

filter - a secondary filter to apply to the found nodes

Returns:

an iterable of the elements inside the query rectangle

Throws:

IllegalArgumentException - if xmin > xmax or ymin > ymax

nearestNeighbour

public List<DistanceResult<T>> nearestNeighbour(DistanceCalculator<T> dc,
                                                NodeFilter<T> filter,
                                                int maxHits,
                                                PointND p)

Get the nearest neighbour of the given point

Parameters:

dc - the DistanceCalculator to use.

filter - a NodeFilter that can be used to ignore some leaf nodes.

maxHits - the maximum number of entries to find.

p - the point to find the nearest neighbour to.

Returns:

A List of DistanceResult with up to maxHits results. Will return an empty list if this tree is empty.