com.bbn.openmap.util.quadtree
Class QuadTree<T>

java.lang.Object
  com.bbn.openmap.util.quadtree.QuadTree<T>

All Implemented Interfaces:

DataOrganizer<T>, java.io.Serializable

public class QuadTree<T>
extends java.lang.Object
implements DataOrganizer<T>, java.io.Serializable

The QuadTree lets you organize objects in a grid, that redefines itself and refines the gridding over locations where more objects are gathered.

See Also:

Serialized Form

Field Summary

protected QuadTreeNode<T>

top

Constructor Summary

QuadTree()

QuadTree(double north, double west, double south, double east, int maxItems)

QuadTree(double north, double west, double south, double east, int maxItems, double minSize)

QuadTree(int up, int left, int down, int right, int maxItems)

Method Summary

void	clear() Clear the tree.
T	get(double lat, double lon) Get an object closest to a lat/lon.
T	get(double lat, double lon, double withinDistance) Get an object closest to a lat/lon, within a maximum distance.
java.util.Collection	get(double north, double west, double south, double east) Get all the objects within a bounding box.
java.util.Collection	get(double north, double west, double south, double east, java.util.Collection collection) Get all the objects within a bounding box, and return the objects in the provided Collection.
boolean	put(double lat, double lon, T obj) Add a object into the tree at a location.
T	remove(double lat, double lon, T obj) Remove a object out of the tree at a location.

Methods inherited from class java.lang.Object

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

Field Detail

top

protected QuadTreeNode<T> top

Constructor Detail

QuadTree

public QuadTree()

QuadTree

public QuadTree(double north,
                double west,
                double south,
                double east,
                int maxItems)

QuadTree

public QuadTree(int up,
                int left,
                int down,
                int right,
                int maxItems)

QuadTree

public QuadTree(double north,
                double west,
                double south,
                double east,
                int maxItems,
                double minSize)

Method Detail

put

public boolean put(double lat,
                   double lon,
                   T obj)

Add a object into the tree at a location.

Specified by:

put in interface DataOrganizer<T>

Parameters:

lat - up-down location in QuadTree Grid (latitude, y)

lon - left-right location in QuadTree Grid (longitude, x)

obj - the object to insert into the tree

Returns:

true if the insertion worked.

remove

public T remove(double lat,
                double lon,
                T obj)

Remove a object out of the tree at a location.

Specified by:

remove in interface DataOrganizer<T>

Parameters:

lat - up-down location in QuadTree Grid (latitude, y)

lon - left-right location in QuadTree Grid (longitude, x)

obj - the object to remove

Returns:

the object removed, null if the object not found.

clear

public void clear()

Clear the tree.

Specified by:

clear in interface DataOrganizer<T>

get

public T get(double lat,
             double lon)

Get an object closest to a lat/lon.

Specified by:

get in interface DataOrganizer<T>

Parameters:

lat - up-down location in QuadTree Grid (latitude, y)

lon - left-right location in QuadTree Grid (longitude, x)

Returns:

the object that was found.

get

public T get(double lat,
             double lon,
             double withinDistance)

Get an object closest to a lat/lon, within a maximum distance.

Specified by:

get in interface DataOrganizer<T>

Parameters:

lat - up-down location in QuadTree Grid (latitude, y)

lon - left-right location in QuadTree Grid (longitude, x)

withinDistance - the maximum distance to get a hit, in decimal degrees.

Returns:

the object that was found, null if nothing is within the maximum distance.

get

public java.util.Collection get(double north,
                                double west,
                                double south,
                                double east)

Get all the objects within a bounding box.

Specified by:

get in interface DataOrganizer<T>

Parameters:

north - top location in QuadTree Grid (latitude, y)

west - left location in QuadTree Grid (longitude, x)

south - lower location in QuadTree Grid (latitude, y)

east - right location in QuadTree Grid (longitude, x)

Returns:

Vector of objects.

get

public java.util.Collection get(double north,
                                double west,
                                double south,
                                double east,
                                java.util.Collection collection)

Get all the objects within a bounding box, and return the objects in the provided Collection.

Parameters:

north - top location in QuadTree Grid (latitude, y)

west - left location in QuadTree Grid (longitude, x)

south - lower location in QuadTree Grid (latitude, y)

east - right location in QuadTree Grid (longitude, x)

collection - a Collection to add objects to.

Returns:

Collection of objects.