Chromium Code Reviews
chromiumcodereview-hr@appspot.gserviceaccount.com (chromiumcodereview-hr) | Please choose your nickname with Settings | Help | Chromium Project | Gerrit Changes | Sign out
(99)

Side by Side Diff: ui/gfx/geometry/r_tree.cc

Issue 245763002: Adds an RTree data structure to gfx/geometry (Closed) Base URL: https://chromium.googlesource.com/chromium/src.git@master
Patch Set: fixing some clang trybots Created 6 years, 7 months ago
Use n/p to move between diff chunks; N/P to move between comments. Draft comments are only viewable by you.
Jump to:
View unified diff | Download patch
« no previous file with comments | « ui/gfx/geometry/r_tree.h ('k') | ui/gfx/geometry/r_tree_unittest.cc » ('j') | no next file with comments »
Toggle Intra-line Diffs ('i') | Expand Comments ('e') | Collapse Comments ('c') | Show Comments Hide Comments ('s')
OLDNEW
(Empty)
1 // Copyright (c) 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 scoped_ptr<Node> new_root(root_->RemoveAndReturnLastChild());
631 root_.swap(new_root);
632 }
633 }
634
635 void RTree::Query(const Rect& query_rect,
636 base::hash_set<intptr_t>* matches_out) const {
637 root_->Query(query_rect, matches_out);
638 }
639
640 void RTree::Clear() {
641 record_map_.clear();
642 root_.reset(new Node(0));
643 }
644
645 void RTree::InsertNode(Node* node, int* highest_reinsert_level) {
646 // Find the most appropriate parent to insert node into.
647 Node* parent = root_->ChooseSubtree(node);
648 DCHECK(parent);
649 // Verify ChooseSubtree returned a Node at the correct level.
650 DCHECK_EQ(parent->level(), node->level() + 1);
651 Node* insert_node = node;
652 Node* insert_parent = parent;
653 Node* needs_bounds_recomputed = insert_parent->parent();
654 ScopedVector<Node> reinserts;
655 // Attempt to insert the Node, if this overflows the Node we must handle it.
656 while (insert_parent &&
657 insert_parent->AddChild(insert_node) > max_children_) {
658 // If we have yet to re-insert nodes at this level during this data insert,
659 // and we're not at the root, R*-Tree calls for re-insertion of some of the
660 // nodes, resulting in a better balance on the tree.
661 if (insert_parent->parent() &&
662 insert_parent->level() > *highest_reinsert_level) {
663 insert_parent->RemoveNodesForReinsert(max_children_ / 3, &reinserts);
664 // Adjust highest_reinsert_level to this level.
665 *highest_reinsert_level = insert_parent->level();
666 // We didn't create any new nodes so we have nothing new to insert.
667 insert_node = NULL;
668 // RemoveNodesForReinsert() does not recompute bounds, so mark it.
669 needs_bounds_recomputed = insert_parent;
670 break;
671 }
672
673 // Split() will create a sibling to insert_parent both of which will have
674 // valid bounds, but this invalidates their parent's bounds.
675 insert_node = insert_parent->Split(min_children_, max_children_);
676 insert_parent = insert_parent->parent();
677 needs_bounds_recomputed = insert_parent;
678 }
679
680 // If we have a Node to insert, and we hit the root of the current tree,
681 // we create a new root which is the parent of the current root and the
682 // insert_node
683 if (!insert_parent && insert_node) {
684 Node* old_root = root_.release();
685 root_.reset(new Node(old_root->level() + 1));
686 root_->AddChild(old_root);
687 root_->AddChild(insert_node);
688 }
689
690 // Recompute bounds along insertion path.
691 if (needs_bounds_recomputed) {
692 needs_bounds_recomputed->RecomputeBounds();
693 }
694
695 // Complete re-inserts, if any.
696 for (size_t i = 0; i < reinserts.size(); ++i) {
697 InsertNode(reinserts[i], highest_reinsert_level);
698 }
699
700 // Clear out reinserts without deleting any of the children, as they have been
701 // re-inserted into the tree.
702 reinserts.weak_clear();
703 }
704
705 void RTree::RemoveNode(Node* node) {
706 // We need to remove this node from its parent.
707 Node* parent = node->parent();
708 // Record nodes are never allowed as the root, so we should always have a
709 // parent.
710 DCHECK(parent);
711 // Should always be a leaf that had the record.
712 DCHECK_EQ(parent->level(), 0);
713 ScopedVector<Node> orphans;
714 Node* child = node;
715
716 // Traverse up the tree, removing the child from each parent and deleting
717 // parent nodes, until we either encounter the root of the tree or a parent
718 // that still has sufficient children.
719 while (parent && parent->RemoveChild(child, &orphans) < min_children_) {
720 if (child != node) {
721 delete child;
722 }
723 child = parent;
724 parent = parent->parent();
725 }
726
727 // If we stopped deleting nodes up the tree before encountering the root,
728 // we'll need to fix up the bounds from the first parent we didn't delete
729 // up to the root.
730 if (parent) {
731 parent->RecomputeBounds();
732 }
733
734 // Now re-insert each of the orphaned nodes back into the tree.
735 for (size_t i = 0; i < orphans.size(); ++i) {
736 int starting_level = -1;
737 InsertNode(orphans[i], &starting_level);
738 }
739
740 // Clear out the orphans list without deleting any of the children, as they
741 // have been re-inserted into the tree.
742 orphans.weak_clear();
743 }
744
745 } // namespace gfx
OLDNEW
« no previous file with comments | « ui/gfx/geometry/r_tree.h ('k') | ui/gfx/geometry/r_tree_unittest.cc » ('j') | no next file with comments »

Powered by Google App Engine
This is Rietveld 408576698