OLD | NEW |
1 | 1 |
2 /* | 2 /* |
3 * Copyright 2012 Google Inc. | 3 * Copyright 2012 Google Inc. |
4 * | 4 * |
5 * Use of this source code is governed by a BSD-style license that can be | 5 * Use of this source code is governed by a BSD-style license that can be |
6 * found in the LICENSE file. | 6 * found in the LICENSE file. |
7 */ | 7 */ |
8 | 8 |
9 #ifndef SkRTree_DEFINED | 9 #ifndef SkRTree_DEFINED |
10 #define SkRTree_DEFINED | 10 #define SkRTree_DEFINED |
(...skipping 13 matching lines...) Expand all Loading... |
24 * which groups rects by position on the Hilbert curve, is probably worth a look
). There also | 24 * which groups rects by position on the Hilbert curve, is probably worth a look
). There also |
25 * exist top-down bulk load variants (VAMSplit, TopDownGreedy, etc). | 25 * exist top-down bulk load variants (VAMSplit, TopDownGreedy, etc). |
26 * | 26 * |
27 * For more details see: | 27 * For more details see: |
28 * | 28 * |
29 * Beckmann, N.; Kriegel, H. P.; Schneider, R.; Seeger, B. (1990). "The R*-tree
: | 29 * Beckmann, N.; Kriegel, H. P.; Schneider, R.; Seeger, B. (1990). "The R*-tree
: |
30 * an efficient and robust access method for points and rectangles" | 30 * an efficient and robust access method for points and rectangles" |
31 */ | 31 */ |
32 class SkRTree : public SkBBoxHierarchy { | 32 class SkRTree : public SkBBoxHierarchy { |
33 public: | 33 public: |
34 | 34 |
35 | 35 |
36 /** | 36 /** |
37 * If you have some prior information about the distribution of bounds you'r
e expecting, you | 37 * If you have some prior information about the distribution of bounds you'r
e expecting, you |
38 * can provide an optional aspect ratio parameter. This allows the bulk-load
algorithm to | 38 * can provide an optional aspect ratio parameter. This allows the bulk-load
algorithm to |
39 * create better proportioned tiles of rectangles. | 39 * create better proportioned tiles of rectangles. |
40 */ | 40 */ |
41 explicit SkRTree(SkScalar aspectRatio = 1); | 41 explicit SkRTree(SkScalar aspectRatio = 1); |
42 virtual ~SkRTree() {} | 42 virtual ~SkRTree() {} |
43 | 43 |
44 void insert(const SkRect[], int N) override; | 44 void insert(const SkRect[], int N) override; |
45 void search(const SkRect& query, SkTDArray<unsigned>* results) const overrid
e; | 45 void search(const SkRect& query, SkTDArray<int>* results) const override; |
46 size_t bytesUsed() const override; | 46 size_t bytesUsed() const override; |
47 | 47 |
48 // Methods and constants below here are only public for tests. | 48 // Methods and constants below here are only public for tests. |
49 | 49 |
50 // Return the depth of the tree structure. | 50 // Return the depth of the tree structure. |
51 int getDepth() const { return fCount ? fRoot.fSubtree->fLevel + 1 : 0; } | 51 int getDepth() const { return fCount ? fRoot.fSubtree->fLevel + 1 : 0; } |
52 // Insertion count (not overall node count, which may be greater). | 52 // Insertion count (not overall node count, which may be greater). |
53 int getCount() const { return fCount; } | 53 int getCount() const { return fCount; } |
54 | 54 |
55 // Get the root bound. | 55 // Get the root bound. |
56 SkRect getRootBound() const override; | 56 SkRect getRootBound() const override; |
57 | 57 |
58 // These values were empirically determined to produce reasonable performanc
e in most cases. | 58 // These values were empirically determined to produce reasonable performanc
e in most cases. |
59 static const int kMinChildren = 6, | 59 static const int kMinChildren = 6, |
60 kMaxChildren = 11; | 60 kMaxChildren = 11; |
61 | 61 |
62 private: | 62 private: |
63 struct Node; | 63 struct Node; |
64 | 64 |
65 struct Branch { | 65 struct Branch { |
66 union { | 66 union { |
67 Node* fSubtree; | 67 Node* fSubtree; |
68 unsigned fOpIndex; | 68 int fOpIndex; |
69 }; | 69 }; |
70 SkRect fBounds; | 70 SkRect fBounds; |
71 }; | 71 }; |
72 | 72 |
73 struct Node { | 73 struct Node { |
74 uint16_t fNumChildren; | 74 uint16_t fNumChildren; |
75 uint16_t fLevel; | 75 uint16_t fLevel; |
76 Branch fChildren[kMaxChildren]; | 76 Branch fChildren[kMaxChildren]; |
77 }; | 77 }; |
78 | 78 |
79 void search(Node* root, const SkRect& query, SkTDArray<unsigned>* results) c
onst; | 79 void search(Node* root, const SkRect& query, SkTDArray<int>* results) const; |
80 | 80 |
81 // Consumes the input array. | 81 // Consumes the input array. |
82 Branch bulkLoad(SkTDArray<Branch>* branches, int level = 0); | 82 Branch bulkLoad(SkTDArray<Branch>* branches, int level = 0); |
83 | 83 |
84 // How many times will bulkLoad() call allocateNodeAtLevel()? | 84 // How many times will bulkLoad() call allocateNodeAtLevel()? |
85 static int CountNodes(int branches, SkScalar aspectRatio); | 85 static int CountNodes(int branches, SkScalar aspectRatio); |
86 | 86 |
87 Node* allocateNodeAtLevel(uint16_t level); | 87 Node* allocateNodeAtLevel(uint16_t level); |
88 | 88 |
89 // This is the count of data elements (rather than total nodes in the tree) | 89 // This is the count of data elements (rather than total nodes in the tree) |
90 int fCount; | 90 int fCount; |
91 SkScalar fAspectRatio; | 91 SkScalar fAspectRatio; |
92 Branch fRoot; | 92 Branch fRoot; |
93 SkTDArray<Node> fNodes; | 93 SkTDArray<Node> fNodes; |
94 | 94 |
95 typedef SkBBoxHierarchy INHERITED; | 95 typedef SkBBoxHierarchy INHERITED; |
96 }; | 96 }; |
97 | 97 |
98 #endif | 98 #endif |
OLD | NEW |