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
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
|
/*
* Copyright 2012 Google Inc.
*
* Use of this source code is governed by a BSD-style license that can be
* found in the LICENSE file.
*/
#ifndef SkRTree_DEFINED
#define SkRTree_DEFINED
#include "SkRect.h"
#include "SkTDArray.h"
#include "SkChunkAlloc.h"
#include "SkBBoxHierarchy.h"
/**
* An R-Tree implementation. In short, it is a balanced n-ary tree containing a hierarchy of
* bounding rectangles.
*
* Much like a B-Tree it maintains balance by enforcing minimum and maximum child counts, and
* splitting nodes when they become overfull. Unlike B-trees, however, we're using spatial data; so
* there isn't a canonical ordering to use when choosing insertion locations and splitting
* distributions. A variety of heuristics have been proposed for these problems; here, we're using
* something resembling an R*-tree, which attempts to minimize area and overlap during insertion,
* and aims to minimize a combination of margin, overlap, and area when splitting.
*
* One detail that is thus far unimplemented that may improve tree quality is attempting to remove
* and reinsert nodes when they become full, instead of immediately splitting (nodes that may have
* been placed well early on may hurt the tree later when more nodes have been added; removing
* and reinserting nodes generally helps reduce overlap and make a better tree). Deletion of nodes
* is also unimplemented.
*
* For more details see:
*
* Beckmann, N.; Kriegel, H. P.; Schneider, R.; Seeger, B. (1990). "The R*-tree:
* an efficient and robust access method for points and rectangles"
*
* It also supports bulk-loading from a batch of bounds and values; if you don't require the tree
* to be usable in its intermediate states while it is being constructed, this is significantly
* quicker than individual insertions and produces more consistent trees.
*/
class SkRTree : public SkBBoxHierarchy {
public:
SK_DECLARE_INST_COUNT(SkRTree)
/**
* Create a new R-Tree with specified min/max child counts.
* The child counts are valid iff:
* - (max + 1) / 2 >= min (splitting an overfull node must be enough to populate 2 nodes)
* - min < max
* - min > 0
* - max < SK_MaxU16
* If you have some prior information about the distribution of bounds you're expecting, you
* can provide an optional aspect ratio parameter. This allows the bulk-load algorithm to create
* better proportioned tiles of rectangles.
*/
static SkRTree* Create(int minChildren, int maxChildren, SkScalar aspectRatio = 1,
bool orderWhenBulkLoading = true);
virtual ~SkRTree();
/**
* Insert a node, consisting of bounds and a data value into the tree, if we don't immediately
* need to use the tree; we may allow the insert to be deferred (this can allow us to bulk-load
* a large batch of nodes at once, which tends to be faster and produce a better tree).
* @param data The data value
* @param bounds The corresponding bounding box
* @param defer Can this insert be deferred? (this may be ignored)
*/
virtual void insert(void* data, const SkIRect& bounds, bool defer = false) SK_OVERRIDE;
/**
* If any inserts have been deferred, this will add them into the tree
*/
virtual void flushDeferredInserts() SK_OVERRIDE;
/**
* Given a query rectangle, populates the passed-in array with the elements it intersects
*/
virtual void search(const SkIRect& query, SkTDArray<void*>* results) SK_OVERRIDE;
virtual void clear() SK_OVERRIDE;
bool isEmpty() const { return 0 == fCount; }
/**
* Gets the depth of the tree structure
*/
virtual int getDepth() const SK_OVERRIDE {
return this->isEmpty() ? 0 : fRoot.fChild.subtree->fLevel + 1;
}
/**
* This gets the insertion count (rather than the node count)
*/
virtual int getCount() const SK_OVERRIDE { return fCount; }
virtual void rewindInserts() SK_OVERRIDE;
private:
struct Node;
/**
* A branch of the tree, this may contain a pointer to another interior node, or a data value
*/
struct Branch {
union {
Node* subtree;
void* data;
} fChild;
SkIRect fBounds;
};
/**
* A node in the tree, has between fMinChildren and fMaxChildren (the root is a special case)
*/
struct Node {
uint16_t fNumChildren;
uint16_t fLevel;
bool isLeaf() { return 0 == fLevel; }
// Since we want to be able to pick min/max child counts at runtime, we assume the creator
// has allocated sufficient space directly after us in memory, and index into that space
Branch* child(size_t index) {
return reinterpret_cast<Branch*>(this + 1) + index;
}
};
typedef int32_t SkIRect::*SortSide;
// Helper for sorting our children arrays by sides of their rects
struct RectLessThan {
RectLessThan(SkRTree::SortSide side) : fSide(side) { }
bool operator()(const SkRTree::Branch lhs, const SkRTree::Branch rhs) const {
return lhs.fBounds.*fSide < rhs.fBounds.*fSide;
}
private:
const SkRTree::SortSide fSide;
};
struct RectLessX {
bool operator()(const SkRTree::Branch lhs, const SkRTree::Branch rhs) {
return ((lhs.fBounds.fRight - lhs.fBounds.fLeft) >> 1) <
((rhs.fBounds.fRight - lhs.fBounds.fLeft) >> 1);
}
};
struct RectLessY {
bool operator()(const SkRTree::Branch lhs, const SkRTree::Branch rhs) {
return ((lhs.fBounds.fBottom - lhs.fBounds.fTop) >> 1) <
((rhs.fBounds.fBottom - lhs.fBounds.fTop) >> 1);
}
};
SkRTree(int minChildren, int maxChildren, SkScalar aspectRatio, bool orderWhenBulkLoading);
/**
* Recursively descend the tree to find an insertion position for 'branch', updates
* bounding boxes on the way up.
*/
Branch* insert(Node* root, Branch* branch, uint16_t level = 0);
int chooseSubtree(Node* root, Branch* branch);
SkIRect computeBounds(Node* n);
int distributeChildren(Branch* children);
void search(Node* root, const SkIRect query, SkTDArray<void*>* results) const;
/**
* This performs a bottom-up bulk load using the STR (sort-tile-recursive) algorithm, this
* seems to generally produce better, more consistent trees at significantly lower cost than
* repeated insertions.
*
* This consumes the input array.
*
* TODO: Experiment with other bulk-load algorithms (in particular the Hilbert pack variant,
* which groups rects by position on the Hilbert curve, is probably worth a look). There also
* exist top-down bulk load variants (VAMSplit, TopDownGreedy, etc).
*/
Branch bulkLoad(SkTDArray<Branch>* branches, int level = 0);
void validate();
int validateSubtree(Node* root, SkIRect bounds, bool isRoot = false);
const int fMinChildren;
const int fMaxChildren;
const size_t fNodeSize;
// This is the count of data elements (rather than total nodes in the tree)
int fCount;
Branch fRoot;
SkChunkAlloc fNodes;
SkTDArray<Branch> fDeferredInserts;
SkScalar fAspectRatio;
bool fSortWhenBulkLoading;
Node* allocateNode(uint16_t level);
typedef SkBBoxHierarchy INHERITED;
};
#endif
|
