rileya@google.com | 1f45e93 | 2012-09-05 16:10:59 +0000 | [diff] [blame] | 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 | |
rileya@google.com | 1f45e93 | 2012-09-05 16:10:59 +0000 | [diff] [blame] | 8 | #include "SkRTree.h" |
tfarina@chromium.org | 8f6884a | 2014-01-24 20:56:26 +0000 | [diff] [blame] | 9 | #include "SkRandom.h" |
tfarina@chromium.org | 8f6884a | 2014-01-24 20:56:26 +0000 | [diff] [blame] | 10 | #include "Test.h" |
rileya@google.com | 1f45e93 | 2012-09-05 16:10:59 +0000 | [diff] [blame] | 11 | |
bsalomon@google.com | 373ebc6 | 2012-09-26 13:08:56 +0000 | [diff] [blame] | 12 | static const int NUM_RECTS = 200; |
rileya@google.com | 1f45e93 | 2012-09-05 16:10:59 +0000 | [diff] [blame] | 13 | static const size_t NUM_ITERATIONS = 100; |
| 14 | static const size_t NUM_QUERIES = 50; |
| 15 | |
mtklein | 533eb78 | 2014-08-27 10:39:42 -0700 | [diff] [blame] | 16 | static SkRect random_rect(SkRandom& rand) { |
| 17 | SkRect rect = {0,0,0,0}; |
rileya@google.com | 1f45e93 | 2012-09-05 16:10:59 +0000 | [diff] [blame] | 18 | while (rect.isEmpty()) { |
mtklein | 533eb78 | 2014-08-27 10:39:42 -0700 | [diff] [blame] | 19 | rect.fLeft = rand.nextRangeF(0, 1000); |
| 20 | rect.fRight = rand.nextRangeF(0, 1000); |
| 21 | rect.fTop = rand.nextRangeF(0, 1000); |
| 22 | rect.fBottom = rand.nextRangeF(0, 1000); |
rileya@google.com | 1f45e93 | 2012-09-05 16:10:59 +0000 | [diff] [blame] | 23 | rect.sort(); |
| 24 | } |
| 25 | return rect; |
| 26 | } |
| 27 | |
mtklein | 6bd4196 | 2014-10-02 07:41:56 -0700 | [diff] [blame] | 28 | static bool verify_query(SkRect query, SkRect rects[], SkTDArray<unsigned>& found) { |
mtklein | 6bd4196 | 2014-10-02 07:41:56 -0700 | [diff] [blame] | 29 | SkTDArray<unsigned> expected; |
rileya@google.com | 1f45e93 | 2012-09-05 16:10:59 +0000 | [diff] [blame] | 30 | // manually intersect with every rectangle |
bsalomon@google.com | 373ebc6 | 2012-09-26 13:08:56 +0000 | [diff] [blame] | 31 | for (int i = 0; i < NUM_RECTS; ++i) { |
mtklein | 6bd4196 | 2014-10-02 07:41:56 -0700 | [diff] [blame] | 32 | if (SkRect::Intersects(query, rects[i])) { |
| 33 | expected.push(i); |
rileya@google.com | 1f45e93 | 2012-09-05 16:10:59 +0000 | [diff] [blame] | 34 | } |
| 35 | } |
| 36 | |
skia.committer@gmail.com | 6c77816 | 2012-09-06 02:01:13 +0000 | [diff] [blame] | 37 | if (expected.count() != found.count()) { |
| 38 | return false; |
| 39 | } |
rileya@google.com | 1f45e93 | 2012-09-05 16:10:59 +0000 | [diff] [blame] | 40 | if (0 == expected.count()) { |
| 41 | return true; |
| 42 | } |
rileya@google.com | 1f45e93 | 2012-09-05 16:10:59 +0000 | [diff] [blame] | 43 | return found == expected; |
| 44 | } |
| 45 | |
mtklein | 6bd4196 | 2014-10-02 07:41:56 -0700 | [diff] [blame] | 46 | static void run_queries(skiatest::Reporter* reporter, SkRandom& rand, SkRect rects[], |
mtklein | a06a953 | 2014-11-18 09:27:49 -0800 | [diff] [blame] | 47 | const SkRTree& tree) { |
robertphillips@google.com | 178a267 | 2012-09-13 13:25:30 +0000 | [diff] [blame] | 48 | for (size_t i = 0; i < NUM_QUERIES; ++i) { |
mtklein | 6bd4196 | 2014-10-02 07:41:56 -0700 | [diff] [blame] | 49 | SkTDArray<unsigned> hits; |
mtklein | 533eb78 | 2014-08-27 10:39:42 -0700 | [diff] [blame] | 50 | SkRect query = random_rect(rand); |
rileya@google.com | 1f45e93 | 2012-09-05 16:10:59 +0000 | [diff] [blame] | 51 | tree.search(query, &hits); |
| 52 | REPORTER_ASSERT(reporter, verify_query(query, rects, hits)); |
| 53 | } |
| 54 | } |
| 55 | |
mtklein | a06a953 | 2014-11-18 09:27:49 -0800 | [diff] [blame] | 56 | DEF_TEST(RTree, reporter) { |
rileya@google.com | 1f45e93 | 2012-09-05 16:10:59 +0000 | [diff] [blame] | 57 | int expectedDepthMin = -1; |
rileya@google.com | 1f45e93 | 2012-09-05 16:10:59 +0000 | [diff] [blame] | 58 | int tmp = NUM_RECTS; |
| 59 | while (tmp > 0) { |
mtklein | a06a953 | 2014-11-18 09:27:49 -0800 | [diff] [blame] | 60 | tmp -= static_cast<int>(pow(static_cast<double>(SkRTree::kMaxChildren), |
| 61 | static_cast<double>(expectedDepthMin + 1))); |
rileya@google.com | 1f45e93 | 2012-09-05 16:10:59 +0000 | [diff] [blame] | 62 | ++expectedDepthMin; |
| 63 | } |
| 64 | |
mtklein | a06a953 | 2014-11-18 09:27:49 -0800 | [diff] [blame] | 65 | int expectedDepthMax = -1; |
rileya@google.com | 1f45e93 | 2012-09-05 16:10:59 +0000 | [diff] [blame] | 66 | tmp = NUM_RECTS; |
| 67 | while (tmp > 0) { |
mtklein | a06a953 | 2014-11-18 09:27:49 -0800 | [diff] [blame] | 68 | tmp -= static_cast<int>(pow(static_cast<double>(SkRTree::kMinChildren), |
| 69 | static_cast<double>(expectedDepthMax + 1))); |
rileya@google.com | 1f45e93 | 2012-09-05 16:10:59 +0000 | [diff] [blame] | 70 | ++expectedDepthMax; |
| 71 | } |
| 72 | |
mtklein | 4477c3c | 2014-10-27 10:27:10 -0700 | [diff] [blame] | 73 | SkRandom rand; |
| 74 | SkAutoTMalloc<SkRect> rects(NUM_RECTS); |
robertphillips@google.com | 178a267 | 2012-09-13 13:25:30 +0000 | [diff] [blame] | 75 | for (size_t i = 0; i < NUM_ITERATIONS; ++i) { |
mtklein | a06a953 | 2014-11-18 09:27:49 -0800 | [diff] [blame] | 76 | SkRTree rtree; |
| 77 | REPORTER_ASSERT(reporter, 0 == rtree.getCount()); |
rileya@google.com | 1f45e93 | 2012-09-05 16:10:59 +0000 | [diff] [blame] | 78 | |
mtklein | 4477c3c | 2014-10-27 10:27:10 -0700 | [diff] [blame] | 79 | for (int j = 0; j < NUM_RECTS; j++) { |
| 80 | rects[j] = random_rect(rand); |
rileya@google.com | 1f45e93 | 2012-09-05 16:10:59 +0000 | [diff] [blame] | 81 | } |
mtklein | 4477c3c | 2014-10-27 10:27:10 -0700 | [diff] [blame] | 82 | |
mtklein | a06a953 | 2014-11-18 09:27:49 -0800 | [diff] [blame] | 83 | rtree.insert(&rects, NUM_RECTS); |
mtklein | 4477c3c | 2014-10-27 10:27:10 -0700 | [diff] [blame] | 84 | SkASSERT(rects); // SkRTree doesn't take ownership of rects. |
| 85 | |
mtklein | a06a953 | 2014-11-18 09:27:49 -0800 | [diff] [blame] | 86 | run_queries(reporter, rand, rects, rtree); |
| 87 | REPORTER_ASSERT(reporter, NUM_RECTS == rtree.getCount()); |
| 88 | REPORTER_ASSERT(reporter, expectedDepthMin <= rtree.getDepth() && |
| 89 | expectedDepthMax >= rtree.getDepth()); |
rileya@google.com | 1f45e93 | 2012-09-05 16:10:59 +0000 | [diff] [blame] | 90 | } |
| 91 | } |