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 "include/core/SkRect.h"
9 #include "include/core/SkTypes.h"
10 #include "include/private/base/SkTemplates.h"
11 #include "src/base/SkRandom.h"
12 #include "src/core/SkRTree.h"
13 #include "tests/Test.h"
14
15 #include <cmath>
16 #include <cstddef>
17 #include <vector>
18
19 using namespace skia_private;
20
21 static const int NUM_RECTS = 200;
22 static const size_t NUM_ITERATIONS = 100;
23 static const size_t NUM_QUERIES = 50;
24
random_rect(SkRandom & rand)25 static SkRect random_rect(SkRandom& rand) {
26 SkRect rect = {0,0,0,0};
27 while (rect.isEmpty()) {
28 rect.fLeft = rand.nextRangeF(0, 1000);
29 rect.fRight = rand.nextRangeF(0, 1000);
30 rect.fTop = rand.nextRangeF(0, 1000);
31 rect.fBottom = rand.nextRangeF(0, 1000);
32 rect.sort();
33 }
34 return rect;
35 }
36
verify_query(SkRect query,SkRect rects[],const std::vector<int> & found)37 static bool verify_query(SkRect query, SkRect rects[], const std::vector<int>& found) {
38 std::vector<int> expected;
39 // manually intersect with every rectangle
40 for (int i = 0; i < NUM_RECTS; ++i) {
41 if (SkRect::Intersects(query, rects[i])) {
42 expected.push_back(i);
43 }
44 }
45
46 if (expected.size() != found.size()) {
47 return false;
48 }
49 if (0 == expected.size()) {
50 return true;
51 }
52 return found == expected;
53 }
54
run_queries(skiatest::Reporter * reporter,SkRandom & rand,SkRect rects[],const SkRTree & tree)55 static void run_queries(skiatest::Reporter* reporter, SkRandom& rand, SkRect rects[],
56 const SkRTree& tree) {
57 for (size_t i = 0; i < NUM_QUERIES; ++i) {
58 std::vector<int> hits;
59 SkRect query = random_rect(rand);
60 tree.search(query, &hits);
61 REPORTER_ASSERT(reporter, verify_query(query, rects, hits));
62 }
63 }
64
DEF_TEST(RTree,reporter)65 DEF_TEST(RTree, reporter) {
66 int expectedDepthMin = -1;
67 int tmp = NUM_RECTS;
68 while (tmp > 0) {
69 tmp -= static_cast<int>(pow(static_cast<double>(SkRTree::kMaxChildren),
70 static_cast<double>(expectedDepthMin + 1)));
71 ++expectedDepthMin;
72 }
73
74 int expectedDepthMax = -1;
75 tmp = NUM_RECTS;
76 while (tmp > 0) {
77 tmp -= static_cast<int>(pow(static_cast<double>(SkRTree::kMinChildren),
78 static_cast<double>(expectedDepthMax + 1)));
79 ++expectedDepthMax;
80 }
81
82 SkRandom rand;
83 AutoTArray<SkRect> rects(NUM_RECTS);
84 for (size_t i = 0; i < NUM_ITERATIONS; ++i) {
85 SkRTree rtree;
86 REPORTER_ASSERT(reporter, 0 == rtree.getCount());
87
88 for (int j = 0; j < NUM_RECTS; j++) {
89 rects[j] = random_rect(rand);
90 }
91
92 rtree.insert(rects.data(), NUM_RECTS);
93
94 run_queries(reporter, rand, rects.data(), rtree);
95 REPORTER_ASSERT(reporter, NUM_RECTS == rtree.getCount());
96 REPORTER_ASSERT(reporter, expectedDepthMin <= rtree.getDepth() &&
97 expectedDepthMax >= rtree.getDepth());
98 }
99 }
100