blob: 9b451d1ff44ad8442aec2da595f22c2701f82d73 [file] [log] [blame]
rileya@google.com1f45e932012-09-05 16:10:59 +00001/*
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.com1f45e932012-09-05 16:10:59 +00008#include "SkRTree.h"
tfarina@chromium.org8f6884a2014-01-24 20:56:26 +00009#include "SkRandom.h"
tfarina@chromium.org8f6884a2014-01-24 20:56:26 +000010#include "Test.h"
rileya@google.com1f45e932012-09-05 16:10:59 +000011
bsalomon@google.com373ebc62012-09-26 13:08:56 +000012static const int NUM_RECTS = 200;
rileya@google.com1f45e932012-09-05 16:10:59 +000013static const size_t NUM_ITERATIONS = 100;
14static const size_t NUM_QUERIES = 50;
15
mtklein533eb782014-08-27 10:39:42 -070016static SkRect random_rect(SkRandom& rand) {
17 SkRect rect = {0,0,0,0};
rileya@google.com1f45e932012-09-05 16:10:59 +000018 while (rect.isEmpty()) {
mtklein533eb782014-08-27 10:39:42 -070019 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.com1f45e932012-09-05 16:10:59 +000023 rect.sort();
24 }
25 return rect;
26}
27
mtkleinc6ad06a2015-08-19 09:51:00 -070028static bool verify_query(SkRect query, SkRect rects[], SkTDArray<int>& found) {
29 SkTDArray<int> expected;
rileya@google.com1f45e932012-09-05 16:10:59 +000030 // manually intersect with every rectangle
bsalomon@google.com373ebc62012-09-26 13:08:56 +000031 for (int i = 0; i < NUM_RECTS; ++i) {
mtklein6bd41962014-10-02 07:41:56 -070032 if (SkRect::Intersects(query, rects[i])) {
Mike Reed5edcd312018-08-08 11:23:41 -040033 expected.push_back(i);
rileya@google.com1f45e932012-09-05 16:10:59 +000034 }
35 }
36
skia.committer@gmail.com6c778162012-09-06 02:01:13 +000037 if (expected.count() != found.count()) {
38 return false;
39 }
rileya@google.com1f45e932012-09-05 16:10:59 +000040 if (0 == expected.count()) {
41 return true;
42 }
rileya@google.com1f45e932012-09-05 16:10:59 +000043 return found == expected;
44}
45
mtklein6bd41962014-10-02 07:41:56 -070046static void run_queries(skiatest::Reporter* reporter, SkRandom& rand, SkRect rects[],
mtkleina06a9532014-11-18 09:27:49 -080047 const SkRTree& tree) {
robertphillips@google.com178a2672012-09-13 13:25:30 +000048 for (size_t i = 0; i < NUM_QUERIES; ++i) {
mtkleinc6ad06a2015-08-19 09:51:00 -070049 SkTDArray<int> hits;
mtklein533eb782014-08-27 10:39:42 -070050 SkRect query = random_rect(rand);
rileya@google.com1f45e932012-09-05 16:10:59 +000051 tree.search(query, &hits);
52 REPORTER_ASSERT(reporter, verify_query(query, rects, hits));
53 }
54}
55
mtkleina06a9532014-11-18 09:27:49 -080056DEF_TEST(RTree, reporter) {
rileya@google.com1f45e932012-09-05 16:10:59 +000057 int expectedDepthMin = -1;
rileya@google.com1f45e932012-09-05 16:10:59 +000058 int tmp = NUM_RECTS;
59 while (tmp > 0) {
mtkleina06a9532014-11-18 09:27:49 -080060 tmp -= static_cast<int>(pow(static_cast<double>(SkRTree::kMaxChildren),
61 static_cast<double>(expectedDepthMin + 1)));
rileya@google.com1f45e932012-09-05 16:10:59 +000062 ++expectedDepthMin;
63 }
64
mtkleina06a9532014-11-18 09:27:49 -080065 int expectedDepthMax = -1;
rileya@google.com1f45e932012-09-05 16:10:59 +000066 tmp = NUM_RECTS;
67 while (tmp > 0) {
mtkleina06a9532014-11-18 09:27:49 -080068 tmp -= static_cast<int>(pow(static_cast<double>(SkRTree::kMinChildren),
69 static_cast<double>(expectedDepthMax + 1)));
rileya@google.com1f45e932012-09-05 16:10:59 +000070 ++expectedDepthMax;
71 }
72
mtklein4477c3c2014-10-27 10:27:10 -070073 SkRandom rand;
74 SkAutoTMalloc<SkRect> rects(NUM_RECTS);
robertphillips@google.com178a2672012-09-13 13:25:30 +000075 for (size_t i = 0; i < NUM_ITERATIONS; ++i) {
mtkleina06a9532014-11-18 09:27:49 -080076 SkRTree rtree;
77 REPORTER_ASSERT(reporter, 0 == rtree.getCount());
rileya@google.com1f45e932012-09-05 16:10:59 +000078
mtklein4477c3c2014-10-27 10:27:10 -070079 for (int j = 0; j < NUM_RECTS; j++) {
80 rects[j] = random_rect(rand);
rileya@google.com1f45e932012-09-05 16:10:59 +000081 }
mtklein4477c3c2014-10-27 10:27:10 -070082
mtkleinbfd5bff2015-02-10 13:44:27 -080083 rtree.insert(rects.get(), NUM_RECTS);
mtklein4477c3c2014-10-27 10:27:10 -070084 SkASSERT(rects); // SkRTree doesn't take ownership of rects.
85
mtkleina06a9532014-11-18 09:27:49 -080086 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.com1f45e932012-09-05 16:10:59 +000090 }
91}