1 /* 2 * Copyright 2012 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 SkRTree_DEFINED 9 #define SkRTree_DEFINED 10 11 #include "include/core/SkRect.h" 12 #include "include/private/SkTDArray.h" 13 #include "src/core/SkBBoxHierarchy.h" 14 15 /** 16 * An R-Tree implementation. In short, it is a balanced n-ary tree containing a hierarchy of 17 * bounding rectangles. 18 * 19 * It only supports bulk-loading, i.e. creation from a batch of bounding rectangles. 20 * This performs a bottom-up bulk load using the STR (sort-tile-recursive) algorithm. 21 * 22 * TODO: Experiment with other bulk-load algorithms (in particular the Hilbert pack variant, 23 * which groups rects by position on the Hilbert curve, is probably worth a look). There also 24 * exist top-down bulk load variants (VAMSplit, TopDownGreedy, etc). 25 * 26 * For more details see: 27 * 28 * Beckmann, N.; Kriegel, H. P.; Schneider, R.; Seeger, B. (1990). "The R*-tree: 29 * an efficient and robust access method for points and rectangles" 30 */ 31 class SkRTree : public SkBBoxHierarchy { 32 public: 33 SkRTree(); ~SkRTree()34 ~SkRTree() override {} 35 36 void insert(const SkRect[], int N) override; 37 void search(const SkRect& query, SkTDArray<int>* results) const override; 38 size_t bytesUsed() const override; 39 40 // Methods and constants below here are only public for tests. 41 42 // Return the depth of the tree structure. getDepth()43 int getDepth() const { return fCount ? fRoot.fSubtree->fLevel + 1 : 0; } 44 // Insertion count (not overall node count, which may be greater). getCount()45 int getCount() const { return fCount; } 46 47 // Get the root bound. 48 SkRect getRootBound() const override; 49 50 // These values were empirically determined to produce reasonable performance in most cases. 51 static const int kMinChildren = 6, 52 kMaxChildren = 11; 53 54 private: 55 struct Node; 56 57 struct Branch { 58 union { 59 Node* fSubtree; 60 int fOpIndex; 61 }; 62 SkRect fBounds; 63 }; 64 65 struct Node { 66 uint16_t fNumChildren; 67 uint16_t fLevel; 68 Branch fChildren[kMaxChildren]; 69 }; 70 71 void search(Node* root, const SkRect& query, SkTDArray<int>* results) const; 72 73 // Consumes the input array. 74 Branch bulkLoad(SkTDArray<Branch>* branches, int level = 0); 75 76 // How many times will bulkLoad() call allocateNodeAtLevel()? 77 static int CountNodes(int branches); 78 79 Node* allocateNodeAtLevel(uint16_t level); 80 81 // This is the count of data elements (rather than total nodes in the tree) 82 int fCount; 83 Branch fRoot; 84 SkTDArray<Node> fNodes; 85 86 typedef SkBBoxHierarchy INHERITED; 87 }; 88 89 #endif 90