16 #ifndef SURGSIM_DATASTRUCTURES_GRID_INL_H 17 #define SURGSIM_DATASTRUCTURES_GRID_INL_H 19 #include <boost/functional/hash.hpp> 23 namespace DataStructures
45 template <
typename T,
size_t B,
size_t N>
49 static_assert(B > 1 && B < 10,
"B (the base) needs to be within [2..9]");
58 size_t toDecimal()
const 61 size_t BexponentDigit = 1;
62 for (
size_t digit = 0; digit < N; ++digit)
64 value += (*this)[digit] * BexponentDigit;
78 if ((*
this)[digit] == B)
96 template <
typename T,
size_t N>
99 return boost::hash_range(nd.data(), nd.data() + N);
102 template <
typename T,
size_t N>
103 Grid<T, N>::Grid(
const Eigen::Matrix<double, N, 1>& cellSize,
const Eigen::AlignedBox<double, N>& bounds)
106 m_neighborsDirtyFlag(false)
108 static_assert(N >= 1,
"A grid must have a positive non null dimension");
111 template <
typename T,
size_t N>
116 template <
typename T,
size_t N>
129 template <
typename T,
size_t N>
130 template <
class Derived>
134 if (!
m_aabb.contains(position))
143 NDId cellId = ((position -
m_aabb.min()).cwiseQuotient(
m_size)).
template cast<int>();
155 template <
typename T,
size_t N>
158 std::array<NDId, powerOf3<N>::value> cellsIds;
163 cell.second.neighbors.clear();
171 for (
size_t index = 0; index < powerOf3<N>::value; ++index)
176 auto neighborCell = m_activeCells.find(cellsIds[index]);
177 if (neighborCell != m_activeCells.end())
179 cell.second.neighbors.insert(cell.second.neighbors.end(),
180 neighborCell->second.elements.cbegin(),
181 neighborCell->second.elements.cend());
184 if (cellsIds[index] != cell.first)
186 neighborCell->second.neighbors.insert(neighborCell->second.neighbors.end(),
187 cell.second.elements.cbegin(),
188 cell.second.elements.cend());
197 template <
typename T,
size_t N>
200 static std::vector<T> empty;
207 auto const foundCell =
m_cellIds.find(element);
216 template <
typename T,
size_t N>
217 template <
class Derived>
220 static const std::vector<T> empty;
223 if (
m_aabb.contains(position))
230 NDId cellId = ((position -
m_aabb.min()).cwiseQuotient(
m_size)).
template cast<int>();
236 std::array<NDId, powerOf3<N>::value> cellsIds;
238 std::vector<T> neighbors;
239 for (
const auto& neighborId : cellsIds)
244 neighbors.insert(neighbors.end(),
245 neighborCell->second.elements.cbegin(),
246 neighborCell->second.elements.cend());
256 template <
typename T,
size_t N>
270 cellId -= NDId::Ones();
272 Number<int, 3, N> currentNumberNDigitBase3;
273 for (
size_t i = 0; i < powerOf3<N>::value; ++i)
275 (*cellsIds)[i] = cellId + currentNumberNDigitBase3;
276 currentNumberNDigitBase3.next();
280 template <
typename T,
size_t N>
283 for (
size_t i = 0; i < N; ++i)
301 #endif // SURGSIM_DATASTRUCTURES_GRID_INL_H Definition: CompoundShapeToGraphics.cpp:29
const std::vector< T > & getNeighbors(const T &element)
Retrieve an elements' neighbors.
Definition: Grid-inl.h:198
Eigen::Matrix< double, Eigen::Dynamic, Eigen::Dynamic > Matrix
A dynamic size matrix.
Definition: Matrix.h:65
Templated function to compute a power of 3 at compile time (useful for template parameter) ...
Definition: Grid.h:32
Eigen::AlignedBox< double, N > m_aabb
Grid min and max.
Definition: Grid.h:107
void getNeighborsCellIds(NDId cellId, std::array< NDId, powerOf3< N >::value > *cellsIds)
Retrieve the neighboring cells id (including this cell)
Definition: Grid-inl.h:257
Eigen::Matrix< double, N, 1 > m_size
Size of each cell (same on all dimension)
Definition: Grid.h:104
virtual ~Grid()
Destructor.
Definition: Grid-inl.h:112
size_t operator()(const NDId &nd) const
Definition: Grid-inl.h:97
bool m_neighborsDirtyFlag
Does the neighbors needs to be recomputed ?
Definition: Grid.h:110
Data structure for a cell's content (the list of elements and the list of all the neighbors) ...
Definition: Grid.h:81
Enable the NDId to be used as a key in an unordered map.
Definition: Grid.h:91
std::unordered_map< T, NDId > m_cellIds
Mapping from element to cell id containing the element.
Definition: Grid.h:101
Grid(const Eigen::Matrix< double, N, 1 > &cellSize, const Eigen::AlignedBox< double, N > &bounds)
Constructor.
Definition: Grid-inl.h:103
void reset()
Reset the grid content and the neighbors' mapping.
Definition: Grid-inl.h:117
Eigen::Matrix< int, N, 1 > NDId
The type of the n-dimensional cell Id.
Definition: Grid.h:88
bool isNdGreaterOrEqual(const NDId &a, const NDId &b)
Definition: Grid-inl.h:281
void update()
Update the neighbors lists.
Definition: Grid-inl.h:156
void addElement(const T element, const Eigen::MatrixBase< Derived > &position)
Add an element in the grid.
Definition: Grid-inl.h:131
std::unordered_map< NDId, CellContent, NDIdHash > m_activeCells
Active cells (referenced by their ids (spatial hashing)) with their content.
Definition: Grid.h:98