## com.bbn.openmap.util.quadtree
Class QuadTreeNode

    java.lang.Object
      com.bbn.openmap.util.quadtree.QuadTreeNode

All Implemented Interfaces:
  java.io.Serializable

public class QuadTreeNode
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 QuadTreeNode[]` `children`
`static float` `DEFAULT_MIN_SIZE`
`protected float` `firstLat`
`protected float` `firstLon`
`protected java.util.Vector` `items`
`protected int` `maxItems`
`protected float` `minSize`
`static float` `NO_MIN_SIZE`
`static int` `NORTHEAST`
`static int` `NORTHWEST`
`static int` `SOUTHEAST`
`static int` `SOUTHWEST`

Constructor Summary
`QuadTreeNode(float north, float west, float south, float 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(float north, float west, float south, float east, int maximumItems, float 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.
`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.
`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.
`java.lang.Object` `get(float lat, float lon, MutableDistance bestDistance)` Get an object closest to a lat/lon.
`java.util.Vector` `get(QuadTreeRect rect, java.util.Vector vector)` Get all the objects within a bounding box.
`protected QuadTreeNode` `getChild(float lat, float lon)` Get the node that covers a certain lat/lon pair.
`boolean` `hasChildren()` Return true if the node has children.
`boolean` `put(float lat, float lon, java.lang.Object obj)` Add a object into the tree at a location.
`boolean` `put(QuadTreeLeaf leaf)` Add a QuadTreeLeaf 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.
`java.lang.Object` `remove(QuadTreeLeaf 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

### NORTHWEST

    public static final int NORTHWEST

See Also:
  Constant Field Values

### NORTHEAST

    public static final int NORTHEAST

See Also:
  Constant Field Values

### SOUTHEAST

    public static final int SOUTHEAST

See Also:
  Constant Field Values

### SOUTHWEST

    public static final int SOUTHWEST

See Also:
  Constant Field Values

### 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.Vector items

### children

    protected QuadTreeNode[] children

### maxItems

    protected int maxItems

### minSize

    protected float 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 float firstLat

### firstLon

    protected float firstLon

Constructor Detail

### QuadTreeNode

    public QuadTreeNode(float north,
                        float west,
                        float south,
                        float 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(float north,
                        float west,
                        float south,
                        float east,
                        int maximumItems,
                        float 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 getChild(float lat,
                                    float 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(float lat,
                       float lon,
                       java.lang.Object 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 pution worked.

### put

    public boolean put(QuadTreeLeaf leaf)

  Add a QuadTreeLeaf into the tree at a location.

  Parameters:
    `leaf` - object-location composite
  Returns:
    true if the pution 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.

  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.

### remove

    public java.lang.Object remove(QuadTreeLeaf 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 java.lang.Object get(float lat,
                                float 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 java.lang.Object get(float lat,
                                float 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 java.lang.Object get(float lat,
                                float 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.Vector get(float north,
                                float west,
                                float south,
                                float 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:
    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.

  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` - current vector of objects.
  Returns:
    Vector of objects.

### get

    public java.util.Vector get(QuadTreeRect rect,
                                java.util.Vector vector)

  Get all the objects within a bounding box.

  Parameters:
    `rect` - boundary of area to fill.
    `vector` - current vector of objects.
  Returns:
    updated Vector of objects.

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