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 "testing/gtest/include/gtest/gtest.h" 6#include "ui/gfx/geometry/r_tree.h" 7#include "ui/gfx/geometry/r_tree_base.h" 8#include "ui/gfx/geometry/rect.h" 9 10namespace gfx { 11 12class RTreeTest : public ::testing::Test { 13 protected: 14 typedef RTree<int> RT; 15 16 // Given a pointer to an RTree, traverse it and verify that its internal 17 // structure is consistent with RTree semantics. 18 void ValidateRTree(RTreeBase* rt) { 19 // If RTree is empty it should have an empty rectangle. 20 if (!rt->root()->count()) { 21 EXPECT_TRUE(rt->root()->rect().IsEmpty()); 22 EXPECT_EQ(0, rt->root()->Level()); 23 return; 24 } 25 // Root is allowed to have fewer than min_children_ but never more than 26 // max_children_. 27 EXPECT_LE(rt->root()->count(), rt->max_children_); 28 // The root should never be a record node. 29 EXPECT_GT(rt->root()->Level(), -1); 30 // The root should never have a parent pointer. 31 EXPECT_TRUE(rt->root()->parent() == NULL); 32 // Bounds must be consistent on the root. 33 CheckBoundsConsistent(rt->root()); 34 for (size_t i = 0; i < rt->root()->count(); ++i) { 35 ValidateNode( 36 rt->root()->child(i), rt->min_children_, rt->max_children_); 37 } 38 } 39 40 // Recursive descent method used by ValidateRTree to check each node within 41 // the RTree for consistency with RTree semantics. 42 void ValidateNode(const RTreeBase::NodeBase* node_base, 43 size_t min_children, 44 size_t max_children) { 45 if (node_base->Level() >= 0) { 46 const RTreeBase::Node* node = 47 static_cast<const RTreeBase::Node*>(node_base); 48 EXPECT_GE(node->count(), min_children); 49 EXPECT_LE(node->count(), max_children); 50 CheckBoundsConsistent(node); 51 for (size_t i = 0; i < node->count(); ++i) 52 ValidateNode(node->child(i), min_children, max_children); 53 } 54 } 55 56 // Check bounds are consistent with children bounds, and other checks 57 // convenient to do while enumerating the children of node. 58 void CheckBoundsConsistent(const RTreeBase::Node* node) { 59 EXPECT_FALSE(node->rect().IsEmpty()); 60 Rect check_bounds; 61 for (size_t i = 0; i < node->count(); ++i) { 62 const RTreeBase::NodeBase* child_node = node->child(i); 63 check_bounds.Union(child_node->rect()); 64 EXPECT_EQ(node->Level() - 1, child_node->Level()); 65 EXPECT_EQ(node, child_node->parent()); 66 } 67 EXPECT_EQ(check_bounds, node->rect()); 68 } 69 70 // Adds count squares stacked around the point (0,0) with key equal to width. 71 void AddStackedSquares(RT* rt, int count) { 72 for (int i = 1; i <= count; ++i) { 73 rt->Insert(Rect(0, 0, i, i), i); 74 ValidateRTree(static_cast<RTreeBase*>(rt)); 75 } 76 } 77 78 // Given an unordered list of matching keys, verifies that it contains all 79 // values [1..length] for the length of that list. 80 void VerifyAllKeys(const RT::Matches& keys) { 81 for (size_t i = 1; i <= keys.size(); ++i) 82 EXPECT_EQ(1U, keys.count(i)); 83 } 84 85 // Given a node and a rectangle, builds an expanded rectangle list where the 86 // ith element of the vector is the union of the rectangle of the ith child of 87 // the node and the argument rectangle. 88 void BuildExpandedRects(RTreeBase::Node* node, 89 const Rect& rect, 90 std::vector<Rect>* expanded_rects) { 91 expanded_rects->clear(); 92 expanded_rects->reserve(node->count()); 93 for (size_t i = 0; i < node->count(); ++i) { 94 Rect expanded_rect(rect); 95 expanded_rect.Union(node->child(i)->rect()); 96 expanded_rects->push_back(expanded_rect); 97 } 98 } 99}; 100 101class RTreeNodeTest : public RTreeTest { 102 protected: 103 typedef RTreeBase::NodeBase RTreeNodeBase; 104 typedef RT::Record RTreeRecord; 105 typedef RTreeBase::Node RTreeNode; 106 typedef RTreeBase::Node::Rects RTreeRects; 107 typedef RTreeBase::Nodes RTreeNodes; 108 109 // Accessors to private members of RTree::Node. 110 const RTreeRecord* record(RTreeNode* node, size_t i) { 111 return static_cast<const RTreeRecord*>(node->child(i)); 112 } 113 114 // Provides access for tests to private methods of RTree::Node. 115 scoped_ptr<RTreeNode> NewNodeAtLevel(size_t level) { 116 return make_scoped_ptr(new RTreeBase::Node(level)); 117 } 118 119 void NodeRecomputeLocalBounds(RTreeNodeBase* node) { 120 node->RecomputeLocalBounds(); 121 } 122 123 bool NodeCompareVertical(RTreeNodeBase* a, RTreeNodeBase* b) { 124 return RTreeBase::Node::CompareVertical(a, b); 125 } 126 127 bool NodeCompareHorizontal(RTreeNodeBase* a, RTreeNodeBase* b) { 128 return RTreeBase::Node::CompareHorizontal(a, b); 129 } 130 131 bool NodeCompareCenterDistanceFromParent( 132 const RTreeNodeBase* a, const RTreeNodeBase* b) { 133 return RTreeBase::Node::CompareCenterDistanceFromParent(a, b); 134 } 135 136 int NodeOverlapIncreaseToAdd(RTreeNode* node, 137 const Rect& rect, 138 const RTreeNodeBase* candidate_node, 139 const Rect& expanded_rect) { 140 return node->OverlapIncreaseToAdd(rect, candidate_node, expanded_rect); 141 } 142 143 void NodeBuildLowBounds(const std::vector<RTreeNodeBase*>& vertical_sort, 144 const std::vector<RTreeNodeBase*>& horizontal_sort, 145 RTreeRects* vertical_bounds, 146 RTreeRects* horizontal_bounds) { 147 RTreeBase::Node::BuildLowBounds( 148 vertical_sort, horizontal_sort, vertical_bounds, horizontal_bounds); 149 } 150 151 void NodeBuildHighBounds(const std::vector<RTreeNodeBase*>& vertical_sort, 152 const std::vector<RTreeNodeBase*>& horizontal_sort, 153 RTreeRects* vertical_bounds, 154 RTreeRects* horizontal_bounds) { 155 RTreeBase::Node::BuildHighBounds( 156 vertical_sort, horizontal_sort, vertical_bounds, horizontal_bounds); 157 } 158 159 int NodeSmallestMarginSum(size_t start_index, 160 size_t end_index, 161 const RTreeRects& low_bounds, 162 const RTreeRects& high_bounds) { 163 return RTreeBase::Node::SmallestMarginSum( 164 start_index, end_index, low_bounds, high_bounds); 165 } 166 167 size_t NodeChooseSplitIndex(size_t min_children, 168 size_t max_children, 169 const RTreeRects& low_bounds, 170 const RTreeRects& high_bounds) { 171 return RTreeBase::Node::ChooseSplitIndex( 172 min_children, max_children, low_bounds, high_bounds); 173 } 174 175 scoped_ptr<RTreeNodeBase> NodeDivideChildren( 176 RTreeNode* node, 177 const RTreeRects& low_bounds, 178 const RTreeRects& high_bounds, 179 const std::vector<RTreeNodeBase*>& sorted_children, 180 size_t split_index) { 181 return node->DivideChildren( 182 low_bounds, high_bounds, sorted_children, split_index); 183 } 184 185 RTreeNode* NodeLeastOverlapIncrease(RTreeNode* node, 186 const Rect& node_rect, 187 const RTreeRects& expanded_rects) { 188 return node->LeastOverlapIncrease(node_rect, expanded_rects); 189 } 190 191 RTreeNode* NodeLeastAreaEnlargement(RTreeNode* node, 192 const Rect& node_rect, 193 const RTreeRects& expanded_rects) { 194 return node->LeastAreaEnlargement(node_rect, expanded_rects); 195 } 196}; 197 198// RTreeNodeTest -------------------------------------------------------------- 199 200TEST_F(RTreeNodeTest, RemoveNodesForReinsert) { 201 // Make a leaf node for testing removal from. 202 scoped_ptr<RTreeNode> test_node(new RTreeNode); 203 // Build 20 record nodes with rectangle centers going from (1,1) to (20,20) 204 for (int i = 1; i <= 20; ++i) 205 test_node->AddChild(scoped_ptr<RTreeNodeBase>( 206 new RTreeRecord(Rect(i - 1, i - 1, 2, 2), i))); 207 208 // Quick verification of the node before removing children. 209 ValidateNode(test_node.get(), 1U, 20U); 210 // Use a scoped vector to delete all children that get removed from the Node. 211 RTreeNodes removals; 212 test_node->RemoveNodesForReinsert(1, &removals); 213 // Should have gotten back 1 node pointer. 214 EXPECT_EQ(1U, removals.size()); 215 // There should be 19 left in the test_node. 216 EXPECT_EQ(19U, test_node->count()); 217 // If we fix up the bounds on the test_node, it should verify. 218 NodeRecomputeLocalBounds(test_node.get()); 219 ValidateNode(test_node.get(), 2U, 20U); 220 // The node we removed should be node 10, as it was exactly in the center. 221 EXPECT_EQ(10, static_cast<RTreeRecord*>(removals[0])->key()); 222 223 // Now remove the next 2. 224 removals.clear(); 225 test_node->RemoveNodesForReinsert(2, &removals); 226 EXPECT_EQ(2U, removals.size()); 227 EXPECT_EQ(17U, test_node->count()); 228 NodeRecomputeLocalBounds(test_node.get()); 229 ValidateNode(test_node.get(), 2U, 20U); 230 // Lastly the 2 nodes we should have gotten back are keys 9 and 11, as their 231 // centers were the closest to the center of the node bounding box. 232 base::hash_set<intptr_t> results_hash; 233 results_hash.insert(static_cast<RTreeRecord*>(removals[0])->key()); 234 results_hash.insert(static_cast<RTreeRecord*>(removals[1])->key()); 235 EXPECT_EQ(1U, results_hash.count(9)); 236 EXPECT_EQ(1U, results_hash.count(11)); 237} 238 239TEST_F(RTreeNodeTest, CompareVertical) { 240 // One rect with lower y than another should always sort lower. 241 RTreeRecord low(Rect(0, 1, 10, 10), 1); 242 RTreeRecord middle(Rect(0, 5, 10, 10), 5); 243 EXPECT_TRUE(NodeCompareVertical(&low, &middle)); 244 EXPECT_FALSE(NodeCompareVertical(&middle, &low)); 245 246 // Try a non-overlapping higher-y rectangle. 247 RTreeRecord high(Rect(-10, 20, 10, 1), 10); 248 EXPECT_TRUE(NodeCompareVertical(&low, &high)); 249 EXPECT_FALSE(NodeCompareVertical(&high, &low)); 250 251 // Ties are broken by lowest bottom y value. 252 RTreeRecord shorter_tie(Rect(10, 1, 100, 2), 2); 253 EXPECT_TRUE(NodeCompareVertical(&shorter_tie, &low)); 254 EXPECT_FALSE(NodeCompareVertical(&low, &shorter_tie)); 255} 256 257TEST_F(RTreeNodeTest, CompareHorizontal) { 258 // One rect with lower x than another should always sort lower than higher x. 259 RTreeRecord low(Rect(1, 0, 10, 10), 1); 260 RTreeRecord middle(Rect(5, 0, 10, 10), 5); 261 EXPECT_TRUE(NodeCompareHorizontal(&low, &middle)); 262 EXPECT_FALSE(NodeCompareHorizontal(&middle, &low)); 263 264 // Try a non-overlapping higher-x rectangle. 265 RTreeRecord high(Rect(20, -10, 1, 10), 10); 266 EXPECT_TRUE(NodeCompareHorizontal(&low, &high)); 267 EXPECT_FALSE(NodeCompareHorizontal(&high, &low)); 268 269 // Ties are broken by lowest bottom x value. 270 RTreeRecord shorter_tie(Rect(1, 10, 2, 100), 2); 271 EXPECT_TRUE(NodeCompareHorizontal(&shorter_tie, &low)); 272 EXPECT_FALSE(NodeCompareHorizontal(&low, &shorter_tie)); 273} 274 275TEST_F(RTreeNodeTest, CompareCenterDistanceFromParent) { 276 // Create a test node we can add children to, for distance comparisons. 277 scoped_ptr<RTreeNode> parent(new RTreeNode); 278 279 // Add three children, one each with centers at (0, 0), (10, 10), (-9, -9), 280 // around which a bounding box will be centered at (0, 0) 281 scoped_ptr<RTreeRecord> center_zero(new RTreeRecord(Rect(-1, -1, 2, 2), 1)); 282 parent->AddChild(center_zero.PassAs<RTreeNodeBase>()); 283 284 scoped_ptr<RTreeRecord> center_positive(new RTreeRecord(Rect(9, 9, 2, 2), 2)); 285 parent->AddChild(center_positive.PassAs<RTreeNodeBase>()); 286 287 scoped_ptr<RTreeRecord> center_negative( 288 new RTreeRecord(Rect(-10, -10, 2, 2), 3)); 289 parent->AddChild(center_negative.PassAs<RTreeNodeBase>()); 290 291 ValidateNode(parent.get(), 1U, 5U); 292 EXPECT_EQ(Rect(-10, -10, 21, 21), parent->rect()); 293 294 EXPECT_TRUE( 295 NodeCompareCenterDistanceFromParent(parent->child(0), parent->child(1))); 296 EXPECT_FALSE( 297 NodeCompareCenterDistanceFromParent(parent->child(1), parent->child(0))); 298 EXPECT_TRUE( 299 NodeCompareCenterDistanceFromParent(parent->child(0), parent->child(2))); 300 EXPECT_FALSE( 301 NodeCompareCenterDistanceFromParent(parent->child(2), parent->child(0))); 302 EXPECT_TRUE( 303 NodeCompareCenterDistanceFromParent(parent->child(2), parent->child(1))); 304 EXPECT_FALSE( 305 NodeCompareCenterDistanceFromParent(parent->child(1), parent->child(2))); 306} 307 308TEST_F(RTreeNodeTest, OverlapIncreaseToAdd) { 309 // Create a test node with three children, for overlap comparisons. 310 scoped_ptr<RTreeNode> parent(new RTreeNode); 311 312 // Add three children, each 4 wide and tall, at (0, 0), (3, 3), (6, 6) with 313 // overlapping corners. 314 Rect top(0, 0, 4, 4); 315 parent->AddChild(scoped_ptr<RTreeNodeBase>(new RTreeRecord(top, 1))); 316 Rect middle(3, 3, 4, 4); 317 parent->AddChild(scoped_ptr<RTreeNodeBase>(new RTreeRecord(middle, 2))); 318 Rect bottom(6, 6, 4, 4); 319 parent->AddChild(scoped_ptr<RTreeNodeBase>(new RTreeRecord(bottom, 3))); 320 ValidateNode(parent.get(), 1U, 5U); 321 322 // Test a rect in corner. 323 Rect corner(0, 0, 1, 1); 324 Rect expanded = top; 325 expanded.Union(corner); 326 // It should not add any overlap to add this to the first child at (0, 0). 327 EXPECT_EQ(0, NodeOverlapIncreaseToAdd( 328 parent.get(), corner, parent->child(0), expanded)); 329 330 expanded = middle; 331 expanded.Union(corner); 332 // Overlap for middle rectangle should increase from 2 pixels at (3, 3) and 333 // (6, 6) to 17 pixels, as it will now cover 4x4 rectangle top, 334 // so a change of +15. 335 EXPECT_EQ(15, NodeOverlapIncreaseToAdd( 336 parent.get(), corner, parent->child(1), expanded)); 337 338 expanded = bottom; 339 expanded.Union(corner); 340 // Overlap for bottom rectangle should increase from 1 pixel at (6, 6) to 341 // 32 pixels, as it will now cover both 4x4 rectangles top and middle, 342 // so a change of 31. 343 EXPECT_EQ(31, NodeOverlapIncreaseToAdd( 344 parent.get(), corner, parent->child(2), expanded)); 345 346 // Test a rect that doesn't overlap with anything, in the far right corner. 347 Rect far_corner(9, 0, 1, 1); 348 expanded = top; 349 expanded.Union(far_corner); 350 // Overlap of top should go from 1 to 4, as it will now cover the entire first 351 // row of pixels in middle. 352 EXPECT_EQ(3, NodeOverlapIncreaseToAdd( 353 parent.get(), far_corner, parent->child(0), expanded)); 354 355 expanded = middle; 356 expanded.Union(far_corner); 357 // Overlap of middle should go from 2 to 8, as it will cover the rightmost 4 358 // pixels of top and the top 4 pixels of bottom as it expands. 359 EXPECT_EQ(6, NodeOverlapIncreaseToAdd( 360 parent.get(), far_corner, parent->child(1), expanded)); 361 362 expanded = bottom; 363 expanded.Union(far_corner); 364 // Overlap of bottom should go from 1 to 4, as it will now cover the rightmost 365 // 4 pixels of middle. 366 EXPECT_EQ(3, NodeOverlapIncreaseToAdd( 367 parent.get(), far_corner, parent->child(2), expanded)); 368} 369 370TEST_F(RTreeNodeTest, BuildLowBounds) { 371 RTreeNodes records; 372 records.reserve(10); 373 for (int i = 1; i <= 10; ++i) 374 records.push_back(new RTreeRecord(Rect(0, 0, i, i), i)); 375 376 RTreeRects vertical_bounds; 377 RTreeRects horizontal_bounds; 378 NodeBuildLowBounds( 379 records.get(), records.get(), &vertical_bounds, &horizontal_bounds); 380 for (int i = 0; i < 10; ++i) { 381 EXPECT_EQ(records[i]->rect(), vertical_bounds[i]); 382 EXPECT_EQ(records[i]->rect(), horizontal_bounds[i]); 383 } 384} 385 386TEST_F(RTreeNodeTest, BuildHighBounds) { 387 RTreeNodes records; 388 records.reserve(25); 389 for (int i = 0; i < 25; ++i) 390 records.push_back(new RTreeRecord(Rect(i, i, 25 - i, 25 - i), i)); 391 392 RTreeRects vertical_bounds; 393 RTreeRects horizontal_bounds; 394 NodeBuildHighBounds( 395 records.get(), records.get(), &vertical_bounds, &horizontal_bounds); 396 for (int i = 0; i < 25; ++i) { 397 EXPECT_EQ(records[i]->rect(), vertical_bounds[i]); 398 EXPECT_EQ(records[i]->rect(), horizontal_bounds[i]); 399 } 400} 401 402TEST_F(RTreeNodeTest, ChooseSplitAxisAndIndexVertical) { 403 RTreeRects low_vertical_bounds; 404 RTreeRects high_vertical_bounds; 405 RTreeRects low_horizontal_bounds; 406 RTreeRects high_horizontal_bounds; 407 // In this test scenario we describe a mirrored, stacked configuration of 408 // horizontal, 1 pixel high rectangles labeled a-f like this: 409 // 410 // shape: | v sort: | h sort: | 411 // -------+---------+---------+ 412 // aaaaa | 0 | 0 | 413 // bbb | 1 | 2 | 414 // c | 2 | 4 | 415 // d | 3 | 5 | 416 // eee | 4 | 3 | 417 // fffff | 5 | 1 | 418 // 419 // These are already sorted vertically from top to bottom. Bounding rectangles 420 // of these vertically sorted will be 5 wide, i tall bounding boxes. 421 for (int i = 0; i < 6; ++i) { 422 low_vertical_bounds.push_back(Rect(0, 0, 5, i + 1)); 423 high_vertical_bounds.push_back(Rect(0, i, 5, 6 - i)); 424 } 425 426 // Low bounds of horizontal sort start with bounds of box a and then jump to 427 // cover everything, as box f is second in horizontal sort. 428 low_horizontal_bounds.push_back(Rect(0, 0, 5, 1)); 429 for (int i = 0; i < 5; ++i) 430 low_horizontal_bounds.push_back(Rect(0, 0, 5, 6)); 431 432 // High horizontal bounds are hand-calculated. 433 high_horizontal_bounds.push_back(Rect(0, 0, 5, 6)); 434 high_horizontal_bounds.push_back(Rect(0, 1, 5, 5)); 435 high_horizontal_bounds.push_back(Rect(1, 1, 3, 4)); 436 high_horizontal_bounds.push_back(Rect(1, 2, 3, 3)); 437 high_horizontal_bounds.push_back(Rect(2, 2, 1, 2)); 438 high_horizontal_bounds.push_back(Rect(2, 3, 1, 1)); 439 440 int smallest_vertical_margin = 441 NodeSmallestMarginSum(2, 3, low_vertical_bounds, high_vertical_bounds); 442 int smallest_horizontal_margin = NodeSmallestMarginSum( 443 2, 3, low_horizontal_bounds, high_horizontal_bounds); 444 EXPECT_LT(smallest_vertical_margin, smallest_horizontal_margin); 445 446 EXPECT_EQ( 447 3U, 448 NodeChooseSplitIndex(2, 5, low_vertical_bounds, high_vertical_bounds)); 449} 450 451TEST_F(RTreeNodeTest, ChooseSplitAxisAndIndexHorizontal) { 452 RTreeRects low_vertical_bounds; 453 RTreeRects high_vertical_bounds; 454 RTreeRects low_horizontal_bounds; 455 RTreeRects high_horizontal_bounds; 456 // We rotate the shape from ChooseSplitAxisAndIndexVertical to test 457 // horizontal split axis detection: 458 // 459 // +--------+ 460 // | a f | 461 // | ab ef | 462 // sort: | abcdef | 463 // | ab ef | 464 // | a f | 465 // |--------+ 466 // v sort: | 024531 | 467 // h sort: | 012345 | 468 // +--------+ 469 // 470 // Low bounds of vertical sort start with bounds of box a and then jump to 471 // cover everything, as box f is second in vertical sort. 472 low_vertical_bounds.push_back(Rect(0, 0, 1, 5)); 473 for (int i = 0; i < 5; ++i) 474 low_vertical_bounds.push_back(Rect(0, 0, 6, 5)); 475 476 // High vertical bounds are hand-calculated. 477 high_vertical_bounds.push_back(Rect(0, 0, 6, 5)); 478 high_vertical_bounds.push_back(Rect(1, 0, 5, 5)); 479 high_vertical_bounds.push_back(Rect(1, 1, 4, 3)); 480 high_vertical_bounds.push_back(Rect(2, 1, 3, 3)); 481 high_vertical_bounds.push_back(Rect(2, 2, 2, 1)); 482 high_vertical_bounds.push_back(Rect(3, 2, 1, 1)); 483 484 // These are already sorted horizontally from left to right. Bounding 485 // rectangles of these horizontally sorted will be i wide, 5 tall bounding 486 // boxes. 487 for (int i = 0; i < 6; ++i) { 488 low_horizontal_bounds.push_back(Rect(0, 0, i + 1, 5)); 489 high_horizontal_bounds.push_back(Rect(i, 0, 6 - i, 5)); 490 } 491 492 int smallest_vertical_margin = 493 NodeSmallestMarginSum(2, 3, low_vertical_bounds, high_vertical_bounds); 494 int smallest_horizontal_margin = NodeSmallestMarginSum( 495 2, 3, low_horizontal_bounds, high_horizontal_bounds); 496 497 EXPECT_GT(smallest_vertical_margin, smallest_horizontal_margin); 498 499 EXPECT_EQ(3U, 500 NodeChooseSplitIndex( 501 2, 5, low_horizontal_bounds, high_horizontal_bounds)); 502} 503 504TEST_F(RTreeNodeTest, DivideChildren) { 505 // Create a test node to split. 506 scoped_ptr<RTreeNode> test_node(new RTreeNode); 507 std::vector<RTreeNodeBase*> sorted_children; 508 RTreeRects low_bounds; 509 RTreeRects high_bounds; 510 // Insert 10 record nodes, also inserting them into our children array. 511 for (int i = 1; i <= 10; ++i) { 512 scoped_ptr<RTreeRecord> record(new RTreeRecord(Rect(0, 0, i, i), i)); 513 sorted_children.push_back(record.get()); 514 test_node->AddChild(record.PassAs<RTreeNodeBase>()); 515 low_bounds.push_back(Rect(0, 0, i, i)); 516 high_bounds.push_back(Rect(0, 0, 10, 10)); 517 } 518 // Split the children in half. 519 scoped_ptr<RTreeNodeBase> split_node_base(NodeDivideChildren( 520 test_node.get(), low_bounds, high_bounds, sorted_children, 5)); 521 RTreeNode* split_node = static_cast<RTreeNode*>(split_node_base.get()); 522 // Both nodes should be valid. 523 ValidateNode(test_node.get(), 1U, 10U); 524 ValidateNode(split_node, 1U, 10U); 525 // Both nodes should have five children. 526 EXPECT_EQ(5U, test_node->count()); 527 EXPECT_EQ(5U, split_node->count()); 528 // Test node should have children 1-5, split node should have children 6-10. 529 for (int i = 0; i < 5; ++i) { 530 EXPECT_EQ(i + 1, record(test_node.get(), i)->key()); 531 EXPECT_EQ(i + 6, record(split_node, i)->key()); 532 } 533} 534 535TEST_F(RTreeNodeTest, RemoveChildNoOrphans) { 536 scoped_ptr<RTreeNode> test_parent(new RTreeNode); 537 test_parent->AddChild( 538 scoped_ptr<RTreeNodeBase>(new RTreeRecord(Rect(0, 0, 1, 1), 1))); 539 test_parent->AddChild( 540 scoped_ptr<RTreeNodeBase>(new RTreeRecord(Rect(0, 0, 2, 2), 2))); 541 test_parent->AddChild( 542 scoped_ptr<RTreeNodeBase>(new RTreeRecord(Rect(0, 0, 3, 3), 3))); 543 ValidateNode(test_parent.get(), 1U, 5U); 544 545 RTreeNodes orphans; 546 547 // Remove the middle node. 548 scoped_ptr<RTreeNodeBase> middle_child( 549 test_parent->RemoveChild(test_parent->child(1), &orphans)); 550 EXPECT_EQ(0U, orphans.size()); 551 EXPECT_EQ(2U, test_parent->count()); 552 NodeRecomputeLocalBounds(test_parent.get()); 553 ValidateNode(test_parent.get(), 1U, 5U); 554 555 // Remove the end node. 556 scoped_ptr<RTreeNodeBase> end_child( 557 test_parent->RemoveChild(test_parent->child(1), &orphans)); 558 EXPECT_EQ(0U, orphans.size()); 559 EXPECT_EQ(1U, test_parent->count()); 560 NodeRecomputeLocalBounds(test_parent.get()); 561 ValidateNode(test_parent.get(), 1U, 5U); 562 563 // Remove the first node. 564 scoped_ptr<RTreeNodeBase> first_child( 565 test_parent->RemoveChild(test_parent->child(0), &orphans)); 566 EXPECT_EQ(0U, orphans.size()); 567 EXPECT_EQ(0U, test_parent->count()); 568} 569 570TEST_F(RTreeNodeTest, RemoveChildOrphans) { 571 // Build binary tree of Nodes of height 4, keeping weak pointers to the 572 // Levels 0 and 1 Nodes and the Records so we can test removal of them below. 573 std::vector<RTreeNode*> level_1_children; 574 std::vector<RTreeNode*> level_0_children; 575 std::vector<RTreeRecord*> records; 576 int id = 1; 577 scoped_ptr<RTreeNode> root(NewNodeAtLevel(2)); 578 for (int i = 0; i < 2; ++i) { 579 scoped_ptr<RTreeNode> level_1_child(NewNodeAtLevel(1)); 580 for (int j = 0; j < 2; ++j) { 581 scoped_ptr<RTreeNode> level_0_child(new RTreeNode); 582 for (int k = 0; k < 2; ++k) { 583 scoped_ptr<RTreeRecord> record( 584 new RTreeRecord(Rect(0, 0, id, id), id)); 585 ++id; 586 records.push_back(record.get()); 587 level_0_child->AddChild(record.PassAs<RTreeNodeBase>()); 588 } 589 level_0_children.push_back(level_0_child.get()); 590 level_1_child->AddChild(level_0_child.PassAs<RTreeNodeBase>()); 591 } 592 level_1_children.push_back(level_1_child.get()); 593 root->AddChild(level_1_child.PassAs<RTreeNodeBase>()); 594 } 595 596 // This should now be a valid tree structure. 597 ValidateNode(root.get(), 2U, 2U); 598 EXPECT_EQ(2U, level_1_children.size()); 599 EXPECT_EQ(4U, level_0_children.size()); 600 EXPECT_EQ(8U, records.size()); 601 602 // Now remove all of the level 0 nodes so we get the record nodes as orphans. 603 RTreeNodes orphans; 604 for (size_t i = 0; i < level_0_children.size(); ++i) 605 level_1_children[i / 2]->RemoveChild(level_0_children[i], &orphans); 606 607 // Orphans should be all 8 records but no order guarantee. 608 EXPECT_EQ(8U, orphans.size()); 609 for (std::vector<RTreeRecord*>::iterator it = records.begin(); 610 it != records.end(); ++it) { 611 RTreeNodes::iterator orphan = 612 std::find(orphans.begin(), orphans.end(), *it); 613 EXPECT_NE(orphan, orphans.end()); 614 orphans.erase(orphan); 615 } 616 EXPECT_EQ(0U, orphans.size()); 617} 618 619TEST_F(RTreeNodeTest, RemoveAndReturnLastChild) { 620 scoped_ptr<RTreeNode> test_parent(new RTreeNode); 621 test_parent->AddChild( 622 scoped_ptr<RTreeNodeBase>(new RTreeRecord(Rect(0, 0, 1, 1), 1))); 623 test_parent->AddChild( 624 scoped_ptr<RTreeNodeBase>(new RTreeRecord(Rect(0, 0, 2, 2), 2))); 625 test_parent->AddChild( 626 scoped_ptr<RTreeNodeBase>(new RTreeRecord(Rect(0, 0, 3, 3), 3))); 627 ValidateNode(test_parent.get(), 1U, 5U); 628 629 RTreeNodeBase* child = test_parent->child(2); 630 scoped_ptr<RTreeNodeBase> last_child(test_parent->RemoveAndReturnLastChild()); 631 EXPECT_EQ(child, last_child.get()); 632 EXPECT_EQ(2U, test_parent->count()); 633 NodeRecomputeLocalBounds(test_parent.get()); 634 ValidateNode(test_parent.get(), 1U, 5U); 635 636 child = test_parent->child(1); 637 scoped_ptr<RTreeNodeBase> middle_child( 638 test_parent->RemoveAndReturnLastChild()); 639 EXPECT_EQ(child, middle_child.get()); 640 EXPECT_EQ(1U, test_parent->count()); 641 NodeRecomputeLocalBounds(test_parent.get()); 642 ValidateNode(test_parent.get(), 1U, 5U); 643 644 child = test_parent->child(0); 645 scoped_ptr<RTreeNodeBase> first_child( 646 test_parent->RemoveAndReturnLastChild()); 647 EXPECT_EQ(child, first_child.get()); 648 EXPECT_EQ(0U, test_parent->count()); 649} 650 651TEST_F(RTreeNodeTest, LeastOverlapIncrease) { 652 scoped_ptr<RTreeNode> test_parent(NewNodeAtLevel(1)); 653 // Construct 4 nodes with 1x2 rects spaced horizontally 1 pixel apart, or: 654 // 655 // a b c d 656 // a b c d 657 // 658 for (int i = 0; i < 4; ++i) { 659 scoped_ptr<RTreeNode> node(new RTreeNode); 660 scoped_ptr<RTreeRecord> record( 661 new RTreeRecord(Rect(i * 2, 0, 1, 2), i + 1)); 662 node->AddChild(record.PassAs<RTreeNodeBase>()); 663 test_parent->AddChild(node.PassAs<RTreeNodeBase>()); 664 } 665 666 ValidateNode(test_parent.get(), 1U, 5U); 667 668 // Test rect at (7, 0) should require minimum overlap on the part of the 669 // fourth rectangle to add: 670 // 671 // a b c dT 672 // a b c d 673 // 674 Rect test_rect_far(7, 0, 1, 1); 675 RTreeRects expanded_rects; 676 BuildExpandedRects(test_parent.get(), test_rect_far, &expanded_rects); 677 RTreeNode* result = NodeLeastOverlapIncrease( 678 test_parent.get(), test_rect_far, expanded_rects); 679 EXPECT_EQ(4, record(result, 0)->key()); 680 681 // Test rect covering the bottom half of all children should be a 4-way tie, 682 // so LeastOverlapIncrease should return NULL: 683 // 684 // a b c d 685 // TTTTTTT 686 // 687 Rect test_rect_tie(0, 1, 7, 1); 688 BuildExpandedRects(test_parent.get(), test_rect_tie, &expanded_rects); 689 result = NodeLeastOverlapIncrease( 690 test_parent.get(), test_rect_tie, expanded_rects); 691 EXPECT_TRUE(result == NULL); 692 693 // Test rect completely inside c should return the third rectangle: 694 // 695 // a b T d 696 // a b c d 697 // 698 Rect test_rect_inside(4, 0, 1, 1); 699 BuildExpandedRects(test_parent.get(), test_rect_inside, &expanded_rects); 700 result = NodeLeastOverlapIncrease( 701 test_parent.get(), test_rect_inside, expanded_rects); 702 EXPECT_EQ(3, record(result, 0)->key()); 703 704 // Add a rectangle that overlaps completely with rectangle c, to test 705 // when there is a tie between two completely contained rectangles: 706 // 707 // a b Ted 708 // a b eed 709 // 710 scoped_ptr<RTreeNode> record_parent(new RTreeNode); 711 record_parent->AddChild( 712 scoped_ptr<RTreeNodeBase>(new RTreeRecord(Rect(4, 0, 2, 2), 9))); 713 test_parent->AddChild(record_parent.PassAs<RTreeNodeBase>()); 714 BuildExpandedRects(test_parent.get(), test_rect_inside, &expanded_rects); 715 result = NodeLeastOverlapIncrease( 716 test_parent.get(), test_rect_inside, expanded_rects); 717 EXPECT_TRUE(result == NULL); 718} 719 720TEST_F(RTreeNodeTest, LeastAreaEnlargement) { 721 scoped_ptr<RTreeNode> test_parent(NewNodeAtLevel(1)); 722 // Construct 4 nodes in a cross-hairs style configuration: 723 // 724 // a 725 // b c 726 // d 727 // 728 scoped_ptr<RTreeNode> node(new RTreeNode); 729 node->AddChild( 730 scoped_ptr<RTreeNodeBase>(new RTreeRecord(Rect(1, 0, 1, 1), 1))); 731 test_parent->AddChild(node.PassAs<RTreeNodeBase>()); 732 node.reset(new RTreeNode); 733 node->AddChild( 734 scoped_ptr<RTreeNodeBase>(new RTreeRecord(Rect(0, 1, 1, 1), 2))); 735 test_parent->AddChild(node.PassAs<RTreeNodeBase>()); 736 node.reset(new RTreeNode); 737 node->AddChild( 738 scoped_ptr<RTreeNodeBase>(new RTreeRecord(Rect(2, 1, 1, 1), 3))); 739 test_parent->AddChild(node.PassAs<RTreeNodeBase>()); 740 node.reset(new RTreeNode); 741 node->AddChild( 742 scoped_ptr<RTreeNodeBase>(new RTreeRecord(Rect(1, 2, 1, 1), 4))); 743 test_parent->AddChild(node.PassAs<RTreeNodeBase>()); 744 745 ValidateNode(test_parent.get(), 1U, 5U); 746 747 // Test rect at (1, 3) should require minimum area to add to Node d: 748 // 749 // a 750 // b c 751 // d 752 // T 753 // 754 Rect test_rect_below(1, 3, 1, 1); 755 RTreeRects expanded_rects; 756 BuildExpandedRects(test_parent.get(), test_rect_below, &expanded_rects); 757 RTreeNode* result = NodeLeastAreaEnlargement( 758 test_parent.get(), test_rect_below, expanded_rects); 759 EXPECT_EQ(4, record(result, 0)->key()); 760 761 // Test rect completely inside b should require minimum area to add to Node b: 762 // 763 // a 764 // T c 765 // d 766 // 767 Rect test_rect_inside(0, 1, 1, 1); 768 BuildExpandedRects(test_parent.get(), test_rect_inside, &expanded_rects); 769 result = NodeLeastAreaEnlargement( 770 test_parent.get(), test_rect_inside, expanded_rects); 771 EXPECT_EQ(2, record(result, 0)->key()); 772 773 // Add e at (0, 1) to overlap b and c, to test tie-breaking: 774 // 775 // a 776 // eee 777 // d 778 // 779 node.reset(new RTreeNode); 780 node->AddChild( 781 scoped_ptr<RTreeNodeBase>(new RTreeRecord(Rect(0, 1, 3, 1), 7))); 782 test_parent->AddChild(node.PassAs<RTreeNodeBase>()); 783 784 ValidateNode(test_parent.get(), 1U, 5U); 785 786 // Test rect at (3, 1) should tie between c and e, but c has smaller area so 787 // the algorithm should select c: 788 // 789 // 790 // a 791 // eeeT 792 // d 793 // 794 Rect test_rect_tie_breaker(3, 1, 1, 1); 795 BuildExpandedRects(test_parent.get(), test_rect_tie_breaker, &expanded_rects); 796 result = NodeLeastAreaEnlargement( 797 test_parent.get(), test_rect_tie_breaker, expanded_rects); 798 EXPECT_EQ(3, record(result, 0)->key()); 799} 800 801// RTreeTest ------------------------------------------------------------------ 802 803// An empty RTree should never return AppendIntersectingRecords results, and 804// RTrees should be empty upon construction. 805TEST_F(RTreeTest, AppendIntersectingRecordsOnEmptyTree) { 806 RT rt(2, 10); 807 ValidateRTree(&rt); 808 RT::Matches results; 809 Rect test_rect(25, 25); 810 rt.AppendIntersectingRecords(test_rect, &results); 811 EXPECT_EQ(0U, results.size()); 812 ValidateRTree(&rt); 813} 814 815// Clear should empty the tree, meaning that all queries should not return 816// results after. 817TEST_F(RTreeTest, ClearEmptiesTreeOfSingleNode) { 818 RT rt(2, 5); 819 rt.Insert(Rect(0, 0, 100, 100), 1); 820 rt.Clear(); 821 RT::Matches results; 822 Rect test_rect(1, 1); 823 rt.AppendIntersectingRecords(test_rect, &results); 824 EXPECT_EQ(0U, results.size()); 825 ValidateRTree(&rt); 826} 827 828// Even with a complex internal structure, clear should empty the tree, meaning 829// that all queries should not return results after. 830TEST_F(RTreeTest, ClearEmptiesTreeOfManyNodes) { 831 RT rt(2, 5); 832 AddStackedSquares(&rt, 100); 833 rt.Clear(); 834 RT::Matches results; 835 Rect test_rect(1, 1); 836 rt.AppendIntersectingRecords(test_rect, &results); 837 EXPECT_EQ(0U, results.size()); 838 ValidateRTree(&rt); 839} 840 841// Duplicate inserts should overwrite previous inserts. 842TEST_F(RTreeTest, DuplicateInsertsOverwrite) { 843 RT rt(2, 5); 844 // Add 100 stacked squares, but always with duplicate key of 0. 845 for (int i = 1; i <= 100; ++i) { 846 rt.Insert(Rect(0, 0, i, i), 0); 847 ValidateRTree(&rt); 848 } 849 RT::Matches results; 850 Rect test_rect(1, 1); 851 rt.AppendIntersectingRecords(test_rect, &results); 852 EXPECT_EQ(1U, results.size()); 853 EXPECT_EQ(1U, results.count(0)); 854} 855 856// Call Remove() once on something that's been inserted repeatedly. 857TEST_F(RTreeTest, DuplicateInsertRemove) { 858 RT rt(3, 9); 859 AddStackedSquares(&rt, 25); 860 for (int i = 1; i <= 100; ++i) { 861 rt.Insert(Rect(0, 0, i, i), 26); 862 ValidateRTree(&rt); 863 } 864 rt.Remove(26); 865 RT::Matches results; 866 Rect test_rect(1, 1); 867 rt.AppendIntersectingRecords(test_rect, &results); 868 EXPECT_EQ(25U, results.size()); 869 VerifyAllKeys(results); 870} 871 872// Call Remove() repeatedly on something that's been inserted once. 873TEST_F(RTreeTest, InsertDuplicateRemove) { 874 RT rt(7, 15); 875 AddStackedSquares(&rt, 101); 876 for (int i = 0; i < 100; ++i) { 877 rt.Remove(101); 878 ValidateRTree(&rt); 879 } 880 RT::Matches results; 881 Rect test_rect(1, 1); 882 rt.AppendIntersectingRecords(test_rect, &results); 883 EXPECT_EQ(100U, results.size()); 884 VerifyAllKeys(results); 885} 886 887// Stacked rects should meet all matching queries regardless of nesting. 888TEST_F(RTreeTest, AppendIntersectingRecordsStackedSquaresNestedHit) { 889 RT rt(2, 5); 890 AddStackedSquares(&rt, 100); 891 RT::Matches results; 892 Rect test_rect(1, 1); 893 rt.AppendIntersectingRecords(test_rect, &results); 894 EXPECT_EQ(100U, results.size()); 895 VerifyAllKeys(results); 896} 897 898// Stacked rects should meet all matching queries when contained completely by 899// the query rectangle. 900TEST_F(RTreeTest, AppendIntersectingRecordsStackedSquaresContainedHit) { 901 RT rt(2, 10); 902 AddStackedSquares(&rt, 100); 903 RT::Matches results; 904 Rect test_rect(0, 0, 100, 100); 905 rt.AppendIntersectingRecords(test_rect, &results); 906 EXPECT_EQ(100U, results.size()); 907 VerifyAllKeys(results); 908} 909 910// Stacked rects should miss a missing query when the query has no intersection 911// with the rects. 912TEST_F(RTreeTest, AppendIntersectingRecordsStackedSquaresCompleteMiss) { 913 RT rt(2, 7); 914 AddStackedSquares(&rt, 100); 915 RT::Matches results; 916 Rect test_rect(150, 150, 100, 100); 917 rt.AppendIntersectingRecords(test_rect, &results); 918 EXPECT_EQ(0U, results.size()); 919} 920 921// Removing half the nodes after insertion should still result in a valid tree. 922TEST_F(RTreeTest, RemoveHalfStackedRects) { 923 RT rt(2, 11); 924 AddStackedSquares(&rt, 200); 925 for (int i = 101; i <= 200; ++i) { 926 rt.Remove(i); 927 ValidateRTree(&rt); 928 } 929 RT::Matches results; 930 Rect test_rect(1, 1); 931 rt.AppendIntersectingRecords(test_rect, &results); 932 EXPECT_EQ(100U, results.size()); 933 VerifyAllKeys(results); 934 935 // Add the nodes back in. 936 for (int i = 101; i <= 200; ++i) { 937 rt.Insert(Rect(0, 0, i, i), i); 938 ValidateRTree(&rt); 939 } 940 results.clear(); 941 rt.AppendIntersectingRecords(test_rect, &results); 942 EXPECT_EQ(200U, results.size()); 943 VerifyAllKeys(results); 944} 945 946TEST_F(RTreeTest, InsertDupToRoot) { 947 RT rt(2, 5); 948 rt.Insert(Rect(0, 0, 1, 2), 1); 949 ValidateRTree(&rt); 950 rt.Insert(Rect(0, 0, 2, 1), 1); 951 ValidateRTree(&rt); 952} 953 954TEST_F(RTreeTest, InsertNegativeCoordsRect) { 955 RT rt(5, 11); 956 for (int i = 1; i <= 100; ++i) { 957 rt.Insert(Rect(-i, -i, i, i), (i * 2) - 1); 958 ValidateRTree(&rt); 959 rt.Insert(Rect(0, 0, i, i), i * 2); 960 ValidateRTree(&rt); 961 } 962 RT::Matches results; 963 Rect test_rect(-1, -1, 2, 2); 964 rt.AppendIntersectingRecords(test_rect, &results); 965 EXPECT_EQ(200U, results.size()); 966 VerifyAllKeys(results); 967} 968 969TEST_F(RTreeTest, RemoveNegativeCoordsRect) { 970 RT rt(7, 21); 971 972 // Add 100 positive stacked squares. 973 AddStackedSquares(&rt, 100); 974 975 // Now add 100 negative stacked squares. 976 for (int i = 101; i <= 200; ++i) { 977 rt.Insert(Rect(100 - i, 100 - i, i - 100, i - 100), 301 - i); 978 ValidateRTree(&rt); 979 } 980 981 // Now remove half of the negative squares. 982 for (int i = 101; i <= 150; ++i) { 983 rt.Remove(301 - i); 984 ValidateRTree(&rt); 985 } 986 987 // Queries should return 100 positive and 50 negative stacked squares. 988 RT::Matches results; 989 Rect test_rect(-1, -1, 2, 2); 990 rt.AppendIntersectingRecords(test_rect, &results); 991 EXPECT_EQ(150U, results.size()); 992 VerifyAllKeys(results); 993} 994 995TEST_F(RTreeTest, InsertEmptyRectReplacementRemovesKey) { 996 RT rt(10, 31); 997 AddStackedSquares(&rt, 50); 998 ValidateRTree(&rt); 999 1000 // Replace last square with empty rect. 1001 rt.Insert(Rect(), 50); 1002 ValidateRTree(&rt); 1003 1004 // Now query large area to get all rects in tree. 1005 RT::Matches results; 1006 Rect test_rect(0, 0, 100, 100); 1007 rt.AppendIntersectingRecords(test_rect, &results); 1008 1009 // Should only be 49 rects in tree. 1010 EXPECT_EQ(49U, results.size()); 1011 VerifyAllKeys(results); 1012} 1013 1014TEST_F(RTreeTest, InsertReplacementMaintainsTree) { 1015 RT rt(2, 5); 1016 AddStackedSquares(&rt, 100); 1017 ValidateRTree(&rt); 1018 1019 for (int i = 1; i <= 100; ++i) { 1020 rt.Insert(Rect(0, 0, 0, 0), i); 1021 ValidateRTree(&rt); 1022 } 1023} 1024 1025} // namespace gfx 1026