src/ui/gfx/geometry/r_tree.h

   1 // Copyright 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_