BoxSearch Class Reference

#include <BoxSearch.hpp>

Public Member Functions
	BoxSearch ()
double	avgEntitiesPerBlock () const
EntityGeneratorForPosition	entitiesFor (Vec bfr) const
EntityGeneratorForRay	entitiesFor (Vec bfr, Vec bfk) const
const Box &	extent () const
void	loadEntities (int numEntities, std::function< Box(int m)> bounds, std::function< bool(int m, const Box &box)> intersects)
int	maxEntitiesPerBlock () const
int	minEntitiesPerBlock () const
int	numBlocks () const

Private Types
using	EntityGeneratorForPosition = const vector< int > &
using	EntityGeneratorForRay = std::unordered_set< int >

Private Member Functions
int	blockIndex (int i, int j, int k) const
int	blockIndex (Vec bfr) const

Private Attributes
double	_avgEntitiesPerBlock
vector< int >	_empty
Box	_extent
vector< vector< int > >	_listv
int	_maxEntitiesPerBlock
int	_minEntitiesPerBlock
int	_numBlocks
Array	_xgrid
Array	_ygrid
Array	_zgrid

Detailed Description

BoxSearch is a utility class for organizing spatial objects in a data structure that allows efficient retrieval of all objects that overlap a given point or ray. The class actually works with the bounding boxes of the objects being held, and leaves more detailed tests for containment or intersection to the client code.

The spatial objects held by a BoxSearch instance are called entities. They are identified by a unique index $m$ ranging from 0 to $M-1$, where $M$ is the number of managed entities. All entities are handed to the BoxSearch instance in one go, so that they can be "bulk-loaded" into the search structure.

The current implementation proceeds as follows. First, a regular Cartesian grid is contructed that partitions 3D space into $N_b^3$ blocks, where $N_b$ depends on the number of entities. Each block is then assigned a list of indices for all entities that possibly intersect with the block. In an attempt to balance the list lengths, the block separation points in each coordinate direction are chosen so that the entity bounding box centers are approximately evently distributed over the blocks in that direction. Locating the block containing a given query position then boils down to three binary searches (one in each direction).

Member Typedef Documentation

EntityGeneratorForPosition

using BoxSearch::EntityGeneratorForPosition = const vector<int>&

private

This typedef defines the generator return type of the entitiesFor function for a position. It represents an iterable sequence of integers. We use a private typedef to hide the actual type, which in the current implementation is simply a reference to a standard vector.

EntityGeneratorForRay

using BoxSearch::EntityGeneratorForRay = std::unordered_set<int>

private

This typedef defines the generator return type of the entitiesFor function for a ray. It represents an iterable sequence of integers. We use a private typedef to hide the actual type, which in the current implementation is simply a copy of a standard unordered set.

Constructor & Destructor Documentation

BoxSearch()

BoxSearch::BoxSearch

(

)

The constructor creates a trivial BoxSearch instance holding no entities. Any queries will come up empty.

Member Function Documentation

avgEntitiesPerBlock()

double BoxSearch::avgEntitiesPerBlock

(

)

const

This function returns the average number of entity references in a search block.

blockIndex() [1/2]

int BoxSearch::blockIndex ( int  i, int  j, int  k  ) const

private

This function returns the linear index in the block list vector for the block with indices (i,j,k) in the three spatial directions.

blockIndex() [2/2]

int BoxSearch::blockIndex ( Vec  bfr ) const

private

This function returns the linear index in the block list vector for the block containing the given position.

entitiesFor() [1/2]

EntityGeneratorForPosition BoxSearch::entitiesFor

(

Vec

bfr

)

const

This function returns an iterable sequence of indices $m$ of all entities that may overlap the specified position, sorted in increasing order. The sequence may be empty.

The function guarantees that the sequence includes all entities whose bounding box overlaps the position. On the other hand, the sequence may contain entities whose bounding box does not overlap the position.

entitiesFor() [2/2]

EntityGeneratorForRay BoxSearch::entitiesFor	(	Vec	bfr,
		Vec	bfk
	)		const

This function returns an iterable sequence of indices $m$ of all entities that may overlap the specified ray (starting point and direction), in arbitrary order. The sequence may be empty.

The function guarantees that the sequence includes all entities whose bounding box overlaps the ray. On the other hand, the sequence may contain entities whose bounding box does not overlap the ray.

extent()

const Box & BoxSearch::extent

(

)

const

This function returns the extent of the search domain, i.e. the union of all entity bounding boxes.

loadEntities()

void BoxSearch::loadEntities	(	int	numEntities,
		std::function< Box(int m)>	bounds,
		std::function< bool(int m, const Box &box)>	intersects
	)

This function loads the specified number of entities $M$ into the search structure, using the information returned by the provided callback functions. Any entities held prevously are removed and replaced by the new ones.

The bounds callback function returns the bounding box of the entity with the given index. The intersects callback function returns true if the entity with the given index possibly intersects the specified box, and false otherwise. A relaxed intersection test such as testing against the bounding box is allowed but a stricter intersection test will result in more efficient retrieval queries.

The callback functions are invoked one or more times for indices $m$ ranging from 0 to $M-1$, in arbitrary order. For given values of their argument(s), the callback functions must always return the same value.

maxEntitiesPerBlock()

int BoxSearch::maxEntitiesPerBlock

(

)

const

This function returns the largest number of entity references in a search block.

minEntitiesPerBlock()

int BoxSearch::minEntitiesPerBlock

(

)

const

This function returns the smallest number of entity references in a search block.

numBlocks()

int BoxSearch::numBlocks

(

)

const

This function returns the number of blocks in the search structure for each spatial dimension, or zero if no entities have been loaded.

---

The documentation for this class was generated from the following file:

• BoxSearch.hpp