34 #include <boost/container/static_vector.hpp> 43 #ifndef DOXYGEN_SHOULD_SKIP_THIS 70 template<
typename T,
typename U =
float, std::
size_t Size = 16>
72 static_assert(Size > 0,
"Size can not be 0");
93 return m_root.insert(value, bounds);
105 return m_root.query(bounds, callback, kind);
124 : m_children(
nullptr)
126 m_entries.reserve(Size);
131 , m_children(
nullptr)
133 m_entries.reserve(Size);
136 bool isLeaf()
const {
137 return m_children ==
nullptr;
140 bool insert(
const T& value,
const Box<U, 2>& bounds) {
141 if (!m_bounds.contains(bounds)) {
146 if (m_entries.size() < Size) {
147 m_entries.push_back({ value, bounds });
154 if (m_entries.size() < Size) {
155 m_entries.push_back({ value, bounds });
160 for (std::size_t i = 0; i < 4; ++i) {
161 if (m_children[i].insert(value, bounds)) {
166 clearChildrenIfEmpty();
168 m_entries.push_back({ value, bounds });
173 if (!m_bounds.intersects(bounds)) {
177 std::size_t found = 0;
179 for (
auto& entry : m_entries) {
182 if (bounds.
contains(entry.bounds)) {
183 callback(entry.value);
190 callback(entry.value);
198 for (std::size_t i = 0; i < 4; ++i) {
199 found += m_children[i].query(bounds, callback, kind);
210 m_children =
nullptr;
215 m_children = std::make_unique<Node[]>(4);
222 std::vector<Entry> entries;
224 for (
auto& entry : m_entries) {
225 bool inserted =
false;
227 for (std::size_t i = 0; i < 4; ++i) {
228 if (m_children[i].insert(entry.value, entry.bounds)) {
235 entries.push_back(entry);
239 std::swap(m_entries, entries);
242 void clearChildrenIfEmpty() {
245 for (std::size_t i = 0; i < 4; ++i) {
246 if (!m_children[i].m_entries.empty()) {
251 m_children =
nullptr;
256 std::vector<Entry> m_entries;
257 std::unique_ptr<Node[]> m_children;
273 template<
typename T,
typename U =
float, std::
size_t N = 2, std::
size_t MaxSize = 16, std::
size_t MinSize = 4>
275 static_assert(
N > 0,
"N can not be 0");
276 static_assert(2 <= MinSize,
"MinSize must be at least 2");
277 static_assert(MinSize <= MaxSize / 2,
"MinSize must be less than MaxSize/2");
285 auto branch = std::make_unique<Branch>();
303 m_root = std::exchange(other.m_root,
nullptr);
310 std::swap(m_root, other.m_root);
329 Leaf *leaf = m_root->chooseSubtree(bounds);
331 Node *splitted = leaf->tryInsert(value, bounds);
332 Node *current = leaf;
334 while (splitted !=
nullptr) {
335 auto splittedBounds = splitted->computeBounds();
336 splitted->updateOriginalBounds(splittedBounds);
338 auto currentBounds = current->computeBounds();
339 current->updateOriginalBounds(currentBounds);
341 if (current == m_root) {
342 auto branch =
new Branch;
344 current->setParent(branch);
345 branch->tryInsert(current, currentBounds);
347 splitted->setParent(branch);
348 branch->tryInsert(splitted, splittedBounds);
350 branch->updateOriginalBounds(branch->computeBounds());
356 Branch *parent = current->getParent();
357 assert(parent !=
nullptr);
359 parent->updateBoundsForChild(currentBounds, current);
361 splitted->setParent(parent);
362 splitted = parent->tryInsert(splitted, splittedBounds);
368 while (current != m_root) {
369 auto currentBounds = current->computeBounds();
371 Branch *parent = current->getParent();
372 assert(parent !=
nullptr);
374 parent->updateBoundsForChild(currentBounds, current);
391 return m_root->query(bounds, callback, kind);
403 static constexpr std::size_t Size = MaxSize + 1;
424 Branch *getParent() noexcept {
428 void setParent(Branch *parent) {
432 bool hasOriginalBounds()
const {
433 return !m_orig.isEmpty();
436 U getOriginalCenterAxisValue(std::size_t axis)
const {
437 return (m_orig.min[axis] + m_orig.max[axis]) / 2;
440 void updateOriginalBounds(
Box<U, N> orig) {
444 virtual ~
Node() =
default;
446 virtual Leaf *chooseSubtree(
const Box<U, N>& bounds) = 0;
448 virtual Box<U, N> computeBounds()
const = 0;
471 struct LeafEntry : Entry {
475 class Leaf :
public Node {
477 using typename Node::SplitOrder;
481 std::size_t found = 0;
483 for (
auto& entry : m_entries) {
486 if (bounds.
contains(entry.bounds)) {
487 callback(entry.value);
494 callback(entry.value);
505 virtual Leaf *chooseSubtree(
const Box<U, N>& bounds)
override {
510 virtual Box<U,N> computeBounds()
const override {
511 assert(!m_entries.empty());
514 for (
auto& entry : m_entries) {
515 res.extend(entry.bounds);
521 Leaf *tryInsert(
const T& value,
const Box<U, N>& bounds) {
523 entry.bounds = bounds;
525 m_entries.push_back(std::move(entry));
527 if (m_entries.size() < Size) {
531 std::vector<Box<U, N>> boxes;
533 std::transform(m_entries.begin(), m_entries.end(), std::back_inserter(boxes), [](
const Entry& entry) {
539 switch (split.order) {
540 case SplitOrder::Min:
541 std::sort(m_entries.begin(), m_entries.end(), EntryMinAxisComparator<LeafEntry>(split.axis));
543 case SplitOrder::Max:
544 std::sort(m_entries.begin(), m_entries.end(), EntryMaxAxisComparator<LeafEntry>(split.axis));
548 auto leaf =
new Leaf;
550 auto splitIteratorBegin = std::next(m_entries.begin(), split.index + 1);
551 auto splitIteratorEnd = m_entries.end();
553 std::move(splitIteratorBegin, splitIteratorEnd, std::back_inserter(leaf->m_entries));
554 m_entries.erase(splitIteratorBegin, splitIteratorEnd);
562 std::tie(split.
axis, split.
order) = computeSplitAxis(boxes);
564 switch (split.
order) {
565 case SplitOrder::Min:
566 std::sort(boxes.begin(), boxes.end(), MinAxisComparator(split.
axis));
568 case SplitOrder::Max:
569 std::sort(boxes.begin(), boxes.end(), MaxAxisComparator(split.
axis));
573 split.
index = computeSplitIndex(boxes, split.
axis);
577 std::tuple<std::size_t, SplitOrder> computeSplitAxis(std::vector<
Box<U, N>>& boxes) {
578 std::size_t currentAxis = 0;
579 U currentValue = std::numeric_limits<U>::max();
580 SplitOrder currentOrder = SplitOrder::Min;
582 for (std::size_t axis = 0; axis <
N; ++axis) {
583 std::sort(boxes.begin(), boxes.end(), MinAxisComparator(axis));
585 U value = computeAxisValue(boxes);
587 if (value < currentValue) {
589 currentValue = value;
590 currentOrder = SplitOrder::Min;
593 std::sort(boxes.begin(), boxes.end(), MaxAxisComparator(axis));
595 value = computeAxisValue(boxes);
597 if (value < currentValue) {
599 currentValue = value;
600 currentOrder = SplitOrder::Max;
604 return std::make_tuple(currentAxis, currentOrder);
607 U computeAxisValue(
const std::vector<
Box<U, N>>& boxes) {
608 std::vector<Box<U, N>> firstBounds;
610 std::partial_sum(boxes.begin(), boxes.end(), std::back_inserter(firstBounds), [](
const Box<U, N>& lhs,
const Box<U, N>& rhs) {
614 std::vector<Box<U, N>> secondBounds;
616 std::partial_sum(boxes.rbegin(), boxes.rend(), std::back_inserter(secondBounds), [](
const Box<U, N>& lhs,
const Box<U, N>& rhs) {
622 for (std::size_t j = MinSize; j <= MaxSize - MinSize + 1; ++j) {
623 value += firstBounds[j].getExtentDistance() + secondBounds[Size - j].getExtentDistance();
629 std::size_t computeSplitIndex(
const std::vector<
Box<U, N>>& boxes, std::size_t axis) {
630 std::vector<Box<U, N>> firstBounds;
632 std::partial_sum(boxes.begin(), boxes.end(), std::back_inserter(firstBounds), [](
const Box<U, N>& lhs,
const Box<U, N>& rhs) {
636 std::vector<Box<U, N>> secondBounds;
638 std::partial_sum(boxes.rbegin(), boxes.rend(), std::back_inserter(secondBounds), [](
const Box<U, N>& lhs,
const Box<U, N>& rhs) {
645 const auto& bounds = firstBounds.back();
648 if (Node::hasOriginalBounds()) {
649 asym = 2.0f * ((bounds.max[axis] + bounds.min[axis]) / 2 - Node::getOriginalCenterAxisValue(axis)) / (bounds.max[axis] - bounds.min[axis]);
652 assert(-1.0f <= asym && asym <= 1.0f);
654 static constexpr
float S = 0.5f;
655 const float mu = (1 - 2.0f * MinSize / (MaxSize + 1)) * asym;
656 const float rho = S * (1 + std::abs(mu));
657 const float y1 = std::exp(- 1 / (S * S));
658 const float ys = 1 / (1 - y1);
660 auto wf = [mu,rho,y1,ys](std::size_t i) {
661 const float xi = 2.0f * i / (MaxSize + 1.0f) - 1.0f;
662 return ys * (std::exp(-
gf::square((xi - mu) / rho) - y1));
667 std::size_t currentIndex = 0;
668 U currentValue = std::numeric_limits<U>::max();
672 if (firstBounds[MinSize].getVolume() == 0 || secondBounds[MinSize].getVolume() == 0) {
680 bool overlapFree =
false;
682 U perimeterMax = 2 * bounds.getExtentDistance() - bounds.getMinimumEdge();
684 for (std::size_t index = MinSize; index <= MaxSize - MinSize + 1; ++index) {
685 auto weight = (firstBounds[index].*overlapFn)(secondBounds[Size - index - 1]);
691 auto value = weight * wf(index);
693 if (value < currentValue) {
694 currentValue = value;
695 currentIndex = index;
700 if (overlapFree && weight == 0) {
701 weight = firstBounds[index].getExtentDistance() + secondBounds[Size - index - 1].getExtentDistance() - perimeterMax;
709 auto value = weight / wf(index);
711 if (value < currentValue) {
712 currentValue = value;
713 currentIndex = index;
722 boost::container::static_vector<LeafEntry, Size> m_entries;
729 struct BranchEntry : Entry {
733 class Branch :
public Node {
735 using typename Node::SplitOrder;
739 for (
auto& entry : m_entries) {
745 std::size_t found = 0;
747 for (
auto& entry : m_entries) {
749 found += entry.child->query(bounds, callback, kind);
756 virtual Leaf *chooseSubtree(
const Box<U, N>& bounds)
override {
757 return chooseNode(bounds)->chooseSubtree(bounds);
761 Node *bestNodeForVolume =
nullptr;
762 U bestVolume = std::numeric_limits<U>::max();
764 Node *bestNodeForExtentDistance =
nullptr;
765 U bestExtentDistance = std::numeric_limits<U>::max();
767 for (
auto& entry : m_entries) {
768 if (entry.bounds.getIntersection(bounds) == bounds) {
769 U volume = entry.bounds.getVolume();
771 if (bestNodeForVolume ==
nullptr || volume < bestVolume) {
773 bestNodeForVolume = entry.child;
776 U extentDistance = entry.bounds.getExtentDistance();
778 if (bestNodeForExtentDistance ==
nullptr || extentDistance < bestExtentDistance) {
779 bestExtentDistance = extentDistance;
780 bestNodeForExtentDistance = entry.child;
785 if (bestNodeForVolume !=
nullptr) {
786 if (bestVolume > 0) {
787 return bestNodeForVolume;
790 assert(bestNodeForExtentDistance);
791 return bestNodeForExtentDistance;
798 Node *covering = searchForCoveringNode(bounds);
800 if (covering !=
nullptr) {
804 std::sort(m_entries.begin(), m_entries.end(), ExtentDistanceEnlargement(bounds));
806 OverlapExtentDistanceEnlargement extentDistanceEnlargement(bounds, m_entries.front());
810 for (p = m_entries.size() - 1; p > 0; --p) {
811 if (extentDistanceEnlargement(m_entries[p]) != 0) {
817 return m_entries[0].child;
820 std::vector<Candidate> candidates(p + 1, { 0,
false,
U() });
821 Node *node =
nullptr;
823 if (existsEmptyVolumeExtension(bounds)) {
824 node = findCandidates<OverlapExtentDistanceEnlargement>(0, p, bounds, candidates);
826 node = findCandidates<OverlapVolumeEnlargement>(0, p, bounds, candidates);
829 if (node !=
nullptr) {
833 candidates.erase(std::remove_if(candidates.begin(), candidates.end(), [](
const Candidate& candidate) {
834 return !candidate.isCandidate;
835 }), candidates.end());
837 assert(!candidates.empty());
839 auto it = std::min_element(candidates.begin(), candidates.end(), [](
const Candidate& lhs,
const Candidate& rhs) {
840 return lhs.overlap < rhs.overlap;
843 return m_entries[it->index].child;
846 virtual Box<U,N> computeBounds()
const override {
847 assert(!m_entries.empty());
850 for (
auto& entry : m_entries) {
851 res.extend(entry.bounds);
857 void updateBoundsForChild(
const Box<U, N>& bounds,
Node *child) {
858 for (
auto& entry : m_entries) {
859 if (entry.child == child) {
860 entry.bounds = bounds;
870 entry.bounds = bounds;
872 m_entries.push_back(std::move(entry));
874 if (m_entries.size() < Size) {
878 std::vector<Box<U, N>> boxes;
880 std::transform(m_entries.begin(), m_entries.end(), std::back_inserter(boxes), [](
const Entry& entry) {
886 switch (split.order) {
887 case SplitOrder::Min:
888 std::sort(m_entries.begin(), m_entries.end(), EntryMinAxisComparator<BranchEntry>(split.axis));
890 case SplitOrder::Max:
891 std::sort(m_entries.begin(), m_entries.end(), EntryMaxAxisComparator<BranchEntry>(split.axis));
895 auto branch =
new Branch;
897 auto splitIteratorBegin = std::next(m_entries.begin(), split.index + 1);
898 auto splitIteratorEnd = m_entries.end();
900 std::move(splitIteratorBegin, splitIteratorEnd, std::back_inserter(branch->m_entries));
901 m_entries.erase(splitIteratorBegin, splitIteratorEnd);
903 for (
auto& entry : branch->m_entries) {
904 entry.child->setParent(branch);
917 bool existsEmptyVolumeExtension(
const Box<U, N>& bounds) {
918 for (
auto& entry : m_entries) {
919 if (entry.bounds.getExtended(bounds).getVolume() == 0) {
927 template<
typename OverlapEnlargement>
928 Node *findCandidates(std::size_t t, std::size_t p,
const Box<U, N>& bounds, std::vector<Candidate>& candidates) {
929 candidates[t].index = t;
930 candidates[t].isCandidate =
true;
932 OverlapEnlargement enlargement(bounds, m_entries[t]);
936 for (std::size_t i = 0; i <= p; ++i) {
941 U localOverlap = enlargement(m_entries[i]);
942 overlap += localOverlap;
944 if (localOverlap == 0 && !candidates[i].isCandidate) {
945 Node *node = findCandidates<OverlapEnlargement>(i, p, bounds, candidates);
947 if (node !=
nullptr) {
954 return m_entries[t].child;
957 candidates[t].overlap = overlap;
962 bool overlapFree =
false;
963 U currentValue = std::numeric_limits<U>::max();
970 for (std::size_t axis = 0; axis <
N; ++axis) {
971 std::sort(boxes.begin(), boxes.end(), MinAxisComparator(axis));
972 computeBestSplitValue(boxes, result, status, axis, SplitOrder::Min);
974 std::sort(boxes.begin(), boxes.end(), MaxAxisComparator(axis));
975 computeBestSplitValue(boxes, result, status, axis, SplitOrder::Max);
981 void computeBestSplitValue(std::vector<
Box<U, N>>& boxes,
SplitResult& result, SplitStatus& status, std::size_t axis, SplitOrder order) {
982 std::vector<Box<U, N>> firstBounds;
984 std::partial_sum(boxes.begin(), boxes.end(), std::back_inserter(firstBounds), [](
const Box<U, N>& lhs,
const Box<U, N>& rhs) {
988 std::vector<Box<U, N>> secondBounds;
990 std::partial_sum(boxes.rbegin(), boxes.rend(), std::back_inserter(secondBounds), [](
const Box<U, N>& lhs,
const Box<U, N>& rhs) {
996 const auto& bounds = firstBounds.back();
999 if (Node::hasOriginalBounds()) {
1000 asym = 2.0f * ((bounds.max[axis] + bounds.min[axis]) / 2 - Node::getOriginalCenterAxisValue(axis)) / (bounds.max[axis] - bounds.min[axis]);
1003 assert(-1.0f <= asym && asym <= 1.0f);
1005 static constexpr
float S = 0.5f;
1006 const float mu = (1 - 2.0f * MinSize / (MaxSize + 1)) * asym;
1007 const float rho = S * (1 + std::abs(mu));
1008 const float y1 = std::exp(- 1 / (S * S));
1009 const float ys = 1 / (1 - y1);
1011 auto wf = [mu,rho,y1,ys](std::size_t i) {
1012 const float xi = 2.0f * i / (MaxSize + 1.0f) - 1.0f;
1013 return ys * (std::exp(-
gf::square((xi - mu) / rho) - y1));
1020 if (firstBounds[MinSize].getVolume() == 0 || secondBounds[MinSize].getVolume() == 0) {
1028 U perimeterMax = 2 * bounds.getExtentDistance() - bounds.getMinimumEdge();
1030 for (std::size_t index = MinSize; index <= MaxSize - MinSize + 1; ++index) {
1031 auto weight = (firstBounds[index].*overlapFn)(secondBounds[Size - index - 1]);
1033 if (!status.overlapFree) {
1035 status.overlapFree =
true;
1037 auto value = weight * wf(index);
1039 if (value < status.currentValue) {
1040 status.currentValue = value;
1041 result.
index = index;
1043 result.
order = order;
1048 if (status.overlapFree && weight == 0) {
1049 weight = firstBounds[index].getExtentDistance() + secondBounds[Size - index - 1].getExtentDistance() - perimeterMax;
1055 assert(weight <= 0);
1057 auto value = weight / wf(index);
1059 if (value < status.currentValue) {
1060 status.currentValue = value;
1061 result.
index = index;
1063 result.
order = order;
1070 boost::container::static_vector<BranchEntry, Size> m_entries;
1077 class ExtentDistanceEnlargement {
1079 ExtentDistanceEnlargement(
const Box<U, N>& bounds)
1085 bool operator()(
const Entry& lhs,
const Entry& rhs)
const {
1086 return getExtentDistanceEnlargement(lhs) < getExtentDistanceEnlargement(rhs);
1089 U getExtentDistanceEnlargement(
const Entry& entry)
const {
1090 return entry.bounds.getExtended(m_bounds).getExtentDistance() - entry.bounds.getExtentDistance();
1097 class OverlapExtentDistanceEnlargement {
1099 OverlapExtentDistanceEnlargement(
const Box<U, N>& bounds,
const Entry& reference)
1101 , m_reference(reference)
1102 , m_extended(reference.bounds.getExtended(bounds))
1107 U operator()(
const Entry& entry)
const {
1108 return getOverlapExtentDistanceEnlargement(entry);
1111 U getOverlapExtentDistanceEnlargement(
const Entry& entry)
const {
1112 return m_extended.getIntersectionExtentDistance(entry.bounds) - m_reference.bounds.getIntersectionExtentDistance(entry.bounds);
1117 const Entry& m_reference;
1122 class OverlapVolumeEnlargement {
1124 OverlapVolumeEnlargement(
const Box<U, N>& bounds,
const Entry& reference)
1126 , m_reference(reference)
1127 , m_extended(reference.bounds.getExtended(bounds))
1132 U operator()(
const Entry& entry)
const {
1133 return getOverlapVolumeEnlargement(entry);
1136 U getOverlapVolumeEnlargement(
const Entry& entry)
const {
1137 return m_extended.getIntersectionVolume(entry.bounds) - m_reference.bounds.getIntersectionVolume(entry.bounds);
1142 const Entry& m_reference;
1146 class MinAxisComparator {
1148 MinAxisComparator(std::size_t axis)
1155 return std::make_tuple(lhs.
min[m_axis], lhs.
max[m_axis]) < std::make_tuple(rhs.
min[m_axis], rhs.
max[m_axis]);
1162 template<
typename Entry>
1163 class EntryMinAxisComparator {
1165 EntryMinAxisComparator(std::size_t axis)
1171 bool operator()(
const Entry& lhs,
const Entry& rhs) {
1172 return std::make_tuple(lhs.bounds.min[m_axis], lhs.bounds.max[m_axis]) < std::make_tuple(rhs.bounds.min[m_axis], rhs.bounds.max[m_axis]);
1179 class MaxAxisComparator {
1181 MaxAxisComparator(std::size_t axis)
1188 return std::make_tuple(lhs.
max[m_axis], lhs.
min[m_axis]) < std::make_tuple(rhs.
max[m_axis], rhs.
min[m_axis]);
1195 template<
typename Entry>
1196 class EntryMaxAxisComparator {
1198 EntryMaxAxisComparator(std::size_t axis)
1204 bool operator()(
const Entry& lhs,
const Entry& rhs) {
1205 return std::make_tuple(lhs.bounds.max[m_axis], lhs.bounds.min[m_axis]) < std::make_tuple(rhs.bounds.max[m_axis], rhs.bounds.min[m_axis]);
1213 void updateBounds(
Node *node) {
1214 while (node !=
nullptr) {
1215 Box<U, N> bounds = node->computeBounds();
1217 Branch *parent = node->getParent();
1219 if (parent !=
nullptr) {
1220 parent->updateBoundsForChild(bounds, node);
1232 #ifndef DOXYGEN_SHOULD_SKIP_THIS 1237 #endif // GF_SPATIAL_H constexpr Box< T, N > getExtended(const Box< T, N > &other) const noexcept
Definition: Box.h:196
The tree is a node, generally an internal node of the tree.
constexpr bool intersects(const Box< T, N > &other) const noexcept
Definition: Box.h:118
void unused(Args &&...)
A simple way to avoid warnings about unused variables.
Definition: Unused.h:35
void clear()
Remove all the objects from the tree.
Definition: Spatial.h:111
std::size_t query(const Box< U, N > &bounds, SpatialQueryCallback< T > callback, SpatialQuery kind=SpatialQuery::Intersect) const
Query objects in the tree.
Definition: Spatial.h:390
std::function< void(const T &)> SpatialQueryCallback
A callback for spatial query.
Definition: Spatial.h:61
constexpr Vector2f transform(const Matrix3f &mat, Vector2f point)
Apply an affine transformation to a 2D point.
Definition: Transform.h:331
Vector< T, N > min
Definition: Box.h:49
Search for all objects that contain the given bounds.
~RStarTree()
Destructor.
Definition: Spatial.h:317
constexpr T square(T val)
Square function.
Definition: Math.h:275
std::size_t index
Definition: Spatial.h:457
std::size_t query(const Box< U, 2 > &bounds, SpatialQueryCallback< T > callback, SpatialQuery kind=SpatialQuery::Intersect) const
Query objects in the tree.
Definition: Spatial.h:104
Search for all objects that intersect the given bounds.
RStarTree & operator=(RStarTree &&other) noexcept
Move assignement.
Definition: Spatial.h:309
void clear()
Remove all the objects from the tree.
Definition: Spatial.h:397
The namespace for gf classes.
Definition: Action.h:34
QuadTree(const Box< U, 2 > &bounds)
Constructor.
Definition: Spatial.h:79
RStarTree()
Constructor.
Definition: Spatial.h:282
An implementation of quadtree.
Definition: Spatial.h:71
Vector< T, N > max
Definition: Box.h:50
Definition: Spatial.h:456
Box< T, 2 > computeBoxQuadrant(const Box< T, 2 > &box, Quadrant quadrant)
Definition: Box.h:263
RStarTree(RStarTree &&other) noexcept
Move constructor.
Definition: Spatial.h:301
static void debug(const char *fmt,...)
Print a debug message.
Definition: Log.h:89
An implemntation of a R* tree.
Definition: Spatial.h:274
SpatialQuery
A kind of spatial query.
Definition: Spatial.h:51
bool insert(const T &value, const Box< U, N > &bounds)
Insert an object in the tree.
Definition: Spatial.h:328
SplitOrder order
Definition: Spatial.h:459
constexpr bool contains(Vector< T, N > point) const noexcept
Definition: Box.h:98
bool insert(const T &value, const Box< U, 2 > &bounds)
Insert an object in the tree.
Definition: Spatial.h:92
std::size_t axis
Definition: Spatial.h:458