OLD | NEW |
(Empty) | |
| 1 /* |
| 2 * Copyright 2014 Google Inc. |
| 3 * |
| 4 * Use of this source code is governed by a BSD-style license that can be |
| 5 * found in the LICENSE file. |
| 6 */ |
| 7 |
| 8 #ifndef SkQuadTree_DEFINED |
| 9 #define SkQuadTree_DEFINED |
| 10 |
| 11 #include "SkRect.h" |
| 12 #include "SkTDArray.h" |
| 13 #include "SkBBoxHierarchy.h" |
| 14 |
| 15 /** |
| 16 * An QuadTree implementation. In short, it is a tree containing a hierarchy of
bounding rectangles |
| 17 * in which each internal node has exactly four children. |
| 18 * |
| 19 * For more details see: |
| 20 * |
| 21 * http://en.wikipedia.org/wiki/Quadtree |
| 22 */ |
| 23 class SkQuadTree : public SkBBoxHierarchy { |
| 24 public: |
| 25 SK_DECLARE_INST_COUNT(SkQuadTree) |
| 26 |
| 27 /** |
| 28 * Create a new QuadTree |
| 29 */ |
| 30 static SkQuadTree* Create(const SkIRect& bounds); |
| 31 virtual ~SkQuadTree(); |
| 32 |
| 33 /** |
| 34 * 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 |
| 36 * a large batch of nodes at once, which tends to be faster and produce a be
tter tree). |
| 37 * @param data The data value |
| 38 * @param bounds The corresponding bounding box |
| 39 * @param defer Can this insert be deferred? (this may be ignored) |
| 40 */ |
| 41 virtual void insert(void* data, const SkIRect& bounds, bool defer = false) S
K_OVERRIDE; |
| 42 |
| 43 /** |
| 44 * If any inserts have been deferred, this will add them into the tree |
| 45 */ |
| 46 virtual void flushDeferredInserts() SK_OVERRIDE {} |
| 47 |
| 48 /** |
| 49 * Given a query rectangle, populates the passed-in array with the elements
it intersects |
| 50 */ |
| 51 virtual void search(const SkIRect& query, SkTDArray<void*>* results) SK_OVER
RIDE; |
| 52 |
| 53 virtual void clear() SK_OVERRIDE; |
| 54 |
| 55 /** |
| 56 * Gets the depth of the tree structure |
| 57 */ |
| 58 virtual int getDepth() const SK_OVERRIDE; |
| 59 |
| 60 /** |
| 61 * This gets the insertion count (rather than the node count) |
| 62 */ |
| 63 virtual int getCount() const SK_OVERRIDE { return fCount; } |
| 64 |
| 65 virtual void rewindInserts() SK_OVERRIDE; |
| 66 |
| 67 private: |
| 68 class QuadTreeNode; |
| 69 |
| 70 SkQuadTree(const SkIRect& bounds); |
| 71 |
| 72 // This is the count of data elements (rather than total nodes in the tree) |
| 73 int fCount; |
| 74 |
| 75 QuadTreeNode* fRoot; |
| 76 |
| 77 typedef SkBBoxHierarchy INHERITED; |
| 78 }; |
| 79 |
| 80 #endif |
OLD | NEW |