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
|
/*
* 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 "SkBBoxHierarchy.h"
#include "SkRect.h"
#include "SkTDArray.h"
/**
* An R-Tree implementation. In short, it is a balanced n-ary tree containing a hierarchy of
* bounding rectangles.
*
* It only supports bulk-loading, i.e. creation from a batch of bounding rectangles.
* This performs a bottom-up bulk load using the STR (sort-tile-recursive) algorithm.
*
* 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).
*
* 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"
*/
class SkRTree : public SkBBoxHierarchy {
public:
/**
* 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.
*/
explicit SkRTree(SkScalar aspectRatio = 1);
virtual ~SkRTree() {}
void insert(const SkRect[], int N) override;
void search(const SkRect& query, SkTDArray<int>* results) const override;
size_t bytesUsed() const override;
// Methods and constants below here are only public for tests.
// Return the depth of the tree structure.
int getDepth() const { return fCount ? fRoot.fSubtree->fLevel + 1 : 0; }
// Insertion count (not overall node count, which may be greater).
int getCount() const { return fCount; }
// Get the root bound.
SkRect getRootBound() const override;
// These values were empirically determined to produce reasonable performance in most cases.
static const int kMinChildren = 6,
kMaxChildren = 11;
private:
struct Node;
struct Branch {
union {
Node* fSubtree;
int fOpIndex;
};
SkRect fBounds;
};
struct Node {
uint16_t fNumChildren;
uint16_t fLevel;
Branch fChildren[kMaxChildren];
};
void search(Node* root, const SkRect& query, SkTDArray<int>* results) const;
// Consumes the input array.
Branch bulkLoad(SkTDArray<Branch>* branches, int level = 0);
// How many times will bulkLoad() call allocateNodeAtLevel()?
static int CountNodes(int branches, SkScalar aspectRatio);
Node* allocateNodeAtLevel(uint16_t level);
// This is the count of data elements (rather than total nodes in the tree)
int fCount;
SkScalar fAspectRatio;
Branch fRoot;
SkTDArray<Node> fNodes;
typedef SkBBoxHierarchy INHERITED;
};
#endif
|
