OLD | NEW |
(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 |
OLD | NEW |