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