OLD | NEW |
1 /* | 1 /* |
2 * Copyright 2014 Google Inc. | 2 * Copyright 2014 Google Inc. |
3 * | 3 * |
4 * Use of this source code is governed by a BSD-style license that can be | 4 * Use of this source code is governed by a BSD-style license that can be |
5 * found in the LICENSE file. | 5 * found in the LICENSE file. |
6 */ | 6 */ |
7 | 7 |
8 #ifndef SkQuadTree_DEFINED | 8 #ifndef SkQuadTree_DEFINED |
9 #define SkQuadTree_DEFINED | 9 #define SkQuadTree_DEFINED |
10 | 10 |
11 #include "SkRect.h" | 11 #include "SkRect.h" |
12 #include "SkTDArray.h" | 12 #include "SkTDArray.h" |
13 #include "SkBBoxHierarchy.h" | 13 #include "SkBBoxHierarchy.h" |
| 14 #include "SkTInternalSList.h" |
| 15 #include "SkTObjectPool.h" |
14 | 16 |
15 /** | 17 /** |
16 * An QuadTree implementation. In short, it is a tree containing a hierarchy of
bounding rectangles | 18 * A QuadTree implementation. In short, it is a tree containing a hierarchy of b
ounding rectangles |
17 * in which each internal node has exactly four children. | 19 * in which each internal node has exactly four children. |
18 * | 20 * |
19 * For more details see: | 21 * For more details see: |
20 * | 22 * |
21 * http://en.wikipedia.org/wiki/Quadtree | 23 * http://en.wikipedia.org/wiki/Quadtree |
22 */ | 24 */ |
23 class SkQuadTree : public SkBBoxHierarchy { | 25 class SkQuadTree : public SkBBoxHierarchy { |
24 public: | 26 public: |
25 SK_DECLARE_INST_COUNT(SkQuadTree) | 27 SK_DECLARE_INST_COUNT(SkQuadTree) |
26 | 28 |
27 /** | 29 /** |
28 * Create a new QuadTree | 30 * Quad tree constructor. |
| 31 * @param bounds The bounding box for the root of the quad tree. |
| 32 * giving the quad tree bounds that fall outside the root |
| 33 * bounds may result in pathological but correct behavior. |
29 */ | 34 */ |
30 static SkQuadTree* Create(const SkIRect& bounds); | 35 SkQuadTree(const SkIRect& bounds); |
| 36 |
31 virtual ~SkQuadTree(); | 37 virtual ~SkQuadTree(); |
32 | 38 |
33 /** | 39 /** |
34 * Insert a node, consisting of bounds and a data value into the tree, if we
don't immediately | 40 * Insert a node, consisting of bounds and a data value into the tree, if we
don't immediately |
35 * need to use the tree; we may allow the insert to be deferred (this can al
low us to bulk-load | 41 * need to use the tree; we may allow the insert to be deferred (this can al
low us to bulk-load |
36 * a large batch of nodes at once, which tends to be faster and produce a be
tter tree). | 42 * a large batch of nodes at once, which tends to be faster and produce a be
tter tree). |
37 * @param data The data value | 43 * @param data The data value |
38 * @param bounds The corresponding bounding box | 44 * @param bounds The corresponding bounding box |
39 * @param defer Can this insert be deferred? (this may be ignored) | 45 * @param defer Can this insert be deferred? (this may be ignored) |
40 */ | 46 */ |
41 virtual void insert(void* data, const SkIRect& bounds, bool defer = false) S
K_OVERRIDE; | 47 virtual void insert(void* data, const SkIRect& bounds, bool defer = false) S
K_OVERRIDE; |
42 | 48 |
43 /** | 49 /** |
44 * If any inserts have been deferred, this will add them into the tree | 50 * If any inserts have been deferred, this will add them into the tree |
45 */ | 51 */ |
46 virtual void flushDeferredInserts() SK_OVERRIDE {} | 52 virtual void flushDeferredInserts() SK_OVERRIDE; |
47 | 53 |
48 /** | 54 /** |
49 * Given a query rectangle, populates the passed-in array with the elements
it intersects | 55 * Given a query rectangle, populates the passed-in array with the elements
it intersects |
50 */ | 56 */ |
51 virtual void search(const SkIRect& query, SkTDArray<void*>* results) SK_OVER
RIDE; | 57 virtual void search(const SkIRect& query, SkTDArray<void*>* results) SK_OVER
RIDE; |
52 | 58 |
53 virtual void clear() SK_OVERRIDE; | 59 virtual void clear() SK_OVERRIDE; |
54 | 60 |
55 /** | 61 /** |
56 * Gets the depth of the tree structure | 62 * Gets the depth of the tree structure |
57 */ | 63 */ |
58 virtual int getDepth() const SK_OVERRIDE; | 64 virtual int getDepth() const SK_OVERRIDE; |
59 | 65 |
60 /** | 66 /** |
61 * This gets the insertion count (rather than the node count) | 67 * This gets the insertion count (rather than the node count) |
62 */ | 68 */ |
63 virtual int getCount() const SK_OVERRIDE { return fCount; } | 69 virtual int getCount() const SK_OVERRIDE { return fEntryCount; } |
64 | 70 |
65 virtual void rewindInserts() SK_OVERRIDE; | 71 virtual void rewindInserts() SK_OVERRIDE; |
66 | 72 |
67 private: | 73 private: |
68 class QuadTreeNode; | 74 struct Entry { |
| 75 Entry() : fData(NULL) {} |
| 76 SkIRect fBounds; |
| 77 void* fData; |
| 78 SK_DECLARE_INTERNAL_SLIST_INTERFACE(Entry); |
| 79 }; |
69 | 80 |
70 SkQuadTree(const SkIRect& bounds); | 81 static const int kChildCount = 4; |
71 | 82 |
72 // This is the count of data elements (rather than total nodes in the tree) | 83 struct Node { |
73 int fCount; | 84 Node() { |
| 85 for (int index=0; index<kChildCount; ++index) { |
| 86 fChildren[index] = NULL; |
| 87 } |
| 88 } |
| 89 SkTInternalSList<Entry> fEntries; |
| 90 SkIRect fBounds; |
| 91 SkIPoint fSplitPoint; // Only valid if the node has children. |
| 92 Node* fChildren[kChildCount]; |
| 93 SK_DECLARE_INTERNAL_SLIST_ADAPTER(Node, fChildren[0]); |
| 94 }; |
74 | 95 |
75 QuadTreeNode* fRoot; | 96 SkTObjectPool<Entry> fEntryPool; |
| 97 SkTObjectPool<Node> fNodePool; |
| 98 int fEntryCount; |
| 99 Node* fRoot; |
| 100 SkTInternalSList<Entry> fDeferred; |
| 101 |
| 102 Node* pickChild(Node* node, const SkIRect& bounds) const; |
| 103 void insert(Node* node, Entry* entry); |
| 104 void search(Node* node, const SkIRect& query, SkTDArray<void*>* results) con
st; |
| 105 void clear(Node* node); |
| 106 int getDepth(Node* node) const; |
76 | 107 |
77 typedef SkBBoxHierarchy INHERITED; | 108 typedef SkBBoxHierarchy INHERITED; |
78 }; | 109 }; |
79 | 110 |
80 #endif | 111 #endif |
OLD | NEW |