Package com.planet_ink.coffee_mud.core.collections

Class RTree<T extends BoundedObject>

java.lang.Object

com.planet_ink.coffee_mud.core.collections.RTree<T>

public class RTree<T extends BoundedObject>
extends java.lang.Object

2D R-Tree implementation for Android. Uses algorithms from: http://www.sai.msu.su/~megera/postgres/gist/papers/Rstar3.pdf

Nested Class Summary

Nested Classes

Modifier and Type	Class	Description
class	RTree.RTreeNode

Constructor Summary

Constructors

Constructor	Description
RTree()	Default constructor.
RTree(int minChildren, int maxChildren)	Creates an R-Tree.

Method Summary

Modifier and Type	Method	Description
void	clear()
boolean	contains(T o)	Returns whether the given object is in the tree
int	count()	Counts the number of items in the tree.
void	insert(T o)	Inserts object o into the tree.
boolean	leafSearch(T o)
java.util.Enumeration<java.util.Map.Entry<T,java.util.List<java.lang.ref.WeakReference<TrackingVector<T>>>>>	objectEntries()
java.util.Enumeration<T>	objects()
void	query(java.util.Collection<T> results)	Adds items whose AABB intersects the query AABB to results
void	query(java.util.Collection<T> results, long px, long py, long pz)	Returns items whose Rect contains the specified point.
void	query(java.util.Collection<T> results, BoundedObject.BoundedCube box)
T	queryOne(long px, long py, long pz)	Returns one item that intersects the query point, or null if no items intersect that point.
T	queryOne(BoundedObject.BoundedCube box)	Returns one item that intersects the query box, or null if nothing intersects the query box.
boolean	remove(T o)	Removes the specified object if it is in the tree.

Methods inherited from class java.lang.Object

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

Constructor Detail

RTree

public RTree()

Default constructor.

RTree

public RTree(int minChildren,
             int maxChildren)

Creates an R-Tree. Sets the splitting algorithm to quadratic splitting.

Parameters:

minChildren - Minimum children in a node. 2 <= minChildren <= maxChildren/2

maxChildren - Maximum children in a node. Node splits at this number + 1

Method Detail

clear

public void clear()

query

public void query(java.util.Collection<T> results)

Adds items whose AABB intersects the query AABB to results

Parameters:

results - A collection to store the query results

query

public void query(java.util.Collection<T> results,
                  BoundedObject.BoundedCube box)

queryOne

public T queryOne(BoundedObject.BoundedCube box)

Returns one item that intersects the query box, or null if nothing intersects the query box.

Parameters:

box - the area to look up

Returns:

the first thing in that area

query

public void query(java.util.Collection<T> results,
                  long px,
                  long py,
                  long pz)

Returns items whose Rect contains the specified point.

Parameters:

results - A collection to store the query results.

px - Point X coordinate

py - Point Y coordinate

pz - Point Z coordinate

queryOne

public T queryOne(long px,
                  long py,
                  long pz)

Returns one item that intersects the query point, or null if no items intersect that point.

Parameters:

px - Point X coordinate

py - Point Y coordinate

pz - Point Z coordinate

Returns:

the first object in that area

remove

public boolean remove(T o)

Removes the specified object if it is in the tree.

Parameters:

o - the object to remove

Returns:

true if it was there to remove, false otherwise

insert

public void insert(T o)

Inserts object o into the tree. Note that if the value of o.getBounds() changes while in the R-tree, the result is undefined.

Parameters:

o - the object to insert into the tree

Throws:

java.lang.NullPointerException - If o == null

contains

public boolean contains(T o)

Returns whether the given object is in the tree

Parameters:

o - the object to look for

Returns:

true if it is in there, false otherwise

objects

public java.util.Enumeration<T> objects()

objectEntries

public java.util.Enumeration<java.util.Map.Entry<T,java.util.List<java.lang.ref.WeakReference<TrackingVector<T>>>>> objectEntries()

leafSearch

public boolean leafSearch(T o)

count

public int count()

Counts the number of items in the tree.

Returns:

the number of items