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

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

All Implemented Interfaces:

java.io.Serializable

public class QuadTreeNode<T>
extends java.lang.Object
implements java.io.Serializable

The QuadTreeNode is the part of the QuadTree that either holds children nodes, or objects as leaves. Currently, the nodes that have children do not hold items that span across children boundaries, since this was designed to handle point data.

See Also:

Serialized Form

Field Summary

protected boolean	allTheSamePoint Added to avoid problems when a node is completely filled with a single point value.
QuadTreeRect	bounds
protected java.util.Collection<QuadTreeNode<T>>	children
static float	DEFAULT_MIN_SIZE
protected double	firstLat
protected double	firstLon
protected java.util.Collection<QuadTreeLeaf<T>>	items
protected int	maxItems
protected double	minSize
static float	NO_MIN_SIZE

Constructor Summary

QuadTreeNode(double north, double west, double south, double east, int maximumItems)
Constructor to use if you are going to store the objects in lat/lon space, and there is really no smallest node size.

QuadTreeNode(double north, double west, double south, double east, int maximumItems, double minimumSize)
Constructor to use if you are going to store the objects in x/y space, and there is a smallest node size because you don't want the nodes to be smaller than a group of pixels.

Method Summary

void	clear() Clear the tree below this node.
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.
java.util.Collection<T>	get(double north, double west, double south, double east) Get all the objects within a bounding box.
java.util.Collection<T>	get(double north, double west, double south, double east, java.util.Collection<T> collection) Get all the objects within a bounding box.
T	get(double lat, double lon, MutableDistance bestDistance) Get an object closest to a lat/lon.
java.util.Collection<T>	get(QuadTreeRect rect, java.util.Collection<T> collection) Get all the objects within a bounding box.
protected QuadTreeNode<T>	getChild(double lat, double lon) Get the node that covers a certain lat/lon pair.
boolean	hasChildren() Return true if the node has children.
boolean	put(double lat, double lon, T obj) Add a object into the tree at a location.
boolean	put(QuadTreeLeaf<T> leaf) Add a QuadTreeLeaf into the tree at a location.
T	remove(double lat, double lon, T obj) Remove a object out of the tree at a location.
T	remove(QuadTreeLeaf<T> leaf) Remove a QuadTreeLeaf out of the tree at a location.
protected void	split() This method splits the node into four children, and disperses the items into the children.

Methods inherited from class java.lang.Object

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

Field Detail

NO_MIN_SIZE

public static final float NO_MIN_SIZE

See Also:

Constant Field Values

DEFAULT_MIN_SIZE

public static final float DEFAULT_MIN_SIZE

See Also:

Constant Field Values

items

protected java.util.Collection<QuadTreeLeaf<T>> items

children

protected java.util.Collection<QuadTreeNode<T>> children

maxItems

protected int maxItems

minSize

protected double minSize

bounds

public QuadTreeRect bounds

allTheSamePoint

protected boolean allTheSamePoint

Added to avoid problems when a node is completely filled with a single point value.

firstLat

protected double firstLat

firstLon

protected double firstLon

Constructor Detail

QuadTreeNode

public QuadTreeNode(double north,
                    double west,
                    double south,
                    double east,
                    int maximumItems)

Constructor to use if you are going to store the objects in lat/lon space, and there is really no smallest node size.

Parameters:

north - northern border of node coverage.

west - western border of node coverage.

south - southern border of node coverage.

east - eastern border of node coverage.

maximumItems - number of items to hold in a node before splitting itself into four children and redispensing the items into them.

QuadTreeNode

public QuadTreeNode(double north,
                    double west,
                    double south,
                    double east,
                    int maximumItems,
                    double minimumSize)

Constructor to use if you are going to store the objects in x/y space, and there is a smallest node size because you don't want the nodes to be smaller than a group of pixels.

Parameters:

north - northern border of node coverage.

west - western border of node coverage.

south - southern border of node coverage.

east - eastern border of node coverage.

maximumItems - number of items to hold in a node before splitting itself into four children and redispensing the items into them.

minimumSize - the minimum difference between the boundaries of the node.

Method Detail

hasChildren

public boolean hasChildren()

Return true if the node has children.

split

protected void split()

This method splits the node into four children, and disperses the items into the children. The split only happens if the boundary size of the node is larger than the minimum size (if we care). The items in this node are cleared after they are put into the children.

getChild

protected QuadTreeNode<T> getChild(double lat,
                                   double lon)

Get the node that covers a certain lat/lon pair.

Parameters:

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

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

Returns:

node if child covers the point, null if the point is out of range.

put

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

Add a object into the tree at a location.

Parameters:

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

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

obj - object to add to the tree.

Returns:

true if the put worked.

put

public boolean put(QuadTreeLeaf<T> leaf)

Add a QuadTreeLeaf into the tree at a location.

Parameters:

leaf - object-location composite

Returns:

true if the pution worked.

remove

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

Remove a object out of the tree at a location.

Parameters:

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

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

obj - the object to be removed.

Returns:

the object removed, null if the object not found.

remove

public T remove(QuadTreeLeaf<T> leaf)

Remove a QuadTreeLeaf out of the tree at a location.

Parameters:

leaf - object-location composite

Returns:

the object removed, null if the object not found.

clear

public void clear()

Clear the tree below this node.

get

public T get(double lat,
             double lon)

Get an object closest to a lat/lon.

Parameters:

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

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

Returns:

the object that matches the best distance, null if no object was found.

get

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

Get an object closest to a lat/lon. If there are children at this node, then the children are searched. The children are checked first, to see if they are closer than the best distance already found. If a closer object is found, bestDistance will be updated with a new Double object that has the new distance.

Parameters:

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

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

withinDistance - maximum get distance.

Returns:

the object that matches the best distance, null if no closer object was found.

get

public T get(double lat,
             double lon,
             MutableDistance bestDistance)

Get an object closest to a lat/lon. If there are children at this node, then the children are searched. The children are checked first, to see if they are closer than the best distance already found. If a closer object is found, bestDistance will be updated with a new Double object that has the new distance.

Parameters:

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

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

bestDistance - the closest distance of the object found so far.

Returns:

the object that matches the best distance, null if no closer object was found.

get

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

Get all the objects within a bounding box.

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:

Collection of objects.

get

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

Get all the objects within a bounding box.

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 - current Collection of objects.

Returns:

collection of objects.

get

public java.util.Collection<T> get(QuadTreeRect rect,
                                   java.util.Collection<T> collection)

Get all the objects within a bounding box.

Parameters:

rect - boundary of area to fill.

collection - current Collection of objects.

Returns:

updated Collection of objects.