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