OLD | NEW |
(Empty) | |
| 1 // Copyright (c) 2014 The Chromium Authors. All rights reserved. |
| 2 // Use of this source code is governed by a BSD-style license that can be |
| 3 // found in the LICENSE file. |
| 4 |
| 5 #ifndef UI_GFX_GEOMETRY_R_TREE_H_ |
| 6 #define UI_GFX_GEOMETRY_R_TREE_H_ |
| 7 |
| 8 #include <vector> |
| 9 |
| 10 #include "base/containers/hash_tables.h" |
| 11 #include "base/gtest_prod_util.h" |
| 12 #include "base/macros.h" |
| 13 #include "base/memory/scoped_ptr.h" |
| 14 #include "base/memory/scoped_vector.h" |
| 15 #include "ui/gfx/geometry/rect.h" |
| 16 #include "ui/gfx/gfx_export.h" |
| 17 |
| 18 namespace gfx { |
| 19 |
| 20 // Defines a heirarchical bounding rectangle data structure for Rect objects, |
| 21 // associated with a generic unique key K for efficient spatial queries. The |
| 22 // R*-tree algorithm is used to build the trees. Based on the papers: |
| 23 // |
| 24 // A Guttman 'R-trees: a dynamic index structure for spatial searching', Proc |
| 25 // ACM SIGMOD Int Conf on Management of Data, 47-57, 1984 |
| 26 // |
| 27 // N Beckmann, H-P Kriegel, R Schneider, B Seeger 'The R*-tree: an efficient and |
| 28 // robust access method for points and rectangles', Proc ACM SIGMOD Int Conf on |
| 29 // Management of Data, 322-331, 1990 |
| 30 class GFX_EXPORT RTree { |
| 31 public: |
| 32 RTree(size_t min_children, size_t max_children); |
| 33 ~RTree(); |
| 34 |
| 35 // Insert a new rect into the tree, associated with provided key. Note that if |
| 36 // rect is empty, this rect will not actually be inserted. Duplicate keys |
| 37 // overwrite old entries. |
| 38 void Insert(const Rect& rect, intptr_t key); |
| 39 |
| 40 // If present, remove the supplied key from the tree. |
| 41 void Remove(intptr_t key); |
| 42 |
| 43 // Fills a supplied list matches_out with all keys having bounding rects |
| 44 // intersecting query_rect. |
| 45 void Query(const Rect& query_rect, |
| 46 base::hash_set<intptr_t>* matches_out) const; |
| 47 |
| 48 // Removes all objects from the tree. |
| 49 void Clear(); |
| 50 |
| 51 private: |
| 52 // Private data structure class for storing internal nodes or leaves with keys |
| 53 // of R-Trees. Note that "leaf" nodes can still have children, the children |
| 54 // will all be Nodes with non-NULL record pointers. |
| 55 class GFX_EXPORT Node { |
| 56 public: |
| 57 // Level counts from -1 for "record" Nodes, that is Nodes that wrap key |
| 58 // values, to 0 for leaf Nodes, that is Nodes that only have record |
| 59 // children, up to the root Node, which has level equal to the height of the |
| 60 // tree. |
| 61 explicit Node(int level); |
| 62 |
| 63 // Builds a new record Node. |
| 64 Node(const Rect& rect, intptr_t key); |
| 65 |
| 66 virtual ~Node(); |
| 67 |
| 68 // Deletes all children and any attached record. |
| 69 void Clear(); |
| 70 |
| 71 // Recursive call to build a list of rects that intersect the query_rect. |
| 72 void Query(const Rect& query_rect, |
| 73 base::hash_set<intptr_t>* matches_out) const; |
| 74 |
| 75 // Recompute our bounds by taking the union of all children rects. Will then |
| 76 // call RecomputeBounds() on our parent for recursive bounds recalculation |
| 77 // up to the root. |
| 78 void RecomputeBounds(); |
| 79 |
| 80 // Removes number_to_remove nodes from this Node, and appends them to the |
| 81 // supplied list. Does not repair bounds upon completion. |
| 82 void RemoveNodesForReinsert(size_t number_to_remove, |
| 83 ScopedVector<Node>* nodes); |
| 84 |
| 85 // Given a pointer to a child node within this Node, remove it from our |
| 86 // list. If that child had any children, append them to the supplied orphan |
| 87 // list. Returns the new count of this node after removal. Does not |
| 88 // recompute bounds, as this node itself may be removed if it now has too |
| 89 // few children. |
| 90 size_t RemoveChild(Node* child_node, ScopedVector<Node>* orphans); |
| 91 |
| 92 // Does what it says on the tin. Returns NULL if no children. Does not |
| 93 // recompute bounds. |
| 94 scoped_ptr<Node> RemoveAndReturnLastChild(); |
| 95 |
| 96 // Given a node, returns the best fit node for insertion of that node at |
| 97 // the nodes level(). |
| 98 Node* ChooseSubtree(Node* node); |
| 99 |
| 100 // Adds the provided node to this Node. Returns the new count of records |
| 101 // stored in the Node. Will recompute the bounds of this node after |
| 102 // addition. |
| 103 size_t AddChild(Node* node); |
| 104 |
| 105 // Returns a sibling to this Node with at least min_children and no greater |
| 106 // than max_children of this Node's children assigned to it, and having the |
| 107 // same parent. Bounds will be valid on both Nodes after this call. |
| 108 Node* Split(size_t min_children, size_t max_children); |
| 109 |
| 110 // For record nodes only, to support re-insert, allows setting the rect. |
| 111 void SetRect(const Rect& rect); |
| 112 |
| 113 // Returns a pointer to the parent of this Node, or NULL if no parent. |
| 114 Node* parent() const { return parent_; } |
| 115 |
| 116 // 0 level() would mean that this Node is a leaf. 1 would mean that this |
| 117 // Node has children that are leaves. Calling level() on root_ returns the |
| 118 // height of the tree - 1. A level of -1 means that this is a Record node. |
| 119 int level() const { return level_; } |
| 120 |
| 121 const Rect& rect() const { return rect_; } |
| 122 |
| 123 size_t count() const { return children_.size(); } |
| 124 |
| 125 intptr_t key() const { return key_; } |
| 126 |
| 127 private: |
| 128 // Returns all records stored in this node and its children. |
| 129 void GetAllValues(base::hash_set<intptr_t>* matches_out) const; |
| 130 |
| 131 // Used for sorting Nodes along vertical and horizontal axes |
| 132 static bool CompareVertical(Node* a, Node* b); |
| 133 |
| 134 static bool CompareHorizontal(Node* a, Node* b); |
| 135 |
| 136 static bool CompareCenterDistanceFromParent(Node* a, Node* b); |
| 137 |
| 138 // Returns the increase in overlap value, as defined in Beckmann et al as |
| 139 // the sum of the areas of the intersection of each |children_| rectangle |
| 140 // (excepting the candidate child) with the argument rectangle. The |
| 141 // expanded_rect argument is computed as the union of the candidate child |
| 142 // rect and the argument rect, and is included here to avoid recomputation. |
| 143 // Here the candidate child is indicated by index in |children_|, and |
| 144 // expanded_rect is the alread-computed union of candidate's rect and |
| 145 // rect. |
| 146 int OverlapIncreaseToAdd(const Rect& rect, |
| 147 size_t candidate, |
| 148 const Rect& expanded_rect); |
| 149 |
| 150 // Bounds recomputation without calling parents to do the same. |
| 151 void RecomputeBoundsNoParents(); |
| 152 |
| 153 // Split() helper methods. |
| 154 // |
| 155 // Given two vectors of Nodes sorted by vertical or horizontal bounds, this |
| 156 // function populates two vectors of Rectangles in which the ith element is |
| 157 // the Union of all bounding rectangles [0,i] in the associated sorted array |
| 158 // of Nodes. |
| 159 static void BuildLowBounds(const std::vector<Node*>& vertical_sort, |
| 160 const std::vector<Node*>& horizontal_sort, |
| 161 std::vector<Rect>* vertical_bounds, |
| 162 std::vector<Rect>* horizontal_bounds); |
| 163 |
| 164 // Given two vectors of Nodes sorted by vertical or horizontal bounds, this |
| 165 // function populates two vectors of Rectangles in which the ith element is |
| 166 // the Union of all bounding rectangles [i, count()) in the associated |
| 167 // sorted array of Nodes. |
| 168 static void BuildHighBounds(const std::vector<Node*>& vertical_sort, |
| 169 const std::vector<Node*>& horizontal_sort, |
| 170 std::vector<Rect>* vertical_bounds, |
| 171 std::vector<Rect>* horizontal_bounds); |
| 172 |
| 173 // Returns true if this is a vertical split, false if a horizontal one. |
| 174 // Based on ChooseSplitAxis algorithm in Beckmann et al. Chooses the axis |
| 175 // with the lowest sum of margin values of bounding boxes. |
| 176 static bool ChooseSplitAxis(const std::vector<Rect>& low_vertical_bounds, |
| 177 const std::vector<Rect>& high_vertical_bounds, |
| 178 const std::vector<Rect>& low_horizontal_bounds, |
| 179 const std::vector<Rect>& high_horizontal_bounds, |
| 180 size_t min_children, |
| 181 size_t max_children); |
| 182 |
| 183 // Used by SplitNode to calculate optimal index of split, after determining |
| 184 // along which axis to sort and split the children rectangles. Returns the |
| 185 // index to the first element in the split children as sorted by the bounds |
| 186 // vectors. |
| 187 static size_t ChooseSplitIndex(size_t min_children, |
| 188 size_t max_children, |
| 189 const std::vector<Rect>& low_bounds, |
| 190 const std::vector<Rect>& high_bounds); |
| 191 |
| 192 // Takes our children_ and divides them into a new node, starting at index |
| 193 // split_index in sorted_children. |
| 194 Node* DivideChildren(const std::vector<Rect>& low_bounds, |
| 195 const std::vector<Rect>& high_bounds, |
| 196 const std::vector<Node*>& sorted_children, |
| 197 size_t split_index); |
| 198 |
| 199 // Returns a pointer to the child node that will result in the least overlap |
| 200 // increase with the addition of node_rect, as defined in the Beckmann et al |
| 201 // paper, or NULL if there's a tie found. Requires a precomputed vector of |
| 202 // expanded rectangles where the ith rectangle in the vector is the union of |
| 203 // |children_|[i] and node_rect. |
| 204 Node* LeastOverlapIncrease(const Rect& node_rect, |
| 205 const std::vector<Rect>& expanded_rects); |
| 206 |
| 207 // Returns a pointer to the child node that will result in the least area |
| 208 // enlargement if the argument node rectangle were to be added to that |
| 209 // nodes' bounding box. Requires a precomputed vector of expanded rectangles |
| 210 // where the ith rectangle in the vector is the union of |children_|[i] and |
| 211 // node_rect. |
| 212 Node* LeastAreaEnlargement(const Rect& node_rect, |
| 213 const std::vector<Rect>& expanded_rects); |
| 214 |
| 215 // This Node's bounding rectangle. |
| 216 Rect rect_; |
| 217 |
| 218 // The height of the node in the tree, counting from -1 at the record node |
| 219 // to 0 at the leaf up to the root node which has level equal to the height |
| 220 // of the tree. |
| 221 int level_; |
| 222 |
| 223 // Pointers to all of our children Nodes. |
| 224 ScopedVector<Node> children_; |
| 225 |
| 226 // A weak pointer to our parent Node in the RTree. The root node will have a |
| 227 // NULL value for |parent_|. |
| 228 Node* parent_; |
| 229 |
| 230 // If this is a record Node, then |key_| will be non-NULL and will contain |
| 231 // the key data. Otherwise, NULL. |
| 232 intptr_t key_; |
| 233 |
| 234 friend class RTreeTest; |
| 235 FRIEND_TEST_ALL_PREFIXES(RTreeTest, NodeBuildHighBounds); |
| 236 FRIEND_TEST_ALL_PREFIXES(RTreeTest, NodeBuildLowBounds); |
| 237 FRIEND_TEST_ALL_PREFIXES(RTreeTest, NodeChooseSplitAxisAndIndex); |
| 238 FRIEND_TEST_ALL_PREFIXES(RTreeTest, NodeChooseSubtree); |
| 239 FRIEND_TEST_ALL_PREFIXES(RTreeTest, NodeCompareCenterDistanceFromParent); |
| 240 FRIEND_TEST_ALL_PREFIXES(RTreeTest, NodeCompareHorizontal); |
| 241 FRIEND_TEST_ALL_PREFIXES(RTreeTest, NodeCompareVertical); |
| 242 FRIEND_TEST_ALL_PREFIXES(RTreeTest, NodeDivideChildren); |
| 243 FRIEND_TEST_ALL_PREFIXES(RTreeTest, NodeLeastAreaEnlargement); |
| 244 FRIEND_TEST_ALL_PREFIXES(RTreeTest, NodeLeastOverlapIncrease); |
| 245 FRIEND_TEST_ALL_PREFIXES(RTreeTest, NodeOverlapIncreaseToAdd); |
| 246 FRIEND_TEST_ALL_PREFIXES(RTreeTest, NodeRemoveAndReturnLastChild); |
| 247 FRIEND_TEST_ALL_PREFIXES(RTreeTest, NodeRemoveChildNoOrphans); |
| 248 FRIEND_TEST_ALL_PREFIXES(RTreeTest, NodeRemoveChildOrphans); |
| 249 FRIEND_TEST_ALL_PREFIXES(RTreeTest, NodeRemoveNodesForReinsert); |
| 250 FRIEND_TEST_ALL_PREFIXES(RTreeTest, NodeSplit); |
| 251 |
| 252 DISALLOW_COPY_AND_ASSIGN(Node); |
| 253 }; |
| 254 |
| 255 // Supports re-insertion of Nodes based on the strategies outlined in |
| 256 // Beckmann et al. |
| 257 void InsertNode(Node* node, int* highset_reinsert_level); |
| 258 |
| 259 // Supports removal of nodes for tree without deletion. |
| 260 void RemoveNode(Node* node); |
| 261 |
| 262 // A pointer to the root node in the RTree. |
| 263 scoped_ptr<Node> root_; |
| 264 |
| 265 // The parameters used to define the shape of the RTree. |
| 266 size_t min_children_; |
| 267 size_t max_children_; |
| 268 |
| 269 // A map of supplied keys to their Node representation within the RTree, for |
| 270 // efficient retrieval of keys without requiring a bounding rect. |
| 271 base::hash_map<intptr_t, Node*> record_map_; |
| 272 |
| 273 friend class RTreeTest; |
| 274 FRIEND_TEST_ALL_PREFIXES(RTreeTest, NodeBuildHighBounds); |
| 275 FRIEND_TEST_ALL_PREFIXES(RTreeTest, NodeBuildLowBounds); |
| 276 FRIEND_TEST_ALL_PREFIXES(RTreeTest, NodeChooseSplitAxisAndIndex); |
| 277 FRIEND_TEST_ALL_PREFIXES(RTreeTest, NodeChooseSubtree); |
| 278 FRIEND_TEST_ALL_PREFIXES(RTreeTest, NodeCompareCenterDistanceFromParent); |
| 279 FRIEND_TEST_ALL_PREFIXES(RTreeTest, NodeCompareHorizontal); |
| 280 FRIEND_TEST_ALL_PREFIXES(RTreeTest, NodeCompareVertical); |
| 281 FRIEND_TEST_ALL_PREFIXES(RTreeTest, NodeDivideChildren); |
| 282 FRIEND_TEST_ALL_PREFIXES(RTreeTest, NodeLeastAreaEnlargement); |
| 283 FRIEND_TEST_ALL_PREFIXES(RTreeTest, NodeLeastOverlapIncrease); |
| 284 FRIEND_TEST_ALL_PREFIXES(RTreeTest, NodeOverlapIncreaseToAdd); |
| 285 FRIEND_TEST_ALL_PREFIXES(RTreeTest, NodeRemoveAndReturnLastChild); |
| 286 FRIEND_TEST_ALL_PREFIXES(RTreeTest, NodeRemoveChildNoOrphans); |
| 287 FRIEND_TEST_ALL_PREFIXES(RTreeTest, NodeRemoveChildOrphans); |
| 288 FRIEND_TEST_ALL_PREFIXES(RTreeTest, NodeRemoveNodesForReinsert); |
| 289 FRIEND_TEST_ALL_PREFIXES(RTreeTest, NodeSplit); |
| 290 |
| 291 DISALLOW_COPY_AND_ASSIGN(RTree); |
| 292 }; |
| 293 |
| 294 } // namespace gfx |
| 295 |
| 296 #endif // UI_GFX_GEOMETRY_R_TREE_H_ |
OLD | NEW |