SkRTree.h revision 158fcaa031d105dc999d9813fee8927db56a871c 
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    virtual void insert(SkAutoTMalloc<SkRect>* boundsArray, int N) SK_OVERRIDE;
45    virtual void search(const SkRect& query, SkTDArray<unsigned>* results) const SK_OVERRIDE;
46    virtual size_t bytesUsed() const SK_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    // These values were empirically determined to produce reasonable performance in most cases.
56    static const int kMinChildren = 6,
57                     kMaxChildren = 11;
58
59private:
60    struct Node;
61
62    struct Branch {
63        union {
64            Node* fSubtree;
65            unsigned fOpIndex;
66        };
67        SkRect fBounds;
68    };
69
70    struct Node {
71        uint16_t fNumChildren;
72        uint16_t fLevel;
73        Branch fChildren[kMaxChildren];
74    };
75
76    void search(Node* root, const SkRect& query, SkTDArray<unsigned>* results) const;
77
78    // Consumes the input array.
79    Branch bulkLoad(SkTDArray<Branch>* branches, int level = 0);
80
81    // How many times will bulkLoad() call allocateNodeAtLevel()?
82    static int CountNodes(int branches, SkScalar aspectRatio);
83
84    Node* allocateNodeAtLevel(uint16_t level);
85
86    // This is the count of data elements (rather than total nodes in the tree)
87    int fCount;
88    SkScalar fAspectRatio;
89    Branch fRoot;
90    SkTDArray<Node> fNodes;
91
92    typedef SkBBoxHierarchy INHERITED;
93};
94
95#endif
96