This class implements a spatial grid data structure using a 3 dimensional grid. More...

#include <SpatialGrid.h>

Classes
class	LineSegmentIterator

class	Triplet

Public Types
typedef std::list< const cObject * >	Voxel

typedef std::vector< Voxel >	Grid

Public Member Functions
bool	insertObject (const cObject *object, const Coord &pos, const Coord &boundingBoxSize)

bool	insertPoint (const cObject *point, const Coord &pos)

bool	removePoint (const cObject *point)

bool	movePoint (const cObject *point, const Coord &newPos)

void	clearGrid ()

void	rangeQuery (const Coord &pos, double range, const IVisitor *visitor) const

void	lineSegmentQuery (const LineSegment &lineSegment, const IVisitor *visitor) const

	SpatialGrid (const Coord &voxelSizes, const Coord &constraintAreaMin, const Coord &constraintAreaMax)

Protected Member Functions
Coord	computeConstraintAreaSideLengths () const

Triplet< int >	computeNumberOfVoxels () const

unsigned int	computeGridVectorLength () const

Triplet< int >	decodeRowMajorIndex (unsigned int ind) const

unsigned int	rowMajorIndex (const Triplet< int > &indices) const

unsigned int	coordToRowMajorIndex (const Coord &pos) const

Triplet< int >	coordToMatrixIndices (const Coord &pos) const

void	computeBoundingVoxels (const Coord &pos, const Triplet< double > &boundings, Triplet< int > &start, Triplet< int > &end) const

Protected Attributes
Grid	grid

unsigned int	gridVectorLength

Triplet< double >	voxelSizes

Coord	constraintAreaSideLengths

Coord	constraintAreaMin

Coord	constraintAreaMax

Triplet< int >	numVoxels

Detailed Description

This class implements a spatial grid data structure using a 3 dimensional grid.

It can also be used with zero-length {X, Y, Z} sides, and then it operates in 1 or 2 dimensional mode.

NOTE: With minimal effort, it can be extended to work in arbitrary dimension spaces.

Member Typedef Documentation

typedef std::vector<Voxel> inet::SpatialGrid::Grid

typedef std::list<const cObject *> inet::SpatialGrid::Voxel

Constructor & Destructor Documentation

inet::SpatialGrid::SpatialGrid	(	const Coord &	voxelSizes,
		const Coord &	constraintAreaMin,
		const Coord &	constraintAreaMax
	)

 {
     this->voxelSizes = Triplet<double>(voxelSizes.x, voxelSizes.y, voxelSizes.z);
     this->constraintAreaMin = constraintAreaMin;
     this->constraintAreaMax = constraintAreaMax;
     constraintAreaSideLengths = computeConstraintAreaSideLengths();
     numVoxels = computeNumberOfVoxels();
     gridVectorLength = computeGridVectorLength();
     if (gridVectorLength <= 0)
         throw cRuntimeError("Invalid gridVectorLength = %d", gridVectorLength);
     grid.resize(gridVectorLength);
 }

Member Function Documentation

void inet::SpatialGrid::clearGrid ( )

 {
     for (unsigned int i = 0; i < gridVectorLength; i++)
         grid[i].clear();
 }

void inet::SpatialGrid::computeBoundingVoxels	(	const Coord &	pos,
		const Triplet< double > &	boundings,
		Triplet< int > &	start,
		Triplet< int > &	end
	)		const

protected

Referenced by insertObject(), and rangeQuery().

 {
     int xVoxel = constraintAreaSideLengths.x == 0 ? 0 : ceil((boundings.x * numVoxels[0]) / constraintAreaSideLengths.x);
     int yVoxel = constraintAreaSideLengths.y == 0 ? 0 : ceil((boundings.y * numVoxels[1]) / constraintAreaSideLengths.y);
     int zVoxel = constraintAreaSideLengths.z == 0 ? 0 : ceil((boundings.z * numVoxels[2]) / constraintAreaSideLengths.z);
     Triplet<int> voxels(xVoxel, yVoxel, zVoxel);
     Triplet<int> matrixIndices = coordToMatrixIndices(pos);
     for (unsigned int i = 0; i < 3; i++)
     {
         start[i] = matrixIndices[i] - voxels[i] < 0 ? 0 : matrixIndices[i] - voxels[i];
         int endCell = matrixIndices[i] + voxels[i] >= numVoxels[i] ? numVoxels[i] - 1 : matrixIndices[i] + voxels[i];
         if (endCell < 0)
             end[i] = 0;
         else
             end[i] = endCell;
     }
 }

Coord inet::SpatialGrid::computeConstraintAreaSideLengths ( ) const

protected

Referenced by SpatialGrid().

 {
     return Coord(constraintAreaMax.x - constraintAreaMin.x, constraintAreaMax.y - constraintAreaMin.y,
             constraintAreaMax.z - constraintAreaMin.z);
 }

unsigned int inet::SpatialGrid::computeGridVectorLength ( ) const

protected

Referenced by SpatialGrid().

 {
     unsigned int gridVectorLength = 1;
     for (unsigned int i = 0; i < 3; i++)
         if (numVoxels[i] != 0)
             gridVectorLength *= numVoxels[i];
     return gridVectorLength;
 }

SpatialGrid::Triplet< int > inet::SpatialGrid::computeNumberOfVoxels ( ) const

protected

Referenced by SpatialGrid().

 {
     return Triplet<int>(
             constraintAreaSideLengths.x == 0 ? 0 : ceil(constraintAreaSideLengths.x / voxelSizes.x),
             constraintAreaSideLengths.y == 0 ? 0 : ceil(constraintAreaSideLengths.y / voxelSizes.y),
             constraintAreaSideLengths.z == 0 ? 0 : ceil(constraintAreaSideLengths.z / voxelSizes.z));
 }

SpatialGrid::Triplet< int > inet::SpatialGrid::coordToMatrixIndices ( const Coord & pos ) const

protected

Referenced by computeBoundingVoxels(), coordToRowMajorIndex(), and inet::SpatialGrid::LineSegmentIterator::LineSegmentIterator().

 {
     int xCoord = numVoxels[0] == 0 ? 0 : std::min((int)floor((pos.x - constraintAreaMin.x) / voxelSizes.x), numVoxels[0] - 1);
     int yCoord = numVoxels[1] == 0 ? 0 : std::min((int)floor((pos.y - constraintAreaMin.y) / voxelSizes.y), numVoxels[1] - 1);
     int zCoord = numVoxels[2] == 0 ? 0 : std::min((int)floor((pos.z - constraintAreaMin.z) / voxelSizes.z), numVoxels[2] - 1);
     return Triplet<int>(xCoord, yCoord, zCoord);
 }

unsigned int inet::SpatialGrid::coordToRowMajorIndex ( const Coord & pos ) const

protected

Referenced by insertPoint().

 {
     return rowMajorIndex(coordToMatrixIndices(pos));
 }

SpatialGrid::Triplet< int > inet::SpatialGrid::decodeRowMajorIndex ( unsigned int ind ) const

protected

 {
     Triplet<int> indices;
     for (unsigned int k = 0; k < 3; k++)
     {
         unsigned int prodDim = 1;
         for (unsigned int l = k + 1; l < 3; l++)
             if (numVoxels[l] > 0)
                 prodDim *= numVoxels[l];
         indices[k] = ind / prodDim;
         ind %= prodDim;
     }
     return indices;
 }

bool inet::SpatialGrid::insertObject	(	const cObject *	object,
		const Coord &	pos,
		const Coord &	boundingBoxSize
	)

Referenced by inet::physicalenvironment::GridObjectCache::insertObject().

 {
     Triplet<int> start, end;
     computeBoundingVoxels(pos, Triplet<double>(boundingBoxSize.x / 2, boundingBoxSize.y / 2, boundingBoxSize.z / 2), start, end);
     for (int i = start[0]; i <= end[0]; i++) {
         for (int j = start[1]; j <= end[1]; j++) {
             for (int k = start[2]; k <= end[2]; k++) {
                 int voxelIndex = rowMajorIndex(Triplet<int>(i,j,k));
                 Voxel& neighborVoxel = grid[voxelIndex];
                 neighborVoxel.push_back(check_and_cast<const cObject*>(object));
             }
         }
     }
     return true;
 }

bool inet::SpatialGrid::insertPoint	(	const cObject *	point,
		const Coord &	pos
	)

Referenced by inet::physicallayer::GridNeighborCache::addRadio(), and inet::physicallayer::GridNeighborCache::fillCubeVector().

 {
     unsigned int ind = coordToRowMajorIndex(pos);
     if (ind >= gridVectorLength)
     {
         throw cRuntimeError("Out of range with index: %d", ind);
         return false;
     }
     grid[ind].push_back(point);
     return true;
 }

void inet::SpatialGrid::lineSegmentQuery	(	const LineSegment &	lineSegment,
		const IVisitor *	visitor
	)		const

Referenced by inet::physicalenvironment::GridObjectCache::visitObjects().

 {
     std::map<const cObject *,bool> visited;
     for (LineSegmentIterator it(this, lineSegment, voxelSizes, numVoxels); !it.end(); ++it)
     {
         Triplet<int> ind = it.getMatrixIndices();
         unsigned int voxelIndex = rowMajorIndex(ind);
         if (voxelIndex >= gridVectorLength)
             throw cRuntimeError("Out of index, gridVectorLength = %d, voxelIndex = %d", gridVectorLength, voxelIndex);
         const Voxel& intersectedVoxel = grid[voxelIndex];
         for (const auto & elem : intersectedVoxel)
         {
             std::map<const cObject *, bool>::const_iterator objIter = visited.find(elem);
             if (objIter == visited.end() || !objIter->second)
                 visitor->visit(elem);
             visited.insert(std::pair<const cObject*,bool>(elem, true));
         }
     }
 }

bool inet::SpatialGrid::movePoint	(	const cObject *	point,
		const Coord &	newPos
	)

 {
     throw cRuntimeError("Unimplemented");
 }

void inet::SpatialGrid::rangeQuery	(	const Coord &	pos,
		double	range,
		const IVisitor *	visitor
	)		const

Referenced by inet::physicallayer::GridNeighborCache::sendToNeighbors().

 {
     Triplet<int> start, end;
     computeBoundingVoxels(pos, Triplet<double>(range, range, range), start, end);
     for (int i = start[0]; i <= end[0]; i++) {
         for (int j = start[1]; j <= end[1]; j++) {
             for (int k = start[2]; k <= end[2]; k++) {
                 int voxelIndex = rowMajorIndex(Triplet<int>(i,j,k));
                 const Voxel& neighborVoxel = grid[voxelIndex];
                 for (const auto & elem : neighborVoxel)
                     visitor->visit(elem);
             }
         }
     }
 }

bool inet::SpatialGrid::removePoint ( const cObject * point )

 {
     throw cRuntimeError("Unimplemented");
 }

unsigned int inet::SpatialGrid::rowMajorIndex ( const Triplet< int > & indices ) const

protected

Referenced by coordToRowMajorIndex(), insertObject(), lineSegmentQuery(), and rangeQuery().

 {
     int ind = 0;
     for (unsigned int k = 0; k < 3; k++)
     {
         unsigned int prodDim = 1;
         for (unsigned int l = k + 1; l < 3; l++)
             if (numVoxels[l] > 0)
                 prodDim *= numVoxels[l];
         ind += prodDim * indices[k];
     }
     return ind;
 }