forked from townforge/townforge
200 lines
5.8 KiB
C++
200 lines
5.8 KiB
C++
// Copyright (c) 2019, Crypto City
|
|
//
|
|
// All rights reserved.
|
|
//
|
|
// Redistribution and use in source and binary forms, with or without modification, are
|
|
// permitted provided that the following conditions are met:
|
|
//
|
|
// 1. Redistributions of source code must retain the above copyright notice, this list of
|
|
// conditions and the following disclaimer.
|
|
//
|
|
// 2. Redistributions in binary form must reproduce the above copyright notice, this list
|
|
// of conditions and the following disclaimer in the documentation and/or other
|
|
// materials provided with the distribution.
|
|
//
|
|
// 3. Neither the name of the copyright holder nor the names of its contributors may be
|
|
// used to endorse or promote products derived from this software without specific
|
|
// prior written permission.
|
|
//
|
|
// THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS "AS IS" AND ANY
|
|
// EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE IMPLIED WARRANTIES OF
|
|
// MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL
|
|
// THE COPYRIGHT HOLDER OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL,
|
|
// SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO,
|
|
// PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS
|
|
// INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT,
|
|
// STRICT LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF
|
|
// THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
|
|
|
|
#include <limits>
|
|
#include <deque>
|
|
#include <set>
|
|
#include "gtest/gtest.h"
|
|
|
|
#define QUADRANT_SPLIT_THREHOLD 2
|
|
#define MIN_QUADRANT_SIZE 2
|
|
#include "cc/quadtree.h"
|
|
|
|
struct T
|
|
{
|
|
uint32_t x0, y0, x1, y1;
|
|
T(uint32_t x0, uint32_t y0, uint32_t x1, uint32_t y1): x0(x0), y0(y0), x1(x1), y1(y1) {}
|
|
bool operator==(const T &t) const { return x0 == t.x0 && y0 == t.y0 && x1 == t.x1 && y1 == t.y1; }
|
|
};
|
|
#define MAXXY std::numeric_limits<uint32_t>::max()
|
|
#define NULLT std::shared_ptr<T>((T*)NULL)
|
|
|
|
TEST(quadtree, intersection)
|
|
{
|
|
// 0 1 2 3
|
|
// 0 . . . .
|
|
// 1 . . . .
|
|
// 2 . . . .
|
|
// 3 . . . .
|
|
EXPECT_TRUE(intersection(1, 1, 2, 2, 2, 1, 3, 2));
|
|
EXPECT_TRUE(intersection(2, 1, 3, 2, 1, 1, 2, 2));
|
|
EXPECT_TRUE(intersection(0, 0, 1, 1, 1, 1, 2, 2));
|
|
EXPECT_TRUE(intersection(1, 1, 2, 2, 0, 0, 1, 1));
|
|
EXPECT_TRUE(intersection(0, 2, 1, 3, 1, 1, 2, 2));
|
|
EXPECT_TRUE(intersection(1, 1, 2, 2, 0, 2, 1, 3));
|
|
EXPECT_TRUE(intersection(466920031, 2502907746, 466920288, 2502908003, 466920032, 2502907550, 466920088, 2502907746));
|
|
}
|
|
|
|
TEST(quadtree, empty)
|
|
{
|
|
Quadtree<T> qt;
|
|
EXPECT_EQ(qt.query_any(0, 0, MAXXY, MAXXY), NULLT);
|
|
std::set<std::shared_ptr<T>> res;
|
|
qt.query(0, 0, MAXXY, MAXXY, res);
|
|
ASSERT_EQ(res.size(), 0);
|
|
}
|
|
|
|
TEST(quadtree, lrtb)
|
|
{
|
|
// . . . . . . .
|
|
// . . . . . . .
|
|
// . . x x x . .
|
|
// . . x x x . .
|
|
// . . x x x . .
|
|
// . . . . . . .
|
|
// . . . . . . .
|
|
Quadtree<T> qt;
|
|
qt.insert(std::shared_ptr<T>(new T{2, 2, 4, 4}));
|
|
ASSERT_EQ(qt.query_any(0, 0, 1, 1), NULLT);
|
|
ASSERT_EQ(qt.query_any(2, 0, 4, 1), NULLT);
|
|
ASSERT_EQ(qt.query_any(5, 0, 6, 1), NULLT);
|
|
ASSERT_EQ(qt.query_any(0, 2, 1, 4), NULLT);
|
|
ASSERT_EQ(qt.query_any(5, 2, 6, 4), NULLT);
|
|
ASSERT_EQ(qt.query_any(0, 5, 1, 6), NULLT);
|
|
ASSERT_EQ(qt.query_any(2, 5, 4, 6), NULLT);
|
|
ASSERT_EQ(qt.query_any(5, 5, 6, 6), NULLT);
|
|
}
|
|
|
|
TEST(quadtree, corners_intersect)
|
|
{
|
|
// . . . . . . .
|
|
// . . . . . . .
|
|
// . . x x x . .
|
|
// . . x x x . .
|
|
// . . x x x . .
|
|
// . . . . . . .
|
|
// . . . . . . .
|
|
Quadtree<T> qt;
|
|
qt.insert(std::shared_ptr<T>(new T{2, 2, 4, 4}));
|
|
ASSERT_NE(qt.query_any(0, 0, 2, 2), NULLT);
|
|
ASSERT_NE(qt.query_any(4, 0, 6, 2), NULLT);
|
|
ASSERT_NE(qt.query_any(0, 4, 2, 6), NULLT);
|
|
ASSERT_NE(qt.query_any(4, 4, 6, 6), NULLT);
|
|
}
|
|
|
|
TEST(quadtree, inside)
|
|
{
|
|
// . . . . . . .
|
|
// . . . . . . .
|
|
// . . x x x . .
|
|
// . . x x x . .
|
|
// . . x x x . .
|
|
// . . . . . . .
|
|
// . . . . . . .
|
|
Quadtree<T> qt;
|
|
qt.insert(std::shared_ptr<T>(new T{2, 2, 4, 4}));
|
|
ASSERT_NE(qt.query_any(3, 3, 3, 3), NULLT);
|
|
}
|
|
|
|
TEST(quadtree, equal)
|
|
{
|
|
// . . . . . . .
|
|
// . . . . . . .
|
|
// . . x x x . .
|
|
// . . x x x . .
|
|
// . . x x x . .
|
|
// . . . . . . .
|
|
// . . . . . . .
|
|
Quadtree<T> qt;
|
|
qt.insert(std::shared_ptr<T>(new T{2, 2, 4, 4}));
|
|
ASSERT_NE(qt.query_any(2, 2, 4, 4), NULLT);
|
|
}
|
|
|
|
TEST(quadtree, encompassing)
|
|
{
|
|
// . . . . . . .
|
|
// . . . . . . .
|
|
// . . x x x . .
|
|
// . . x x x . .
|
|
// . . x x x . .
|
|
// . . . . . . .
|
|
// . . . . . . .
|
|
Quadtree<T> qt;
|
|
qt.insert(std::shared_ptr<T>(new T{2, 2, 4, 4}));
|
|
ASSERT_NE(qt.query_any(1, 1, 4, 5), NULLT);
|
|
}
|
|
|
|
TEST(quadtree, point_query)
|
|
{
|
|
// . . . . . . .
|
|
// . . . . . . .
|
|
// . . x x x . .
|
|
// . . x x x . .
|
|
// . . x x x . .
|
|
// . . . . . . .
|
|
// . . . . . . .
|
|
Quadtree<T> qt;
|
|
qt.insert(std::shared_ptr<T>(new T{2, 2, 4, 4}));
|
|
for (uint32_t y = 0; y <= 6; ++y)
|
|
for (uint32_t x = 0; x <= 6; ++x)
|
|
ASSERT_EQ(qt.query_any(x, y, x, y) == NULLT, x < 2 || y < 2 || x > 4 || y > 4);
|
|
}
|
|
|
|
TEST(quadtree, point_results)
|
|
{
|
|
Quadtree<T> qt;
|
|
for (uint32_t y = 0; y <= 6; ++y)
|
|
for (uint32_t x = 0; x <= 6; ++x)
|
|
qt.insert(std::shared_ptr<T>(new T{x, y, x, y}));
|
|
for (uint32_t y = 0; y <= 6; ++y)
|
|
{
|
|
for (uint32_t x = 0; x <= 6; ++x)
|
|
{
|
|
std::set<std::shared_ptr<T>> res;
|
|
qt.query(x, y, x, y, res);
|
|
ASSERT_EQ(res.size(), 1);
|
|
ASSERT_EQ(**res.begin(), (T{x, y, x, y}));
|
|
}
|
|
}
|
|
for (uint32_t y = 0; y <= 5; ++y)
|
|
{
|
|
for (uint32_t x = 0; x <= 5; ++x)
|
|
{
|
|
std::set<std::shared_ptr<T>> res;
|
|
qt.query(x, y, x+1, y+1, res);
|
|
ASSERT_EQ(res.size(), 4);
|
|
}
|
|
}
|
|
std::set<std::shared_ptr<T>> res;
|
|
qt.query(0, 0, MAXXY, MAXXY, res);
|
|
ASSERT_EQ(res.size(), 49);
|
|
res.clear();
|
|
qt.query(1, 0, 3, 49, res);
|
|
ASSERT_EQ(res.size(), 21);
|
|
}
|