com.bbn.openmap.util.quadtree
Class QuadTree

java.lang.Object
  extended by com.bbn.openmap.util.quadtree.QuadTree
All Implemented Interfaces:
DataOrganizer, java.io.Serializable

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

The QuadTree lets you organize objects in a grid, that redefines itself and focuses more gridding when more objects appear in a certain area.

See Also:
Serialized Form

Field Summary
protected  QuadTreeNode top
           
 
Constructor Summary
QuadTree()
           
QuadTree(float north, float west, float south, float east, int maxItems)
           
QuadTree(float north, float west, float south, float east, int maxItems, float minSize)
           
QuadTree(int up, int left, int down, int right, int maxItems)
           
 
Method Summary
 void clear()
          Clear the tree.
 java.lang.Object get(float lat, float lon)
          Get an object closest to a lat/lon.
 java.lang.Object get(float lat, float lon, double withinDistance)
          Get an object closest to a lat/lon, within a maximum distance.
 java.util.Vector get(float north, float west, float south, float east)
          Get all the objects within a bounding box.
 java.util.Vector get(float north, float west, float south, float east, java.util.Vector vector)
          Get all the objects within a bounding box, and return the objects within a given Vector.
 boolean put(float lat, float lon, java.lang.Object obj)
          Add a object into the tree at a location.
 java.lang.Object remove(float lat, float lon, java.lang.Object 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 top
Constructor Detail

QuadTree

public QuadTree()

QuadTree

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

QuadTree

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

QuadTree

public QuadTree(float north,
                float west,
                float south,
                float east,
                int maxItems,
                float minSize)
Method Detail

put

public boolean put(float lat,
                   float lon,
                   java.lang.Object obj)
Add a object into the tree at a location.

Specified by:
put in interface DataOrganizer
Parameters:
lat - up-down location in QuadTree Grid (latitude, y)
lon - left-right location in QuadTree Grid (longitude, x)
Returns:
true if the insertion worked.

remove

public java.lang.Object remove(float lat,
                               float lon,
                               java.lang.Object obj)
Remove a object out of the tree at a location.

Specified by:
remove in interface DataOrganizer
Parameters:
lat - up-down location in QuadTree Grid (latitude, y)
lon - left-right location in QuadTree Grid (longitude, x)
Returns:
the object removed, null if the object not found.

clear

public void clear()
Clear the tree.

Specified by:
clear in interface DataOrganizer

get

public java.lang.Object get(float lat,
                            float lon)
Get an object closest to a lat/lon.

Specified by:
get in interface DataOrganizer
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 java.lang.Object get(float lat,
                            float lon,
                            double withinDistance)
Get an object closest to a lat/lon, within a maximum distance.

Specified by:
get in interface DataOrganizer
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.Vector get(float north,
                            float west,
                            float south,
                            float east)
Get all the objects within a bounding box.

Specified by:
get in interface DataOrganizer
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.Vector get(float north,
                            float west,
                            float south,
                            float east,
                            java.util.Vector vector)
Get all the objects within a bounding box, and return the objects within a given Vector.

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)
vector - a vector to add objects to.
Returns:
Vector of objects.


Copyright (C) BBNT Solutions LLC; See http://openmap.bbn.com/ for details