Adds an RTree data structure to gfx/geometry

ui/gfx/geometry/r_tree.cc

+// Copyright (c) 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.
+
+#include "ui/gfx/geometry/r_tree.h"
+
+#include <algorithm>
+#include <limits>
+
+#include "base/logging.h"
+
+namespace gfx {
+
+RTree::Node::Node(int level)
+    : base::LinkNode<Node>(),
+      level_(level),
+      count_(0),
+      parent_(NULL),
+      key_(NULL) {}
+
+RTree::Node::Node(const Rect& rect, void* key)
+    : base::LinkNode<Node>(),
+      rect_(rect),
+      level_(-1),
+      count_(0),
+      parent_(NULL),
+      key_(key) {}
+
+RTree::Node::~Node() {
+  Clear();
+}
+
+void RTree::Node::Clear() {
+  // Iterate through children and delete them all.
+  while (children_.head() != children_.end()) {
+    base::LinkNode<Node>* node = children_.head();
+    node->RemoveFromList();
+    delete node->value();
+  }
+  key_ = NULL;
+}
+
+void RTree::Node::Query(
+    const Rect& query_rect, std::set<void*>* matches_out) const {
+  // Check own bounding box for intersection, can cull all children if no
+  // intersection.
+  if (!rect_.Intersects(query_rect)) {
+    return;
+  }
+
+  // Conversely if we are completely contained within the query rect we can
+  // confidently skip all bounds checks for ourselves and all our children.
+  if (query_rect.Contains(rect_)) {
+    GetAllValues(matches_out);
+    return;
+  }
+
+  // We intersect the query rect but we are not are not contained within it.
+  // If we are a record node, then add our record value. Otherwise we must
+  // query each of our children in turn.
+  if (key_) {
+    DCHECK_EQ(level_, -1);
+    matches_out->insert(key_);
+  } else {
+    for (base::LinkNode<Node>* link_node = children_.head();
+         link_node != children_.end();
+         link_node = link_node->next()) {
+      Node* node = link_node->value();
+      // Sanity-check our children.
+      DCHECK_EQ(node->parent_, this);
+      DCHECK_EQ(level_ - 1, node->level_);
+      DCHECK(rect_.Contains(node->rect_));
+      node->Query(query_rect, matches_out);
+    }
+  }
+}
+
+void RTree::Node::RecomputeBounds() {
+  RecomputeBoundsNoParents();
+  // Recompute our parent's bounds recursively up to the root.
+  if (parent_) {
+    parent_->RecomputeBounds();
+  }
+}
+
+void RTree::Node::RemoveNodesForReinsert(
+    size_t number_to_remove, std::list<Node*>* nodes) {

[piman, 2014/04/21 23:59:31]

Why not std::vector<Node*>? You know the size ahead of time, so you can even
reserve() the vector.

[luken, 2014/04/28 01:33:34]

Done.

+  DCHECK_GE(count_, number_to_remove);
+  // Sort our children in descending order of distance from our bounding
+  // rect center to their bounding rect center.
+  std::vector<Node*> center_sort;
+  center_sort.reserve(count_);
+  // copy points to our children into each array.
+  for (base::LinkNode<Node>* link_node = children_.head();
+       link_node != children_.end();
+       link_node = link_node->next()) {
+    center_sort.push_back(link_node->value());
+  }
+  DCHECK_EQ(count_, center_sort.size());
+  std::sort(center_sort.begin(),
+            center_sort.end(),
+            &RTree::Node::CompareCenterDistanceFromParent);
+  // Remove the highest distance nodes from our children list, and then add them
+  // to the returned list.
+  for (size_t i = 0; i < number_to_remove; ++i) {
+    center_sort[i]->RemoveFromList();
+    nodes->push_back(center_sort[i]);
+  }
+  // Update our internal references including bounds.
+  count_ = count_ - number_to_remove;
+}
+
+size_t RTree::Node::RemoveChild(Node* child_node, std::list<Node*>* orphans) {

[piman, 2014/04/21 23:59:31]

std::vector here too? You also know the size.

[luken, 2014/04/28 01:33:34]

Done.

+  // Should actually be one of our children.
+  DCHECK_EQ(child_node->parent_, this);
+  // Remove any children of this child and append to orphans list.
+  Node* orphan = child_node->RemoveAndReturnFirstChild();
+  while (orphan) {
+    orphans->push_back(orphan);
+    orphan = child_node->RemoveAndReturnFirstChild();
+  }

[piman, 2014/04/21 23:59:31]

It seems like we could simply walk the list of children, can't we?
It would alleviate some of the overhead of calling a function for each child,
and factor some of the processing (e.g. updating child_node's count_).

[luken, 2014/04/28 01:33:34]

Done.

+  child_node->RemoveFromList();
+  count_--;
+  return count_;
+}
+
+RTree::Node* RTree::Node::RemoveAndReturnFirstChild() {
+  if (children_.head() == children_.end()) {
+    return NULL;
+  }
+  Node* first_child = children_.head()->value();
+  DCHECK_EQ(first_child->parent_, this);
+  first_child->RemoveFromList();

[piman, 2014/04/21 23:59:31]

Do we need to --count_ ?

[luken, 2014/04/28 01:33:34]

Done.

+  // Invalidate parent, as this child may even become the new root.
+  first_child->parent_ = NULL;
+  return first_child;
+}
+
+// Uses the R*-Tree algorithm CHOOSELEAF proposed by Beckmann et al.
+RTree::Node* RTree::Node::ChooseSubtree(Node* node) {
+  // Should never be called on a record node.
+  DCHECK(!key_);
+  DCHECK(level_ >= 0);
+  DCHECK(node);
+
+  // If we are a parent of nodes on the provided node level, we are done.
+  if (level_ == node->level_ + 1) {
+    return this;
+  }
+  // We are an internal node, and thus guaranteed to have children.
+  DCHECK(children_.head() != children_.end());
+
+  // Iterate over all children to find best candidate for insertion.
+  Node* best_candidate = NULL;
+  int least_overlap_increase = std::numeric_limits<int>::max();
+  int least_area_change = std::numeric_limits<int>::max();
+  for (base::LinkNode<Node>* link_node = children_.head();
+       link_node != children_.end();
+       link_node = link_node->next()) {
+    Node* candidate_node = link_node->value();
+    // All of our children should be at our level - 1.
+    DCHECK_EQ(level_ - 1, candidate_node->level_);
+    // All of our children should have us as a parent.
+    DCHECK_EQ(this, candidate_node->parent_);
+    int overlap_increase = std::numeric_limits<int>::max();
+    // For Nodes whose children are leaves, we calculate minimum overlap
+    // increase caused by addition of this new record Node.
+    if (!candidate_node->level_) {

[piman, 2014/04/21 23:59:31]

This is a loop constant (given checks above). Can we optimize a bit by breaking
down into smaller functions, and move the check out of the loop?

[luken, 2014/04/28 01:33:34]

So the algorithm calls for node selection using minimum overlap increase only on
leaves, but asks that we break ties using the non-leaf node selection algorithm
of minimum area change to add, breaking ties in that with least area. I broke
the overlap increase out to a function, for better readability. Particularly
given your observation that with hierarchical bounding boxes overlap increase is
likely to be 0 frequently we need to continue to break leaf ties with the
non-leaf code.

+      // Expand candidate rect to include the new node rect.
+      Rect expanded_rect = candidate_node->rect_;
+      expanded_rect.Union(node->rect_);

[piman, 2014/04/21 23:59:31]

If node->rect_ is fully contained in candidate_node->rect_, then you found the
best candidate, which lets you avoid the O(n) inner loop, and (on average) half
of the outer loop. Because of the hierarchical bounding boxes, this seems like a
fairly common case, is it worth specializing?

[luken, 2014/04/28 01:33:34]

Yes, good observation, done.

+      int total_original_overlap = 0;
+      int total_expanded_overlap = 0;
+
+      // Now calculate overlap with all other rects in this node.
+      for (base::LinkNode<Node>* overlap_link_node = children_.head();
+           overlap_link_node != children_.end();
+           overlap_link_node = overlap_link_node->next()) {
+        Node* overlap_node = overlap_link_node->value();
+        // Skip calculating overlap with the candidate rect.
+        if (overlap_node == candidate_node) {
+          continue;
+        }
+        Rect overlap_rect = candidate_node->rect_;
+        overlap_rect.Intersect(overlap_node->rect_);
+        total_original_overlap += overlap_rect.width() * overlap_rect.height();

[piman, 2014/04/21 23:59:31]

nit: overlap_rect.size().GetArea()
(other places too).

[luken, 2014/04/28 01:33:34]

Done.

+        Rect expanded_overlap_rect = expanded_rect;
+        expanded_overlap_rect.Intersect(overlap_node->value()->rect_);

[piman, 2014/04/21 23:59:31]

overlap_node->rect_?

[luken, 2014/04/28 01:33:34]

Done.

+        total_expanded_overlap +=
+            expanded_overlap_rect.width() * expanded_overlap_rect.height();
+      }
+
+      // Compare this overlap increase with best one to date, update best.
+      overlap_increase = total_expanded_overlap - total_original_overlap;
+      if (overlap_increase < least_overlap_increase) {
+        best_candidate = candidate_node->value();

[piman, 2014/04/21 23:59:31]

no ->value()

[luken, 2014/04/28 01:33:34]

Done.

+        least_overlap_increase = overlap_increase;
+        least_area_change = AreaChangeToAdd(candidate_node->rect_, node->rect_);

[piman, 2014/04/21 23:59:31]

AreaChangeToAdd computes the union bounds, that we already computed on line 170.
Can we just compute
expanded_rect.size().GetArea()-candidate_node->rect_.size().GetArea() ?

[piman, 2014/04/21 23:59:31]

you probably want a continue here.
the rest of the loop will trigger (because at this point least_overlap_increase
== overlap_increasem and candidate_area_change == least_area_change), leading to
more computations that can only cause best_candidate = candidate_node, which is
already the case.

[luken, 2014/04/28 01:33:34]

I don't quite understand this. This code is not in the inner loop, is that what
you were thinking we should continue out of?

[luken, 2014/04/28 01:33:34]

Done.

+      }
+    }
+
+    // For non-leaf internal nodes, or for leafs that are tied, we choose least
+    // area enlargement required to add this rect.
+    if (candidate_node->level_ > 0 ||
+        overlap_increase == least_overlap_increase) {

[piman, 2014/04/21 23:59:31]

This is always true if candidate_node->level_ > 0 (because in that case, both
overlap_increase and least_overlap_increase are
std::numeric_limits<int>::max()). So maybe you can skip that test and/or factor
the candidate_node->level_ > 0 case out of the loop (see above).

[luken, 2014/04/28 01:33:34]

The candidadate_node->level_ == 0 case needs this code to resolve (frequent!)
ties in overlap increase.

+       int candidate_area_change =
+          AreaChangeToAdd(candidate_node->rect_, node->rect_);

[piman, 2014/04/21 23:59:31]

You already computed expanded_rect in the (candidate_node->level_ == 0) case, so
you might as well move that computation out of the if test and reuse it here.

[luken, 2014/04/28 01:33:34]

Done.

+      if (candidate_area_change < least_area_change) {
+        best_candidate = candidate_node;
+        least_area_change = candidate_area_change;
+      } else if (candidate_area_change == least_area_change) {
+        // It is assumed we will always tie with a valid candidate.
+        DCHECK(best_candidate);
+        // Ties are broken by choosing entry with least area
+        if (candidate_node->rect_.width() * candidate_node->rect_.height() <
+            best_candidate->rect_.width() * best_candidate->rect_.height()) {
+          best_candidate = candidate_node;
+        }
+      }
+    }
+  }
+
+  DCHECK(best_candidate);
+  return best_candidate->ChooseSubtree(node);
+}
+
+size_t RTree::Node::AddNode(Node* node) {
+  DCHECK(node);
+  // Sanity-check that the level of the child being added is one more than ours.
+  DCHECK_EQ(level_ - 1, node->level_);
+  node->parent_ = this;
+  children_.Append(node);
+  ++count_;
+  rect_.Union(node->rect_);
+  return count_;
+}
+
+RTree::Node* RTree::Node::Split(size_t min_children, size_t max_children) {
+  // Please don't attempt to split a record Node.
+  DCHECK(!key_);
+  // We should have the correct number of children to begin with.
+  DCHECK_GT(count_, max_children);
+  // First determine if splitting along the horizontal or vertical axis. We
+  // sort the rectangles of our children by lower then upper values along each
+  // axis.
+  std::vector<Node*> horizontal_sort;
+  std::vector<Node*> vertical_sort;
+  horizontal_sort.reserve(count_);
+  vertical_sort.reserve(count_);
+  // Copy pointers to our children into each array.
+  for (base::LinkNode<Node>* link_node = children_.head();
+       link_node != children_.end();
+       link_node = link_node->next()) {
+    Node* node = link_node->value();
+    DCHECK_EQ(node->parent_, this);
+    DCHECK_EQ(level_ - 1, node->level_);
+    horizontal_sort.push_back(node);
+    vertical_sort.push_back(node);
+  }
+  DCHECK_EQ(count_, horizontal_sort.size());
+  std::sort(horizontal_sort.begin(),
+            horizontal_sort.end(),
+            &RTree::Node::CompareHorizontal);
+  std::sort(vertical_sort.begin(),
+            vertical_sort.end(),
+            &RTree::Node::CompareVertical);
+
+  // We will be examining the bounding boxes of different splits of our children
+  // sorted along each axis. Here we precompute the bounding boxes of these
+  // distributions. For the low bounds the ith element can be considered the
+  // union of all rects [0,i] in the relevant sorted axis array.
+  std::vector<Rect> low_horizontal_bounds;
+  std::vector<Rect> low_vertical_bounds;
+  Rect horizontal_bounds;
+  Rect vertical_bounds;
+  low_horizontal_bounds.reserve(count_);
+  low_vertical_bounds.reserve(count_);
+  for (size_t i = 0; i < count_; ++i) {
+    horizontal_bounds.Union(horizontal_sort[i]->rect_);
+    vertical_bounds.Union(vertical_sort[i]->rect_);
+    low_horizontal_bounds.push_back(horizontal_bounds);
+    low_vertical_bounds.push_back(vertical_bounds);
+  }
+  // For the high bounds the ith element can be considered the union of all
+  // rects [i, count_) in the relevant sorted axis array.
+  std::vector<Rect> high_horizontal_bounds;
+  std::vector<Rect> high_vertical_bounds;
+  horizontal_bounds.SetRect(0, 0, 0, 0);
+  vertical_bounds.SetRect(0, 0, 0, 0);
+  high_horizontal_bounds.resize(count_);
+  high_vertical_bounds.resize(count_);
+  for (int j = static_cast<int>(count_) - 1; j >= 0; --j) {
+    horizontal_bounds.Union(horizontal_sort[j]->rect_);
+    vertical_bounds.Union(vertical_sort[j]->rect_);
+    high_horizontal_bounds[j] = horizontal_bounds;
+    high_vertical_bounds[j] = vertical_bounds;
+  }
+
+  // Examine the possible distributions of each sorted list by iterating through
+  // valid split points p, min_children <= p <= max_children - min_children, and
+  // computing the sums of the margins of the required bounding boxes in each
+  // group. Smallest margin sum will determine split axis.
+  int smallest_horizontal_margin_sum = std::numeric_limits<int>::max();
+  int smallest_vertical_margin_sum = std::numeric_limits<int>::max();
+  for (size_t p = min_children; p < max_children - min_children; ++p) {
+    int horizontal_margin_sum =
+        low_horizontal_bounds[p].width() + low_horizontal_bounds[p].height() +
+        high_horizontal_bounds[p].width() + high_horizontal_bounds[p].height();
+    int vertical_margin_sum =
+        low_vertical_bounds[p].width() + low_vertical_bounds[p].height() +
+        high_vertical_bounds[p].width() + high_vertical_bounds[p].height();
+    // Update margin minima if necessary.
+    smallest_horizontal_margin_sum =
+        std::min(horizontal_margin_sum, smallest_horizontal_margin_sum);
+    smallest_vertical_margin_sum =
+        std::min(vertical_margin_sum, smallest_vertical_margin_sum);
+  }
+
+  // Split along the axis perpendicular to the axis with the overall smallest
+  // margin sum. Meaning the axis sort resulting in two boxes with the smallest
+  // combined margin will become the axis along which the sorted rectangles are
+  // distributed to the two Nodes.
+  bool is_vertical_split =
+      smallest_vertical_margin_sum < smallest_horizontal_margin_sum;
+
+  // Lastly we determine optimal index.
+  size_t optimal_split_index;
+  if (is_vertical_split) {
+    optimal_split_index = CalculateOptimalSplitIndex(min_children,
+                                                     max_children,
+                                                     &low_vertical_bounds,
+                                                     &high_vertical_bounds);
+  } else {
+    optimal_split_index = CalculateOptimalSplitIndex(min_children,
+                                                     max_children,
+                                                     &low_horizontal_bounds,
+                                                     &high_horizontal_bounds);
+  }
+
+  // We have the optimal sort axis as well as the optimal index. Create the
+  // new Node and give it the latter half of our children.
+  Node* sibling = new Node(level_);
+  sibling->parent_ = parent_;
+  sibling->count_ = count_ - optimal_split_index - 1;
+  count_ = optimal_split_index + 1;
+  if (is_vertical_split) {
+    rect_ = low_vertical_bounds[optimal_split_index];
+    sibling->rect_ = high_vertical_bounds[optimal_split_index + 1];
+    // Give these children to our sibling.
+    for (size_t i = optimal_split_index + 1; i < vertical_sort.size(); ++i) {
+      Node* neice = vertical_sort[i];
+      neice->RemoveFromList();
+      neice->parent_ = sibling;
+      sibling->children_.Append(neice);
+    }
+  } else {
+    rect_ = low_horizontal_bounds[optimal_split_index];
+    sibling->rect_ = high_horizontal_bounds[optimal_split_index + 1];
+    for (size_t i = optimal_split_index + 1; i < horizontal_sort.size(); ++i) {
+      Node* nephew = horizontal_sort[i];
+      nephew->RemoveFromList();
+      nephew->parent_ = sibling;
+      sibling->children_.Append(nephew);
+    }
+  }
+
+  return sibling;
+}
+
+void RTree::Node::SetRect(const Rect& rect) {
+  // Record nodes only, please.
+  DCHECK(key_);
+  rect_ = rect;
+}
+
+RTree::Node* RTree::Node::parent() const {
+  return parent_;
+}
+
+int RTree::Node::level() const {
+  return level_;
+}
+
+const Rect& RTree::Node::rect() const {
+  return rect_;
+}
+
+size_t RTree::Node::count() const {
+  return count_;
+}
+
+bool RTree::Node::Validate(size_t min_children, size_t max_children) const {

[piman, 2014/04/21 23:59:31]

You can never return anything but true (by induction). Make it a void?
Alternatively, replace the DCHECKs by returning false. It'd be nice to test
things in release too.

[luken, 2014/04/28 01:33:34]

Yeah I didn't know that we run unit tests in release mode, which seems obvious
that we would now that I think about it.

Because I had to make RTreeTest a friend of this class I have moved the
Validate() methods over to RTreeTest and refactored them to use the EXPECT_*
testing macros. This seems a better fit.

+  // We don't call Validate() directly on Record nodes.
+  DCHECK(!key_);
+  // Need to have at least one child.
+  DCHECK_NE(children_.head(), children_.end());
+  // Independently compute a bounding rectangle, and make sure it is identical
+  // to our current bounding rectangle.
+  Rect bounds(0, 0, 0, 0);
+  size_t check_count = 0;
+  for (base::LinkNode<Node>* link_node = children_.head();
+       link_node != children_.end();
+       link_node = link_node->next()) {
+    check_count++;
+    Node* node = link_node->value();
+    bounds.Union(node->rect_);
+    DCHECK_EQ(node->parent_, this);
+    DCHECK_LE(node->count_, max_children);
+    DCHECK_EQ(level_ - 1, node->level_);
+    if (level_) {
+      DCHECK_GE(node->count_, min_children);
+      if (!node->Validate(min_children, max_children)) {
+        return false;
+      }
+    } else {
+      DCHECK_EQ(node->count_, 0U);
+      DCHECK_EQ(node->children_.head(), node->children_.end());
+      DCHECK(node->key_);
+    }
+  }
+  DCHECK_EQ(count_, check_count);
+  DCHECK(!rect_.IsEmpty());
+  DCHECK(rect_ == bounds);
+  return true;
+}
+
+// Returns all contained record_node values for this node and all children.
+void RTree::Node::GetAllValues(std::set<void*>* matches_out) const {
+  if (key_) {
+    DCHECK_EQ(level_, -1);
+    matches_out->insert(key_);
+  } else {
+    for (base::LinkNode<Node>* link_node = children_.head();
+         link_node != children_.end();
+         link_node = link_node->next()) {
+      Node* node = link_node->value();
+      // Sanity-check our children.
+      DCHECK_EQ(node->parent_, this);
+      DCHECK_EQ(level_ - 1, node->level_);
+      DCHECK(rect_.Contains(node->rect_));
+      node->GetAllValues(matches_out);
+    }
+  }
+}
+
+// static
+int RTree::Node::AreaChangeToAdd(const Rect& bounds, const Rect& rect) {

[piman, 2014/04/21 23:59:31]

nit: might as well make it a free function (in anonymous namespace) since it
doesn't need to access Node's internals.

[luken, 2014/04/28 01:33:34]

Done.

+  // Quick test for containment of rect in bounds, resulting in 0 area change.
+  if (bounds.Contains(rect)) {
+    return 0;
+  }
+  int current_area = bounds.width() * bounds.height();
+  Rect test_rect(bounds);
+  // Expand a copy of bounds to contain the new rectangle.
+  test_rect.Union(rect);
+  return (test_rect.width() * test_rect.height()) - current_area;
+}
+
+// static
+bool RTree::Node::CompareVertical(Node* a, Node* b) {
+  // Sort nodes by top coordinate first.
+  if (a->rect_.y() < b->rect_.y()) {
+    return true;
+  } else if (a->rect_.y() == b->rect_.y()) {
+    // If top coordinate is equal, sort by lowest bottom coordinate.
+    return a->rect_.bottom() < b->rect_.bottom();

[piman, 2014/04/21 23:59:31]

test height() instead of bottom(), since the latter involves an extra addition.

[luken, 2014/04/28 01:33:34]

Done.

+  }
+  return false;
+}
+
+// static
+bool RTree::Node::CompareHorizontal(Node* a, Node* b) {
+  // Sort nodes by left coordinate first.
+  if (a->rect_.x() < b->rect_.x()) {
+    return true;
+  } else if (a->rect_.x() == b->rect_.x()) {
+    // If left coordinate is equal, sort by lowest right coordinate.
+    return a->rect_.right() < b->rect_.right();

[piman, 2014/04/21 23:59:31]

test width() instead of right().

[luken, 2014/04/28 01:33:34]

Done.

+  }
+  return false;
+}
+
+// Sort these two nodes by the distance of the center of their rects from the
+// center of their parent's rect. We don't bother with square roots because we
+// are only comparing the two values for sorting purposes.
+// static
+bool RTree::Node::CompareCenterDistanceFromParent(Node* a, Node* b) {
+  // This comparison assumes the nodes have the same parent.
+  DCHECK(a->parent_ == b->parent_);
+  // This comparison requires that each node have a parent.
+  DCHECK(a->parent_);
+  // Sanity-check level_ of these nodes is equal.
+  DCHECK_EQ(a->level_, b->level_);
+  // Also the parent of the nodes should have level one higher.
+  DCHECK_EQ(a->level_, a->parent_->level_ - 1);
+
+  // Find the parent.
+  Node* p = a->parent();
+
+  // First we calculate the center of the parent rectangle.
+  int p_center_x = p->rect_.x() + (p->rect_.width() / 2);
+  int p_center_y = p->rect_.y() + (p->rect_.height() / 2);

[piman, 2014/04/21 23:59:31]

nit: it would be more readable to make a free inline function Point
CenterOfRect(const Rect& rect), then have
Point p_center = CenterOfRect(p->rect_);
Point a_center = CenterOfRect(a->rect_);
Point b_center = CenterOfRect(b->rect_);


and then return (a_center-p_center).LengthSquared() >
(b_center-p_center).LengthSquared();

[luken, 2014/04/28 01:33:34]

Done.

+
+  // Next we calculate the squared distance of a's center to p's center.
+  int a_dist_sq_x = a->rect_.x() + (a->rect_.width() / 2) - p_center_x;
+  a_dist_sq_x *= a_dist_sq_x;
+  int a_dist_sq_y = a->rect_.y() + (a->rect_.height() / 2) - p_center_y;
+  a_dist_sq_y *= a_dist_sq_y;
+
+  // Now we do the same for b.
+  int b_dist_sq_x = b->rect_.x() + (b->rect_.width() / 2) - p_center_x;
+  b_dist_sq_x *= b_dist_sq_x;
+  int b_dist_sq_y = b->rect_.y() + (b->rect_.height() / 2) - p_center_y;
+  b_dist_sq_y *= b_dist_sq_y;
+
+  // We are sorting by greatest to least distance so we invert the logic on the
+  // comparison.
+  return (a_dist_sq_x + a_dist_sq_y) > (b_dist_sq_x + b_dist_sq_y);
+}
+
+size_t RTree::Node::CalculateOptimalSplitIndex(
+    size_t min_children,
+    size_t max_children,
+    const std::vector<Rect>* low_bounds,
+    const std::vector<Rect>* high_bounds) {
+  int smallest_overlap_area = std::numeric_limits<int>::max();
+  int smallest_combined_area = std::numeric_limits<int>::max();
+  size_t optimal_split_index = 0;
+  for (size_t p = min_children; p < max_children - min_children; ++p) {
+    Rect overlap_bounds = low_bounds->at(p);
+    overlap_bounds.Union(high_bounds->at(p));
+    int overlap_area = overlap_bounds.width() * overlap_bounds.height();
+    if (overlap_area < smallest_overlap_area) {
+      smallest_overlap_area = overlap_area;
+      smallest_combined_area =
+          (low_bounds->at(p).width() * low_bounds->at(p).height()) +
+          (high_bounds->at(p).width() * high_bounds->at(p).height());
+      optimal_split_index = p;
+    } else if (overlap_area == smallest_overlap_area) {
+      // Break ties with smallest combined area of the two bounding boxes.
+      int combined_area =
+          (low_bounds->at(p).width() * low_bounds->at(p).height()) +
+          (high_bounds->at(p).width() * high_bounds->at(p).height());
+      if (combined_area < smallest_combined_area) {
+        smallest_combined_area = combined_area;
+        optimal_split_index = p;
+      }
+    }
+  }
+
+  return optimal_split_index;
+}
+
+void RTree::Node::RecomputeBoundsNoParents() {
+  // Clear our rectangle, then reset it to union of our children.
+  rect_.SetRect(0, 0, 0, 0);
+  for (base::LinkNode<Node>* node = children_.head(); node != children_.end();
+       node = node->next()) {
+    rect_.Union(node->value()->rect_);
+  }
+}
+
+RTree::RTree(size_t min_children, size_t max_children)
+    : root_(NULL), min_children_(min_children), max_children_(max_children) {
+  // R-Trees require min_children >= 2
+  DCHECK_GE(min_children_, 2U);
+  // R-Trees also require min_children <= max_children / 2
+  DCHECK_LE(min_children_, max_children_ / 2U);
+}
+
+RTree::~RTree() {
+  Clear();
+}
+
+void RTree::Insert(const Rect& rect, void* key) {
+  // Non-NULL keys, please.
+  DCHECK(key);
+
+  // An empty rectangle will never intersect with any other rectangle, and so
+  // has no purpose within a spatial database.
+  if (rect.IsEmpty())
+    return;

[piman, 2014/04/21 23:59:31]

That goes contrary to the tests below.
Either remove this test or remove the ones below, though the later means
Insert(empty_rect, key) where key as already in the tree would not update the
existing rect (which seems wrong?)

Please add a test case for this.

[luken, 2014/04/28 01:33:34]

yes, this one is a bug, good catch, removed. I added a test case,
InsertEmptyRectReplacementRemovesKey

+
+  Node* record_node = NULL;
+  // Check if this key is already present in the tree.
+  std::map<void*, Node*>::iterator it = record_map_.find(key);
+  if (it != record_map_.end()) {
+    // We will re-use this node structure, regardless of re-insert or return.
+    record_node = it->second;
+    // If the new rect and the current rect are identical we can skip rest of
+    // Insert() as nothing has changed.
+    if (record_node->rect() == rect) {
+      return;
+    }
+
+    // Remove the node from the tree in its current position.
+    Remove(record_node);
+
+    // If we are replacing this key with an empty rectangle we just remove the
+    // old node from the list and return, thus preventing insertion of empty
+    // rectangles into our spatial database.
+    if (rect.IsEmpty()) {
+      record_map_.erase(it);
+      delete record_node;
+      return;
+    }
+
+    // Reset the rectangle to the new value.
+    record_node->SetRect(rect);
+  } else {
+    if (rect.IsEmpty()) {
+      return;
+    }
+    // Build a new record Node for insertion in to tree.
+    record_node = new Node(rect, key);
+    // Add this new node to our map, for easy retrieval later.
+    record_map_.insert(std::make_pair(key, record_node));
+ }
+
+  // Make a root_ if needed.
+  if (!root_) {
+    root_ = new Node(0);

[piman, 2014/04/21 23:59:31]

Should we just do this in the constructor, and save the test here? I don't think
there's much to save memory-wise by having this lazily constructed, but you'll
pay the cost on every node, every time you rebuild the tree (and remove, and
queries, etc.).

[luken, 2014/04/28 01:33:34]

Done.

+  }
+
+  // Call internal Insert with this new node and no re-inserts for this
+  // of a data node having happened yet.
+  int starting_level = -1;
+  Insert(record_node, &starting_level);
+}
+
+void RTree::Remove(void* key) {
+  // Search the map for the leaf parent that has the provided record.
+  std::map<void*, Node*>::iterator it = record_map_.find(key);
+  // If not in the map it's not in the tree, we're done.
+  if (it == record_map_.end()) {
+    return;
+  }
+  Node* node = it->second;
+  // Remove this node from the map.
+  record_map_.erase(it);
+  // Now remove it from the RTree.
+  Remove(node);
+  delete node;
+
+  // Lastly check the root. If it has only one non-leaf child, delete it and
+  // replace it with its child. If it has no children, we can delete the
+  // entire empty tree.
+  if (root_->count() == 1 && root_->level() > 0) {
+    Node* new_root = root_->RemoveAndReturnFirstChild();
+    DCHECK(new_root);
+    delete root_;
+    root_ = new_root;
+  } else if (root_->count() == 0) {
+    delete root_;
+    root_ = NULL;
+  }
+}
+
+void RTree::Query(const Rect& query_rect, std::set<void*>* matches_out) const {
+  if (root_) {
+    root_->Query(query_rect, matches_out);
+  }
+}
+
+void RTree::Clear() {
+  record_map_.clear();
+  delete root_;
+  root_ = NULL;
+}
+
+void RTree::Insert(Node* node, int* highest_reinsert_level) {
+  // Internal Insert always assumes that a root has been created.
+  DCHECK(root_);
+  // Find the most appropriate parent to insert node into.
+  Node* parent = root_->ChooseSubtree(node);
+  DCHECK(parent);
+  // Verify ChooseSubtree returned a Node at the correct level.
+  DCHECK_EQ(parent->level(), node->level() + 1);
+  Node* insert_node = node;
+  Node* insert_parent = parent;
+  Node* needs_bounds_recomputed = insert_parent->parent();
+  std::list<Node*> reinserts;
+  // Attempt to insert the Node, if this overflows the Node we must handle it.
+  while (insert_parent && insert_parent->AddNode(insert_node) > max_children_) {
+    // If we have yet to re-insert nodes at this level during this data insert,
+    // and we're not at the root, R*-Tree calls for re-insertion of some of the
+    // nodes, resulting in a better balance on the tree.
+    if (insert_parent->parent() &&
+        insert_parent->level() > *highest_reinsert_level) {
+      insert_parent->RemoveNodesForReinsert(max_children_ / 3, &reinserts);
+      // Adjust highest_reinsert_level to this level.
+      *highest_reinsert_level = insert_parent->level();
+      // We didn't create any new nodes so we have nothing new to insert.
+      insert_node = NULL;
+      // RemoveNodesForReinsert() does not recompute bounds, so mark it.
+      needs_bounds_recomputed = insert_parent;
+      break;
+    }
+
+    // Split() will create a sibling to insert_parent both of which will have
+    // valid bounds, but this invalidates their parent's bounds.
+    insert_node = insert_parent->Split(min_children_, max_children_);
+    insert_parent = insert_parent->parent();
+    needs_bounds_recomputed = insert_parent;
+  }
+
+  // If we have a Node to insert, and we hit the root of the current tree,
+  // we create a new root which is the parent of the current root and the
+  // insert_node
+  if (!insert_parent && insert_node) {
+    Node* old_root = root_;
+    root_ = new Node(old_root->level() + 1);
+    root_->AddNode(old_root);
+    root_->AddNode(insert_node);
+  }
+
+  // Recompute bounds along insertion path.
+  if (needs_bounds_recomputed) {

[piman, 2014/04/21 23:59:31]

In which case can this be NULL?

[luken, 2014/04/28 01:33:34]

Two I can think of:

a) inserting direct child of the root without a split.
b) any insert resulting in a split of the root (which, granted, could be handled
as an else case to the above if on 710)

+    needs_bounds_recomputed->RecomputeBounds();

[piman, 2014/04/21 23:59:31]

If we have reinserts, we'll recompute bounds for part of the tree multiple times
(at least once more for each later insert). Is there a way to avoid this, e.g.
keep track of nodes that changed, and recompute only once in the common
ancestors of those nodes?

There's a similar concern for Remove()

[luken, 2014/04/28 01:33:34]

Insert() and Remove() as described in both the R-Tree and R*-Tree paper require
that the entire tree have valid bounds as entry conditions to their algorithms.
I see what you're saying, and it might be possible, but I am worried it would
complicate what is already an arguably overcomplicated system. Or am I
misunderstanding your feedback here?

+  }
+
+  // Complete reinserts, if any.
+  for (std::list<Node*>::iterator it = reinserts.begin();
+       it != reinserts.end();
+       it++) {
+    Insert((*it), highest_reinsert_level);

[piman, 2014/04/21 23:59:31]

nit: () superfluous

[luken, 2014/04/28 01:33:34]

Done.

+  }
+}
+
+void RTree::Remove(Node* node) {
+  // We need to remove this node from its parent.
+  Node* parent = node->parent();
+  // Record nodes are never allowed as the root, so we should always have a
+  // parent.
+  DCHECK(parent);
+  // Should always be a leaf that had the record.
+  DCHECK_EQ(parent->level(), 0);
+  std::list<Node*> orphans;
+  Node* child = node;
+
+  // Traverse up the tree, removing the child from each parent and deleting
+  // parent nodes, until we either encounter the root of the tree or a parent
+  // that still has sufficient children.
+  while (parent && parent->RemoveChild(child, &orphans) < min_children_) {
+    if (child != node) {
+      delete child;
+    }
+    child = parent;
+    parent = parent->parent();
+  }
+
+  // If we stopped deleting nodes up the tree before encountering the root,
+  // we'll need to fix up the bounds from the first parent we didn't delete
+  // up to the root.
+  if (parent) {
+    parent->RecomputeBounds();
+  }
+
+  // Now re-insert each of the orphaned nodes back into the tree.
+  for (std::list<Node*>::iterator it = orphans.begin(); it != orphans.end();
+       it++) {
+    int starting_level = -1;
+    Insert((*it), &starting_level);

[piman, 2014/04/21 23:59:31]

nit: no need for extra ()

[luken, 2014/04/28 01:33:34]

Done.

+  }
+}
+
+bool RTree::Validate() const {
+  if (!root_) {
+    return true;
+  }
+  // Root is special in that it needs to have at least one child but can
+  // have less than min_children.
+  DCHECK_GE(root_->count(), 1U);
+  DCHECK_LE(root_->count(), max_children_);
+  return root_->Validate(min_children_, max_children_);
+}
+
+}  // namespace gfx