inet::SpatialGrid Class Reference

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

Grid

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

Voxel

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

Constructor & Destructor Documentation

SpatialGrid()

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

clearGrid()

void inet::SpatialGrid::clearGrid

(

)

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

computeBoundingVoxels()

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

protected

{
    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;
    }
}

Referenced by insertObject(), and rangeQuery().

computeConstraintAreaSideLengths()

Coord inet::SpatialGrid::computeConstraintAreaSideLengths ( ) const

protected

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

Referenced by SpatialGrid().

computeGridVectorLength()

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

protected

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

Referenced by SpatialGrid().

computeNumberOfVoxels()

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

protected

{
    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));
}

Referenced by SpatialGrid().

coordToMatrixIndices()

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

protected

{
    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);
}

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

coordToRowMajorIndex()

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

protected

{
    return rowMajorIndex(coordToMatrixIndices(pos));
}

Referenced by insertPoint().

decodeRowMajorIndex()

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;
}

insertObject()

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

{
    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;
}

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

insertPoint()

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

{
    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;
}

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

lineSegmentQuery()

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

{
    std::set<const cObject *> 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) {
            if (!contains(visited, elem)) {
                visitor->visit(elem);
                visited.insert(elem);
            }
        }
    }
}

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

movePoint()

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

{
    throw cRuntimeError("Unimplemented");
}

rangeQuery()

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

{
    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);
            }
        }
    }
}

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

removePoint()

bool inet::SpatialGrid::removePoint

(

const cObject *

point

)

{
    throw cRuntimeError("Unimplemented");
}

rowMajorIndex()

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

protected

{
    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;
}

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

Member Data Documentation

constraintAreaMax

Coord inet::SpatialGrid::constraintAreaMax

protected

Referenced by computeConstraintAreaSideLengths(), and SpatialGrid().

constraintAreaMin

Coord inet::SpatialGrid::constraintAreaMin

protected

Referenced by computeConstraintAreaSideLengths(), coordToMatrixIndices(), inet::SpatialGrid::LineSegmentIterator::LineSegmentIterator(), and SpatialGrid().

constraintAreaSideLengths

Coord inet::SpatialGrid::constraintAreaSideLengths

protected

Referenced by computeBoundingVoxels(), computeNumberOfVoxels(), and SpatialGrid().

grid

Grid inet::SpatialGrid::grid

protected

Referenced by clearGrid(), insertObject(), insertPoint(), lineSegmentQuery(), rangeQuery(), and SpatialGrid().

gridVectorLength

unsigned int inet::SpatialGrid::gridVectorLength

protected

Referenced by clearGrid(), computeGridVectorLength(), insertPoint(), lineSegmentQuery(), and SpatialGrid().

numVoxels

Triplet<int> inet::SpatialGrid::numVoxels

protected

Referenced by computeBoundingVoxels(), computeGridVectorLength(), coordToMatrixIndices(), decodeRowMajorIndex(), lineSegmentQuery(), rowMajorIndex(), and SpatialGrid().

voxelSizes

Triplet<double> inet::SpatialGrid::voxelSizes

protected

Referenced by computeNumberOfVoxels(), coordToMatrixIndices(), inet::SpatialGrid::LineSegmentIterator::LineSegmentIterator(), lineSegmentQuery(), and SpatialGrid().

---

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

• SpatialGrid.h
• SpatialGrid.cc