| 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 84 matching lines...) Expand 10 before | Expand all | Expand 10 after Loading... |
| 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 }; | 138 }; |
| 139 | 139 |
| 140 } // namespace cc | 140 } // namespace cc |
| 141 | 141 |
| 142 #endif // CC_BASE_RTREE_H_ | 142 #endif // CC_BASE_RTREE_H_ |
| OLD | NEW |