Package gov.nasa.worldwind.util

Class BitSetQuadTreeFilter

  • Direct Known Subclasses:
    BasicQuadTree, BitSetQuadTreeFilter.FindIntersectingBitsOp
    public abstract class BitSetQuadTreeFilter
extends java.lang.Object
    This abstract class filters items through a quad tree to perform an operation on those items that intersect the tree's cells. For each submitted item, this class' doOperation(int, int, double[], double[]) method is called for each leaf or intermediate cell that intersects the item. That method typically stores the item's association with the intersecting cell, either to populate a quadtree membership list or to mark it as a visible item.

    The filter uses a bit-set to identify cells that intersect submitted items. This minimal memory eliminates the need to retain cell information other than identity. Only cell identities are retained by this abstract class. Subclasses provide the means to retain item information associated with intersecting cells.

    • Nested Class Summary

      Nested Classes 
      Modifier and Type Class Description
      static class  BitSetQuadTreeFilter.FindIntersectingBitsOp
      A quadtree filter that determines the bit positions of cells associated with items and intersecting a specified region.

    • Field Summary

      Fields 
      Modifier and Type Field Description
      protected java.util.BitSet bits  
      protected int[] levelSizes  
      protected int maxLevel  
      protected int numLevels  
      protected int[] path  
      protected int[] powersOf4  
      protected boolean stopped  

    • Constructor Summary

      Constructors 
      Constructor Description
      BitSetQuadTreeFilter​(int numLevels, java.util.BitSet bitSet)
      Constructs an instance of this class.

    • Method Summary

      All Methods Static Methods Instance Methods Abstract Methods Concrete Methods 
      Modifier and Type Method Description
      protected int computeBitPosition​(int level, int position)
      Computes the bit position of a quadtree cell.
      protected static int[] computeLevelSizes​(int numLevels)
      An internal method that computes the number of ancestor cells at each level.
      protected abstract boolean doOperation​(int level, int position, double[] cellRegion, double[] itemCoords)
      A method implemented by subclasses and called during tree traversal to perform an operation on an intersecting item.
      int getNumLevels()
      Returns the number of levels in the filter.
      protected int intersects​(double[] cellRegion, double[] itemCoords)
      Determines whether an item intersects a cell.
      boolean isStopped()
      Indicates whether traversal has been stopped.
      void start()
      Re-initialize for traversal.
      void stop()
      Stop the current traversal of the quadtree.
      protected void testAndDo​(int level, int position, double[] cellRegion, double[] itemCoords)
      The main, recursive traversal method.

      • Methods inherited from class java.lang.Object

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

    • Field Detail

      • bits

        protected java.util.BitSet bits

      • maxLevel

        protected int maxLevel

      • numLevels

        protected int numLevels

      • powersOf4

        protected int[] powersOf4

      • levelSizes

        protected int[] levelSizes

      • path

        protected int[] path

      • stopped

        protected boolean stopped

    • Constructor Detail

      • BitSetQuadTreeFilter

        public BitSetQuadTreeFilter​(int numLevels,
                            java.util.BitSet bitSet)
        Constructs an instance of this class.
        Parameters:
        numLevels - the number of levels in the quadtree.
        bitSet - a BitSet to use as the quadtree index. If null, a new set is created. Depending on the operation, the bit-set is modified or only read.
        Throws:
        java.lang.IllegalArgumentException - if numLevels is less than 1.

    • Method Detail

      • doOperation

        protected abstract boolean doOperation​(int level,
                                       int position,
                                       double[] cellRegion,
                                       double[] itemCoords)
        A method implemented by subclasses and called during tree traversal to perform an operation on an intersecting item. The method's implementation typically stores a reference to the intersecting item, or stores the cell's identity for later reference. See for example BasicQuadTree and BitSetQuadTreeFilter.FindIntersectingBitsOp.
        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.

      • getNumLevels

        public int getNumLevels()
        Returns the number of levels in the filter.
        Returns:
        the number of levels in the filter.

      • stop

        public void stop()
        Stop the current traversal of the quadtree. start() must be called before attempting a subsequent traversal.

      • isStopped

        public boolean isStopped()
        Indicates whether traversal has been stopped.
        Returns:
        true if traversal has been stopped, otherwise false.

      • start

        public void start()
        Re-initialize for traversal. Must be called to perform subsequent traversals after having called stop().

      • computeLevelSizes

        protected static int[] computeLevelSizes​(int numLevels)
        An internal method that computes the number of ancestor cells at each level. Level 0 has 0 ancestor cells, level 1 has 4, level 2 has 20 (16 + 4), etc.
        Parameters:
        numLevels - the number of quadtree levels.
        Returns:
        an array of numLevels + 1 elements containing the sums of ancestor-level cell counts for each quadtree level. The last element in the array contains the total number of cells in the tree.

      • testAndDo

        protected void testAndDo​(int level,
                         int position,
                         double[] cellRegion,
                         double[] itemCoords)
        The main, recursive traversal method. Called once for each cell. Tests for intersection between items and cells, subdivides cells and continues depth-first traversal on those descendants. Terminates traversal when the end of the tree is reached or when the subclass's doOperation(int, int, double[], double[]) method returns false.
        Parameters:
        level - the quadtree level currently being traversed.
        position - the position o f 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 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.

      • intersects

        protected int intersects​(double[] cellRegion,
                         double[] itemCoords)
        Determines whether an item intersects a cell.
        Parameters:
        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 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:
        non-zero if the item intersects the region. 0 if no intersection.

      • computeBitPosition

        protected int computeBitPosition​(int level,
                                 int position)
        Computes the bit position of a quadtree cell.
        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.
        Returns:
        the cell's bit position in the class' bit-list.