RTreeTest.cpp 2.7 KB

12345678910111213141516171819202122232425262728293031323334353637383940414243444546474849505152535455565758596061626364656667686970717273747576777879808182838485868788899091
  1. /*
  2. * Copyright 2012 Google Inc.
  3. *
  4. * Use of this source code is governed by a BSD-style license that can be
  5. * found in the LICENSE file.
  6. */
  7. #include "include/utils/SkRandom.h"
  8. #include "src/core/SkRTree.h"
  9. #include "tests/Test.h"
  10. static const int NUM_RECTS = 200;
  11. static const size_t NUM_ITERATIONS = 100;
  12. static const size_t NUM_QUERIES = 50;
  13. static SkRect random_rect(SkRandom& rand) {
  14. SkRect rect = {0,0,0,0};
  15. while (rect.isEmpty()) {
  16. rect.fLeft = rand.nextRangeF(0, 1000);
  17. rect.fRight = rand.nextRangeF(0, 1000);
  18. rect.fTop = rand.nextRangeF(0, 1000);
  19. rect.fBottom = rand.nextRangeF(0, 1000);
  20. rect.sort();
  21. }
  22. return rect;
  23. }
  24. static bool verify_query(SkRect query, SkRect rects[], SkTDArray<int>& found) {
  25. SkTDArray<int> expected;
  26. // manually intersect with every rectangle
  27. for (int i = 0; i < NUM_RECTS; ++i) {
  28. if (SkRect::Intersects(query, rects[i])) {
  29. expected.push_back(i);
  30. }
  31. }
  32. if (expected.count() != found.count()) {
  33. return false;
  34. }
  35. if (0 == expected.count()) {
  36. return true;
  37. }
  38. return found == expected;
  39. }
  40. static void run_queries(skiatest::Reporter* reporter, SkRandom& rand, SkRect rects[],
  41. const SkRTree& tree) {
  42. for (size_t i = 0; i < NUM_QUERIES; ++i) {
  43. SkTDArray<int> hits;
  44. SkRect query = random_rect(rand);
  45. tree.search(query, &hits);
  46. REPORTER_ASSERT(reporter, verify_query(query, rects, hits));
  47. }
  48. }
  49. DEF_TEST(RTree, reporter) {
  50. int expectedDepthMin = -1;
  51. int tmp = NUM_RECTS;
  52. while (tmp > 0) {
  53. tmp -= static_cast<int>(pow(static_cast<double>(SkRTree::kMaxChildren),
  54. static_cast<double>(expectedDepthMin + 1)));
  55. ++expectedDepthMin;
  56. }
  57. int expectedDepthMax = -1;
  58. tmp = NUM_RECTS;
  59. while (tmp > 0) {
  60. tmp -= static_cast<int>(pow(static_cast<double>(SkRTree::kMinChildren),
  61. static_cast<double>(expectedDepthMax + 1)));
  62. ++expectedDepthMax;
  63. }
  64. SkRandom rand;
  65. SkAutoTMalloc<SkRect> rects(NUM_RECTS);
  66. for (size_t i = 0; i < NUM_ITERATIONS; ++i) {
  67. SkRTree rtree;
  68. REPORTER_ASSERT(reporter, 0 == rtree.getCount());
  69. for (int j = 0; j < NUM_RECTS; j++) {
  70. rects[j] = random_rect(rand);
  71. }
  72. rtree.insert(rects.get(), NUM_RECTS);
  73. SkASSERT(rects); // SkRTree doesn't take ownership of rects.
  74. run_queries(reporter, rand, rects, rtree);
  75. REPORTER_ASSERT(reporter, NUM_RECTS == rtree.getCount());
  76. REPORTER_ASSERT(reporter, expectedDepthMin <= rtree.getDepth() &&
  77. expectedDepthMax >= rtree.getDepth());
  78. }
  79. }