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 */
32class SkRTree : public SkBBoxHierarchy {
33public:
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);
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.
51    int getDepth() const { return fCount ? fRoot.fSubtree->fLevel + 1 : 0; }
52    // Insertion count (not overall node count, which may be greater).
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
62private:
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