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
8 #include "SkRTree.h"
9 #include "SkRandom.h"
10 #include "Test.h"
11
12 static const int NUM_RECTS = 200;
13 static const size_t NUM_ITERATIONS = 100;
14 static const size_t NUM_QUERIES = 50;
15
random_rect(SkRandom & rand)16 static SkRect random_rect(SkRandom& rand) {
17 SkRect rect = {0,0,0,0};
18 while (rect.isEmpty()) {
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);
23 rect.sort();
24 }
25 return rect;
26 }
27
verify_query(SkRect query,SkRect rects[],SkTDArray<int> & found)28 static bool verify_query(SkRect query, SkRect rects[], SkTDArray<int>& found) {
29 SkTDArray<int> expected;
30 // manually intersect with every rectangle
31 for (int i = 0; i < NUM_RECTS; ++i) {
32 if (SkRect::Intersects(query, rects[i])) {
33 expected.push(i);
34 }
35 }
36
37 if (expected.count() != found.count()) {
38 return false;
39 }
40 if (0 == expected.count()) {
41 return true;
42 }
43 return found == expected;
44 }
45
run_queries(skiatest::Reporter * reporter,SkRandom & rand,SkRect rects[],const SkRTree & tree)46 static void run_queries(skiatest::Reporter* reporter, SkRandom& rand, SkRect rects[],
47 const SkRTree& tree) {
48 for (size_t i = 0; i < NUM_QUERIES; ++i) {
49 SkTDArray<int> hits;
50 SkRect query = random_rect(rand);
51 tree.search(query, &hits);
52 REPORTER_ASSERT(reporter, verify_query(query, rects, hits));
53 }
54 }
55
DEF_TEST(RTree,reporter)56 DEF_TEST(RTree, reporter) {
57 int expectedDepthMin = -1;
58 int tmp = NUM_RECTS;
59 while (tmp > 0) {
60 tmp -= static_cast<int>(pow(static_cast<double>(SkRTree::kMaxChildren),
61 static_cast<double>(expectedDepthMin + 1)));
62 ++expectedDepthMin;
63 }
64
65 int expectedDepthMax = -1;
66 tmp = NUM_RECTS;
67 while (tmp > 0) {
68 tmp -= static_cast<int>(pow(static_cast<double>(SkRTree::kMinChildren),
69 static_cast<double>(expectedDepthMax + 1)));
70 ++expectedDepthMax;
71 }
72
73 SkRandom rand;
74 SkAutoTMalloc<SkRect> rects(NUM_RECTS);
75 for (size_t i = 0; i < NUM_ITERATIONS; ++i) {
76 SkRTree rtree;
77 REPORTER_ASSERT(reporter, 0 == rtree.getCount());
78
79 for (int j = 0; j < NUM_RECTS; j++) {
80 rects[j] = random_rect(rand);
81 }
82
83 rtree.insert(rects.get(), NUM_RECTS);
84 SkASSERT(rects); // SkRTree doesn't take ownership of rects.
85
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());
90 }
91 }
92