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