cobalt / cobalt / 07c204f02a8437b2b0d3a3536a986b4ee0f3c2e1 / . / src / cobalt / math / r_tree_base.h

// 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 COBALT_MATH_R_TREE_BASE_H_ | |

#define COBALT_MATH_R_TREE_BASE_H_ | |

#include <vector> | |

#include "base/hash_tables.h" | |

#include "base/memory/scoped_ptr.h" | |

#include "base/memory/scoped_vector.h" | |

#include "cobalt/math/rect.h" | |

namespace cobalt { | |

namespace math { | |

class 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 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 RecordBase : public NodeBase { | |

public: | |

explicit RecordBase(const Rect& rect); | |

virtual ~RecordBase(); | |

virtual void AppendIntersectingRecords(const Rect& query_rect, | |

Records* records_out) const OVERRIDE; | |

virtual void AppendAllRecords(Records* records_out) const OVERRIDE; | |

virtual scoped_ptr<NodeBase> RemoveAndReturnLastChild() OVERRIDE; | |

virtual int Level() const OVERRIDE; | |

private: | |

friend class RTreeTest; | |

friend class RTreeNodeTest; | |

DISALLOW_COPY_AND_ASSIGN(RecordBase); | |

}; | |

class Node : public NodeBase { | |

public: | |

// Constructs an empty Node with |level_| of 0. | |

Node(); | |

virtual ~Node(); | |

virtual void AppendIntersectingRecords(const Rect& query_rect, | |

Records* records_out) const OVERRIDE; | |

virtual scoped_ptr<NodeBase> RemoveAndReturnLastChild() OVERRIDE; | |

virtual int Level() const OVERRIDE; | |

virtual 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); | |

virtual 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 math | |

} // namespace cobalt | |

#endif // COBALT_MATH_R_TREE_BASE_H_ |