RTreeTest.cpp File Reference

#include "include/core/SkRect.h"
#include "include/core/SkTypes.h"
#include "include/private/base/SkTemplates.h"
#include "src/base/SkRandom.h"
#include "src/core/SkRTree.h"
#include "tests/Test.h"
#include <cmath>
#include <cstddef>
#include <vector>

Go to the source code of this file.

Functions
static SkRect	random_rect (SkRandom &rand)
static bool	verify_query (SkRect query, SkRect rects[], const std::vector< int > &found)
static void	run_queries (skiatest::Reporter *reporter, SkRandom &rand, SkRect rects[], const SkRTree &tree)
	DEF_TEST (RTree, reporter)

Variables
static const int	NUM_RECTS = 200
static const size_t	NUM_ITERATIONS = 100
static const size_t	NUM_QUERIES = 50

Function Documentation

DEF_TEST()

DEF_TEST	(	RTree	,
		reporter
	)

Definition at line 65 of file RTreeTest.cpp.

                          {
    int expectedDepthMin = -1;
    int tmp = NUM_RECTS;
    while (tmp > 0) {
        tmp -= static_cast<int>(pow(static_cast<double>(SkRTree::kMaxChildren),
                                    static_cast<double>(expectedDepthMin + 1)));
        ++expectedDepthMin;
    }
 
    int expectedDepthMax = -1;
    tmp = NUM_RECTS;
    while (tmp > 0) {
        tmp -= static_cast<int>(pow(static_cast<double>(SkRTree::kMinChildren),
                                    static_cast<double>(expectedDepthMax + 1)));
        ++expectedDepthMax;
    }
 
    SkRandom rand;
    AutoTArray<SkRect> rects(NUM_RECTS);
    for (size_t i = 0; i < NUM_ITERATIONS; ++i) {
        SkRTree rtree;
        REPORTER_ASSERT(reporter, 0 == rtree.getCount());
 
        for (int j = 0; j < NUM_RECTS; j++) {
            rects[j] = random_rect(rand);
        }
 
        rtree.insert(rects.data(), NUM_RECTS);
 
        run_queries(reporter, rand, rects.data(), rtree);
        REPORTER_ASSERT(reporter, NUM_RECTS == rtree.getCount());
        REPORTER_ASSERT(reporter, expectedDepthMin <= rtree.getDepth() &&
                                  expectedDepthMax >= rtree.getDepth());
    }
}

random_rect()

static SkRect random_rect ( SkRandom &  rand )

static

Definition at line 25 of file RTreeTest.cpp.

                                          {
    SkRect rect = {0,0,0,0};
    while (rect.isEmpty()) {
        rect.fLeft   = rand.nextRangeF(0, 1000);
        rect.fRight  = rand.nextRangeF(0, 1000);
        rect.fTop    = rand.nextRangeF(0, 1000);
        rect.fBottom = rand.nextRangeF(0, 1000);
        rect.sort();
    }
    return rect;
}

run_queries()

static void run_queries ( skiatest::Reporter *  reporter, SkRandom &  rand, SkRect  rects[], const SkRTree &  tree  )

static

Definition at line 55 of file RTreeTest.cpp.

                                             {
    for (size_t i = 0; i < NUM_QUERIES; ++i) {
        std::vector<int> hits;
        SkRect query = random_rect(rand);
        tree.search(query, &hits);
        REPORTER_ASSERT(reporter, verify_query(query, rects, hits));
    }
}

verify_query()

static bool verify_query ( SkRect  query, SkRect  rects[], const std::vector< int > &  found  )

static

Definition at line 37 of file RTreeTest.cpp.

                                                                                    {
    std::vector<int> expected;
    // manually intersect with every rectangle
    for (int i = 0; i < NUM_RECTS; ++i) {
        if (SkRect::Intersects(query, rects[i])) {
            expected.push_back(i);
        }
    }
 
    if (expected.size() != found.size()) {
        return false;
    }
    if (0 == expected.size()) {
        return true;
    }
    return found == expected;
}

Variable Documentation

NUM_ITERATIONS

const size_t NUM_ITERATIONS = 100

static

Definition at line 22 of file RTreeTest.cpp.

NUM_QUERIES

const size_t NUM_QUERIES = 50

static

Definition at line 23 of file RTreeTest.cpp.

NUM_RECTS

const int NUM_RECTS = 200

static

Definition at line 21 of file RTreeTest.cpp.