| OLD | NEW |
|---|
| (Empty) |
| 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 #include "ui/gfx/geometry/r_tree.h" | |
| 6 | |
| 7 #include <algorithm> | |
| 8 #include <limits> | |
| 9 | |
| 10 #include "base/logging.h" | |
| 11 | |
| 12 namespace { | |
| 13 | |
| 14 // Returns the center coordinates of the given rectangle. | |
| 15 gfx::Vector2d CenterOfRect(const gfx::Rect& rect) { | |
| 16 return rect.OffsetFromOrigin() + | |
| 17 gfx::Vector2d(rect.width() / 2, rect.height() / 2); | |
| 18 } | |
| 19 } | |
| 20 | |
| 21 namespace gfx { | |
| 22 | |
| 23 RTree::Node::Node(int level) : level_(level), parent_(NULL), key_(0) { | |
| 24 } | |
| 25 | |
| 26 RTree::Node::Node(const Rect& rect, intptr_t key) | |
| 27 : rect_(rect), level_(-1), parent_(NULL), key_(key) { | |
| 28 } | |
| 29 | |
| 30 RTree::Node::~Node() { | |
| 31 Clear(); | |
| 32 } | |
| 33 | |
| 34 void RTree::Node::Clear() { | |
| 35 // Iterate through children and delete them all. | |
| 36 children_.clear(); | |
| 37 key_ = 0; | |
| 38 } | |
| 39 | |
| 40 void RTree::Node::Query(const Rect& query_rect, | |
| 41 base::hash_set<intptr_t>* matches_out) const { | |
| 42 // Check own bounding box for intersection, can cull all children if no | |
| 43 // intersection. | |
| 44 if (!rect_.Intersects(query_rect)) { | |
| 45 return; | |
| 46 } | |
| 47 | |
| 48 // Conversely if we are completely contained within the query rect we can | |
| 49 // confidently skip all bounds checks for ourselves and all our children. | |
| 50 if (query_rect.Contains(rect_)) { | |
| 51 GetAllValues(matches_out); | |
| 52 return; | |
| 53 } | |
| 54 | |
| 55 // We intersect the query rect but we are not are not contained within it. | |
| 56 // If we are a record node, then add our record value. Otherwise we must | |
| 57 // query each of our children in turn. | |
| 58 if (key_) { | |
| 59 DCHECK_EQ(level_, -1); | |
| 60 matches_out->insert(key_); | |
| 61 } else { | |
| 62 for (size_t i = 0; i < children_.size(); ++i) { | |
| 63 // Sanity-check our children. | |
| 64 Node* node = children_[i]; | |
| 65 DCHECK_EQ(node->parent_, this); | |
| 66 DCHECK_EQ(level_ - 1, node->level_); | |
| 67 DCHECK(rect_.Contains(node->rect_)); | |
| 68 node->Query(query_rect, matches_out); | |
| 69 } | |
| 70 } | |
| 71 } | |
| 72 | |
| 73 void RTree::Node::RecomputeBounds() { | |
| 74 RecomputeBoundsNoParents(); | |
| 75 // Recompute our parent's bounds recursively up to the root. | |
| 76 if (parent_) { | |
| 77 parent_->RecomputeBounds(); | |
| 78 } | |
| 79 } | |
| 80 | |
| 81 void RTree::Node::RemoveNodesForReinsert(size_t number_to_remove, | |
| 82 ScopedVector<Node>* nodes) { | |
| 83 DCHECK_GE(children_.size(), number_to_remove); | |
| 84 | |
| 85 // Sort our children by their distance from the center of their rectangles to | |
| 86 // the center of our bounding rectangle. | |
| 87 std::sort(children_.begin(), | |
| 88 children_.end(), | |
| 89 &RTree::Node::CompareCenterDistanceFromParent); | |
| 90 | |
| 91 // Add lowest distance nodes from our children list to the returned vector. | |
| 92 nodes->insert( | |
| 93 nodes->end(), children_.begin(), children_.begin() + number_to_remove); | |
| 94 // Remove those same nodes from our list, without deleting them. | |
| 95 children_.weak_erase(children_.begin(), children_.begin() + number_to_remove); | |
| 96 } | |
| 97 | |
| 98 size_t RTree::Node::RemoveChild(Node* child_node, ScopedVector<Node>* orphans) { | |
| 99 // Should actually be one of our children. | |
| 100 DCHECK_EQ(child_node->parent_, this); | |
| 101 | |
| 102 // Add children of child_node to the orphans vector. | |
| 103 orphans->insert(orphans->end(), | |
| 104 child_node->children_.begin(), | |
| 105 child_node->children_.end()); | |
| 106 // Remove without deletion those children from the child_node vector. | |
| 107 child_node->children_.weak_clear(); | |
| 108 | |
| 109 // Find an iterator to this Node in our own children_ vector. | |
| 110 ScopedVector<Node>::iterator child_it = children_.end(); | |
| 111 for (size_t i = 0; i < children_.size(); ++i) { | |
| 112 if (children_[i] == child_node) { | |
| 113 child_it = children_.begin() + i; | |
| 114 break; | |
| 115 } | |
| 116 } | |
| 117 // Should have found the pointer in our children_ vector. | |
| 118 DCHECK(child_it != children_.end()); | |
| 119 // Remove without deleting the child node from our children_ vector. | |
| 120 children_.weak_erase(child_it); | |
| 121 | |
| 122 return children_.size(); | |
| 123 } | |
| 124 | |
| 125 scoped_ptr<RTree::Node> RTree::Node::RemoveAndReturnLastChild() { | |
| 126 if (!children_.size()) | |
| 127 return scoped_ptr<Node>(); | |
| 128 | |
| 129 scoped_ptr<Node> last_child(children_[children_.size() - 1]); | |
| 130 DCHECK_EQ(last_child->parent_, this); | |
| 131 children_.weak_erase(children_.begin() + children_.size() - 1); | |
| 132 // Invalidate parent, as this child may even become the new root. | |
| 133 last_child->parent_ = NULL; | |
| 134 return last_child.Pass(); | |
| 135 } | |
| 136 | |
| 137 // Uses the R*-Tree algorithm CHOOSELEAF proposed by Beckmann et al. | |
| 138 RTree::Node* RTree::Node::ChooseSubtree(Node* node) { | |
| 139 // Should never be called on a record node. | |
| 140 DCHECK(!key_); | |
| 141 DCHECK(level_ >= 0); | |
| 142 DCHECK(node); | |
| 143 | |
| 144 // If we are a parent of nodes on the provided node level, we are done. | |
| 145 if (level_ == node->level_ + 1) | |
| 146 return this; | |
| 147 | |
| 148 // We are an internal node, and thus guaranteed to have children. | |
| 149 DCHECK_GT(children_.size(), 0U); | |
| 150 | |
| 151 // Iterate over all children to find best candidate for insertion. | |
| 152 Node* best_candidate = NULL; | |
| 153 | |
| 154 // Precompute a vector of expanded rects, used both by LeastOverlapIncrease | |
| 155 // and LeastAreaEnlargement. | |
| 156 std::vector<Rect> expanded_rects; | |
| 157 expanded_rects.reserve(children_.size()); | |
| 158 for (size_t i = 0; i < children_.size(); ++i) { | |
| 159 Rect expanded_rect(node->rect_); | |
| 160 expanded_rect.Union(children_[i]->rect_); | |
| 161 expanded_rects.push_back(expanded_rect); | |
| 162 } | |
| 163 | |
| 164 // For parents of leaf nodes, we pick the node that will cause the least | |
| 165 // increase in overlap by the addition of this new node. This may detect a | |
| 166 // tie, in which case it will return NULL. | |
| 167 if (level_ == 1) | |
| 168 best_candidate = LeastOverlapIncrease(node->rect_, expanded_rects); | |
| 169 | |
| 170 // For non-parents of leaf nodes, or for parents of leaf nodes with ties in | |
| 171 // overlap increase, we choose the subtree with least area enlargement caused | |
| 172 // by the addition of the new node. | |
| 173 if (!best_candidate) | |
| 174 best_candidate = LeastAreaEnlargement(node->rect_, expanded_rects); | |
| 175 | |
| 176 DCHECK(best_candidate); | |
| 177 return best_candidate->ChooseSubtree(node); | |
| 178 } | |
| 179 | |
| 180 RTree::Node* RTree::Node::LeastAreaEnlargement( | |
| 181 const Rect& node_rect, | |
| 182 const std::vector<Rect>& expanded_rects) { | |
| 183 Node* best_node = NULL; | |
| 184 int least_area_enlargement = std::numeric_limits<int>::max(); | |
| 185 for (size_t i = 0; i < children_.size(); ++i) { | |
| 186 Node* candidate_node = children_[i]; | |
| 187 int area_change = expanded_rects[i].size().GetArea() - | |
| 188 candidate_node->rect_.size().GetArea(); | |
| 189 if (area_change < least_area_enlargement) { | |
| 190 best_node = candidate_node; | |
| 191 least_area_enlargement = area_change; | |
| 192 } else if (area_change == least_area_enlargement) { | |
| 193 // Ties are broken by choosing entry with least area. | |
| 194 DCHECK(best_node); | |
| 195 if (candidate_node->rect_.size().GetArea() < | |
| 196 best_node->rect_.size().GetArea()) { | |
| 197 best_node = candidate_node; | |
| 198 } | |
| 199 } | |
| 200 } | |
| 201 | |
| 202 DCHECK(best_node); | |
| 203 return best_node; | |
| 204 } | |
| 205 | |
| 206 RTree::Node* RTree::Node::LeastOverlapIncrease( | |
| 207 const Rect& node_rect, | |
| 208 const std::vector<Rect>& expanded_rects) { | |
| 209 Node* best_node = NULL; | |
| 210 bool has_tied_node = false; | |
| 211 int least_overlap_increase = std::numeric_limits<int>::max(); | |
| 212 for (size_t i = 0; i < children_.size(); ++i) { | |
| 213 int overlap_increase = | |
| 214 OverlapIncreaseToAdd(node_rect, i, expanded_rects[i]); | |
| 215 if (overlap_increase < least_overlap_increase) { | |
| 216 least_overlap_increase = overlap_increase; | |
| 217 best_node = children_[i]; | |
| 218 has_tied_node = false; | |
| 219 } else if (overlap_increase == least_overlap_increase) { | |
| 220 has_tied_node = true; | |
| 221 // If we are tied at zero there is no possible better overlap increase, | |
| 222 // so we can report a tie early. | |
| 223 if (overlap_increase == 0) { | |
| 224 return NULL; | |
| 225 } | |
| 226 } | |
| 227 } | |
| 228 | |
| 229 // If we ended up with a tie return NULL to report it. | |
| 230 if (has_tied_node) | |
| 231 return NULL; | |
| 232 | |
| 233 return best_node; | |
| 234 } | |
| 235 | |
| 236 int RTree::Node::OverlapIncreaseToAdd(const Rect& rect, | |
| 237 size_t candidate, | |
| 238 const Rect& expanded_rect) { | |
| 239 Node* candidate_node = children_[candidate]; | |
| 240 | |
| 241 // Early-out option for when rect is contained completely within candidate. | |
| 242 if (candidate_node->rect_.Contains(rect)) { | |
| 243 return 0; | |
| 244 } | |
| 245 | |
| 246 int total_original_overlap = 0; | |
| 247 int total_expanded_overlap = 0; | |
| 248 | |
| 249 // Now calculate overlap with all other rects in this node. | |
| 250 for (size_t i = 0; i < children_.size(); ++i) { | |
| 251 // Skip calculating overlap with the candidate rect. | |
| 252 if (i == candidate) | |
| 253 continue; | |
| 254 Node* overlap_node = children_[i]; | |
| 255 Rect overlap_rect = candidate_node->rect_; | |
| 256 overlap_rect.Intersect(overlap_node->rect_); | |
| 257 total_original_overlap += overlap_rect.size().GetArea(); | |
| 258 Rect expanded_overlap_rect = expanded_rect; | |
| 259 expanded_overlap_rect.Intersect(overlap_node->rect_); | |
| 260 total_expanded_overlap += expanded_overlap_rect.size().GetArea(); | |
| 261 } | |
| 262 | |
| 263 // Compare this overlap increase with best one to date, update best. | |
| 264 int overlap_increase = total_expanded_overlap - total_original_overlap; | |
| 265 return overlap_increase; | |
| 266 } | |
| 267 | |
| 268 size_t RTree::Node::AddChild(Node* node) { | |
| 269 DCHECK(node); | |
| 270 // Sanity-check that the level of the child being added is one more than ours. | |
| 271 DCHECK_EQ(level_ - 1, node->level_); | |
| 272 node->parent_ = this; | |
| 273 children_.push_back(node); | |
| 274 rect_.Union(node->rect_); | |
| 275 return children_.size(); | |
| 276 } | |
| 277 | |
| 278 RTree::Node* RTree::Node::Split(size_t min_children, size_t max_children) { | |
| 279 // Please don't attempt to split a record Node. | |
| 280 DCHECK(!key_); | |
| 281 // We should have too many children to begin with. | |
| 282 DCHECK_GT(children_.size(), max_children); | |
| 283 // First determine if splitting along the horizontal or vertical axis. We | |
| 284 // sort the rectangles of our children by lower then upper values along both | |
| 285 // horizontal and vertical axes. | |
| 286 std::vector<Node*> vertical_sort(children_.get()); | |
| 287 std::vector<Node*> horizontal_sort(children_.get()); | |
| 288 std::sort(vertical_sort.begin(), | |
| 289 vertical_sort.end(), | |
| 290 &RTree::Node::CompareVertical); | |
| 291 std::sort(horizontal_sort.begin(), | |
| 292 horizontal_sort.end(), | |
| 293 &RTree::Node::CompareHorizontal); | |
| 294 | |
| 295 // We will be examining the bounding boxes of different splits of our children | |
| 296 // sorted along each axis. Here we precompute the bounding boxes of these | |
| 297 // distributions. For the low bounds the ith element can be considered the | |
| 298 // union of all rects [0,i] in the relevant sorted axis array. | |
| 299 std::vector<Rect> low_vertical_bounds; | |
| 300 std::vector<Rect> low_horizontal_bounds; | |
| 301 BuildLowBounds(vertical_sort, | |
| 302 horizontal_sort, | |
| 303 &low_vertical_bounds, | |
| 304 &low_horizontal_bounds); | |
| 305 | |
| 306 // For the high bounds the ith element can be considered the union of all | |
| 307 // rects [i, children_.size()) in the relevant sorted axis array. | |
| 308 std::vector<Rect> high_vertical_bounds; | |
| 309 std::vector<Rect> high_horizontal_bounds; | |
| 310 BuildHighBounds(vertical_sort, | |
| 311 horizontal_sort, | |
| 312 &high_vertical_bounds, | |
| 313 &high_horizontal_bounds); | |
| 314 | |
| 315 bool is_vertical_split = ChooseSplitAxis(low_vertical_bounds, | |
| 316 high_vertical_bounds, | |
| 317 low_horizontal_bounds, | |
| 318 high_horizontal_bounds, | |
| 319 min_children, | |
| 320 max_children); | |
| 321 | |
| 322 // Lastly we determine optimal index and do the split. | |
| 323 Node* sibling = NULL; | |
| 324 if (is_vertical_split) { | |
| 325 size_t split_index = ChooseSplitIndex( | |
| 326 min_children, max_children, low_vertical_bounds, high_vertical_bounds); | |
| 327 sibling = DivideChildren( | |
| 328 low_vertical_bounds, high_vertical_bounds, vertical_sort, split_index); | |
| 329 } else { | |
| 330 size_t split_index = ChooseSplitIndex(min_children, | |
| 331 max_children, | |
| 332 low_horizontal_bounds, | |
| 333 high_horizontal_bounds); | |
| 334 sibling = DivideChildren(low_horizontal_bounds, | |
| 335 high_horizontal_bounds, | |
| 336 horizontal_sort, | |
| 337 split_index); | |
| 338 } | |
| 339 | |
| 340 return sibling; | |
| 341 } | |
| 342 | |
| 343 // static | |
| 344 void RTree::Node::BuildLowBounds(const std::vector<Node*>& vertical_sort, | |
| 345 const std::vector<Node*>& horizontal_sort, | |
| 346 std::vector<Rect>* vertical_bounds, | |
| 347 std::vector<Rect>* horizontal_bounds) { | |
| 348 DCHECK_EQ(vertical_sort.size(), horizontal_sort.size()); | |
| 349 Rect vertical_bounds_rect; | |
| 350 Rect horizontal_bounds_rect; | |
| 351 vertical_bounds->reserve(vertical_sort.size()); | |
| 352 horizontal_bounds->reserve(horizontal_sort.size()); | |
| 353 for (size_t i = 0; i < vertical_sort.size(); ++i) { | |
| 354 vertical_bounds_rect.Union(vertical_sort[i]->rect_); | |
| 355 horizontal_bounds_rect.Union(horizontal_sort[i]->rect_); | |
| 356 vertical_bounds->push_back(vertical_bounds_rect); | |
| 357 horizontal_bounds->push_back(horizontal_bounds_rect); | |
| 358 } | |
| 359 } | |
| 360 | |
| 361 // static | |
| 362 void RTree::Node::BuildHighBounds(const std::vector<Node*>& vertical_sort, | |
| 363 const std::vector<Node*>& horizontal_sort, | |
| 364 std::vector<Rect>* vertical_bounds, | |
| 365 std::vector<Rect>* horizontal_bounds) { | |
| 366 DCHECK_EQ(vertical_sort.size(), horizontal_sort.size()); | |
| 367 Rect vertical_bounds_rect; | |
| 368 Rect horizontal_bounds_rect; | |
| 369 vertical_bounds->resize(vertical_sort.size()); | |
| 370 horizontal_bounds->resize(horizontal_sort.size()); | |
| 371 for (int i = static_cast<int>(vertical_sort.size()) - 1; i >= 0; --i) { | |
| 372 vertical_bounds_rect.Union(vertical_sort[i]->rect_); | |
| 373 horizontal_bounds_rect.Union(horizontal_sort[i]->rect_); | |
| 374 vertical_bounds->at(i) = vertical_bounds_rect; | |
| 375 horizontal_bounds->at(i) = horizontal_bounds_rect; | |
| 376 } | |
| 377 } | |
| 378 | |
| 379 // static | |
| 380 bool RTree::Node::ChooseSplitAxis( | |
| 381 const std::vector<Rect>& low_vertical_bounds, | |
| 382 const std::vector<Rect>& high_vertical_bounds, | |
| 383 const std::vector<Rect>& low_horizontal_bounds, | |
| 384 const std::vector<Rect>& high_horizontal_bounds, | |
| 385 size_t min_children, | |
| 386 size_t max_children) { | |
| 387 // Examine the possible distributions of each sorted list by iterating through | |
| 388 // valid split points p, min_children <= p <= max_children - min_children, and | |
| 389 // computing the sums of the margins of the bounding boxes in each group. | |
| 390 // Smallest margin sum will determine split axis. | |
| 391 int smallest_horizontal_margin_sum = std::numeric_limits<int>::max(); | |
| 392 int smallest_vertical_margin_sum = std::numeric_limits<int>::max(); | |
| 393 for (size_t p = min_children; p < max_children - min_children; ++p) { | |
| 394 int horizontal_margin_sum = | |
| 395 low_horizontal_bounds[p].width() + low_horizontal_bounds[p].height() + | |
| 396 high_horizontal_bounds[p].width() + high_horizontal_bounds[p].height(); | |
| 397 int vertical_margin_sum = | |
| 398 low_vertical_bounds[p].width() + low_vertical_bounds[p].height() + | |
| 399 high_vertical_bounds[p].width() + high_vertical_bounds[p].height(); | |
| 400 // Update margin minima if necessary. | |
| 401 smallest_horizontal_margin_sum = | |
| 402 std::min(horizontal_margin_sum, smallest_horizontal_margin_sum); | |
| 403 smallest_vertical_margin_sum = | |
| 404 std::min(vertical_margin_sum, smallest_vertical_margin_sum); | |
| 405 } | |
| 406 | |
| 407 // Split along the axis perpendicular to the axis with the overall smallest | |
| 408 // margin sum. Meaning the axis sort resulting in two boxes with the smallest | |
| 409 // combined margin will become the axis along which the sorted rectangles are | |
| 410 // distributed to the two Nodes. | |
| 411 bool is_vertical_split = | |
| 412 smallest_vertical_margin_sum < smallest_horizontal_margin_sum; | |
| 413 return is_vertical_split; | |
| 414 } | |
| 415 | |
| 416 RTree::Node* RTree::Node::DivideChildren( | |
| 417 const std::vector<Rect>& low_bounds, | |
| 418 const std::vector<Rect>& high_bounds, | |
| 419 const std::vector<Node*>& sorted_children, | |
| 420 size_t split_index) { | |
| 421 Node* sibling = new Node(level_); | |
| 422 sibling->parent_ = parent_; | |
| 423 rect_ = low_bounds[split_index - 1]; | |
| 424 sibling->rect_ = high_bounds[split_index]; | |
| 425 // Our own children_ vector is unsorted, so we wipe it out and divide the | |
| 426 // sorted bounds rects between ourselves and our sibling. | |
| 427 children_.weak_clear(); | |
| 428 children_.insert(children_.end(), | |
| 429 sorted_children.begin(), | |
| 430 sorted_children.begin() + split_index); | |
| 431 sibling->children_.insert(sibling->children_.end(), | |
| 432 sorted_children.begin() + split_index, | |
| 433 sorted_children.end()); | |
| 434 | |
| 435 // Fix up sibling parentage or it's gonna be an awkward Thanksgiving. | |
| 436 for (size_t i = 0; i < sibling->children_.size(); ++i) { | |
| 437 sibling->children_[i]->parent_ = sibling; | |
| 438 } | |
| 439 | |
| 440 return sibling; | |
| 441 } | |
| 442 | |
| 443 void RTree::Node::SetRect(const Rect& rect) { | |
| 444 // Record nodes only, please. | |
| 445 DCHECK(key_); | |
| 446 rect_ = rect; | |
| 447 } | |
| 448 | |
| 449 // Returns all contained record_node values for this node and all children. | |
| 450 void RTree::Node::GetAllValues(base::hash_set<intptr_t>* matches_out) const { | |
| 451 if (key_) { | |
| 452 DCHECK_EQ(level_, -1); | |
| 453 matches_out->insert(key_); | |
| 454 } else { | |
| 455 for (size_t i = 0; i < children_.size(); ++i) { | |
| 456 Node* node = children_[i]; | |
| 457 // Sanity-check our children. | |
| 458 DCHECK_EQ(node->parent_, this); | |
| 459 DCHECK_EQ(level_ - 1, node->level_); | |
| 460 DCHECK(rect_.Contains(node->rect_)); | |
| 461 node->GetAllValues(matches_out); | |
| 462 } | |
| 463 } | |
| 464 } | |
| 465 | |
| 466 // static | |
| 467 bool RTree::Node::CompareVertical(Node* a, Node* b) { | |
| 468 // Sort nodes by top coordinate first. | |
| 469 if (a->rect_.y() < b->rect_.y()) { | |
| 470 return true; | |
| 471 } else if (a->rect_.y() == b->rect_.y()) { | |
| 472 // If top coordinate is equal, sort by lowest bottom coordinate. | |
| 473 return a->rect_.height() < b->rect_.height(); | |
| 474 } | |
| 475 return false; | |
| 476 } | |
| 477 | |
| 478 // static | |
| 479 bool RTree::Node::CompareHorizontal(Node* a, Node* b) { | |
| 480 // Sort nodes by left coordinate first. | |
| 481 if (a->rect_.x() < b->rect_.x()) { | |
| 482 return true; | |
| 483 } else if (a->rect_.x() == b->rect_.x()) { | |
| 484 // If left coordinate is equal, sort by lowest right coordinate. | |
| 485 return a->rect_.width() < b->rect_.width(); | |
| 486 } | |
| 487 return false; | |
| 488 } | |
| 489 | |
| 490 // Sort these two nodes by the distance of the center of their rects from the | |
| 491 // center of their parent's rect. We don't bother with square roots because we | |
| 492 // are only comparing the two values for sorting purposes. | |
| 493 // static | |
| 494 bool RTree::Node::CompareCenterDistanceFromParent(Node* a, Node* b) { | |
| 495 // This comparison assumes the nodes have the same parent. | |
| 496 DCHECK(a->parent_ == b->parent_); | |
| 497 // This comparison requires that each node have a parent. | |
| 498 DCHECK(a->parent_); | |
| 499 // Sanity-check level_ of these nodes is equal. | |
| 500 DCHECK_EQ(a->level_, b->level_); | |
| 501 // Also the parent of the nodes should have level one higher. | |
| 502 DCHECK_EQ(a->level_, a->parent_->level_ - 1); | |
| 503 | |
| 504 // Find the parent. | |
| 505 Node* p = a->parent(); | |
| 506 | |
| 507 Vector2d p_center = CenterOfRect(p->rect_); | |
| 508 Vector2d a_center = CenterOfRect(a->rect_); | |
| 509 Vector2d b_center = CenterOfRect(b->rect_); | |
| 510 | |
| 511 return (a_center - p_center).LengthSquared() < | |
| 512 (b_center - p_center).LengthSquared(); | |
| 513 } | |
| 514 | |
| 515 size_t RTree::Node::ChooseSplitIndex(size_t min_children, | |
| 516 size_t max_children, | |
| 517 const std::vector<Rect>& low_bounds, | |
| 518 const std::vector<Rect>& high_bounds) { | |
| 519 int smallest_overlap_area = std::numeric_limits<int>::max(); | |
| 520 int smallest_combined_area = std::numeric_limits<int>::max(); | |
| 521 size_t optimal_split_index = 0; | |
| 522 for (size_t p = min_children; p < max_children - min_children; ++p) { | |
| 523 Rect overlap_bounds = low_bounds[p]; | |
| 524 overlap_bounds.Union(high_bounds[p]); | |
| 525 int overlap_area = overlap_bounds.size().GetArea(); | |
| 526 if (overlap_area < smallest_overlap_area) { | |
| 527 smallest_overlap_area = overlap_area; | |
| 528 smallest_combined_area = | |
| 529 low_bounds[p].size().GetArea() + high_bounds[p].size().GetArea(); | |
| 530 optimal_split_index = p; | |
| 531 } else if (overlap_area == smallest_overlap_area) { | |
| 532 // Break ties with smallest combined area of the two bounding boxes. | |
| 533 int combined_area = | |
| 534 low_bounds[p].size().GetArea() + high_bounds[p].size().GetArea(); | |
| 535 if (combined_area < smallest_combined_area) { | |
| 536 smallest_combined_area = combined_area; | |
| 537 optimal_split_index = p; | |
| 538 } | |
| 539 } | |
| 540 } | |
| 541 | |
| 542 // optimal_split_index currently points at the last element in the first set, | |
| 543 // so advance it by 1 to point at the first element in the second set. | |
| 544 return optimal_split_index + 1; | |
| 545 } | |
| 546 | |
| 547 void RTree::Node::RecomputeBoundsNoParents() { | |
| 548 // Clear our rectangle, then reset it to union of our children. | |
| 549 rect_.SetRect(0, 0, 0, 0); | |
| 550 for (size_t i = 0; i < children_.size(); ++i) { | |
| 551 rect_.Union(children_[i]->rect_); | |
| 552 } | |
| 553 } | |
| 554 | |
| 555 RTree::RTree(size_t min_children, size_t max_children) | |
| 556 : root_(new Node(0)), | |
| 557 min_children_(min_children), | |
| 558 max_children_(max_children) { | |
| 559 // R-Trees require min_children >= 2 | |
| 560 DCHECK_GE(min_children_, 2U); | |
| 561 // R-Trees also require min_children <= max_children / 2 | |
| 562 DCHECK_LE(min_children_, max_children_ / 2U); | |
| 563 root_.reset(new Node(0)); | |
| 564 } | |
| 565 | |
| 566 RTree::~RTree() { | |
| 567 Clear(); | |
| 568 } | |
| 569 | |
| 570 void RTree::Insert(const Rect& rect, intptr_t key) { | |
| 571 // Non-NULL keys, please. | |
| 572 DCHECK(key); | |
| 573 | |
| 574 Node* record_node = NULL; | |
| 575 // Check if this key is already present in the tree. | |
| 576 base::hash_map<intptr_t, Node*>::iterator it = record_map_.find(key); | |
| 577 if (it != record_map_.end()) { | |
| 578 // We will re-use this node structure, regardless of re-insert or return. | |
| 579 record_node = it->second; | |
| 580 // If the new rect and the current rect are identical we can skip rest of | |
| 581 // Insert() as nothing has changed. | |
| 582 if (record_node->rect() == rect) | |
| 583 return; | |
| 584 | |
| 585 // Remove the node from the tree in its current position. | |
| 586 RemoveNode(record_node); | |
| 587 | |
| 588 // If we are replacing this key with an empty rectangle we just remove the | |
| 589 // old node from the list and return, thus preventing insertion of empty | |
| 590 // rectangles into our spatial database. | |
| 591 if (rect.IsEmpty()) { | |
| 592 record_map_.erase(it); | |
| 593 delete record_node; | |
| 594 return; | |
| 595 } | |
| 596 | |
| 597 // Reset the rectangle to the new value. | |
| 598 record_node->SetRect(rect); | |
| 599 } else { | |
| 600 if (rect.IsEmpty()) | |
| 601 return; | |
| 602 // Build a new record Node for insertion in to tree. | |
| 603 record_node = new Node(rect, key); | |
| 604 // Add this new node to our map, for easy retrieval later. | |
| 605 record_map_.insert(std::make_pair(key, record_node)); | |
| 606 } | |
| 607 | |
| 608 // Call internal Insert with this new node and allowing all re-inserts. | |
| 609 int starting_level = -1; | |
| 610 InsertNode(record_node, &starting_level); | |
| 611 } | |
| 612 | |
| 613 void RTree::Remove(intptr_t key) { | |
| 614 // Search the map for the leaf parent that has the provided record. | |
| 615 base::hash_map<intptr_t, Node*>::iterator it = record_map_.find(key); | |
| 616 // If not in the map it's not in the tree, we're done. | |
| 617 if (it == record_map_.end()) | |
| 618 return; | |
| 619 | |
| 620 Node* node = it->second; | |
| 621 // Remove this node from the map. | |
| 622 record_map_.erase(it); | |
| 623 // Now remove it from the RTree. | |
| 624 RemoveNode(node); | |
| 625 delete node; | |
| 626 | |
| 627 // Lastly check the root. If it has only one non-leaf child, delete it and | |
| 628 // replace it with its child. | |
| 629 if (root_->count() == 1 && root_->level() > 0) { | |
| 630 root_ = root_->RemoveAndReturnLastChild(); | |
| 631 } | |
| 632 } | |
| 633 | |
| 634 void RTree::Query(const Rect& query_rect, | |
| 635 base::hash_set<intptr_t>* matches_out) const { | |
| 636 root_->Query(query_rect, matches_out); | |
| 637 } | |
| 638 | |
| 639 void RTree::Clear() { | |
| 640 record_map_.clear(); | |
| 641 root_.reset(new Node(0)); | |
| 642 } | |
| 643 | |
| 644 void RTree::InsertNode(Node* node, int* highest_reinsert_level) { | |
| 645 // Find the most appropriate parent to insert node into. | |
| 646 Node* parent = root_->ChooseSubtree(node); | |
| 647 DCHECK(parent); | |
| 648 // Verify ChooseSubtree returned a Node at the correct level. | |
| 649 DCHECK_EQ(parent->level(), node->level() + 1); | |
| 650 Node* insert_node = node; | |
| 651 Node* insert_parent = parent; | |
| 652 Node* needs_bounds_recomputed = insert_parent->parent(); | |
| 653 ScopedVector<Node> reinserts; | |
| 654 // Attempt to insert the Node, if this overflows the Node we must handle it. | |
| 655 while (insert_parent && | |
| 656 insert_parent->AddChild(insert_node) > max_children_) { | |
| 657 // If we have yet to re-insert nodes at this level during this data insert, | |
| 658 // and we're not at the root, R*-Tree calls for re-insertion of some of the | |
| 659 // nodes, resulting in a better balance on the tree. | |
| 660 if (insert_parent->parent() && | |
| 661 insert_parent->level() > *highest_reinsert_level) { | |
| 662 insert_parent->RemoveNodesForReinsert(max_children_ / 3, &reinserts); | |
| 663 // Adjust highest_reinsert_level to this level. | |
| 664 *highest_reinsert_level = insert_parent->level(); | |
| 665 // We didn't create any new nodes so we have nothing new to insert. | |
| 666 insert_node = NULL; | |
| 667 // RemoveNodesForReinsert() does not recompute bounds, so mark it. | |
| 668 needs_bounds_recomputed = insert_parent; | |
| 669 break; | |
| 670 } | |
| 671 | |
| 672 // Split() will create a sibling to insert_parent both of which will have | |
| 673 // valid bounds, but this invalidates their parent's bounds. | |
| 674 insert_node = insert_parent->Split(min_children_, max_children_); | |
| 675 insert_parent = insert_parent->parent(); | |
| 676 needs_bounds_recomputed = insert_parent; | |
| 677 } | |
| 678 | |
| 679 // If we have a Node to insert, and we hit the root of the current tree, | |
| 680 // we create a new root which is the parent of the current root and the | |
| 681 // insert_node | |
| 682 if (!insert_parent && insert_node) { | |
| 683 Node* old_root = root_.release(); | |
| 684 root_.reset(new Node(old_root->level() + 1)); | |
| 685 root_->AddChild(old_root); | |
| 686 root_->AddChild(insert_node); | |
| 687 } | |
| 688 | |
| 689 // Recompute bounds along insertion path. | |
| 690 if (needs_bounds_recomputed) { | |
| 691 needs_bounds_recomputed->RecomputeBounds(); | |
| 692 } | |
| 693 | |
| 694 // Complete re-inserts, if any. | |
| 695 for (size_t i = 0; i < reinserts.size(); ++i) { | |
| 696 InsertNode(reinserts[i], highest_reinsert_level); | |
| 697 } | |
| 698 | |
| 699 // Clear out reinserts without deleting any of the children, as they have been | |
| 700 // re-inserted into the tree. | |
| 701 reinserts.weak_clear(); | |
| 702 } | |
| 703 | |
| 704 void RTree::RemoveNode(Node* node) { | |
| 705 // We need to remove this node from its parent. | |
| 706 Node* parent = node->parent(); | |
| 707 // Record nodes are never allowed as the root, so we should always have a | |
| 708 // parent. | |
| 709 DCHECK(parent); | |
| 710 // Should always be a leaf that had the record. | |
| 711 DCHECK_EQ(parent->level(), 0); | |
| 712 ScopedVector<Node> orphans; | |
| 713 Node* child = node; | |
| 714 | |
| 715 // Traverse up the tree, removing the child from each parent and deleting | |
| 716 // parent nodes, until we either encounter the root of the tree or a parent | |
| 717 // that still has sufficient children. | |
| 718 while (parent) { | |
| 719 size_t children_remaining = parent->RemoveChild(child, &orphans); | |
| 720 if (child != node) | |
| 721 delete child; | |
| 722 | |
| 723 if (children_remaining >= min_children_) | |
| 724 break; | |
| 725 | |
| 726 child = parent; | |
| 727 parent = parent->parent(); | |
| 728 } | |
| 729 | |
| 730 // If we stopped deleting nodes up the tree before encountering the root, | |
| 731 // we'll need to fix up the bounds from the first parent we didn't delete | |
| 732 // up to the root. | |
| 733 if (parent) { | |
| 734 parent->RecomputeBounds(); | |
| 735 } else { | |
| 736 root_->RecomputeBounds(); | |
| 737 } | |
| 738 | |
| 739 // Now re-insert each of the orphaned nodes back into the tree. | |
| 740 for (size_t i = 0; i < orphans.size(); ++i) { | |
| 741 int starting_level = -1; | |
| 742 InsertNode(orphans[i], &starting_level); | |
| 743 } | |
| 744 | |
| 745 // Clear out the orphans list without deleting any of the children, as they | |
| 746 // have been re-inserted into the tree. | |
| 747 orphans.weak_clear(); | |
| 748 } | |
| 749 | |
| 750 } // namespace gfx | |
| OLD | NEW |
|---|
Chromium Code Reviews
Issue 342723002:
Repairs crash in RTreeBase::Node::LeastAreaEnlargement (Closed)
Base URL: https://chromium.googlesource.com/chromium/src.git@master