public class BasicQuadTree<T> extends BitSetQuadTreeFilter implements java.lang.Iterable<T>
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.
BitSetQuadTreeFilter.FindIntersectingBitsOp
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 |
bits, levelSizes, maxLevel, numLevels, path, powersOf4, stopped
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.
|
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.
|
computeBitPosition, computeLevelSizes, getNumLevels, intersects, isStopped, start, stop, testAndDo
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
public BasicQuadTree(int numLevels, Sector sector, java.util.Map<java.lang.String,java.util.List<T>> itemMap)
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.
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.java.lang.IllegalArgumentException
- if numLevels
is less than 1.public BasicQuadTree(int numLevels, Sector sector, java.util.Map<java.lang.String,java.util.List<T>> itemMap, boolean allowDuplicates)
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.
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.java.lang.IllegalArgumentException
- if numLevels
is less than 1.public void add(T item, double[] itemCoords)
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.java.lang.IllegalArgumentException
- if either item
or itemCoords
is null.public void add(T item, double[] itemCoords, java.lang.String itemName)
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.java.lang.IllegalArgumentException
- if either item
or itemCoords
is null.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)
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.outItems
is returned.public void clear()
public boolean contains(T item)
item
- the item to check. If null, false is returned.protected boolean doOperation(int level, int position, double[] cellRegion, double[] itemCoords)
doOperation
in class BitSetQuadTreeFilter
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.public T getByName(java.lang.String name)
name
- the item name. If null, null is returned.public java.util.Set<T> getItemsAtLocation(java.lang.Iterable<LatLon> locations, java.util.Set<T> outItems)
locations
- the locations of interest.outItems
- a Set
in which to place the items. If null, a new set is created.outItems
argument is returned, or
a new set if that argument is null.java.lang.IllegalArgumentException
- if locations
is null.public java.util.Set<T> getItemsAtLocation(LatLon location, java.util.Set<T> outItems)
location
- the location of interest.outItems
- a Set
in which to place the items. If null, a new set is created.outItems
argument is returned, or
a new set if that argument is null.java.lang.IllegalArgumentException
- if location
is null.public java.util.Set<T> getItemsInRegion(Sector testSector, java.util.Set<T> outItems)
testSector
- the sector of interest.outItems
- a Set
in which to place the items. If null, a new set is created.outItems
argument is returned, or
a new set if that argument is null.java.lang.IllegalArgumentException
- if testSector
is null.public java.util.Set<T> getItemsInRegions(java.lang.Iterable<Sector> testSectors, java.util.Set<T> outItems)
testSectors
- the sectors of interest.outItems
- a Set
in which to place the items. If null, a new set is created.outItems
argument is returned, or
a new set if that argument is null.java.lang.IllegalArgumentException
- if testSectors
is null.public java.util.Set<T> getItemsInRegions(SectorGeometryList geometryList, java.util.Set<T> outItems)
SectorGeometry
.
This method is a convenience for finding the items intersecting the current visible regions.geometryList
- the list of sector geometry.outItems
- a Set
in which to place the items. If null, a new set is created.outItems
argument is returned, or
a new set if that argument is null.java.lang.IllegalArgumentException
- if geometryList
is null.public boolean hasItems()
public java.util.Iterator<T> iterator()
Note The Iterator.remove()
operation is not supported.
iterator
in interface java.lang.Iterable<T>
protected void makeLevelZeroCells(Sector sector)
sector
- the sector to subdivide to create the cells.public void remove(T item)
Note: For large collections, this can be an expensive operation.
item
- the item to remove. If null, no item is removed.public void removeByName(java.lang.String name)
Note: For large collections, this can be an expensive operation.
name
- the name of the item to remove. If null, no item is removed.