34 #include <boost/container/static_vector.hpp> 43 #ifndef DOXYGEN_SHOULD_SKIP_THIS 52 template<
typename U, std::
size_t N>
82 template<
typename T,
typename U =
float, std::
size_t Size = 16>
84 static_assert(Size > 0,
"Size can not be 0");
105 Node *node = m_root.chooseNode(bounds);
107 if (node ==
nullptr) {
111 return node->insert(std::move(value), bounds);
123 return m_root.query(bounds, callback, kind);
135 std::vector<SpatialStructure<U, 2>> structures;
136 m_root.appendToStructure(structures, 0);
149 : m_children(
nullptr)
151 m_entries.reserve(Size);
156 , m_children(
nullptr)
158 m_entries.reserve(Size);
161 bool isLeaf()
const {
162 return m_children ==
nullptr;
166 if (!m_bounds.contains(bounds)) {
171 if (m_entries.size() < Size) {
178 if (m_entries.size() < Size) {
183 for (std::size_t i = 0; i < 4; ++i) {
184 if (m_children[i].chooseNode(bounds) !=
nullptr) {
185 return &m_children[i];
189 clearChildrenIfEmpty();
194 bool insert(
T&& value,
const Box<U, 2>& bounds) {
195 m_entries.push_back({ std::move(value), bounds });
200 if (!m_bounds.intersects(bounds)) {
204 std::size_t found = 0;
206 for (
auto& entry : m_entries) {
209 if (bounds.
contains(entry.bounds)) {
210 callback(entry.value);
217 callback(entry.value);
225 for (std::size_t i = 0; i < 4; ++i) {
226 found += m_children[i].query(bounds, callback, kind);
237 m_children =
nullptr;
243 for (
auto& entry : m_entries) {
248 for (std::size_t i = 0; i < 4; ++i) {
249 m_children[i].appendToStructure(structures, level + 1);
256 m_children = std::make_unique<Node[]>(4);
263 std::vector<Entry> entries;
265 for (
auto& entry : m_entries) {
266 bool inserted =
false;
268 for (std::size_t i = 0; i < 4; ++i) {
269 if (m_children[i].m_bounds.contains(entry.bounds)) {
270 m_children[i].m_entries.push_back(std::move(entry));
277 entries.push_back(std::move(entry));
281 std::swap(m_entries, entries);
284 void clearChildrenIfEmpty() {
287 for (std::size_t i = 0; i < 4; ++i) {
288 if (!m_children[i].m_entries.empty()) {
293 m_children =
nullptr;
298 std::vector<Entry> m_entries;
299 std::unique_ptr<Node[]> m_children;
315 template<
typename T,
typename U =
float, std::
size_t N = 2, std::
size_t MaxSize = 16, std::
size_t MinSize = 4>
317 static_assert(
N > 0,
"N can not be 0");
318 static_assert(2 <= MinSize,
"MinSize must be at least 2");
319 static_assert(MinSize <= MaxSize / 2,
"MinSize must be less than MaxSize/2");
345 m_root = std::exchange(other.m_root,
nullptr);
352 std::swap(m_root, other.m_root);
371 Leaf *leaf = m_root->chooseSubtree(bounds);
373 Node *splitted = leaf->tryInsert(std::move(value), bounds);
374 Node *current = leaf;
376 while (splitted !=
nullptr) {
377 auto splittedBounds = splitted->computeBounds();
378 splitted->updateOriginalBounds(splittedBounds);
380 auto currentBounds = current->computeBounds();
381 current->updateOriginalBounds(currentBounds);
383 if (current == m_root) {
384 auto branch =
new Branch;
386 current->setParent(branch);
387 branch->tryInsert(current, currentBounds);
389 splitted->setParent(branch);
390 branch->tryInsert(splitted, splittedBounds);
392 branch->updateOriginalBounds(branch->computeBounds());
398 Branch *parent = current->getParent();
399 assert(parent !=
nullptr);
401 parent->updateBoundsForChild(currentBounds, current);
403 splitted->setParent(parent);
404 splitted = parent->tryInsert(splitted, splittedBounds);
410 while (current != m_root) {
411 auto currentBounds = current->computeBounds();
413 Branch *parent = current->getParent();
414 assert(parent !=
nullptr);
416 parent->updateBoundsForChild(currentBounds, current);
433 return m_root->query(bounds, callback, kind);
445 std::vector<SpatialStructure<U, N>> structures;
446 m_root->appendToStructure(structures, 0);
451 static constexpr std::size_t Size = MaxSize + 1;
483 Branch *getParent() noexcept {
487 void setParent(Branch *parent) {
491 bool hasOriginalBounds()
const {
492 return !m_orig.isEmpty();
495 U getOriginalCenterAxisValue(std::size_t axis)
const {
496 return (m_orig.min[axis] + m_orig.max[axis]) / 2;
499 void updateOriginalBounds(
Box<U, N> orig) {
503 virtual ~
Node() =
default;
505 virtual Leaf *chooseSubtree(
const Box<U, N>& bounds) = 0;
507 virtual Box<U, N> computeBounds()
const = 0;
520 struct LeafEntry : Entry {
524 class Leaf :
public Node {
527 std::size_t found = 0;
531 for (
auto& entry : m_entries) {
532 if (bounds.
contains(entry.bounds)) {
533 callback(entry.value);
540 for (
auto& entry : m_entries) {
542 callback(entry.value);
553 virtual Leaf *chooseSubtree(
const Box<U, N>& bounds)
override {
558 virtual Box<U,N> computeBounds()
const override {
559 assert(!m_entries.empty());
562 for (
auto& entry : m_entries) {
563 res.extend(entry.bounds);
569 virtual void appendToStructure(std::vector<
SpatialStructure<U, N>>& structures,
int level)
const override {
570 for (
auto& entry : m_entries) {
575 Leaf *tryInsert(
T&& value,
const Box<U, N>& bounds) {
577 entry.bounds = bounds;
578 entry.value = std::move(value);
579 m_entries.push_back(std::move(entry));
581 if (m_entries.size() < Size) {
585 std::vector<Box<U, N>> boxes;
587 std::transform(m_entries.begin(), m_entries.end(), std::back_inserter(boxes), [](
const Entry& entry) {
591 SplitResult split = computeSplit(boxes);
593 switch (split.order) {
594 case SplitOrder::Min:
595 std::sort(m_entries.begin(), m_entries.end(), EntryMinAxisComparator<LeafEntry>(split.axis));
597 case SplitOrder::Max:
598 std::sort(m_entries.begin(), m_entries.end(), EntryMaxAxisComparator<LeafEntry>(split.axis));
602 auto leaf =
new Leaf;
604 auto splitIteratorBegin = std::next(m_entries.begin(), split.index + 1);
605 auto splitIteratorEnd = m_entries.end();
607 std::move(splitIteratorBegin, splitIteratorEnd, std::back_inserter(leaf->m_entries));
608 m_entries.erase(splitIteratorBegin, splitIteratorEnd);
614 SplitResult computeSplit(std::vector<
Box<U, N>>& boxes) {
616 std::tie(split.axis, split.order) = computeSplitAxis(boxes);
618 switch (split.order) {
619 case SplitOrder::Min:
620 std::sort(boxes.begin(), boxes.end(), MinAxisComparator(split.axis));
622 case SplitOrder::Max:
623 std::sort(boxes.begin(), boxes.end(), MaxAxisComparator(split.axis));
627 split.index = computeSplitIndex(boxes, split.axis);
631 std::tuple<std::size_t, SplitOrder> computeSplitAxis(std::vector<
Box<U, N>>& boxes) {
632 std::size_t currentAxis = 0;
633 U currentValue = std::numeric_limits<U>::max();
634 SplitOrder currentOrder = SplitOrder::Min;
636 for (std::size_t axis = 0; axis <
N; ++axis) {
637 std::sort(boxes.begin(), boxes.end(), MinAxisComparator(axis));
639 U value = computeAxisValue(boxes);
641 if (value < currentValue) {
643 currentValue = value;
644 currentOrder = SplitOrder::Min;
647 std::sort(boxes.begin(), boxes.end(), MaxAxisComparator(axis));
649 value = computeAxisValue(boxes);
651 if (value < currentValue) {
653 currentValue = value;
654 currentOrder = SplitOrder::Max;
658 return std::make_tuple(currentAxis, currentOrder);
661 U computeAxisValue(
const std::vector<
Box<U, N>>& boxes) {
662 std::vector<Box<U, N>> firstBounds;
664 std::partial_sum(boxes.begin(), boxes.end(), std::back_inserter(firstBounds), [](
const Box<U, N>& lhs,
const Box<U, N>& rhs) {
668 std::vector<Box<U, N>> secondBounds;
670 std::partial_sum(boxes.rbegin(), boxes.rend(), std::back_inserter(secondBounds), [](
const Box<U, N>& lhs,
const Box<U, N>& rhs) {
676 for (std::size_t j = MinSize; j <= MaxSize - MinSize + 1; ++j) {
677 value += firstBounds[j].getExtentDistance() + secondBounds[Size - j].getExtentDistance();
683 std::size_t computeSplitIndex(
const std::vector<
Box<U, N>>& boxes, std::size_t axis) {
684 std::vector<Box<U, N>> firstBounds;
686 std::partial_sum(boxes.begin(), boxes.end(), std::back_inserter(firstBounds), [](
const Box<U, N>& lhs,
const Box<U, N>& rhs) {
690 std::vector<Box<U, N>> secondBounds;
692 std::partial_sum(boxes.rbegin(), boxes.rend(), std::back_inserter(secondBounds), [](
const Box<U, N>& lhs,
const Box<U, N>& rhs) {
699 const auto& bounds = firstBounds.back();
702 if (Node::hasOriginalBounds()) {
703 asym = 2.0f * ((bounds.max[axis] + bounds.min[axis]) / 2 - Node::getOriginalCenterAxisValue(axis)) / (bounds.max[axis] - bounds.min[axis]);
706 assert(-1.0f <= asym && asym <= 1.0f);
708 static constexpr
float S = 0.5f;
709 const float mu = (1 - 2.0f * MinSize / (MaxSize + 1)) * asym;
710 const float rho = S * (1 + std::abs(mu));
711 const float y1 = std::exp(- 1 / (S * S));
712 const float ys = 1 / (1 - y1);
714 auto wf = [mu,rho,y1,ys](std::size_t i) {
715 const float xi = 2.0f * i / (MaxSize + 1.0f) - 1.0f;
716 return ys * (std::exp(-
gf::square((xi - mu) / rho) - y1));
721 std::size_t currentIndex = 0;
722 U currentValue = std::numeric_limits<U>::max();
726 if (firstBounds[MinSize].getVolume() == 0 || secondBounds[MinSize].getVolume() == 0) {
734 bool overlapFree =
false;
736 U perimeterMax = 2 * bounds.getExtentDistance() - bounds.getMinimumEdge();
738 for (std::size_t index = MinSize; index <= MaxSize - MinSize + 1; ++index) {
739 auto weight = (firstBounds[index].*overlapFn)(secondBounds[Size - index - 1]);
745 auto value = weight * wf(index);
747 if (value < currentValue) {
748 currentValue = value;
749 currentIndex = index;
754 if (overlapFree && weight == 0) {
755 weight = firstBounds[index].getExtentDistance() + secondBounds[Size - index - 1].getExtentDistance() - perimeterMax;
758 auto value = weight / wf(index);
760 if (value < currentValue) {
761 currentValue = value;
762 currentIndex = index;
771 boost::container::static_vector<LeafEntry, Size> m_entries;
778 struct BranchEntry : Entry {
782 class Branch :
public Node {
785 for (
auto& entry : m_entries) {
791 std::size_t found = 0;
793 for (
auto& entry : m_entries) {
795 found += entry.child->query(bounds, callback, kind);
802 virtual Leaf *chooseSubtree(
const Box<U, N>& bounds)
override {
803 return chooseNode(bounds)->chooseSubtree(bounds);
807 Node *bestNodeForVolume =
nullptr;
808 U bestVolume = std::numeric_limits<U>::max();
810 Node *bestNodeForExtentDistance =
nullptr;
811 U bestExtentDistance = std::numeric_limits<U>::max();
813 for (
auto& entry : m_entries) {
814 if (entry.bounds.getIntersection(bounds) == bounds) {
815 U volume = entry.bounds.getVolume();
817 if (bestNodeForVolume ==
nullptr || volume < bestVolume) {
819 bestNodeForVolume = entry.child;
822 U extentDistance = entry.bounds.getExtentDistance();
824 if (bestNodeForExtentDistance ==
nullptr || extentDistance < bestExtentDistance) {
825 bestExtentDistance = extentDistance;
826 bestNodeForExtentDistance = entry.child;
831 if (bestNodeForVolume !=
nullptr) {
832 if (bestVolume > 0) {
833 return bestNodeForVolume;
836 assert(bestNodeForExtentDistance);
837 return bestNodeForExtentDistance;
844 Node *covering = searchForCoveringNode(bounds);
846 if (covering !=
nullptr) {
850 std::sort(m_entries.begin(), m_entries.end(), ExtentDistanceEnlargement(bounds));
852 OverlapExtentDistanceEnlargement extentDistanceEnlargement(bounds, m_entries.front());
856 for (p = m_entries.size() - 1; p > 0; --p) {
857 if (extentDistanceEnlargement(m_entries[p]) != 0) {
863 return m_entries[0].child;
866 std::vector<Candidate> candidates(p + 1, { 0,
false,
U() });
867 Node *node =
nullptr;
869 if (existsEmptyVolumeExtension(bounds)) {
870 node = findCandidates<OverlapExtentDistanceEnlargement>(0, p, bounds, candidates);
872 node = findCandidates<OverlapVolumeEnlargement>(0, p, bounds, candidates);
875 if (node !=
nullptr) {
879 candidates.erase(std::remove_if(candidates.begin(), candidates.end(), [](
const Candidate& candidate) {
880 return !candidate.isCandidate;
881 }), candidates.end());
883 assert(!candidates.empty());
885 auto it = std::min_element(candidates.begin(), candidates.end(), [](
const Candidate& lhs,
const Candidate& rhs) {
886 return lhs.overlap < rhs.overlap;
889 return m_entries[it->index].child;
892 virtual Box<U,N> computeBounds()
const override {
893 assert(!m_entries.empty());
896 for (
auto& entry : m_entries) {
897 res.extend(entry.bounds);
903 virtual void appendToStructure(std::vector<
SpatialStructure<U, N>>& structures,
int level)
const override {
904 for (
auto& entry : m_entries) {
906 entry.child->appendToStructure(structures, level + 1);
910 void updateBoundsForChild(
const Box<U, N>& bounds,
Node *child) {
911 for (
auto& entry : m_entries) {
912 if (entry.child == child) {
913 entry.bounds = bounds;
923 entry.bounds = bounds;
925 m_entries.push_back(std::move(entry));
927 if (m_entries.size() < Size) {
931 std::vector<Box<U, N>> boxes;
933 std::transform(m_entries.begin(), m_entries.end(), std::back_inserter(boxes), [](
const Entry& entry) {
937 SplitResult split = computeSplit(boxes);
939 switch (split.order) {
940 case SplitOrder::Min:
941 std::sort(m_entries.begin(), m_entries.end(), EntryMinAxisComparator<BranchEntry>(split.axis));
943 case SplitOrder::Max:
944 std::sort(m_entries.begin(), m_entries.end(), EntryMaxAxisComparator<BranchEntry>(split.axis));
948 auto branch =
new Branch;
950 auto splitIteratorBegin = std::next(m_entries.begin(), split.index + 1);
951 auto splitIteratorEnd = m_entries.end();
953 std::move(splitIteratorBegin, splitIteratorEnd, std::back_inserter(branch->m_entries));
954 m_entries.erase(splitIteratorBegin, splitIteratorEnd);
956 for (
auto& entry : branch->m_entries) {
957 entry.child->setParent(branch);
970 bool existsEmptyVolumeExtension(
const Box<U, N>& bounds) {
971 for (
auto& entry : m_entries) {
972 if (entry.bounds.getExtended(bounds).getVolume() == 0) {
980 template<
typename OverlapEnlargement>
981 Node *findCandidates(std::size_t t, std::size_t p,
const Box<U, N>& bounds, std::vector<Candidate>& candidates) {
982 candidates[t].index = t;
983 candidates[t].isCandidate =
true;
985 OverlapEnlargement enlargement(bounds, m_entries[t]);
989 for (std::size_t i = 0; i <= p; ++i) {
994 U localOverlap = enlargement(m_entries[i]);
995 overlap += localOverlap;
997 if (localOverlap == 0 && !candidates[i].isCandidate) {
998 Node *node = findCandidates<OverlapEnlargement>(i, p, bounds, candidates);
1000 if (node !=
nullptr) {
1007 return m_entries[t].child;
1010 candidates[t].overlap = overlap;
1014 struct SplitStatus {
1015 bool overlapFree =
false;
1016 U currentValue = std::numeric_limits<U>::max();
1019 SplitResult computeSplit(std::vector<
Box<U, N>>& boxes) {
1023 for (std::size_t axis = 0; axis <
N; ++axis) {
1024 std::sort(boxes.begin(), boxes.end(), MinAxisComparator(axis));
1025 computeBestSplitValue(boxes, result, status, axis, SplitOrder::Min);
1027 std::sort(boxes.begin(), boxes.end(), MaxAxisComparator(axis));
1028 computeBestSplitValue(boxes, result, status, axis, SplitOrder::Max);
1034 void computeBestSplitValue(std::vector<
Box<U, N>>& boxes, SplitResult& result, SplitStatus& status, std::size_t axis, SplitOrder order) {
1035 std::vector<Box<U, N>> firstBounds;
1037 std::partial_sum(boxes.begin(), boxes.end(), std::back_inserter(firstBounds), [](
const Box<U, N>& lhs,
const Box<U, N>& rhs) {
1041 std::vector<Box<U, N>> secondBounds;
1043 std::partial_sum(boxes.rbegin(), boxes.rend(), std::back_inserter(secondBounds), [](
const Box<U, N>& lhs,
const Box<U, N>& rhs) {
1049 const auto& bounds = firstBounds.back();
1052 if (Node::hasOriginalBounds()) {
1053 asym = 2.0f * ((bounds.max[axis] + bounds.min[axis]) / 2 - Node::getOriginalCenterAxisValue(axis)) / (bounds.max[axis] - bounds.min[axis]);
1056 assert(-1.0f <= asym && asym <= 1.0f);
1058 static constexpr
float S = 0.5f;
1059 const float mu = (1 - 2.0f * MinSize / (MaxSize + 1)) * asym;
1060 const float rho = S * (1 + std::abs(mu));
1061 const float y1 = std::exp(- 1 / (S * S));
1062 const float ys = 1 / (1 - y1);
1064 auto wf = [mu,rho,y1,ys](std::size_t i) {
1065 const float xi = 2.0f * i / (MaxSize + 1.0f) - 1.0f;
1066 return ys * (std::exp(-
gf::square((xi - mu) / rho) - y1));
1073 if (firstBounds[MinSize].getVolume() == 0 || secondBounds[MinSize].getVolume() == 0) {
1081 U perimeterMax = 2 * bounds.getExtentDistance() - bounds.getMinimumEdge();
1083 for (std::size_t index = MinSize; index <= MaxSize - MinSize + 1; ++index) {
1084 auto weight = (firstBounds[index].*overlapFn)(secondBounds[Size - index - 1]);
1086 if (!status.overlapFree) {
1088 status.overlapFree =
true;
1090 auto value = weight * wf(index);
1092 if (value < status.currentValue) {
1093 status.currentValue = value;
1094 result.index = index;
1096 result.order = order;
1101 if (status.overlapFree && weight == 0) {
1102 weight = firstBounds[index].getExtentDistance() + secondBounds[Size - index - 1].getExtentDistance() - perimeterMax;
1103 assert(weight <= 0);
1105 auto value = weight / wf(index);
1107 if (value < status.currentValue) {
1108 status.currentValue = value;
1109 result.index = index;
1111 result.order = order;
1118 boost::container::static_vector<BranchEntry, Size> m_entries;
1125 class ExtentDistanceEnlargement {
1127 ExtentDistanceEnlargement(
const Box<U, N>& bounds)
1133 bool operator()(
const Entry& lhs,
const Entry& rhs)
const {
1134 return getExtentDistanceEnlargement(lhs) < getExtentDistanceEnlargement(rhs);
1137 U getExtentDistanceEnlargement(
const Entry& entry)
const {
1138 return entry.bounds.getExtended(m_bounds).getExtentDistance() - entry.bounds.getExtentDistance();
1145 class OverlapExtentDistanceEnlargement {
1147 OverlapExtentDistanceEnlargement(
const Box<U, N>& bounds,
const Entry& reference)
1149 , m_reference(reference)
1150 , m_extended(reference.bounds.getExtended(bounds))
1155 U operator()(
const Entry& entry)
const {
1156 return getOverlapExtentDistanceEnlargement(entry);
1159 U getOverlapExtentDistanceEnlargement(
const Entry& entry)
const {
1160 return m_extended.getIntersectionExtentDistance(entry.bounds) - m_reference.bounds.getIntersectionExtentDistance(entry.bounds);
1165 const Entry& m_reference;
1170 class OverlapVolumeEnlargement {
1172 OverlapVolumeEnlargement(
const Box<U, N>& bounds,
const Entry& reference)
1174 , m_reference(reference)
1175 , m_extended(reference.bounds.getExtended(bounds))
1180 U operator()(
const Entry& entry)
const {
1181 return getOverlapVolumeEnlargement(entry);
1184 U getOverlapVolumeEnlargement(
const Entry& entry)
const {
1185 return m_extended.getIntersectionVolume(entry.bounds) - m_reference.bounds.getIntersectionVolume(entry.bounds);
1190 const Entry& m_reference;
1194 class MinAxisComparator {
1196 MinAxisComparator(std::size_t axis)
1203 return std::make_tuple(lhs.
min[m_axis], lhs.
max[m_axis]) < std::make_tuple(rhs.
min[m_axis], rhs.
max[m_axis]);
1210 template<
typename Entry>
1211 class EntryMinAxisComparator {
1213 EntryMinAxisComparator(std::size_t axis)
1219 bool operator()(
const Entry& lhs,
const Entry& rhs) {
1220 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]);
1227 class MaxAxisComparator {
1229 MaxAxisComparator(std::size_t axis)
1236 return std::make_tuple(lhs.
max[m_axis], lhs.
min[m_axis]) < std::make_tuple(rhs.
max[m_axis], rhs.
min[m_axis]);
1243 template<
typename Entry>
1244 class EntryMaxAxisComparator {
1246 EntryMaxAxisComparator(std::size_t axis)
1252 bool operator()(
const Entry& lhs,
const Entry& rhs) {
1253 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]);
1261 void updateBounds(
Node *node) {
1262 while (node !=
nullptr) {
1263 Box<U, N> bounds = node->computeBounds();
1265 Branch *parent = node->getParent();
1267 if (parent !=
nullptr) {
1268 parent->updateBoundsForChild(bounds, node);
1280 #ifndef DOXYGEN_SHOULD_SKIP_THIS 1285 #endif // GF_SPATIAL_H constexpr Box< T, N > getExtended(const Box< T, N > &other) const noexcept
Definition: Box.h:196
bool insert(T value, const Box< U, N > &bounds)
Insert an object in the tree.
Definition: Spatial.h:370
constexpr bool intersects(const Box< T, N > &other) const noexcept
Definition: Box.h:118
void clear()
Remove all the objects from the tree.
Definition: Spatial.h:129
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:432
std::function< void(const T &)> SpatialQueryCallback
A callback for spatial query.
Definition: Spatial.h:73
std::vector< SpatialStructure< U, N > > getStructure() const
Definition: Spatial.h:444
constexpr Vector2f transform(const Matrix3f &mat, Vector2f point)
Apply an affine transformation to a 2D point.
Definition: Transform.h:331
SpatialStructureType type
Definition: Spatial.h:55
Box< U, N > bounds
Definition: Spatial.h:54
Vector< T, N > min
Definition: Box.h:49
Search for all objects that contain the given bounds.
~RStarTree()
Destructor.
Definition: Spatial.h:359
std::vector< SpatialStructure< U, 2 > > getStructure() const
Definition: Spatial.h:134
constexpr T square(T val)
Square function.
Definition: Math.h:275
SpatialStructureType
Definition: Spatial.h:47
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:122
Search for all objects that intersect the given bounds.
RStarTree & operator=(RStarTree &&other) noexcept
Move assignement.
Definition: Spatial.h:351
void clear()
Remove all the objects from the tree.
Definition: Spatial.h:439
The namespace for gf classes.
Definition: Action.h:35
QuadTree(const Box< U, 2 > &bounds)
Constructor.
Definition: Spatial.h:91
RStarTree()
Constructor.
Definition: Spatial.h:324
An implementation of quadtree.
Definition: Spatial.h:83
Vector< T, N > max
Definition: Box.h:50
Box< T, 2 > computeBoxQuadrant(const Box< T, 2 > &box, Quadrant quadrant)
Definition: Box.h:263
int level
Definition: Spatial.h:56
RStarTree(RStarTree &&other) noexcept
Move constructor.
Definition: Spatial.h:343
An implemntation of a R* tree.
Definition: Spatial.h:316
SpatialQuery
A kind of spatial query.
Definition: Spatial.h:63
bool insert(T value, const Box< U, 2 > &bounds)
Insert an object in the tree.
Definition: Spatial.h:104
constexpr bool contains(Vector< T, N > point) const noexcept
Definition: Box.h:98
constexpr void unused(Args &&...)
A simple way to avoid warnings about unused variables.
Definition: Unused.h:35