gov.nasa.worldwind.util
Class BitSetQuadTreeFilter

java.lang.Object
  gov.nasa.worldwind.util.BitSetQuadTreeFilter

Direct Known Subclasses:

BasicQuadTree, BitSetQuadTreeFilter.FindIntersectingBitsOp

public abstract class BitSetQuadTreeFilter
extends 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

static class

BitSetQuadTreeFilter.FindIntersectingBitsOp A quadtree filter that determines the bit positions of cells associated with items and intersecting a specified region.

Field Summary

protected BitSet	bits
protected int[]	levelSizes
protected int	maxLevel
protected int	numLevels
protected int[]	path
protected int[]	powersOf4
protected boolean	stopped

Constructor Summary

BitSetQuadTreeFilter(int numLevels, BitSet bitSet)
Constructs an instance of this class.

Method Summary

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, finalize, getClass, hashCode, notify, notifyAll, toString, wait, wait, wait

Field Detail

bits

protected BitSet bits

levelSizes

protected int[] levelSizes

maxLevel

protected int maxLevel

numLevels

protected int numLevels

path

protected int[] path

powersOf4

protected int[] powersOf4

stopped

protected boolean stopped

Constructor Detail

BitSetQuadTreeFilter

public BitSetQuadTreeFilter(int numLevels,
                            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:

IllegalArgumentException - if numLevels is less than 1.

Method Detail

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.

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.

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.

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.

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().

stop

public void stop()

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

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.