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 "SkBBoxHierarchy.h" 12 #include "SkRect.h" 13 #include "SkTDArray.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 34 35 /** 36 * If you have some prior information about the distribution of bounds you're expecting, you 37 * can provide an optional aspect ratio parameter. This allows the bulk-load algorithm to 38 * create better proportioned tiles of rectangles. 39 */ 40 explicit SkRTree(SkScalar aspectRatio = 1); ~SkRTree()41 ~SkRTree() override {} 42 43 void insert(const SkRect[], int N) override; 44 void search(const SkRect& query, SkTDArray<int>* results) const override; 45 size_t bytesUsed() const override; 46 47 // Methods and constants below here are only public for tests. 48 49 // Return the depth of the tree structure. getDepth()50 int getDepth() const { return fCount ? fRoot.fSubtree->fLevel + 1 : 0; } 51 // Insertion count (not overall node count, which may be greater). getCount()52 int getCount() const { return fCount; } 53 54 // Get the root bound. 55 SkRect getRootBound() const override; 56 57 // These values were empirically determined to produce reasonable performance in most cases. 58 static const int kMinChildren = 6, 59 kMaxChildren = 11; 60 61 private: 62 struct Node; 63 64 struct Branch { 65 union { 66 Node* fSubtree; 67 int fOpIndex; 68 }; 69 SkRect fBounds; 70 }; 71 72 struct Node { 73 uint16_t fNumChildren; 74 uint16_t fLevel; 75 Branch fChildren[kMaxChildren]; 76 }; 77 78 void search(Node* root, const SkRect& query, SkTDArray<int>* results) const; 79 80 // Consumes the input array. 81 Branch bulkLoad(SkTDArray<Branch>* branches, int level = 0); 82 83 // How many times will bulkLoad() call allocateNodeAtLevel()? 84 static int CountNodes(int branches, SkScalar aspectRatio); 85 86 Node* allocateNodeAtLevel(uint16_t level); 87 88 // This is the count of data elements (rather than total nodes in the tree) 89 int fCount; 90 SkScalar fAspectRatio; 91 Branch fRoot; 92 SkTDArray<Node> fNodes; 93 94 typedef SkBBoxHierarchy INHERITED; 95 }; 96 97 #endif 98