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/SkBBHFactory.h"
12#include "include/core/SkRect.h"
13
14/**
15 * An R-Tree implementation. In short, it is a balanced n-ary tree containing a hierarchy of
16 * bounding rectangles.
17 *
18 * It only supports bulk-loading, i.e. creation from a batch of bounding rectangles.
19 * This performs a bottom-up bulk load using the STR (sort-tile-recursive) algorithm.
20 *
21 * TODO: Experiment with other bulk-load algorithms (in particular the Hilbert pack variant,
22 * which groups rects by position on the Hilbert curve, is probably worth a look). There also
23 * exist top-down bulk load variants (VAMSplit, TopDownGreedy, etc).
24 *
25 * For more details see:
26 *
27 * Beckmann, N.; Kriegel, H. P.; Schneider, R.; Seeger, B. (1990). "The R*-tree:
28 * an efficient and robust access method for points and rectangles"
29 */
30class SkRTree : public SkBBoxHierarchy {
31public:
32 SkRTree();
33
34 void insert(const SkRect[], int N) override;
35 void search(const SkRect& query, std::vector<int>* results) const override;
36 size_t bytesUsed() const override;
37
38 // Methods and constants below here are only public for tests.
39
40 // Return the depth of the tree structure.
41 int getDepth() const { return fCount ? fRoot.fSubtree->fLevel + 1 : 0; }
42 // Insertion count (not overall node count, which may be greater).
43 int getCount() const { return fCount; }
44
45 // These values were empirically determined to produce reasonable performance in most cases.
46 static const int kMinChildren = 6,
47 kMaxChildren = 11;
48
49private:
50 struct Node;
51
52 struct Branch {
53 union {
54 Node* fSubtree;
55 int fOpIndex;
56 };
57 SkRect fBounds;
58 };
59
60 struct Node {
61 uint16_t fNumChildren;
62 uint16_t fLevel;
63 Branch fChildren[kMaxChildren];
64 };
65
66 void search(Node* root, const SkRect& query, std::vector<int>* results) const;
67
68 // Consumes the input array.
69 Branch bulkLoad(std::vector<Branch>* branches, int level = 0);
70
71 // How many times will bulkLoad() call allocateNodeAtLevel()?
72 static int CountNodes(int branches);
73
74 Node* allocateNodeAtLevel(uint16_t level);
75
76 // This is the count of data elements (rather than total nodes in the tree)
77 int fCount;
78 Branch fRoot;
79 std::vector<Node> fNodes;
80};
81
82#endif
83