A container of points sorted in cells. More...

#include <SpacePartition.h>

Public Types
using	Coord_t = details::ExtractCoordType_t< Point_t >
	type of point coordinate More...

using	Range_t = CoordRangeCells< Coord_t >
	type of coordinate range More...

using	Indexer_t = typename Grid_t::Indexer_t
	type of index manager of the grid More...

using	CellIndexOffset_t = typename Indexer_t::CellIndexOffset_t
	type of difference between cell indices More...

using	CellIndex_t = typename Indexer_t::CellIndex_t

using	CellID_t = typename Indexer_t::CellID_t
	type of cell index More...

using	Cell_t = typename Grid_t::Cell_t
	type of cell More...

Public Member Functions
	SpacePartition (Range_t rangeX, Range_t rangeY, Range_t rangeZ)
	Constructs the partition in a given volume with the given cell size. More...

void	fill (PointIter begin, PointIter end)

CellIndexOffset_t	pointIndex (Point_t const &point) const

Indexer_t const &	indexManager () const
	Returns the index manager of the grid. More...

bool	has (CellIndexOffset_t ofs) const
	Returns whether there is a cell with the specified index (signed!) More...

Cell_t const &	operator[] (CellIndex_t index) const
	Returns the cell with the specified index. More...

Grid_t::const_iterator	begin () const
	Returns a constant iterator pointing to the first cell. More...

Grid_t::const_iterator	end () const
	Returns a constant iterator pointing after the last cell. More...

Protected Types
using	CellDimIndex_t = typename Grid_t::CellDimIndex_t

Protected Attributes
Coord_t	cellSize
	length of the side of each cubic cell More...

Range_t	xRange
	coordinates of the contained volume on x axis More...

Range_t	yRange
	coordinates of the contained volume on z axis More...

Range_t	zRange
	coordinates of the contained volume on z axis More...

Grid_t	data
	container of points More...

Private Types
using	Point_t = decltype(*(PointIter()))
	type of the point More...

using	Grid_t = ::util::GridContainer3D< PointIter >
	data container More...

Detailed Description

template<typename PointIter>
class lar::example::SpacePartition< PointIter >

A container of points sorted in cells.

Template Parameters

PointIter type of iterator to the point

This container arranges its elements into a 3D grid according to their position in space. The "position" is defined by the PositionExtractor class.

The container stores a bit on information for each cell (it is not sparse), therefore its size can become large very quickly. Currently each (empty) cell in the grid uses sizeof(std::vector<...>), that is 24, bytes.

Currently, no facility is provided to find an element, although from a copy of the element, its position in the container can be computed with pointIndex().

For example, suppose you need to arrange points in a box of 6 x 8 x 4 (arbitrary units) symmetric around the origin, each with 20 cells. This already makes a quite large container of 8000 elements.

std::vector<std::array<double, 3U>> data;
// fill the data points
lar::examples::SpacePartition<double const*> partition(
  { -3.0, 3.0, 0.3 },
  { -4.0, 4.0, 0.4 },
  { -2.0, 2.0, 0.2 }
  );
// populate the partition
for (auto const& point: data) partition.fill(point.data());
// find the cell for a reference point
const double refPoint[] = { 0.5, 0.5, 0.5 };
auto cellIndex = partition.pointIndex(refPoint);
// do something with all the points in the same cell as the reference one
for (double const* point: partition[cellIndex]) {
  // ...
}
// do something with all cells
for (auto const& cell: partition) {
  // and process all points in each cell
  for (double const* point: cell) {
    // ...
  }
}

Note that in the example the stored data is direct pointers to the data in order to save space (the data is 3 doubles big, that is 24 bytes, while a pointer is usually only 8 bytes). The class PositionExtractor is specialized for double const* in this same library.

Definition at line 222 of file SpacePartition.h.

Member Typedef Documentation

template<typename PointIter>

using lar::example::SpacePartition< PointIter >::Cell_t = typename Grid_t::Cell_t

type of cell

Definition at line 243 of file SpacePartition.h.

template<typename PointIter>

using lar::example::SpacePartition< PointIter >::CellDimIndex_t = typename Grid_t::CellDimIndex_t

protected

Definition at line 276 of file SpacePartition.h.

template<typename PointIter>

using lar::example::SpacePartition< PointIter >::CellID_t = typename Indexer_t::CellID_t

type of cell index

type of cell identifier

Definition at line 240 of file SpacePartition.h.

template<typename PointIter>

using lar::example::SpacePartition< PointIter >::CellIndex_t = typename Indexer_t::CellIndex_t

Definition at line 237 of file SpacePartition.h.

template<typename PointIter>

using lar::example::SpacePartition< PointIter >::CellIndexOffset_t = typename Indexer_t::CellIndexOffset_t

type of difference between cell indices

Definition at line 235 of file SpacePartition.h.

template<typename PointIter>

using lar::example::SpacePartition< PointIter >::Coord_t = details::ExtractCoordType_t<Point_t>

type of point coordinate

Definition at line 228 of file SpacePartition.h.

template<typename PointIter>

using lar::example::SpacePartition< PointIter >::Grid_t = ::util::GridContainer3D<PointIter>

private

data container

Definition at line 224 of file SpacePartition.h.

template<typename PointIter>

using lar::example::SpacePartition< PointIter >::Indexer_t = typename Grid_t::Indexer_t

type of index manager of the grid

Definition at line 232 of file SpacePartition.h.

template<typename PointIter>

using lar::example::SpacePartition< PointIter >::Point_t = decltype(*(PointIter()))

private

type of the point

Definition at line 223 of file SpacePartition.h.

template<typename PointIter>

using lar::example::SpacePartition< PointIter >::Range_t = CoordRangeCells<Coord_t>

type of coordinate range

Definition at line 229 of file SpacePartition.h.

Constructor & Destructor Documentation

template<typename PointIter >

lar::example::SpacePartition< PointIter >::SpacePartition	(	Range_t	rangeX,
		Range_t	rangeY,
		Range_t	rangeZ
	)

Constructs the partition in a given volume with the given cell size.

Definition at line 431 of file SpacePartition.h.

   : xRange(rangeX)
   , yRange(rangeY)
   , zRange(rangeZ)
   , data(details::diceVolume(xRange, yRange, zRange))
 {
   /*
     std::cout << "Grid: "
       << indexManager().sizeX() << " x "
       << indexManager().sizeY() << " x " << indexManager().sizeZ()
       << " (" << indexManager().size() << " cells)"
       << "\n  range X: " << xRange.lower << " -- " << xRange.upper << " [/" << xRange.cellSize << "]"
       << "\n  range Y: " << yRange.lower << " -- " << yRange.upper << " [/" << yRange.cellSize << "]"
       << "\n  range Z: " << zRange.lower << " -- " << zRange.upper << " [/" << zRange.cellSize << "]"
       << std::endl;
   */
 } // lar::example::SpacePartition<>::SpacePartition

Member Function Documentation

template<typename PointIter>

Grid_t::const_iterator lar::example::SpacePartition< PointIter >::begin ( ) const

Returns a constant iterator pointing to the first cell.

template<typename PointIter>

Grid_t::const_iterator lar::example::SpacePartition< PointIter >::end ( ) const

Returns a constant iterator pointing after the last cell.

template<typename PointIter >

void lar::example::SpacePartition< PointIter >::fill	(	PointIter	begin,
		PointIter	end
	)

Fills the partition with the points in the specified range

Exceptions

std::runtime_error a point is outside the covered volume

Definition at line 453 of file SpacePartition.h.

 {
 
   PointIter it = begin;
   while (it != end) {
     // if the point is outside the volume, pointIndex will throw an exception
     data.insert(pointIndex(*it), it);
     ++it;
   } // while
 
 } // lar::example::SpacePartition<>::fill()

template<typename PointIter>

bool lar::example::SpacePartition< PointIter >::has ( CellIndexOffset_t ofs ) const

inline

Returns whether there is a cell with the specified index (signed!)

Definition at line 262 of file SpacePartition.h.

263 { return data.has(ofs); }

util::details::GridContainerBase::has

bool has(CellIndexOffset_t index) const

Returns whether the specified index is valid.

Definition: GridContainers.h:87

lar::example::SpacePartition::data

Grid_t data

container of points

Definition: SpacePartition.h:284

template<typename PointIter>

Indexer_t const& lar::example::SpacePartition< PointIter >::indexManager ( ) const

inline

Returns the index manager of the grid.

Definition at line 258 of file SpacePartition.h.

259 { return data.indexManager(); }

util::details::GridContainerBase::indexManager

Indexer_t const & indexManager() const

Returns the index manager of the grid.

Definition: GridContainers.h:138

lar::example::SpacePartition::data

Grid_t data

container of points

Definition: SpacePartition.h:284

template<typename PointIter>

Cell_t const& lar::example::SpacePartition< PointIter >::operator[] ( CellIndex_t index ) const

inline

Returns the cell with the specified index.

Definition at line 266 of file SpacePartition.h.

267 { return data[index]; }

lar::example::SpacePartition::data

Grid_t data

container of points

Definition: SpacePartition.h:284

template<typename PointIter >

lar::example::SpacePartition< PointIter >::CellIndexOffset_t lar::example::SpacePartition< PointIter >::pointIndex ( Point_t const & point ) const

Returns the index pertaining the point (might be invalid!)

Exceptions

std::runtime_error point is outside the covered volume

Definition at line 469 of file SpacePartition.h.

 {
   // compute the cell ID coordinates
   Coord_t const x = details::extractPositionX(point);
   CellDimIndex_t const xc = xRange.findCell(x);
   if (!data.hasX(xc)) {
     throw std::runtime_error
       ("Point out of the volume (x = " + std::to_string(x) + ")");
   }
 
   Coord_t const y = details::extractPositionY(point);
   CellDimIndex_t const yc = yRange.findCell(y);
   if (!data.hasY(yc)) {
     throw std::runtime_error
       ("Point out of the volume (y = " + std::to_string(y) + ")");
   }
 
   Coord_t const z = details::extractPositionZ(point);
   CellDimIndex_t const zc = zRange.findCell(z);
   if (!data.hasZ(zc)) {
     throw std::runtime_error
       ("Point out of the volume (z = " + std::to_string(z) + ")");
   }
 
   // return its index
   return data.index(CellID_t{{ xc, yc, zc }});
 
 } // lar::example::SpacePartition<>::pointIndex()