1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
|
#pragma once
/**
* LooseQuadtree written by Zozo
* use freely under MIT license
*
* Loose quadtree (unlike normal quadtrees which are for points only) is
* a region tree designed to store bounding boxes effectively
* See boost::geometry::index::rtree for a more advanced, general solution!
*
* This implementation features:
* - Fully adaptive behavior, adjusts its bounds, height and memory on demand
* - Every object will be stored on the level to which its size corresponds to
* - Gives theoretically optimal search results (see previous)
* - Uses tree structure instead of hashed (smaller memory footprint, cache friendly)
* - Uses as much data in-place as it can (by using its own allocator)
* - Allocates memory in big chunks
* - Uses axis-aligned bounding boxes for calculations
* - Uses left-top-width-height bounds for better precision (no right-bottom)
* - Uses left-top closed right-bottom open interval logic (for integral types)
* - Uses X-towards-right Y-towards-bottom screen-like coordinate system
* - It is suitable for both floating- and fixed-point logic
* - This library is not thread-safe but multiple queries can be run at once
*
* Generic parameters are:
* - NumberT generic number type allows its floating- and fixed-point usage
* - ObjectT* only pointer is stored, no object copying is done, not an inclusive container
* - BoundingBoxExtractorT allows using your own bounding box type/source, needs
* BoundingBoxExtractor::ExtractBoundingBox(ObjectT* in, BoundingBox<Number>* out) implemented
*/
namespace loose_quadtree {
template <typename NumberT>
struct BoundingBox {
using Number = NumberT;
constexpr BoundingBox(Number _left, Number _top, Number _width, Number _height) :
left(_left), top(_top), width(_width), height(_height) {}
bool Intersects(const BoundingBox<Number>& other) const ;
bool Contains(const BoundingBox<Number>& other) const;
bool Contains(Number x, Number y) const;
BoundingBox& operator=(const BoundingBox&) noexcept = default;
BoundingBox(const BoundingBox&) noexcept = default;
Number left;
Number top;
Number width;
Number height;
};
template <typename NumberT, typename ObjectT, typename BoundingBoxExtractorT>
class LooseQuadtree {
public:
using Number = NumberT;
using Object = ObjectT;
using BoundingBoxExtractor = BoundingBoxExtractorT;
private:
class Impl;
public:
class Query {
public:
~Query();
Query() = delete;
Query(const Query&) = delete;
Query& operator=(const Query&) = delete;
Query(Query&&) noexcept;
Query& operator=(Query&&) noexcept;
bool EndOfQuery() const;
Object* GetCurrent() const;
void Next();
private:
friend class LooseQuadtree<Number, Object, BoundingBoxExtractor>::Impl;
class Impl;
Query(Impl* pimpl);
Impl* pimpl_;
};
LooseQuadtree() = default;
~LooseQuadtree() = default;
LooseQuadtree(const LooseQuadtree&) = delete;
LooseQuadtree& operator=(const LooseQuadtree&) = delete;
bool Insert(Object* object); ///< true if it was inserted (else updated)
bool Update(Object* object); ///< true if it was updated (else inserted)
bool Remove(Object* object); ///< true if it was removed
bool Contains(Object* object) const; ///< true if object is in tree
Query QueryIntersectsRegion(const BoundingBox<Number>& region);
Query QueryInsideRegion(const BoundingBox<Number>& region);
Query QueryContainsRegion(const BoundingBox<Number>& region);
const BoundingBox<Number>& GetLooseBoundingBox() const;
///< double its size to get a bounding box including everything contained for sure
int GetSize() const;
bool IsEmpty() const;
void Clear();
void ForceCleanup(); ///< does a full data structure and memory cleanup
///< cleanup is semi-automatic during queries so you needn't call this normally
private:
Impl impl_;
};
} //loose_quadtree
|
