src/third_party/skia/tests/RTreeTest.cpp

   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
  13 static const size_t MIN_CHILDREN = 6;
  14 static const size_t MAX_CHILDREN = 11;
  15
  16 static const int NUM_RECTS = 200;
  17 static const size_t NUM_ITERATIONS = 100;
  18 static const size_t NUM_QUERIES = 50;
  19
  20 static 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
  32 static 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
  59 static 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
  69 static 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
 109 DEF_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 }