Package gov.nasa.worldwind.util

Class 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.

    • Constructor Summary

      Constructors 
      Constructor 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

      All Methods Instance Methods Concrete Methods 
      Modifier and Type Method 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​(LatLon location, java.util.Set<T> outItems)
      Finds and returns the items within a tree cell containing a specified location.
      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> getItemsInRegion​(Sector testSector, java.util.Set<T> outItems)
      Finds and returns the items intersecting a specified sector.
      java.util.Set<T> getItemsInRegions​(SectorGeometryList geometryList, java.util.Set<T> outItems)
      Finds and returns the items intersecting a specified collection of SectorGeometry.
      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.
      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 java.lang.Object

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

      • Methods inherited from interface java.lang.Iterable

        forEach, spliterator

    • Field Detail

      • levelZeroCells

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

      • items

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

      • currentItem

        protected T currentItem

      • currentName

        protected java.lang.String currentName

      • nameMap

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

      • allowDuplicates

        protected boolean allowDuplicates

    • 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

      • makeLevelZeroCells

        protected void makeLevelZeroCells​(Sector sector)
        Creates the quadtree's level-zero cells.
        Parameters:
        sector - the sector to subdivide to create the cells.

      • hasItems

        public boolean hasItems()
        Indicates whether the tree contains any items.
        Returns:
        true if the tree contains items, otherwise false.

      • 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.

      • 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.

      • 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.

      • addItem

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

      • 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.

      • clear

        public void clear()
        Removes all items from the tree.

      • 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.

      • 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.

      • 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.

      • 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.

      • 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.

      • 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.

      • 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.