RTreeTest.cpp revision 4477c3c0e6eb064772aefe8737425cd1c2ce557f 
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 "SkTSort.h"
11#include "Test.h"
12
13static const size_t MIN_CHILDREN = 6;
14static const size_t MAX_CHILDREN = 11;
15
16static const int NUM_RECTS = 200;
17static const size_t NUM_ITERATIONS = 100;
18static const size_t NUM_QUERIES = 50;
19
20static SkRect random_rect(SkRandom& rand) {
21    SkRect rect = {0,0,0,0};
22    while (rect.isEmpty()) {
23        rect.fLeft   = rand.nextRangeF(0, 1000);
24        rect.fRight  = rand.nextRangeF(0, 1000);
25        rect.fTop    = rand.nextRangeF(0, 1000);
26        rect.fBottom = rand.nextRangeF(0, 1000);
27        rect.sort();
28    }
29    return rect;
30}
31
32static bool verify_query(SkRect query, SkRect rects[], SkTDArray<unsigned>& found) {
33    // TODO(mtklein): no need to do this after everything's SkRects
34    query.roundOut();
35
36    SkTDArray<unsigned> expected;
37
38    // manually intersect with every rectangle
39    for (int i = 0; i < NUM_RECTS; ++i) {
40        if (SkRect::Intersects(query, rects[i])) {
41            expected.push(i);
42        }
43    }
44
45    if (expected.count() != found.count()) {
46        return false;
47    }
48
49    if (0 == expected.count()) {
50        return true;
51    }
52
53    // skia:2834.  RTree doesn't always return results in order.
54    SkTQSort(expected.begin(), expected.end() -1);
55    SkTQSort(found.begin(), found.end() -1);
56    return found == expected;
57}
58
59static void run_queries(skiatest::Reporter* reporter, SkRandom& rand, SkRect rects[],
60                       SkRTree& tree) {
61    for (size_t i = 0; i < NUM_QUERIES; ++i) {
62        SkTDArray<unsigned> hits;
63        SkRect query = random_rect(rand);
64        tree.search(query, &hits);
65        REPORTER_ASSERT(reporter, verify_query(query, rects, hits));
66    }
67}
68
69static void rtree_test_main(SkRTree* rtree, skiatest::Reporter* reporter) {
70    SkASSERT(rtree);
71
72    int expectedDepthMin = -1;
73    int expectedDepthMax = -1;
74
75    int tmp = NUM_RECTS;
76    while (tmp > 0) {
77        tmp -= static_cast<int>(pow(static_cast<double>(MAX_CHILDREN),
78                                static_cast<double>(expectedDepthMin + 1)));
79        ++expectedDepthMin;
80    }
81
82    tmp = NUM_RECTS;
83    while (tmp > 0) {
84        tmp -= static_cast<int>(pow(static_cast<double>(MIN_CHILDREN),
85                                static_cast<double>(expectedDepthMax + 1)));
86        ++expectedDepthMax;
87    }
88
89    SkRandom rand;
90    SkAutoTMalloc<SkRect> rects(NUM_RECTS);
91    for (size_t i = 0; i < NUM_ITERATIONS; ++i) {
92        rtree->clear();
93        REPORTER_ASSERT(reporter, 0 == rtree->getCount());
94
95        for (int j = 0; j < NUM_RECTS; j++) {
96            rects[j] = random_rect(rand);
97        }
98
99        rtree->insert(&rects, NUM_RECTS);
100        SkASSERT(rects);  // SkRTree doesn't take ownership of rects.
101
102        run_queries(reporter, rand, rects, *rtree);
103        REPORTER_ASSERT(reporter, NUM_RECTS == rtree->getCount());
104        REPORTER_ASSERT(reporter, expectedDepthMin <= rtree->getDepth() &&
105                                  expectedDepthMax >= rtree->getDepth());
106    }
107}
108
109DEF_TEST(RTree, reporter) {
110    SkRTree* rtree = SkRTree::Create(MIN_CHILDREN, MAX_CHILDREN);
111    SkAutoUnref au(rtree);
112    rtree_test_main(rtree, reporter);
113
114    // Rtree that orders input rectangles on deferred insert.
115    SkRTree* unsortedRtree = SkRTree::Create(MIN_CHILDREN, MAX_CHILDREN, 1, false);
116    SkAutoUnref auo(unsortedRtree);
117    rtree_test_main(unsortedRtree, reporter);
118}
119