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