1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 109 110 111 112 113 114 115 116 117 118 119 120 121 122 123 124 125 126 127 128 129 130 131 132 133 134 135 136 137 138 139 140 141 142 143 144 145 146 147 148 149 150 151 152 153 154 155 156 157 158 159 160 161 162 163 164 165 166 167 168 169 170 171 172 173 174 175 176 177 178 179 180 181 182 183 184 185 186 187 188 189 190 191 192 193 194 195 196 197 198 199 200 201 202 203 204 205 206 207 208 209 210 211 212 213 214 215 216 217 218 219 220 221 222 223 224 225 226 227 228 229 230 231 232 233 234 235 236 237 238 239 240 241 242 243 244 245 246 247 248 249 250 251 252 253 254 255 256 257 258 259 260 261 262 263 264 265 266 267 268 269 270 271 272 273 274 275 276 277 278 279 280 281 282 283 284 285 286 287 288 289 290 291 292 293 294 295 296 297 298 299 300 301 302 303 304 305 306 307 308 309
|
// Copyright 2014 The Chromium Authors. All rights reserved.
// Use of this source code is governed by a BSD-style license that can be
// found in the LICENSE file.
// Provides an implementation the parts of the RTree data structure that don't
// require knowledge of the generic key type. Don't use these objects directly,
// rather specialize the RTree<> object in r_tree.h. This file defines the
// internal objects of an RTree, namely Nodes (internal nodes of the tree) and
// Records, which hold (key, rectangle) pairs.
#ifndef UI_GFX_GEOMETRY_R_TREE_BASE_H_
#define UI_GFX_GEOMETRY_R_TREE_BASE_H_
#include <list>
#include <vector>
#include "base/containers/hash_tables.h"
#include "base/macros.h"
#include "base/memory/scoped_ptr.h"
#include "base/memory/scoped_vector.h"
#include "ui/gfx/geometry/rect.h"
#include "ui/gfx/gfx_export.h"
namespace gfx {
class GFX_EXPORT RTreeBase {
protected:
class NodeBase;
class RecordBase;
typedef std::vector<const RecordBase*> Records;
typedef ScopedVector<NodeBase> Nodes;
RTreeBase(size_t min_children, size_t max_children);
~RTreeBase();
// Protected data structure class for storing internal Nodes or leaves with
// Records.
class GFX_EXPORT NodeBase {
public:
virtual ~NodeBase();
// Appends to |records_out| the set of Records in this subtree with rects
// that intersect |query_rect|. Avoids clearing |records_out| so that it
// can be called recursively.
virtual void AppendIntersectingRecords(const Rect& query_rect,
Records* records_out) const = 0;
// Returns all records stored in the subtree rooted at this node. Appends to
// |matches_out| without clearing.
virtual void AppendAllRecords(Records* records_out) const = 0;
// Returns NULL if no children. Does not recompute bounds.
virtual scoped_ptr<NodeBase> RemoveAndReturnLastChild() = 0;
// Returns -1 for Records, or the height of this subtree for Nodes. The
// height of a leaf Node (a Node containing only Records) is 0, a leaf's
// parent is 1, etc. Note that in an R*-Tree, all branches from the root
// Node will be the same height.
virtual int Level() const = 0;
// Recomputes our bounds by taking the union of all child rects, then calls
// recursively on our parent so that ultimately all nodes up to the root
// recompute their bounds.
void RecomputeBoundsUpToRoot();
NodeBase* parent() { return parent_; }
const NodeBase* parent() const { return parent_; }
void set_parent(NodeBase* parent) { parent_ = parent; }
const Rect& rect() const { return rect_; }
void set_rect(const Rect& rect) { rect_ = rect; }
protected:
NodeBase(const Rect& rect, NodeBase* parent);
// Bounds recomputation without calling parents to do the same.
virtual void RecomputeLocalBounds();
private:
friend class RTreeTest;
friend class RTreeNodeTest;
// This Node's bounding rectangle.
Rect rect_;
// A weak pointer to our parent Node in the RTree. The root node will have a
// NULL value for |parent_|.
NodeBase* parent_;
DISALLOW_COPY_AND_ASSIGN(NodeBase);
};
class GFX_EXPORT RecordBase : public NodeBase {
public:
explicit RecordBase(const Rect& rect);
~RecordBase() override;
void AppendIntersectingRecords(const Rect& query_rect,
Records* records_out) const override;
void AppendAllRecords(Records* records_out) const override;
scoped_ptr<NodeBase> RemoveAndReturnLastChild() override;
int Level() const override;
private:
friend class RTreeTest;
friend class RTreeNodeTest;
DISALLOW_COPY_AND_ASSIGN(RecordBase);
};
class GFX_EXPORT Node : public NodeBase {
public:
// Constructs an empty Node with |level_| of 0.
Node();
~Node() override;
void AppendIntersectingRecords(const Rect& query_rect,
Records* records_out) const override;
scoped_ptr<NodeBase> RemoveAndReturnLastChild() override;
int Level() const override;
void AppendAllRecords(Records* matches_out) const override;
// Constructs a new Node that is the parent of this Node and already has
// this Node as its sole child. Valid to call only on root Nodes, meaning
// Nodes with |parent_| NULL. Note that ownership of this Node is
// transferred to the parent returned by this function.
scoped_ptr<Node> ConstructParent();
// Removes |number_to_remove| children from this Node, and appends them to
// the supplied list. Does not repair bounds upon completion. Nodes are
// selected in the manner suggested in the Beckmann et al. paper, which
// suggests that the children should be sorted by the distance from the
// center of their bounding rectangle to their parent's bounding rectangle,
// and then the n closest children should be removed for re-insertion. This
// removal occurs at most once on each level of the tree when overflowing
// nodes that have exceeded the maximum number of children during an Insert.
void RemoveNodesForReinsert(size_t number_to_remove, Nodes* nodes);
// Given a pointer to a child node within this Node, removes it from our
// list. If that child had any children, appends them to the supplied orphan
// list. Returns the removed child. Does not recompute bounds, as the caller
// might subsequently remove this node as well, meaning the recomputation
// would be wasted work.
scoped_ptr<NodeBase> RemoveChild(NodeBase* child_node, Nodes* orphans);
// Returns the best parent for insertion of the provided |node| as a child.
Node* ChooseSubtree(NodeBase* node);
// Adds |node| as a child of this Node, and recomputes the bounds of this
// node after the addition of the child. Returns the new count of children
// stored in this Node. This node becomes the owner of |node|.
size_t AddChild(scoped_ptr<NodeBase> node);
// Returns a sibling to this Node with at least min_children and no greater
// than max_children of this Node's children assigned to it, and having the
// same parent. Bounds will be valid on both Nodes after this call.
scoped_ptr<NodeBase> Split(size_t min_children, size_t max_children);
size_t count() const { return children_.size(); }
const NodeBase* child(size_t i) const { return children_[i]; }
NodeBase* child(size_t i) { return children_[i]; }
private:
typedef std::vector<Rect> Rects;
explicit Node(int level);
// Given two arrays of bounds rectangles as computed by BuildLowBounds()
// and BuildHighBounds(), returns the index of the element in those arrays
// along which a split of the arrays would result in a minimum amount of
// overlap (area of intersection) in the two groups.
static size_t ChooseSplitIndex(size_t start_index,
size_t end_index,
const Rects& low_bounds,
const Rects& high_bounds);
// R*-Tree attempts to keep groups of rectangles that are roughly square
// in shape. It does this by comparing the "margins" of different bounding
// boxes, where margin is defined as the sum of the length of all four sides
// of a rectangle. For two rectangles of equal area, the one with the
// smallest margin will be the rectangle whose width and height differ the
// least. When splitting we decide to split along an axis chosen from the
// rectangles either sorted vertically or horizontally by finding the axis
// that would result in the smallest sum of margins between the two bounding
// boxes of the resulting split. Returns the smallest sum computed given the
// sorted bounding boxes and a range to look within.
static int SmallestMarginSum(size_t start_index,
size_t end_index,
const Rects& low_bounds,
const Rects& high_bounds);
// Sorts nodes primarily by increasing y coordinates, and secondarily by
// increasing height.
static bool CompareVertical(const NodeBase* a, const NodeBase* b);
// Sorts nodes primarily by increasing x coordinates, and secondarily by
// increasing width.
static bool CompareHorizontal(const NodeBase* a, const NodeBase* b);
// Sorts nodes by the distance of the center of their rectangles to the
// center of their parent's rectangles.
static bool CompareCenterDistanceFromParent(
const NodeBase* a, const NodeBase* b);
// Given two vectors of Nodes sorted by vertical or horizontal bounds,
// populates two vectors of Rectangles in which the ith element is the union
// of all bounding rectangles [0,i] in the associated sorted array of Nodes.
static void BuildLowBounds(const std::vector<NodeBase*>& vertical_sort,
const std::vector<NodeBase*>& horizontal_sort,
Rects* vertical_bounds,
Rects* horizontal_bounds);
// Given two vectors of Nodes sorted by vertical or horizontal bounds,
// populates two vectors of Rectangles in which the ith element is the
// union of all bounding rectangles [i, count()) in the associated sorted
// array of Nodes.
static void BuildHighBounds(const std::vector<NodeBase*>& vertical_sort,
const std::vector<NodeBase*>& horizontal_sort,
Rects* vertical_bounds,
Rects* horizontal_bounds);
void RecomputeLocalBounds() override;
// Returns the increase in overlap value, as defined in Beckmann et al. as
// the sum of the areas of the intersection of all child rectangles
// (excepting the candidate child) with the argument rectangle. Here the
// |candidate_node| is one of our |children_|, and |expanded_rect| is the
// already-computed union of the candidate's rect and |rect|.
int OverlapIncreaseToAdd(const Rect& rect,
const NodeBase* candidate_node,
const Rect& expanded_rect) const;
// Returns a new node containing children [split_index, count()) within
// |sorted_children|. Children before |split_index| remain with |this|.
scoped_ptr<NodeBase> DivideChildren(
const Rects& low_bounds,
const Rects& high_bounds,
const std::vector<NodeBase*>& sorted_children,
size_t split_index);
// Returns a pointer to the child node that will result in the least overlap
// increase with the addition of node_rect, or NULL if there's a tie found.
// Requires a precomputed vector of expanded rectangles where the ith
// rectangle in the vector is the union of |children_|[i] and node_rect.
// Overlap is defined in Beckmann et al. as the sum of the areas of
// intersection of all child rectangles with the |node_rect| argument
// rectangle. This heuristic attempts to choose the node for which adding
// the new rectangle to their bounding box will result in the least overlap
// with the other rectangles, thus trying to preserve the usefulness of the
// bounding rectangle by keeping it from covering too much redundant area.
Node* LeastOverlapIncrease(const Rect& node_rect,
const Rects& expanded_rects);
// Returns a pointer to the child node that will result in the least area
// enlargement if the argument node rectangle were to be added to that
// node's bounding box. Requires a precomputed vector of expanded rectangles
// where the ith rectangle in the vector is the union of children_[i] and
// |node_rect|.
Node* LeastAreaEnlargement(const Rect& node_rect,
const Rects& expanded_rects);
const int level_;
Nodes children_;
friend class RTreeTest;
friend class RTreeNodeTest;
DISALLOW_COPY_AND_ASSIGN(Node);
};
// Inserts |node| into the tree. The |highest_reinsert_level| supports
// re-insertion as described by Beckmann et al. As Node overflows progagate
// up the tree the algorithm performs a reinsertion of the overflow Nodes
// (instead of a split) at most once per level of the tree. A starting value
// of -1 for |highest_reinsert_level| means that reinserts are permitted for
// every level of the tree. This should always be set to -1 except by
// recursive calls from within InsertNode().
void InsertNode(scoped_ptr<NodeBase> node, int* highest_reinsert_level);
// Removes |node| from the tree without deleting it.
scoped_ptr<NodeBase> RemoveNode(NodeBase* node);
// If |root_| has only one child, deletes the |root_| Node and replaces it
// with its only descendant child. Otherwise does nothing.
void PruneRootIfNecessary();
// Deletes the entire current tree and replaces it with an empty Node.
void ResetRoot();
const Node* root() const { return root_.get(); }
private:
friend class RTreeTest;
friend class RTreeNodeTest;
// A pointer to the root node in the RTree.
scoped_ptr<Node> root_;
// The parameters used to define the shape of the RTree.
const size_t min_children_;
const size_t max_children_;
DISALLOW_COPY_AND_ASSIGN(RTreeBase);
};
} // namespace gfx
#endif // UI_GFX_GEOMETRY_R_TREE_BASE_H_
|