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

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

Issue 245763002: Adds an RTree data structure to gfx/geometry (Closed) Base URL: https://chromium.googlesource.com/chromium/src.git@master
Patch Set: ready for review, thanks 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
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 <set>
6
7 #include "testing/gtest/include/gtest/gtest.h"
8 #include "ui/gfx/geometry/r_tree.h"
9 #include "ui/gfx/geometry/rect.h"
10
11 namespace gfx {
12
13 class RTreeTest : public ::testing::Test {
14 protected:
15 // Given a pointer to an RTree, traverse it and verify its internal structure
16 // is consistent with the RTree semantics.
17 void ValidateRTree(RTree* rt) {
18 // If RTree is empty it should have an empty rectangle.
19 if (!rt->root_->count()) {
20 EXPECT_TRUE(rt->root_->rect().IsEmpty());
21 EXPECT_EQ(rt->root_->level(), 0);
22 return;
23 }
24 // Root is allowed to have fewer than min_children_ but never more than
25 // max_children_.
26 EXPECT_LE(rt->root_->count(), rt->max_children_);
27 // The root should never be a record node.
28 EXPECT_GT(rt->root_->level(), -1);
29 EXPECT_FALSE(rt->root_->key());
30 // The root should never have a parent pointer.
31 EXPECT_FALSE(rt->root_->parent());
32 // Bounds must be consistent on the root.
33 CheckBoundsConsistent(rt->root_.get());
34 // We traverse root's children ourselves, so we can avoid asserts about
35 // root's potential inconsistencies.
36 for (size_t i = 0; i < rt->root_->children_.size(); ++i) {
37 ValidateNode(
38 rt->root_->children_[i], rt->min_children_, rt->max_children_);
39 }
40 }
41
42 // Recursive descent method used by ValidateRTree to check each node within
43 // the RTree for consistency with RTree semantics.
44 void ValidateNode(RTree::Node* node,
45 size_t min_children,
46 size_t max_children) {
47 // Record nodes have different requirements, handle up front.
48 if (node->level() == -1) {
49 // Record nodes may have no children.
50 EXPECT_EQ(node->count(), 0U);
51 // They must have an associated non-NULL key.
52 EXPECT_TRUE(node->key());
53 // They must always have a parent.
54 EXPECT_TRUE(node->parent());
55 return;
56 }
57 // Non-record node, normal expectations apply.
58 EXPECT_GE(node->count(), min_children);
59 EXPECT_LE(node->count(), max_children);
60 EXPECT_TRUE(node->key() == NULL);
61 CheckBoundsConsistent(node);
62 for (size_t i = 0; i < node->children_.size(); ++i) {
63 ValidateNode(node->children_[i], min_children, max_children);
64 }
65 }
66
67 // Check bounds are consistent with children bounds, and other checks
68 // convenient to do while enumerating the children of node.
69 void CheckBoundsConsistent(RTree::Node* node) {
70 EXPECT_FALSE(node->rect_.IsEmpty());
71 Rect check_bounds(0, 0, 0, 0);
72 for (size_t i = 0; i < node->children_.size(); ++i) {
73 RTree::Node* child_node = node->children_[i];
74 check_bounds.Union(child_node->rect());
75 EXPECT_EQ(node->level() - 1, child_node->level());
76 EXPECT_EQ(node, child_node->parent());
77 }
78 EXPECT_EQ(node->rect_, check_bounds);
79 }
80
81 // Adds count squares stacked around the point (0,0) with key equal to width.
82 void AddStackedSquares(RTree* rt, int count) {
83 for (int i = 1; i <= count; ++i) {
84 rt->Insert(Rect(0, 0, i, i), reinterpret_cast<const void*>(i));
85 ValidateRTree(rt);
86 }
87 }
88
89 // Given an unordered list of matching keys, verify that it contains all
90 // values [1..length] for the length of that list.
91 void VerifyAllKeys(const std::set<const void*>& keys) {
92 // Verify that the keys are in values [1,count].
93 for (size_t i = 1; i <= keys.size(); ++i) {
94 EXPECT_TRUE(keys.count(reinterpret_cast<const void*>(i)) == 1U);
95 }
96 }
97 };
98
99 // An empty RTree should never return Query results, and RTrees should be empty
100 // upon construction.
101 TEST_F(RTreeTest, QueryEmptyTree) {
102 RTree rt(2, 10);
103 ValidateRTree(&rt);
104 std::set<const void*> results;
105 Rect test_rect(25, 25);
106 rt.Query(test_rect, &results);
107 EXPECT_EQ(results.size(), 0U);
108 ValidateRTree(&rt);
109 }
110
111 // Clear should empty the tree, meaning that all queries should not return
112 // results after.
113 TEST_F(RTreeTest, ClearEmptiesTreeOfSingleNode) {
114 RTree rt(2, 5);
115 rt.Insert(Rect(0, 0, 100, 100), reinterpret_cast<const void*>(1));
116 rt.Clear();
117 std::set<const void*> results;
118 Rect test_rect(1, 1);
119 rt.Query(test_rect, &results);
120 EXPECT_EQ(results.size(), 0U);
121 ValidateRTree(&rt);
122 }
123
124 // Even with a complex internal structure, clear should empty the tree, meaning
125 // that all queries should not return results after.
126 TEST_F(RTreeTest, ClearEmptiesTreeOfManyNodes) {
127 RTree rt(2, 5);
128 AddStackedSquares(&rt, 100);
129 rt.Clear();
130 std::set<const void*> results;
131 Rect test_rect(1, 1);
132 rt.Query(test_rect, &results);
133 EXPECT_EQ(results.size(), 0U);
134 ValidateRTree(&rt);
135 }
136
137 // Duplicate inserts should overwrite previous inserts.
138 TEST_F(RTreeTest, DuplicateInsertsOverwrite) {
139 RTree rt(2, 5);
140 // Add 100 stacked squares, but always with duplicate key of 1.
141 for (int i = 1; i <= 100; ++i) {
142 rt.Insert(Rect(0, 0, i, i), reinterpret_cast<const void*>(1));
143 ValidateRTree(&rt);
144 }
145 std::set<const void*> results;
146 Rect test_rect(1, 1);
147 rt.Query(test_rect, &results);
148 EXPECT_EQ(results.size(), 1U);
149 EXPECT_TRUE(*results.begin() == reinterpret_cast<const void*>(1));
150 }
151
152 // Call Remove() once on something that's been inserted repeatedly.
153 TEST_F(RTreeTest, DuplicateInsertRemove) {
154 RTree rt(3, 9);
155 AddStackedSquares(&rt, 25);
156 for (int i = 1; i <= 100; ++i) {
157 rt.Insert(Rect(0, 0, i, i), reinterpret_cast<const void*>(26));
158 ValidateRTree(&rt);
159 }
160 rt.Remove(reinterpret_cast<const void*>(26));
161 std::set<const void*> results;
162 Rect test_rect(1, 1);
163 rt.Query(test_rect, &results);
164 EXPECT_EQ(results.size(), 25U);
165 VerifyAllKeys(results);
166 }
167
168 // Call Remove() repeatedly on something that's been inserted once.
169 TEST_F(RTreeTest, InsertDuplicateRemove) {
170 RTree rt(7, 15);
171 AddStackedSquares(&rt, 101);
172 for (int i = 0; i < 100; ++i) {
173 rt.Remove(reinterpret_cast<const void*>(101));
174 ValidateRTree(&rt);
175 }
176 std::set<const void*> results;
177 Rect test_rect(1, 1);
178 rt.Query(test_rect, &results);
179 EXPECT_EQ(results.size(), 100U);
180 VerifyAllKeys(results);
181 }
182
183 // Stacked rects should meet all matching queries regardless of nesting.
184 TEST_F(RTreeTest, QueryStackedSquaresNestedHit) {
185 RTree rt(2, 5);
186 AddStackedSquares(&rt, 100);
187 std::set<const void*> results;
188 Rect test_rect(1, 1);
189 rt.Query(test_rect, &results);
190 EXPECT_EQ(results.size(), 100U);
191 VerifyAllKeys(results);
192 }
193
194 // Stacked rects should meet all matching queries when contained completely by
195 // the query rectangle.
196 TEST_F(RTreeTest, QueryStackedSquaresContainedHit) {
197 RTree rt(2, 10);
198 AddStackedSquares(&rt, 100);
199 std::set<const void*> results;
200 Rect test_rect(0, 0, 100, 100);
201 rt.Query(test_rect, &results);
202 EXPECT_EQ(results.size(), 100U);
203 VerifyAllKeys(results);
204 }
205
206 // Stacked rects should miss a missing query when the query has no intersection
207 // with the rects.
208 TEST_F(RTreeTest, QueryStackedSquaresCompleteMiss) {
209 RTree rt(2, 7);
210 AddStackedSquares(&rt, 100);
211 std::set<const void*> results;
212 Rect test_rect(150, 150, 100, 100);
213 rt.Query(test_rect, &results);
214 EXPECT_EQ(results.size(), 0U);
215 }
216
217 // Removing half the nodes after insertion should still result in a valid tree.
218 TEST_F(RTreeTest, RemoveHalfStackedRects) {
219 RTree rt(2, 11);
220 AddStackedSquares(&rt, 200);
221 for (int i = 101; i <= 200; ++i) {
222 rt.Remove(reinterpret_cast<const void*>(i));
223 ValidateRTree(&rt);
224 }
225 std::set<const void*> results;
226 Rect test_rect(1, 1);
227 rt.Query(test_rect, &results);
228 EXPECT_EQ(results.size(), 100U);
229 VerifyAllKeys(results);
230 // Add the nodes back in.
231 for (int i = 101; i <= 200; ++i) {
232 rt.Insert(Rect(0, 0, i, i), reinterpret_cast<const void*>(i));
233 ValidateRTree(&rt);
234 }
235 results.clear();
236 rt.Query(test_rect, &results);
237 EXPECT_EQ(results.size(), 200U);
238 VerifyAllKeys(results);
239 }
240
241 TEST_F(RTreeTest, InsertNegativeCoordsRect) {
242 RTree rt(5, 11);
243 for (int i = 1; i <= 100; ++i) {
244 rt.Insert(Rect(-i, -i, i, i), reinterpret_cast<const void*>((i * 2) - 1));
245 ValidateRTree(&rt);
246 rt.Insert(Rect(0, 0, i, i), reinterpret_cast<const void*>(i * 2));
247 ValidateRTree(&rt);
248 }
249 std::set<const void*> results;
250 Rect test_rect(-1, -1, 2, 2);
251 rt.Query(test_rect, &results);
252 EXPECT_EQ(results.size(), 200U);
253 VerifyAllKeys(results);
254 }
255
256 TEST_F(RTreeTest, RemoveNegativeCoordsRect) {
257 RTree rt(7, 21);
258 // Add 100 positive stacked squares.
259 AddStackedSquares(&rt, 100);
260 // Now add 100 negative stacked squares.
261 for (int i = 101; i <= 200; ++i) {
262 rt.Insert(Rect(100 - i, 100 - i, i - 100, i - 100),
263 reinterpret_cast<const void*>(301 - i));
264 ValidateRTree(&rt);
265 }
266 // Now remove half of the negative squares.
267 for (int i = 101; i <= 150; ++i) {
268 rt.Remove(reinterpret_cast<const void*>(301 - i));
269 ValidateRTree(&rt);
270 }
271 // Queries should return 100 positive and 50 negative stacked squares.
272 std::set<const void*> results;
273 Rect test_rect(-1, -1, 2, 2);
274 rt.Query(test_rect, &results);
275 EXPECT_EQ(results.size(), 150U);
276 VerifyAllKeys(results);
277 }
278
279 TEST_F(RTreeTest, InsertEmptyRectReplacementRemovesKey) {
280 RTree rt(10, 31);
281 AddStackedSquares(&rt, 50);
282 ValidateRTree(&rt);
283
284 // Replace last square with empty rect.
285 rt.Insert(Rect(0, 0, 0, 0), reinterpret_cast<const void*>(50));
286 ValidateRTree(&rt);
287
288 // Now query large area to get all rects in tree.
289 std::set<const void*> results;
290 Rect test_rect(0, 0, 100, 100);
291 rt.Query(test_rect, &results);
292
293 // Should only be 49 rects in tree.
294 EXPECT_EQ(results.size(), 49U);
295 VerifyAllKeys(results);
296 }
297
298 TEST_F(RTreeTest, NodeRemoveNodesForReinsert) {
299 // Make a leaf node for testing removal from.
300 scoped_ptr<RTree::Node> test_node(new RTree::Node(0));
301 // Build 20 record nodes with rectangle centers going from (1,1) to (20,20)
302 for (int i = 1; i <= 20; ++i) {
303 test_node->AddChild(new RTree::Node(Rect(i - 1, i - 1, 2, 2),
304 reinterpret_cast<const void*>(i)));
305 }
306 // Quick verification of the node before removing children.
307 ValidateNode(test_node.get(), 1U, 20U);
308 // Use a scoped vector to delete all children that get removed from the Node.
309 ScopedVector<RTree::Node> removals;
310 test_node->RemoveNodesForReinsert(1, &removals.get());
311 // Should have gotten back 1 node pointers.
312 EXPECT_EQ(removals.size(), 1U);
313 // There should be 19 left in the test_node.
314 EXPECT_EQ(test_node->count(), 19U);
315 // If we fix up the bounds on the test_node, it should verify.
316 test_node->RecomputeBoundsNoParents();
317 ValidateNode(test_node.get(), 2U, 20U);
318 // The node we removed should be node 10, as it was exactly in the center.
319 EXPECT_TRUE(removals[0]->key() == reinterpret_cast<const void*>(10));
320
321 // Now remove the next 2.
322 removals.clear();
323 test_node->RemoveNodesForReinsert(2, &removals.get());
324 EXPECT_EQ(removals.size(), 2U);
325 EXPECT_EQ(test_node->count(), 17U);
326 test_node->RecomputeBoundsNoParents();
327 ValidateNode(test_node.get(), 2U, 20U);
328 // Lastly the 2 nodes we should have gotten back are keys 9 and 11, as their
329 // centers were the closest to the center of the node bounding box.
330 EXPECT_TRUE(removals[0]->key() == reinterpret_cast<const void*>(9) ||
331 removals[0]->key() == reinterpret_cast<const void*>(11));
332 EXPECT_TRUE(removals[1]->key() == reinterpret_cast<const void*>(9) ||
333 removals[1]->key() == reinterpret_cast<const void*>(11));
334 EXPECT_TRUE(removals[0]->key() != removals[1]->key());
335 }
336
337 TEST_F(RTreeTest, NodeCompareVertical) {
338 // One rect with lower y than another should always sort lower than higher y.
339 RTree::Node low(Rect(0, 1, 10, 10), reinterpret_cast<const void*>(1));
340 RTree::Node middle(Rect(0, 5, 10, 10), reinterpret_cast<const void*>(5));
341 EXPECT_TRUE(RTree::Node::CompareVertical(&low, &middle));
342 EXPECT_FALSE(RTree::Node::CompareVertical(&middle, &low));
343
344 // Try a non-overlapping higher-y rectangle.
345 RTree::Node high(Rect(-10, 20, 10, 1), reinterpret_cast<const void*>(10));
346 EXPECT_TRUE(RTree::Node::CompareVertical(&low, &high));
347 EXPECT_FALSE(RTree::Node::CompareVertical(&high, &low));
348
349 // Ties are broken by lowest bottom y value.
350 RTree::Node shorter_tie(Rect(10, 1, 100, 2),
351 reinterpret_cast<const void*>(2));
352 EXPECT_TRUE(RTree::Node::CompareVertical(&shorter_tie, &low));
353 EXPECT_FALSE(RTree::Node::CompareVertical(&low, &shorter_tie));
354 }
355
356 TEST_F(RTreeTest, NodeCompareHorizontal) {
357 // One rect with lower x than another should always sort lower than higher x.
358 RTree::Node low(Rect(1, 0, 10, 10), reinterpret_cast<const void*>(1));
359 RTree::Node middle(Rect(5, 0, 10, 10), reinterpret_cast<const void*>(5));
360 EXPECT_TRUE(RTree::Node::CompareHorizontal(&low, &middle));
361 EXPECT_FALSE(RTree::Node::CompareHorizontal(&middle, &low));
362
363 // Try a non-overlapping higher-x rectangle.
364 RTree::Node high(Rect(20, -10, 1, 10), reinterpret_cast<const void*>(10));
365 EXPECT_TRUE(RTree::Node::CompareHorizontal(&low, &high));
366 EXPECT_FALSE(RTree::Node::CompareHorizontal(&high, &low));
367
368 // Ties are broken by lowest bottom x value.
369 RTree::Node shorter_tie(Rect(1, 10, 2, 100),
370 reinterpret_cast<const void*>(2));
371 EXPECT_TRUE(RTree::Node::CompareHorizontal(&shorter_tie, &low));
372 EXPECT_FALSE(RTree::Node::CompareHorizontal(&low, &shorter_tie));
373 }
374
375 TEST_F(RTreeTest, NodeCompareCenterDistanceFromParent) {
376 // Create a test node we can add children to, for distance comparisons.
377 scoped_ptr<RTree::Node> parent(new RTree::Node(0));
378
379 // Add three children, one each with centers at (0, 0), (10, 10), (-9, -9),
380 // around which a bounding box will be centered at (0, 0)
381 RTree::Node* center_zero =
382 new RTree::Node(Rect(-1, -1, 2, 2), reinterpret_cast<const void*>(1));
383 parent->AddChild(center_zero);
384
385 RTree::Node* center_positive =
386 new RTree::Node(Rect(9, 9, 2, 2), reinterpret_cast<const void*>(2));
387 parent->AddChild(center_positive);
388
389 RTree::Node* center_negative =
390 new RTree::Node(Rect(-10, -10, 2, 2), reinterpret_cast<const void*>(3));
391 parent->AddChild(center_negative);
392
393 ValidateNode(parent.get(), 1U, 5U);
394 EXPECT_TRUE(parent->rect_ == Rect(-10, -10, 21, 21));
395
396 EXPECT_TRUE(RTree::Node::CompareCenterDistanceFromParent(center_zero,
397 center_positive));
398 EXPECT_FALSE(RTree::Node::CompareCenterDistanceFromParent(center_positive,
399 center_zero));
400
401 EXPECT_TRUE(RTree::Node::CompareCenterDistanceFromParent(center_zero,
402 center_negative));
403 EXPECT_FALSE(RTree::Node::CompareCenterDistanceFromParent(center_negative,
404 center_zero));
405
406 EXPECT_TRUE(RTree::Node::CompareCenterDistanceFromParent(center_negative,
407 center_positive));
408 EXPECT_FALSE(RTree::Node::CompareCenterDistanceFromParent(center_positive,
409 center_negative));
410 }
411
412 TEST_F(RTreeTest, NodeOverlapIncreaseToAdd) {
413 // Create a test node with three children, for overlap comparisons.
414 scoped_ptr<RTree::Node> parent(new RTree::Node(0));
415
416 // Add three children, each 4 wide and tall, at (0, 0), (3, 3), (6, 6) with
417 // overlapping corners.
418 Rect top(0, 0, 4, 4);
419 parent->AddChild(new RTree::Node(top, reinterpret_cast<const void*>(1)));
420 Rect middle(3, 3, 4, 4);
421 parent->AddChild(new RTree::Node(middle, reinterpret_cast<const void*>(2)));
422 Rect bottom(6, 6, 4, 4);
423 parent->AddChild(new RTree::Node(bottom, reinterpret_cast<const void*>(3)));
424 ValidateNode(parent.get(), 1U, 5U);
425
426 // Test a rect in corner.
427 Rect corner(0, 0, 1, 1);
428 Rect expanded = top;
429 expanded.Union(corner);
430 // It should not add any overlap to add this to the first child at (0, 0);
431 EXPECT_EQ(parent->OverlapIncreaseToAdd(corner, 0, expanded), 0);
432
433 expanded = middle;
434 expanded.Union(corner);
435 // Overlap for middle rectangle should increase from 2 pixels at (3, 3) and
436 // (6, 6) to 17 pixels, as it will now cover 4x4 rectangle top,
437 // so a change of +15
438 EXPECT_EQ(parent->OverlapIncreaseToAdd(corner, 1, expanded), 15);
439
440 expanded = bottom;
441 expanded.Union(corner);
442 // Overlap for bottom rectangle should increase from 1 pixel at (6, 6) to
443 // 32 pixels, as it will now cover both 4x4 rectangles top and middle,
444 // so a change of 31
445 EXPECT_EQ(parent->OverlapIncreaseToAdd(corner, 2, expanded), 31);
446
447 // Test a rect that doesn't overlap with anything, in the far right corner.
448 Rect far_corner(9, 0, 1, 1);
449 expanded = top;
450 expanded.Union(far_corner);
451 // Overlap of top should go from 1 to 4, as it will now cover the entire first
452 // row of pixels in middle.
453 EXPECT_EQ(parent->OverlapIncreaseToAdd(far_corner, 0, expanded), 3);
454
455 expanded = middle;
456 expanded.Union(far_corner);
457 // Overlap of middle should go from 2 to 8, as it will cover the rightmost 4
458 // pixels of top and the top 4 pixles of bottom as it expands.
459 EXPECT_EQ(parent->OverlapIncreaseToAdd(far_corner, 1, expanded), 6);
460
461 expanded = bottom;
462 expanded.Union(far_corner);
463 // Overlap of bottom should go from 1 to 4, as it will now cover the rightmost
464 // 4 pixels of middle.
465 EXPECT_EQ(parent->OverlapIncreaseToAdd(far_corner, 2, expanded), 3);
466 }
467
468 TEST_F(RTreeTest, NodeBuildLowBounds) {
469 ScopedVector<RTree::Node> nodes;
470 nodes.reserve(10);
471 for (int i = 1; i <= 10; ++i) {
472 nodes.push_back(
473 new RTree::Node(Rect(0, 0, i, i), reinterpret_cast<const void*>(i)));
474 }
475 std::vector<Rect> vertical_bounds;
476 std::vector<Rect> horizontal_bounds;
477 RTree::Node::BuildLowBounds(
478 nodes.get(), nodes.get(), &vertical_bounds, &horizontal_bounds);
479 for (int i = 0; i < 10; ++i) {
480 EXPECT_EQ(vertical_bounds[i], Rect(0, 0, i + 1, i + 1));
481 EXPECT_EQ(horizontal_bounds[i], Rect(0, 0, i + 1, i + 1));
482 }
483 }
484
485 TEST_F(RTreeTest, NodeBuildHighBounds) {
486 ScopedVector<RTree::Node> nodes;
487 nodes.reserve(25);
488 for (int i = 0; i < 25; ++i) {
489 nodes.push_back(new RTree::Node(Rect(i, i, 25 - i, 25 - i),
490 reinterpret_cast<const void*>(i)));
491 }
492 std::vector<Rect> vertical_bounds;
493 std::vector<Rect> horizontal_bounds;
494 RTree::Node::BuildHighBounds(
495 nodes.get(), nodes.get(), &vertical_bounds, &horizontal_bounds);
496 for (int i = 0; i < 25; ++i) {
497 EXPECT_EQ(vertical_bounds[i], Rect(i, i, 25 - i, 25 - i));
498 EXPECT_EQ(horizontal_bounds[i], Rect(i, i, 25 - i, 25 - i));
499 }
500 }
501
502 TEST_F(RTreeTest, NodeChooseSplitAxisAndIndex) {
503 std::vector<Rect> low_vertical_bounds;
504 std::vector<Rect> high_vertical_bounds;
505 std::vector<Rect> low_horizontal_bounds;
506 std::vector<Rect> high_horizontal_bounds;
507 // In this test scenario we describe a mirrored, stacked configuration of
508 // horizontal, 1 pixel high rectangles labeled a-f like this:
509 //
510 // shape: | v sort: | h sort: |
511 // -------+---------+---------+
512 // aaaaa | 0 | 0 |
513 // bbb | 1 | 2 |
514 // c | 2 | 4 |
515 // d | 3 | 5 |
516 // eee | 4 | 3 |
517 // fffff | 5 | 1 |
518 //
519 // These are already sorted vertically from top to bottom. Bounding rectangles
520 // of these vertically sorted will be 5 wide, i tall bounding boxes.
521 for (int i = 0; i < 6; ++i) {
522 low_vertical_bounds.push_back(Rect(0, 0, 5, i + 1));
523 high_vertical_bounds.push_back(Rect(0, i, 5, 6 - i));
524 }
525
526 // Low bounds of horizontal sort start with bounds of box a and then jump to
527 // cover everything, as box f is second in horizontal sort.
528 low_horizontal_bounds.push_back(Rect(0, 0, 5, 1));
529 for (int i = 0; i < 5; ++i) {
530 low_horizontal_bounds.push_back(Rect(0, 0, 5, 6));
531 }
532
533 // High horizontal bounds are hand-calculated.
534 high_horizontal_bounds.push_back(Rect(0, 0, 5, 6));
535 high_horizontal_bounds.push_back(Rect(0, 1, 5, 5));
536 high_horizontal_bounds.push_back(Rect(1, 1, 3, 4));
537 high_horizontal_bounds.push_back(Rect(1, 2, 3, 3));
538 high_horizontal_bounds.push_back(Rect(2, 2, 1, 2));
539 high_horizontal_bounds.push_back(Rect(2, 3, 1, 1));
540
541 // This should split vertically, right down the middle.
542 EXPECT_TRUE(RTree::Node::ChooseSplitAxis(low_vertical_bounds,
543 high_vertical_bounds,
544 low_horizontal_bounds,
545 high_horizontal_bounds,
546 2,
547 5));
548 EXPECT_EQ(3U,
549 RTree::Node::ChooseSplitIndex(
550 2, 5, low_vertical_bounds, high_vertical_bounds));
551
552 // We rotate the shape to test horizontal split axis detection:
553 //
554 // +--------+
555 // | a f |
556 // | ab ef |
557 // sort: | abcdef |
558 // | ab ef |
559 // | a f |
560 // |--------+
561 // v sort: | 024531 |
562 // h sort: | 012345 |
563 // +--------+
564 //
565 // Clear out old bounds first.
566 low_vertical_bounds.clear();
567 high_vertical_bounds.clear();
568 low_horizontal_bounds.clear();
569 high_horizontal_bounds.clear();
570
571 // Low bounds of vertical sort start with bounds of box a and then jump to
572 // cover everything, as box f is second in vertical sort.
573 low_vertical_bounds.push_back(Rect(0, 0, 1, 5));
574 for (int i = 0; i < 5; ++i) {
575 low_vertical_bounds.push_back(Rect(0, 0, 6, 5));
576 }
577
578 // High vertical bounds are hand-calculated.
579 high_vertical_bounds.push_back(Rect(0, 0, 6, 5));
580 high_vertical_bounds.push_back(Rect(1, 0, 5, 5));
581 high_vertical_bounds.push_back(Rect(1, 1, 4, 3));
582 high_vertical_bounds.push_back(Rect(2, 1, 3, 3));
583 high_vertical_bounds.push_back(Rect(2, 2, 2, 1));
584 high_vertical_bounds.push_back(Rect(3, 2, 1, 1));
585
586 // These are already sorted horizontally from left to right. Bounding
587 // rectangles of these horizontally sorted will be i wide, 5 tall bounding
588 // boxes.
589 for (int i = 0; i < 6; ++i) {
590 low_horizontal_bounds.push_back(Rect(0, 0, i + 1, 5));
591 high_horizontal_bounds.push_back(Rect(i, 0, 6 - i, 5));
592 }
593
594 // This should split horizontally, right down the middle.
595 EXPECT_FALSE(RTree::Node::ChooseSplitAxis(low_vertical_bounds,
596 high_vertical_bounds,
597 low_horizontal_bounds,
598 high_horizontal_bounds,
599 2,
600 5));
601 EXPECT_EQ(3U,
602 RTree::Node::ChooseSplitIndex(
603 2, 5, low_horizontal_bounds, high_horizontal_bounds));
604 }
605
606 TEST_F(RTreeTest, NodeDivideChildren) {
607 // Create a test node to split.
608 scoped_ptr<RTree::Node> test_node(new RTree::Node(0));
609 std::vector<RTree::Node*> sorted_children;
610 std::vector<Rect> low_bounds;
611 std::vector<Rect> high_bounds;
612 // Insert 10 record nodes, also inserting them into our children array.
613 for (int i = 1; i <= 10; ++i) {
614 RTree::Node* node =
615 new RTree::Node(Rect(0, 0, i, i), reinterpret_cast<const void*>(i));
616 test_node->AddChild(node);
617 sorted_children.push_back(node);
618 low_bounds.push_back(Rect(0, 0, i, i));
619 high_bounds.push_back(Rect(0, 0, 10, 10));
620 }
621 // Split the children in half.
622 scoped_ptr<RTree::Node> split_node(
623 test_node->DivideChildren(low_bounds, high_bounds, sorted_children, 5));
624 // Both nodes should be valid.
625 ValidateNode(test_node.get(), 1U, 10U);
626 ValidateNode(split_node.get(), 1U, 10U);
627 // Both nodes should have five children.
628 EXPECT_EQ(test_node->children_.size(), 5U);
629 EXPECT_EQ(split_node->children_.size(), 5U);
630 // Test node should have children 1-5, split node should have children 6-10.
631 for (int i = 0; i < 5; ++i) {
632 EXPECT_EQ(test_node->children_[i]->key(),
633 reinterpret_cast<const void*>(i + 1));
634 EXPECT_EQ(split_node->children_[i]->key(),
635 reinterpret_cast<const void*>(i + 6));
636 }
637 }
638
639 TEST_F(RTreeTest, NodeRemoveChildNoOrphans) {
640 scoped_ptr<RTree::Node> test_parent(new RTree::Node(0));
641 scoped_ptr<RTree::Node> child_one(
642 new RTree::Node(Rect(0, 0, 1, 1), reinterpret_cast<const void*>(1)));
643 scoped_ptr<RTree::Node> child_two(
644 new RTree::Node(Rect(0, 0, 2, 2), reinterpret_cast<const void*>(2)));
645 scoped_ptr<RTree::Node> child_three(
646 new RTree::Node(Rect(0, 0, 3, 3), reinterpret_cast<const void*>(3)));
647 test_parent->AddChild(child_one.get());
648 test_parent->AddChild(child_two.get());
649 test_parent->AddChild(child_three.get());
650 ValidateNode(test_parent.get(), 1U, 5U);
651 // Remove the middle node.
652 std::vector<RTree::Node*> orphans;
653 EXPECT_EQ(test_parent->RemoveChild(child_two.get(), &orphans), 2U);
654 EXPECT_EQ(orphans.size(), 0U);
655 EXPECT_EQ(test_parent->count(), 2U);
656 test_parent->RecomputeBoundsNoParents();
657 ValidateNode(test_parent.get(), 1U, 5U);
658 // Remove the end node.
659 EXPECT_EQ(test_parent->RemoveChild(child_three.get(), &orphans), 1U);
660 EXPECT_EQ(orphans.size(), 0U);
661 EXPECT_EQ(test_parent->count(), 1U);
662 test_parent->RecomputeBoundsNoParents();
663 ValidateNode(test_parent.get(), 1U, 5U);
664 // Remove the first node.
665 EXPECT_EQ(test_parent->RemoveChild(child_one.get(), &orphans), 0U);
666 EXPECT_EQ(orphans.size(), 0U);
667 EXPECT_EQ(test_parent->count(), 0U);
668 }
669
670 TEST_F(RTreeTest, NodeRemoveChildOrphans) {
671 // Build flattened binary tree of Nodes 4 deep, from the record nodes up.
672 ScopedVector<RTree::Node> nodes;
673 nodes.resize(15);
674 // Indicies 7 through 15 are record nodes.
675 for (int i = 7; i < 15; ++i) {
676 nodes[i] =
677 new RTree::Node(Rect(0, 0, i, i), reinterpret_cast<const void*>(i));
678 }
679 // Nodes 3 through 6 are level 0 (leaves) and get 2 record nodes each.
680 for (int i = 3; i < 7; ++i) {
681 nodes[i] = new RTree::Node(0);
682 nodes[i]->AddChild(nodes[(i * 2) + 1]);
683 nodes[i]->AddChild(nodes[(i * 2) + 2]);
684 }
685 // Nodes 1 and 2 are level 1 and get 2 leaves each.
686 for (int i = 1; i < 3; ++i) {
687 nodes[i] = new RTree::Node(1);
688 nodes[i]->AddChild(nodes[(i * 2) + 1]);
689 nodes[i]->AddChild(nodes[(i * 2) + 2]);
690 }
691 // Node 0 is level 2 and gets 2 childen.
692 nodes[0] = new RTree::Node(2);
693 nodes[0]->AddChild(nodes[1]);
694 nodes[0]->AddChild(nodes[2]);
695 // This should now be a valid node structure.
696 ValidateNode(nodes[0], 2U, 2U);
697
698 // Now remove the level 0 nodes, so we get the record nodes as orphans.
699 std::vector<RTree::Node*> orphans;
700 EXPECT_EQ(nodes[1]->RemoveChild(nodes[3], &orphans), 1U);
701 EXPECT_EQ(nodes[1]->RemoveChild(nodes[4], &orphans), 0U);
702 EXPECT_EQ(nodes[2]->RemoveChild(nodes[5], &orphans), 1U);
703 EXPECT_EQ(nodes[2]->RemoveChild(nodes[6], &orphans), 0U);
704
705 // Orphans should be nodes 7 through 15 in order.
706 EXPECT_EQ(orphans.size(), 8U);
707 for (int i = 0; i < 8; ++i) {
708 EXPECT_EQ(orphans[i], nodes[i + 7]);
709 }
710
711 // Now we remove nodes 1 and 2 from the root, expecting no further orphans.
712 // This prevents a crash due to double-delete on test exit, as no node should
713 // own any other node right now.
714 EXPECT_EQ(nodes[0]->RemoveChild(nodes[1], &orphans), 1U);
715 EXPECT_EQ(nodes[0]->RemoveChild(nodes[2], &orphans), 0U);
716 }
717
718 TEST_F(RTreeTest, NodeRemoveAndReturnLastChild) {
719 scoped_ptr<RTree::Node> test_parent(new RTree::Node(0));
720 scoped_ptr<RTree::Node> child_one(
721 new RTree::Node(Rect(0, 0, 1, 1), reinterpret_cast<const void*>(1)));
722 scoped_ptr<RTree::Node> child_two(
723 new RTree::Node(Rect(0, 0, 2, 2), reinterpret_cast<const void*>(2)));
724 scoped_ptr<RTree::Node> child_three(
725 new RTree::Node(Rect(0, 0, 3, 3), reinterpret_cast<const void*>(3)));
726 test_parent->AddChild(child_one.get());
727 test_parent->AddChild(child_two.get());
728 test_parent->AddChild(child_three.get());
729 ValidateNode(test_parent.get(), 1U, 5U);
730
731 EXPECT_EQ(test_parent->RemoveAndReturnLastChild(), child_three.get());
732 EXPECT_EQ(test_parent->count(), 2U);
733 test_parent->RecomputeBoundsNoParents();
734 ValidateNode(test_parent.get(), 1U, 5U);
735
736 EXPECT_EQ(test_parent->RemoveAndReturnLastChild(), child_two.get());
737 EXPECT_EQ(test_parent->count(), 1U);
738 test_parent->RecomputeBoundsNoParents();
739 ValidateNode(test_parent.get(), 1U, 5U);
740
741 EXPECT_EQ(test_parent->RemoveAndReturnLastChild(), child_one.get());
742 EXPECT_EQ(test_parent->count(), 0U);
743 }
744
745 // TODO: investigate and remove needless children ordering assumptions.
746 TEST_F(RTreeTest, NodeLeastOverlapIncrease) {
747 scoped_ptr<RTree::Node> test_parent(new RTree::Node(0));
748 // Construct 4 nodes with 1x2 retangles spaced horizontally 1 pixel apart, or:
749 //
750 // a b c d
751 // a b c d
752 //
753 for (int i = 0; i < 4; ++i) {
754 test_parent->AddChild(new RTree::Node(
755 Rect(i * 2, 0, 1, 2), reinterpret_cast<const void*>(i + 1)));
756 }
757
758 ValidateNode(test_parent.get(), 1U, 5U);
759
760 // Test rect at (7, 0) should require minimum overlap on the part of the
761 // fourth rectangle to add:
762 //
763 // a b c dT
764 // a b c d
765 //
766 scoped_ptr<RTree::Node> test_node_far(
767 new RTree::Node(Rect(7, 0, 1, 1), reinterpret_cast<const void*>(7)));
768 EXPECT_EQ(test_parent->LeastOverlapIncrease(test_node_far.get()),
769 test_parent->children_[3]);
770
771 // Test rect covering the bottom half of all children should be a 4-way tie,
772 // so LeastOverlapIncrease should return NULL:
773 //
774 // a b c d
775 // TTTTTTT
776 //
777 scoped_ptr<RTree::Node> test_node_tie(
778 new RTree::Node(Rect(0, 1, 7, 1), reinterpret_cast<const void*>(8)));
779 EXPECT_TRUE(test_parent->LeastOverlapIncrease(test_node_tie.get()) == NULL);
780
781 // Test rect completely inside c should return the third rectangle:
782 //
783 // a b T d
784 // a b c d
785 //
786 scoped_ptr<RTree::Node> test_node_inside(
787 new RTree::Node(Rect(4, 0, 1, 1), reinterpret_cast<const void*>(8)));
788 EXPECT_EQ(test_parent->LeastOverlapIncrease(test_node_inside.get()),
789 test_parent->children_[2]);
790
791 // Add a rectangle that overlaps completely with rectangle c, to test
792 // when there is a tie between two completely contained rectangles:
793 //
794 // a b Ted
795 // a b eed
796 //
797 test_parent->AddChild(
798 new RTree::Node(Rect(4, 0, 2, 2), reinterpret_cast<const void*>(9)));
799 EXPECT_TRUE(test_parent->LeastOverlapIncrease(test_node_inside.get()) ==
800 NULL);
801 }
802
803 TEST_F(RTreeTest, NodeLeastAreaEnlargement) {
804 scoped_ptr<RTree::Node> test_parent(new RTree::Node(0));
805 // Construct 4 nodes in a cross-hairs style configuration:
806 //
807 // a
808 // b c
809 // d
810 //
811 test_parent->AddChild(
812 new RTree::Node(Rect(1, 0, 1, 1), reinterpret_cast<const void*>(1)));
813 test_parent->AddChild(
814 new RTree::Node(Rect(0, 1, 1, 1), reinterpret_cast<const void*>(2)));
815 test_parent->AddChild(
816 new RTree::Node(Rect(2, 1, 1, 1), reinterpret_cast<const void*>(3)));
817 test_parent->AddChild(
818 new RTree::Node(Rect(1, 2, 1, 1), reinterpret_cast<const void*>(4)));
819
820 ValidateNode(test_parent.get(), 1U, 5U);
821
822 // Test rect at (1, 3) should require minimum area to add to Node d:
823 //
824 // a
825 // b c
826 // d
827 // T
828 //
829 scoped_ptr<RTree::Node> test_node_below(
830 new RTree::Node(Rect(1, 3, 1, 1), reinterpret_cast<const void*>(5)));
831 EXPECT_EQ(test_parent->LeastAreaEnlargement(test_node_below.get()),
832 test_parent->children_[3]);
833
834 // Test rect completely inside b should require minimum area to add to Node b:
835 //
836 // a
837 // T c
838 // d
839 //
840 scoped_ptr<RTree::Node> test_node_inside(
841 new RTree::Node(Rect(0, 1, 1, 1), reinterpret_cast<const void*>(6)));
842 EXPECT_EQ(test_parent->LeastAreaEnlargement(test_node_inside.get()),
843 test_parent->children_[1]);
844
845 // Add e at (0, 1) to overlap b and c, to test tie-breaking:
846 //
847 // a
848 // eee
849 // d
850 //
851 test_parent->AddChild(
852 new RTree::Node(Rect(0, 1, 3, 1), reinterpret_cast<const void*>(7)));
853
854 ValidateNode(test_parent.get(), 1U, 5U);
855
856 // Test rect at (3, 1) should tie between c and e, but c has smaller area so
857 // the algorithm should select c:
858 //
859 //
860 // a
861 // eeeT
862 // d
863 //
864 scoped_ptr<RTree::Node> test_node_tie_breaker(
865 new RTree::Node(Rect(3, 1, 1, 1), reinterpret_cast<const void*>(8)));
866 EXPECT_EQ(test_parent->LeastAreaEnlargement(test_node_tie_breaker.get()),
867 test_parent->children_[2]);
868 }
869
870 } // namespace gfx
OLDNEW
« ui/gfx/geometry/r_tree.cc ('K') | « ui/gfx/geometry/r_tree.cc ('k') | ui/gfx/gfx.gyp » ('j') | no next file with comments »

Powered by Google App Engine
This is Rietveld 408576698