OLD | NEW |
1 // Copyright (c) 2015 The Chromium Authors. All rights reserved. | 1 // Copyright (c) 2015 The Chromium Authors. All rights reserved. |
2 // Use of this source code is governed by a BSD-style license that can be | 2 // Use of this source code is governed by a BSD-style license that can be |
3 // found in the LICENSE file. | 3 // found in the LICENSE file. |
4 | 4 |
5 #ifndef CC_BASE_RTREE_H_ | 5 #ifndef CC_BASE_RTREE_H_ |
6 #define CC_BASE_RTREE_H_ | 6 #define CC_BASE_RTREE_H_ |
7 | 7 |
8 #include <stddef.h> | 8 #include <stddef.h> |
9 #include <stdint.h> | 9 #include <stdint.h> |
10 | 10 |
11 #include <vector> | 11 #include <vector> |
12 | 12 |
13 #include "cc/base/cc_export.h" | 13 #include "cc/base/base_export.h" |
14 #include "ui/gfx/geometry/rect.h" | 14 #include "ui/gfx/geometry/rect.h" |
15 | 15 |
16 namespace cc { | 16 namespace cc { |
17 | 17 |
18 // The following description and most of the implementation is borrowed from | 18 // The following description and most of the implementation is borrowed from |
19 // Skia's SkRTree implementation. | 19 // Skia's SkRTree implementation. |
20 // | 20 // |
21 // An R-Tree implementation. In short, it is a balanced n-ary tree containing a | 21 // An R-Tree implementation. In short, it is a balanced n-ary tree containing a |
22 // hierarchy of bounding rectangles. | 22 // hierarchy of bounding rectangles. |
23 // | 23 // |
24 // It only supports bulk-loading, i.e. creation from a batch of bounding | 24 // It only supports bulk-loading, i.e. creation from a batch of bounding |
25 // rectangles. This performs a bottom-up bulk load using the STR | 25 // rectangles. This performs a bottom-up bulk load using the STR |
26 // (sort-tile-recursive) algorithm. | 26 // (sort-tile-recursive) algorithm. |
27 // | 27 // |
28 // Things to do: Experiment with other bulk-load algorithms (in particular the | 28 // Things to do: Experiment with other bulk-load algorithms (in particular the |
29 // Hilbert pack variant, which groups rects by position on the Hilbert curve, is | 29 // Hilbert pack variant, which groups rects by position on the Hilbert curve, is |
30 // probably worth a look). There also exist top-down bulk load variants | 30 // probably worth a look). There also exist top-down bulk load variants |
31 // (VAMSplit, TopDownGreedy, etc). | 31 // (VAMSplit, TopDownGreedy, etc). |
32 // | 32 // |
33 // For more details see: | 33 // For more details see: |
34 // | 34 // |
35 // Beckmann, N.; Kriegel, H. P.; Schneider, R.; Seeger, B. (1990). | 35 // Beckmann, N.; Kriegel, H. P.; Schneider, R.; Seeger, B. (1990). |
36 // "The R*-tree: an efficient and robust access method for points and | 36 // "The R*-tree: an efficient and robust access method for points and |
37 // rectangles" | 37 // rectangles" |
38 class CC_EXPORT RTree { | 38 class CC_BASE_EXPORT RTree { |
39 public: | 39 public: |
40 RTree(); | 40 RTree(); |
41 ~RTree(); | 41 ~RTree(); |
42 | 42 |
43 template <typename Container, typename Functor> | 43 template <typename Container, typename Functor> |
44 void Build(const Container& items, const Functor& bounds_getter) { | 44 void Build(const Container& items, const Functor& bounds_getter) { |
45 DCHECK_EQ(0u, num_data_elements_); | 45 DCHECK_EQ(0u, num_data_elements_); |
46 | 46 |
47 std::vector<Branch> branches; | 47 std::vector<Branch> branches; |
48 branches.reserve(items.size()); | 48 branches.reserve(items.size()); |
(...skipping 79 matching lines...) Expand 10 before | Expand all | Expand 10 after Loading... |
128 std::vector<size_t>* results) const; | 128 std::vector<size_t>* results) const; |
129 | 129 |
130 // Consumes the input array. | 130 // Consumes the input array. |
131 Branch BuildRecursive(std::vector<Branch>* branches, int level); | 131 Branch BuildRecursive(std::vector<Branch>* branches, int level); |
132 Node* AllocateNodeAtLevel(int level); | 132 Node* AllocateNodeAtLevel(int level); |
133 | 133 |
134 // This is the count of data elements (rather than total nodes in the tree) | 134 // This is the count of data elements (rather than total nodes in the tree) |
135 size_t num_data_elements_; | 135 size_t num_data_elements_; |
136 Branch root_; | 136 Branch root_; |
137 std::vector<Node> nodes_; | 137 std::vector<Node> nodes_; |
| 138 |
| 139 DISALLOW_COPY_AND_ASSIGN(RTree); |
138 }; | 140 }; |
139 | 141 |
140 } // namespace cc | 142 } // namespace cc |
141 | 143 |
142 #endif // CC_BASE_RTREE_H_ | 144 #endif // CC_BASE_RTREE_H_ |
OLD | NEW |