gov.nasa.worldwind.util

Class BasicQuadTree<T>

java.lang.Object

gov.nasa.worldwind.util.BitSetQuadTreeFilter

gov.nasa.worldwind.util.BasicQuadTree<T>

All Implemented Interfaces:

java.lang.Iterable<T>

public class BasicQuadTree<T>
extends BitSetQuadTreeFilter
implements java.lang.Iterable<T>

Implements a quadtree backed by a bit-set index. A bit-set provides a minimal-memory index. Each bit identifies one cell in the quadtree.

This class provides methods to add and remove items from the quadtree, and to determine the items intersecting specified regions.

Items can be added with an associated name, and can be retrieved and removed by name.

Nested Class Summary

Nested classes/interfaces inherited from class gov.nasa.worldwind.util.BitSetQuadTreeFilter

BitSetQuadTreeFilter.FindIntersectingBitsOp

Field Summary

Fields

Modifier and Type	Field and Description
protected boolean	allowDuplicates
protected T	currentItem
protected java.lang.String	currentName
protected java.util.Map<java.lang.String,java.util.List<T>>	items
protected java.util.ArrayList<double[]>	levelZeroCells
protected java.util.HashMap<java.lang.String,T>	nameMap

Fields inherited from class gov.nasa.worldwind.util.BitSetQuadTreeFilter

bits, levelSizes, maxLevel, numLevels, path, powersOf4, stopped

Constructor Summary

Constructors

Constructor and Description
BasicQuadTree(int numLevels, Sector sector, java.util.Map<java.lang.String,java.util.List<T>> itemMap) Constructs a quadtree of a specified level and spanning a specified region.
BasicQuadTree(int numLevels, Sector sector, java.util.Map<java.lang.String,java.util.List<T>> itemMap, boolean allowDuplicates) Constructs a quadtree of a specified level and spanning a specified region.

Method Summary

Modifier and Type	Method and Description
void	add(T item, double[] itemCoords) Add an item to the quadtree.
void	add(T item, double[] itemCoords, java.lang.String itemName) Add a named item to the quadtree.
protected void	addItem(T item, double[] itemCoords, java.lang.String name)
protected java.util.Set<T>	buildItemSet(java.util.List<java.lang.Integer> bitIds, java.util.Set<T> outItems) Adds the items identified by a list of bit IDs to the set returned by the get methods.
void	clear() Removes all items from the tree.
boolean	contains(T item) Indicates whether an item is contained in the tree.
protected boolean	doOperation(int level, int position, double[] cellRegion, double[] itemCoords) Performs the add operation of the quadtree.
T	getByName(java.lang.String name) Returns a named item.
java.util.Set<T>	getItemsAtLocation(java.lang.Iterable<LatLon> locations, java.util.Set<T> outItems) Finds and returns the items within tree cells containing specified locations.
java.util.Set<T>	getItemsAtLocation(LatLon location, java.util.Set<T> outItems) Finds and returns the items within a tree cell containing a specified location.
java.util.Set<T>	getItemsInRegion(Sector testSector, java.util.Set<T> outItems) Finds and returns the items intersecting a specified sector.
java.util.Set<T>	getItemsInRegions(java.lang.Iterable<Sector> testSectors, java.util.Set<T> outItems) Finds and returns the items intersecting a specified collection of sectors.
java.util.Set<T>	getItemsInRegions(SectorGeometryList geometryList, java.util.Set<T> outItems) Finds and returns the items intersecting a specified collection of SectorGeometry.
boolean	hasItems() Indicates whether the tree contains any items.
java.util.Iterator<T>	iterator() Returns an iterator over the items in the tree.
protected void	makeLevelZeroCells(Sector sector) Creates the quadtree's level-zero cells.
void	remove(T item) Removes an item from the tree.
void	removeByName(java.lang.String name) Removes an item from the tree by name.

Methods inherited from class gov.nasa.worldwind.util.BitSetQuadTreeFilter

computeBitPosition, computeLevelSizes, getNumLevels, intersects, isStopped, start, stop, testAndDo

Methods inherited from class java.lang.Object

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

Methods inherited from interface java.lang.Iterable

forEach, spliterator

Field Detail

allowDuplicates

protected boolean allowDuplicates

currentItem

protected T currentItem

currentName

protected java.lang.String currentName

items

protected java.util.Map<java.lang.String,java.util.List<T>> items

levelZeroCells

protected java.util.ArrayList<double[]> levelZeroCells

nameMap

protected java.util.HashMap<java.lang.String,T> nameMap

Constructor Detail

BasicQuadTree

public BasicQuadTree(int numLevels,
                     Sector sector,
                     java.util.Map<java.lang.String,java.util.List<T>> itemMap)

Constructs a quadtree of a specified level and spanning a specified region.

The number of levels in the quadtree must be specified to the constructor. The more levels there are the more discriminating searches will be, but at the cost of some performance because more cells are searched. For the Earth, a level count of 8 provides leaf cells about 75 km along their meridian edges (edges of constant Earth, a level count of 8 provides leaf cells about 75 km along their meridian edges (edges of constant longitude). Additional levels successfully halve the distance, fewer levels double that distance.

Parameters:

numLevels - the number of levels in the quadtree. The more levels there are the more discriminating searches will be, but at the cost of some performance.

sector - the region the tree spans.

itemMap - a Map to hold the items added to the quadtree. May be null, in which case a new map is created.

Throws:

java.lang.IllegalArgumentException - if numLevels is less than 1.

BasicQuadTree

public BasicQuadTree(int numLevels,
                     Sector sector,
                     java.util.Map<java.lang.String,java.util.List<T>> itemMap,
                     boolean allowDuplicates)

Constructs a quadtree of a specified level and spanning a specified region.

The number of levels in the quadtree must be specified to the constructor. The more levels there are the more discriminating searches will be, but at the cost of some performance because more cells are searched. For the Earth, a level count of 8 provides leaf cells about 75 km along their meridian edges (edges of constant Earth, a level count of 8 provides leaf cells about 75 km along their meridian edges (edges of constant longitude). Additional levels successfully halve the distance, fewer levels double that distance.

Parameters:

numLevels - the number of levels in the quadtree. The more levels there are the more discriminating searches will be, but at the cost of some performance.

sector - the region the tree spans.

itemMap - a Map to hold the items added to the quadtree. May be null, in which case a new map is created.

allowDuplicates - Indicates whether the collection held by this quadtree may contain duplicate entries. Specifying true, which is the default, may cause an individual item to be associated with multiple quadtree regions if the item's coordinates fall on a region boundary. In this case that item will be returned multiple times from an iterator created by this class. Specifying false prevents this.

Throws:

java.lang.IllegalArgumentException - if numLevels is less than 1.

Method Detail

add

public void add(T item,
                double[] itemCoords)

Add an item to the quadtree. Any duplicates are duplicated in the tree.

Parameters:

item - the item to add.

itemCoords - an array specifying the region or location of the item. If the array's length is 2 it represents a location in [latitude, longitude]. If its length is 4 it represents a region, with the same layout as the nodeRegion argument.

Throws:

java.lang.IllegalArgumentException - if either item or itemCoords is null.

add

public void add(T item,
                double[] itemCoords,
                java.lang.String itemName)

Add a named item to the quadtree. Any item duplicates are duplicated in the tree. Any name duplicates replace the current name association; the name then refers to the item added.

Parameters:

item - the item to add.

itemCoords - an array specifying the region or location of the item. If the array's length is 2 it represents a location in [latitude, longitude]. If its length is 4 it represents a region, with the same layout as the nodeRegion argument.

itemName - the item name. If null, the item is added without a name.

Throws:

java.lang.IllegalArgumentException - if either item or itemCoords is null.

addItem

protected void addItem(T item,
                       double[] itemCoords,
                       java.lang.String name)

buildItemSet

protected java.util.Set<T> buildItemSet(java.util.List<java.lang.Integer> bitIds,
                                        java.util.Set<T> outItems)

Adds the items identified by a list of bit IDs to the set returned by the get methods.

Parameters:

bitIds - the bit numbers of the cells containing the items to return.

outItems - a Set in which to place the items. If null, a new set is created.

Returns:

the set of items. The value passed as the outItems is returned.

clear

public void clear()

Removes all items from the tree.

contains

public boolean contains(T item)

Indicates whether an item is contained in the tree.

Parameters:

item - the item to check. If null, false is returned.

Returns:

true if the item is in the tree, otherwise false.

doOperation

protected boolean doOperation(int level,
                              int position,
                              double[] cellRegion,
                              double[] itemCoords)

Performs the add operation of the quadtree.

Specified by:

doOperation in class BitSetQuadTreeFilter

Parameters:

level - the quadtree level currently being traversed.

position - the position of the cell in its parent cell, either 0, 1, 2, or 3. Cell positions starts with 0 at the southwest corner of the parent cell and increment counter-clockwise: cell 1 is SE, cell 2 is NE and cell 3 is NW.

cellRegion - an array specifying the coordinates of the cell's region. The first two entries are the minimum and maximum values on the Y axis (typically latitude). The last two entries are the minimum and maximum values on the X axis, (typically longitude).

itemCoords - an array specifying the region or location of the intersecting item. If the array's length is 2 it represents a location in [latitude, longitude]. If its length is 4 it represents a region, with the same layout as the nodeRegion argument.

Returns:

true if traversal should continue to the cell's descendants, false if traversal should not continue to the cell's descendants.

getByName

public T getByName(java.lang.String name)

Returns a named item.

Parameters:

name - the item name. If null, null is returned.

Returns:

the named item, or null if the item is not in the tree or the specified name is null.

getItemsAtLocation

public java.util.Set<T> getItemsAtLocation(java.lang.Iterable<LatLon> locations,
                                           java.util.Set<T> outItems)

Finds and returns the items within tree cells containing specified locations.

Parameters:

locations - the locations of interest.

outItems - a Set in which to place the items. If null, a new set is created.

Returns:

the set of intersecting items. The same set passed as the outItems argument is returned, or a new set if that argument is null.

Throws:

java.lang.IllegalArgumentException - if locations is null.

getItemsAtLocation

public java.util.Set<T> getItemsAtLocation(LatLon location,
                                           java.util.Set<T> outItems)

Finds and returns the items within a tree cell containing a specified location.

Parameters:

location - the location of interest.

outItems - a Set in which to place the items. If null, a new set is created.

Returns:

the set of intersecting items. The same set passed as the outItems argument is returned, or a new set if that argument is null.

Throws:

java.lang.IllegalArgumentException - if location is null.

getItemsInRegion

public java.util.Set<T> getItemsInRegion(Sector testSector,
                                         java.util.Set<T> outItems)

Finds and returns the items intersecting a specified sector.

Parameters:

testSector - the sector of interest.

outItems - a Set in which to place the items. If null, a new set is created.

Returns:

the set of intersecting items. The same set passed as the outItems argument is returned, or a new set if that argument is null.

Throws:

java.lang.IllegalArgumentException - if testSector is null.

getItemsInRegions

public java.util.Set<T> getItemsInRegions(java.lang.Iterable<Sector> testSectors,
                                          java.util.Set<T> outItems)

Finds and returns the items intersecting a specified collection of sectors.

Parameters:

testSectors - the sectors of interest.

outItems - a Set in which to place the items. If null, a new set is created.

Returns:

the set of intersecting items. The same set passed as the outItems argument is returned, or a new set if that argument is null.

Throws:

java.lang.IllegalArgumentException - if testSectors is null.

getItemsInRegions

public java.util.Set<T> getItemsInRegions(SectorGeometryList geometryList,
                                          java.util.Set<T> outItems)

Finds and returns the items intersecting a specified collection of SectorGeometry. This method is a convenience for finding the items intersecting the current visible regions.

Parameters:

geometryList - the list of sector geometry.

outItems - a Set in which to place the items. If null, a new set is created.

Returns:

the set of intersecting items. The same set passed as the outItems argument is returned, or a new set if that argument is null.

Throws:

java.lang.IllegalArgumentException - if geometryList is null.

hasItems

public boolean hasItems()

Indicates whether the tree contains any items.

Returns:

true if the tree contains items, otherwise false.

iterator

public java.util.Iterator<T> iterator()

Returns an iterator over the items in the tree. There is no specific iteration order and the iterator may return duplicate entries.

Note The Iterator.remove() operation is not supported.

Specified by:

iterator in interface java.lang.Iterable<T>

Returns:

an iterator over the items in the tree.

makeLevelZeroCells

protected void makeLevelZeroCells(Sector sector)

Creates the quadtree's level-zero cells.

Parameters:

sector - the sector to subdivide to create the cells.

remove

public void remove(T item)

Removes an item from the tree.

Note: For large collections, this can be an expensive operation.

Parameters:

item - the item to remove. If null, no item is removed.

removeByName

public void removeByName(java.lang.String name)

Removes an item from the tree by name.

Note: For large collections, this can be an expensive operation.

Parameters:

name - the name of the item to remove. If null, no item is removed.