1 
2 /*
3  * Copyright 2012 Google Inc.
4  *
5  * Use of this source code is governed by a BSD-style license that can be
6  * found in the LICENSE file.
7  */
8 
9 #ifndef SkRTree_DEFINED
10 #define SkRTree_DEFINED
11 
12 #include "SkBBoxHierarchy.h"
13 #include "SkRect.h"
14 #include "SkTDArray.h"
15 
16 /**
17  * An R-Tree implementation. In short, it is a balanced n-ary tree containing a hierarchy of
18  * bounding rectangles.
19  *
20  * It only supports bulk-loading, i.e. creation from a batch of bounding rectangles.
21  * This performs a bottom-up bulk load using the STR (sort-tile-recursive) algorithm.
22  *
23  * TODO: Experiment with other bulk-load algorithms (in particular the Hilbert pack variant,
24  * which groups rects by position on the Hilbert curve, is probably worth a look). There also
25  * exist top-down bulk load variants (VAMSplit, TopDownGreedy, etc).
26  *
27  * For more details see:
28  *
29  *  Beckmann, N.; Kriegel, H. P.; Schneider, R.; Seeger, B. (1990). "The R*-tree:
30  *      an efficient and robust access method for points and rectangles"
31  */
32 class SkRTree : public SkBBoxHierarchy {
33 public:
34     SK_DECLARE_INST_COUNT(SkRTree)
35 
36     /**
37      * If you have some prior information about the distribution of bounds you're expecting, you
38      * can provide an optional aspect ratio parameter. This allows the bulk-load algorithm to
39      * create better proportioned tiles of rectangles.
40      */
41     explicit SkRTree(SkScalar aspectRatio = 1);
~SkRTree()42     virtual ~SkRTree() {}
43 
44     void insert(const SkRect[], int N) override;
45     void search(const SkRect& query, SkTDArray<unsigned>* results) const override;
46     size_t bytesUsed() const override;
47 
48     // Methods and constants below here are only public for tests.
49 
50     // Return the depth of the tree structure.
getDepth()51     int getDepth() const { return fCount ? fRoot.fSubtree->fLevel + 1 : 0; }
52     // Insertion count (not overall node count, which may be greater).
getCount()53     int getCount() const { return fCount; }
54 
55     // Get the root bound.
56     SkRect getRootBound() const override;
57 
58     // These values were empirically determined to produce reasonable performance in most cases.
59     static const int kMinChildren = 6,
60                      kMaxChildren = 11;
61 
62 private:
63     struct Node;
64 
65     struct Branch {
66         union {
67             Node* fSubtree;
68             unsigned fOpIndex;
69         };
70         SkRect fBounds;
71     };
72 
73     struct Node {
74         uint16_t fNumChildren;
75         uint16_t fLevel;
76         Branch fChildren[kMaxChildren];
77     };
78 
79     void search(Node* root, const SkRect& query, SkTDArray<unsigned>* results) const;
80 
81     // Consumes the input array.
82     Branch bulkLoad(SkTDArray<Branch>* branches, int level = 0);
83 
84     // How many times will bulkLoad() call allocateNodeAtLevel()?
85     static int CountNodes(int branches, SkScalar aspectRatio);
86 
87     Node* allocateNodeAtLevel(uint16_t level);
88 
89     // This is the count of data elements (rather than total nodes in the tree)
90     int fCount;
91     SkScalar fAspectRatio;
92     Branch fRoot;
93     SkTDArray<Node> fNodes;
94 
95     typedef SkBBoxHierarchy INHERITED;
96 };
97 
98 #endif
99