21 #ifndef GF_SPATIAL_R_STAR_TREE_H 22 #define GF_SPATIAL_R_STAR_TREE_H 27 #include <boost/container/static_vector.hpp> 29 #include <gf/Handle.h> 30 #include <gf/Portability.h> 33 #include "BlockAllocator.h" 37 #ifndef DOXYGEN_SHOULD_SKIP_THIS 52 static constexpr std::size_t MaxSize = 16;
53 static constexpr std::size_t MinSize = 4;
107 std::size_t allocateEntry();
108 void disposeEntry(std::size_t index);
110 std::size_t allocateNode();
111 void disposeNode(std::size_t index);
113 RectF computeBounds(std::size_t nodeIndex);
114 void updateBoundsForChild(std::size_t parentIndex,
const RectF& bounds, std::size_t childIndex);
116 void doInsert(std::size_t entryIndex,
const RectF& bounds);
118 std::size_t chooseSubtree(std::size_t nodeIndex,
const RectF& bounds);
119 std::size_t chooseNode(std::size_t nodeIndex,
const RectF& bounds);
120 std::size_t searchForCoveringNode(std::size_t nodeIndex,
const RectF& bounds);
121 bool existsEmptyVolumeExtension(std::size_t nodeIndex,
const RectF& bounds);
129 template<
typename OverlapEnlargement>
130 std::size_t findCandidates(std::size_t nodeIndex, std::size_t t, std::size_t p,
const RectF& bounds, std::vector<Candidate>& candidates);
132 std::size_t doInsertInLeaf(std::size_t nodeIndex, std::size_t entryIndex,
const RectF& entryBounds);
133 std::size_t doInsertInBranch(std::size_t nodeIndex, std::size_t childIndex,
const RectF& childBounds);
137 void getEntriesAndDispose(std::size_t nodeIndex, std::vector<std::size_t>& eliminated);
138 void doRemove(std::size_t entryIndex);
140 void validate()
const;
141 std::size_t validateNode(std::size_t nodeIndex)
const;
144 static constexpr std::size_t Size = MaxSize + 1;
168 boost::container::static_vector<Member, Size> members;
175 #ifndef DOXYGEN_SHOULD_SKIP_THIS 180 #endif // GF_SPATIAL_R_STAR_TREE_H The structure represents an internal node.
std::function< void(Handle)> SpatialQueryCallback
A callback for spatial query.
Definition: spatial/Types.h:81
SpatialId
A spatial id.
Definition: spatial/Types.h:41
Search for all objects that intersect the given bounds.
The namespace for gf classes.
Definition: Action.h:35
Definition: RStarTree.h:160
RectF bounds
Definition: RStarTree.h:161
An implemntation of a R* tree.
Definition: RStarTree.h:50
SpatialQuery
A kind of spatial query.
Definition: spatial/Types.h:72
std::size_t index
Definition: RStarTree.h:162