From 42305cd3b9942ba07fbae85a855ad23f1ad044a2 Mon Sep 17 00:00:00 2001 From: Stanislaw Halik Date: Sat, 25 Feb 2023 00:53:04 +0100 Subject: kill lqt --- test/app.hpp | 2 - test/bbox.cpp | 25 -- test/main.cpp | 2 - test/quadtree.cpp | 729 ------------------------------------------------------ 4 files changed, 758 deletions(-) delete mode 100644 test/bbox.cpp delete mode 100644 test/quadtree.cpp (limited to 'test') diff --git a/test/app.hpp b/test/app.hpp index 46ea3fc0..b3787826 100644 --- a/test/app.hpp +++ b/test/app.hpp @@ -28,8 +28,6 @@ struct test_app final : private FM_APPLICATION static void test_const_math(); static void test_serializer(); static void test_entity(); - static void test_quadtree(); static void test_loader(); - static void test_bbox(); }; } // namespace floormat diff --git a/test/bbox.cpp b/test/bbox.cpp deleted file mode 100644 index 9ffd6122..00000000 --- a/test/bbox.cpp +++ /dev/null @@ -1,25 +0,0 @@ -#include "app.hpp" -#include "src/chunk.hpp" -#include "src/collision.hpp" -#include -#include - -namespace floormat { - -void test_app::test_bbox() -{ - auto c = make_test_chunk(); - - constexpr auto pos1 = sTILE_SIZE2 * (TILE_MAX_DIM/2) - Vector2s(0, sTILE_SIZE2[1]/2); - constexpr auto b1 = Vector4s{pos1[0], pos1[1], sTILE_SIZE2[0], sTILE_SIZE2[1]}; - constexpr auto pos2 = Vector2s(iTILE_SIZE2 * (Vector2i(TILE_MAX_DIM/2) - Vector2i(-1, -1)) - Vector2i(0, iTILE_SIZE[1]/2)); - constexpr auto b2 = Vector4s{pos2[0], pos2[1], usTILE_SIZE2[0], usTILE_SIZE2[1]}; - { - auto q1 = c.query_collisions(b1, collision::move); - fm_assert(q1); - auto q2 = c.query_collisions(b2, collision::move); - fm_assert(!q2); - } -} - -} // namespace floormat diff --git a/test/main.cpp b/test/main.cpp index 305c4926..c01f09f0 100644 --- a/test/main.cpp +++ b/test/main.cpp @@ -25,8 +25,6 @@ int test_app::exec() test_serializer(); test_entity(); test_loader(); - test_bbox(); - test_quadtree(); return 0; } diff --git a/test/quadtree.cpp b/test/quadtree.cpp deleted file mode 100644 index f1a3ab6f..00000000 --- a/test/quadtree.cpp +++ /dev/null @@ -1,729 +0,0 @@ -#if defined __GNUG__ || defined __CLION_IDE__ -#pragma GCC diagnostic ignored "-Wfloat-equal" -#endif -#ifdef _MSC_VER -#pragma warning(disable : 4244) -#endif -#define ASSERT fm_assert - -#include "compat/LooseQuadtree.h" -#include "compat/LooseQuadtree-impl.h" -#include "compat/assert.hpp" -#include "src/collision.hpp" -#include "test/app.hpp" - -#include -#include -#include -#include -#include - -using namespace loose_quadtree; - -namespace { - -template -void TestBoundingBox() { - BoundingBox big(100, 100, 200, 50); - BoundingBox small_inside(200, 125, 5, 5); - BoundingBox edge_inside(110, 110, 190, 40); - BoundingBox edge_outside(300, 150, 20, 5); - BoundingBox intersecting1(290, 90, 29, 25); - BoundingBox intersecting2(290, 110, 29, 25); - BoundingBox outside(290, 210, 29, 25); - - ASSERT(big.Contains(100, 100)); - ASSERT(!big.Contains(300, 150)); - - ASSERT(big.Contains(big)); - ASSERT(big.Contains(small_inside)); - ASSERT(!small_inside.Contains(big)); - ASSERT(big.Contains(edge_inside)); - ASSERT(!edge_inside.Contains(big)); - ASSERT(!big.Contains(edge_outside)); - ASSERT(!edge_outside.Contains(big)); - ASSERT(!big.Contains(intersecting1)); - ASSERT(!intersecting1.Contains(big)); - ASSERT(!big.Contains(intersecting2)); - ASSERT(!intersecting1.Contains(big)); - ASSERT(!intersecting1.Contains(intersecting2)); - ASSERT(!big.Contains(outside)); - ASSERT(!outside.Contains(big)); - - ASSERT(big.Intersects(big)); - ASSERT(big.Intersects(small_inside)); - ASSERT(small_inside.Intersects(big)); - ASSERT(big.Intersects(edge_inside)); - ASSERT(edge_inside.Intersects(big)); - ASSERT(!big.Intersects(edge_outside)); - ASSERT(!edge_outside.Intersects(big)); - ASSERT(big.Intersects(intersecting1)); - ASSERT(intersecting1.Intersects(big)); - ASSERT(big.Intersects(intersecting2)); - ASSERT(intersecting2.Intersects(big)); - ASSERT(intersecting1.Intersects(intersecting2)); - ASSERT(!big.Intersects(outside)); - ASSERT(!outside.Intersects(big)); -} - - - -template -void TestForwardTreeTraversal() { - detail::BlocksAllocator allocator; - detail::ForwardTreeTraversal> fortt; - detail::TreeNode> root(allocator); - detail::TreeNode> tl(allocator); - detail::TreeNode> tr(allocator); - detail::TreeNode> br(allocator); - detail::TreeNode> bl(allocator); - root.top_left = &tl; - tl.top_right = &tr; - tr.bottom_right = &br; - root.bottom_left = &bl; - fortt.StartAt(&root, BoundingBox(0, 0, 64, 64)); - ASSERT(fortt.GetDepth() == 0); - ASSERT(fortt.GetNode() == &root); - ASSERT(fortt.GetNodeBoundingBox().left == 0); - ASSERT(fortt.GetNodeBoundingBox().top == 0); - ASSERT(fortt.GetNodeBoundingBox().width == 64); - ASSERT(fortt.GetNodeBoundingBox().height == 64); - fortt.GoTopLeft(); - ASSERT(fortt.GetDepth() == 1); - ASSERT(fortt.GetNode() == &tl); - ASSERT(fortt.GetNodeBoundingBox().left == 0); - ASSERT(fortt.GetNodeBoundingBox().top == 0); - ASSERT(fortt.GetNodeBoundingBox().width == 32); - ASSERT(fortt.GetNodeBoundingBox().height == 32); - fortt.GoTopRight(); - ASSERT(fortt.GetDepth() == 2); - ASSERT(fortt.GetNode() == &tr); - ASSERT(fortt.GetNodeBoundingBox().left == 16); - ASSERT(fortt.GetNodeBoundingBox().top == 0); - ASSERT(fortt.GetNodeBoundingBox().width == 16); - ASSERT(fortt.GetNodeBoundingBox().height == 16); - fortt.GoBottomRight(); - ASSERT(fortt.GetDepth() == 3); - ASSERT(fortt.GetNode() == &br); - ASSERT(fortt.GetNodeBoundingBox().left == 24); - ASSERT(fortt.GetNodeBoundingBox().top == 8); - ASSERT(fortt.GetNodeBoundingBox().width == 8); - ASSERT(fortt.GetNodeBoundingBox().height == 8); - fortt.StartAt(&root, BoundingBox(0, 0, 64, 64)); - ASSERT(fortt.GetDepth() == 0); - ASSERT(fortt.GetNode() == &root); - ASSERT(fortt.GetNodeBoundingBox().left == 0); - ASSERT(fortt.GetNodeBoundingBox().top == 0); - ASSERT(fortt.GetNodeBoundingBox().width == 64); - ASSERT(fortt.GetNodeBoundingBox().height == 64); - fortt.GoBottomLeft(); - ASSERT(fortt.GetDepth() == 1); - ASSERT(fortt.GetNode() == &bl); - ASSERT(fortt.GetNodeBoundingBox().left == 0); - ASSERT(fortt.GetNodeBoundingBox().top == 32); - ASSERT(fortt.GetNodeBoundingBox().width == 32); - ASSERT(fortt.GetNodeBoundingBox().height == 32); -} - -template -void TestFullTreeTraversal() { - detail::BlocksAllocator allocator; - detail::FullTreeTraversal> fultt; - detail::TreeNode> root(allocator); - detail::TreeNode> tl(allocator); - detail::TreeNode> tr(allocator); - detail::TreeNode> br(allocator); - detail::TreeNode> bl(allocator); - root.top_left = &tl; - tl.top_right = &tr; - tr.bottom_right = &br; - br.bottom_left = &bl; - fultt.StartAt(&root, BoundingBox(0, 0, 64, 64)); - ASSERT(fultt.GetDepth() == 0); - ASSERT(fultt.GetNode() == &root); - ASSERT(fultt.GetNodeCurrentChild() == detail::ChildPosition::kNone); - fultt.GoTopLeft(); - ASSERT(fultt.GetDepth() == 1); - ASSERT(fultt.GetNode() == &tl); - ASSERT(fultt.GetNodeCurrentChild() == detail::ChildPosition::kNone); - fultt.GoTopRight(); - ASSERT(fultt.GetDepth() == 2); - ASSERT(fultt.GetNode() == &tr); - ASSERT(fultt.GetNodeCurrentChild() == detail::ChildPosition::kNone); - fultt.GoBottomRight(); - ASSERT(fultt.GetDepth() == 3); - ASSERT(fultt.GetNode() == &br); - ASSERT(fultt.GetNodeCurrentChild() == detail::ChildPosition::kNone); - fultt.GoBottomLeft(); - ASSERT(fultt.GetDepth() == 4); - ASSERT(fultt.GetNode() == &bl); - ASSERT(fultt.GetNodeCurrentChild() == detail::ChildPosition::kNone); - fultt.GoUp(); - ASSERT(fultt.GetDepth() == 3); - ASSERT(fultt.GetNode() == &br); - ASSERT(fultt.GetNodeCurrentChild() == detail::ChildPosition::kBottomLeft); - fultt.GoUp(); - ASSERT(fultt.GetDepth() == 2); - ASSERT(fultt.GetNode() == &tr); - ASSERT(fultt.GetNodeCurrentChild() == detail::ChildPosition::kBottomRight); - fultt.GoUp(); - ASSERT(fultt.GetDepth() == 1); - ASSERT(fultt.GetNode() == &tl); - ASSERT(fultt.GetNodeCurrentChild() == detail::ChildPosition::kTopRight); - fultt.GoUp(); - ASSERT(fultt.GetDepth() == 0); - ASSERT(fultt.GetNode() == &root); - ASSERT(fultt.GetNodeCurrentChild() == detail::ChildPosition::kTopLeft); -} - -template -void TestBoundingBoxDiscrepancy() { - detail::BlocksAllocator allocator; - detail::FullTreeTraversal> ftt; - detail::TreeNode> root(allocator); - detail::TreeNode> tl(allocator); - detail::TreeNode> tr(allocator); - detail::TreeNode> br(allocator); - root.top_left = &tl; - root.top_right = &tr; - root.bottom_right = &br; - ftt.StartAt(&root, BoundingBox(10, 10, 17, 19)); - NumberT orig_width = ftt.GetNodeBoundingBox().width; - NumberT orig_height = ftt.GetNodeBoundingBox().height; - ftt.GoTopLeft(); - NumberT tl_width = ftt.GetNodeBoundingBox().width; - NumberT tl_height = ftt.GetNodeBoundingBox().height; - ftt.GoUp(); - ftt.GoTopRight(); - NumberT tr_width = ftt.GetNodeBoundingBox().width; - NumberT tr_height = ftt.GetNodeBoundingBox().height; - ftt.GoUp(); - ftt.GoBottomRight(); - NumberT br_width = ftt.GetNodeBoundingBox().width; - NumberT br_height = ftt.GetNodeBoundingBox().height; - ftt.GoUp(); - ASSERT(orig_width == tl_width + tr_width); - ASSERT(orig_height == tl_height + br_height); - ASSERT(tr_width == br_width); - ASSERT(tl_height == tr_height); -} - -template -void TestTraversals() { - TestForwardTreeTraversal(); - TestFullTreeTraversal(); - TestBoundingBoxDiscrepancy(); -} - - -template -void TestInsertRemove(bool reclaim_losses) { - std::vector> objects; - objects.emplace_back(1000, 1300, 50, 30); - objects.emplace_back(1060, 1300, 50, 30); - objects.emplace_back(1060, 1300, 5, 3); - LooseQuadtree, TrivialBBExtractor> lqt; - if (reclaim_losses) lqt.ForceCleanup(); - ASSERT(lqt.GetSize() == 0); - ASSERT(lqt.IsEmpty()); - ASSERT(!lqt.Contains(&objects[0])); - ASSERT(lqt.GetSize() == 0); - lqt.Insert(&objects[0]); - ASSERT(lqt.GetSize() == 1); - ASSERT(!lqt.IsEmpty()); - ASSERT(lqt.Contains(&objects[0])); - ASSERT(!lqt.Contains(&objects[1])); - ASSERT(lqt.GetLooseBoundingBox().Intersects(objects[0])); - ASSERT(!objects[0].Contains(lqt.GetLooseBoundingBox())); - lqt.Remove(&objects[0]); - ASSERT(!lqt.Contains(&objects[0])); - ASSERT(lqt.GetSize() == 0); - ASSERT(lqt.IsEmpty()); - if (reclaim_losses) lqt.ForceCleanup(); - - lqt.Insert(&objects[1]); - ASSERT(lqt.GetSize() == 1); - ASSERT(!lqt.Contains(&objects[0])); - ASSERT(lqt.Contains(&objects[1])); - lqt.Insert(&objects[0]); - lqt.Insert(&objects[0]); - lqt.Insert(&objects[0]); - ASSERT(lqt.GetSize() == 2); - ASSERT(lqt.Contains(&objects[0])); - ASSERT(lqt.Contains(&objects[1])); - ASSERT(!lqt.Contains(&objects[2])); - if (reclaim_losses) lqt.ForceCleanup(); - lqt.Insert(&objects[2]); - ASSERT(lqt.GetSize() == 3); - ASSERT(lqt.Contains(&objects[0])); - ASSERT(lqt.Contains(&objects[1])); - ASSERT(lqt.Contains(&objects[2])); - if (reclaim_losses) lqt.ForceCleanup(); - ASSERT(lqt.GetLooseBoundingBox().Intersects(objects[0])); - ASSERT(!objects[0].Contains(lqt.GetLooseBoundingBox())); - ASSERT(lqt.GetLooseBoundingBox().Intersects(objects[1])); - ASSERT(!objects[1].Contains(lqt.GetLooseBoundingBox())); - ASSERT(lqt.GetLooseBoundingBox().Intersects(objects[2])); - ASSERT(!objects[2].Contains(lqt.GetLooseBoundingBox())); - lqt.Remove(&objects[1]); - lqt.Remove(&objects[1]); - lqt.Remove(&objects[1]); - ASSERT(lqt.GetSize() == 2); - ASSERT(lqt.Contains(&objects[0])); - ASSERT(!lqt.Contains(&objects[1])); - ASSERT(lqt.Contains(&objects[2])); - if (reclaim_losses) lqt.ForceCleanup(); - lqt.Remove(&objects[0]); - ASSERT(lqt.GetSize() == 1); - ASSERT(!lqt.Contains(&objects[0])); - ASSERT(!lqt.Contains(&objects[1])); - ASSERT(lqt.Contains(&objects[2])); - if (reclaim_losses) lqt.ForceCleanup(); - lqt.Remove(&objects[0]); - ASSERT(lqt.GetSize() == 1); - ASSERT(!lqt.Contains(&objects[0])); - ASSERT(!lqt.Contains(&objects[1])); - ASSERT(lqt.Contains(&objects[2])); - if (reclaim_losses) lqt.ForceCleanup(); - lqt.Remove(&objects[2]); - ASSERT(lqt.GetSize() == 0); - ASSERT(!lqt.Contains(&objects[0])); - ASSERT(!lqt.Contains(&objects[1])); - ASSERT(!lqt.Contains(&objects[2])); - if (reclaim_losses) lqt.ForceCleanup(); -} - -template -void TestUpdate(bool reclaim_losses) { - std::vector> objects; - objects.emplace_back(1000, 1000, 50, 30); - objects.emplace_back(1060, 1000, 50, 30); - objects.emplace_back(1060, 1000, 5, 3); - LooseQuadtree, TrivialBBExtractor> lqt; - if (reclaim_losses) lqt.ForceCleanup(); - lqt.Insert(&objects[0]); - lqt.Insert(&objects[1]); - lqt.Insert(&objects[2]); - if (reclaim_losses) lqt.ForceCleanup(); - ASSERT(lqt.GetSize() == 3); - ASSERT(lqt.Contains(&objects[0])); - ASSERT(lqt.Contains(&objects[1])); - ASSERT(lqt.Contains(&objects[2])); - ASSERT(lqt.GetLooseBoundingBox().Intersects(objects[0])); - ASSERT(lqt.GetLooseBoundingBox().Intersects(objects[1])); - ASSERT(lqt.GetLooseBoundingBox().Intersects(objects[2])); - ASSERT(!objects[0].Contains(lqt.GetLooseBoundingBox())); - ASSERT(!objects[1].Contains(lqt.GetLooseBoundingBox())); - ASSERT(!objects[2].Contains(lqt.GetLooseBoundingBox())); - objects[2].width = 50; - objects[2].height = 30; - lqt.Update(&objects[2]); - objects[0].left = 1060; - lqt.Update(&objects[0]); - ASSERT(lqt.GetSize() == 3); - ASSERT(lqt.Contains(&objects[0])); - ASSERT(lqt.Contains(&objects[1])); - ASSERT(lqt.Contains(&objects[2])); - ASSERT(lqt.GetLooseBoundingBox().Intersects(objects[0])); - ASSERT(lqt.GetLooseBoundingBox().Intersects(objects[1])); - ASSERT(lqt.GetLooseBoundingBox().Intersects(objects[2])); - ASSERT(!objects[0].Contains(lqt.GetLooseBoundingBox())); - ASSERT(!objects[1].Contains(lqt.GetLooseBoundingBox())); - ASSERT(!objects[2].Contains(lqt.GetLooseBoundingBox())); - if (reclaim_losses) lqt.ForceCleanup(); - ASSERT(lqt.GetSize() == 3); - ASSERT(lqt.Contains(&objects[0])); - ASSERT(lqt.Contains(&objects[1])); - ASSERT(lqt.Contains(&objects[2])); - ASSERT(lqt.GetLooseBoundingBox().Intersects(objects[0])); - ASSERT(lqt.GetLooseBoundingBox().Intersects(objects[1])); - ASSERT(lqt.GetLooseBoundingBox().Intersects(objects[2])); - ASSERT(!objects[0].Contains(lqt.GetLooseBoundingBox())); - ASSERT(!objects[1].Contains(lqt.GetLooseBoundingBox())); - ASSERT(!objects[2].Contains(lqt.GetLooseBoundingBox())); - lqt.Remove(&objects[0]); - ASSERT(lqt.GetSize() == 2); - if (reclaim_losses) lqt.ForceCleanup(); - lqt.Remove(&objects[1]); - ASSERT(lqt.GetSize() == 1); - if (reclaim_losses) lqt.ForceCleanup(); - lqt.Remove(&objects[2]); - ASSERT(lqt.GetSize() == 0); - if (reclaim_losses) lqt.ForceCleanup(); -} - -template -void TestMoreTrees(bool reclaim_losses) { - std::vector> objects; - objects.emplace_back(1000, 1000, 50, 30); - objects.emplace_back(1060, 1000, 50, 30); - objects.emplace_back(1060, 1000, 5, 3); - LooseQuadtree, TrivialBBExtractor> lqt; - if (reclaim_losses) lqt.ForceCleanup(); - lqt.Insert(&objects[0]); - lqt.Insert(&objects[1]); - ASSERT(lqt.GetSize() == 2); - ASSERT(lqt.Contains(&objects[0])); - ASSERT(lqt.Contains(&objects[1])); - ASSERT(lqt.GetLooseBoundingBox().Intersects(objects[0])); - ASSERT(lqt.GetLooseBoundingBox().Intersects(objects[1])); - ASSERT(!objects[0].Contains(lqt.GetLooseBoundingBox())); - ASSERT(!objects[1].Contains(lqt.GetLooseBoundingBox())); - if (reclaim_losses) lqt.ForceCleanup(); - { - LooseQuadtree, TrivialBBExtractor> lqt2; - if (reclaim_losses) lqt2.ForceCleanup(); - ASSERT(lqt2.GetSize() == 0); - lqt2.Insert(&objects[1]); - lqt2.Insert(&objects[2]); - lqt.Insert(&objects[2]); - if (reclaim_losses) lqt.ForceCleanup(); - ASSERT(lqt2.GetSize() == 2); - ASSERT(!lqt2.Contains(&objects[0])); - ASSERT(lqt2.Contains(&objects[1])); - ASSERT(lqt2.Contains(&objects[2])); - if (reclaim_losses) lqt2.ForceCleanup(); - lqt2.Remove(&objects[1]); - lqt2.Remove(&objects[2]); - ASSERT(lqt2.GetSize() == 0); - if (reclaim_losses) lqt2.ForceCleanup(); - } - { - LooseQuadtree, TrivialBBExtractor> lqt2; - lqt2.Insert(&objects[1]); - if (reclaim_losses) lqt2.ForceCleanup(); - } - { - LooseQuadtree, TrivialBBExtractor> lqt2; - lqt2.Insert(&objects[1]); - lqt2.Insert(&objects[2]); - lqt2.Insert(&objects[0]); - ASSERT(lqt2.Contains(&objects[1])); - lqt2.Clear(); - ASSERT(lqt2.GetSize() == 0); - ASSERT(!lqt2.Contains(&objects[1])); - if (reclaim_losses) lqt2.ForceCleanup(); - ASSERT(lqt2.GetSize() == 0); - ASSERT(!lqt2.Contains(&objects[1])); - lqt2.Insert(&objects[1]); - ASSERT(lqt2.GetSize() == 1); - ASSERT(lqt2.Contains(&objects[1])); - } - ASSERT(lqt.GetSize() == 3); - ASSERT(lqt.Contains(&objects[0])); - ASSERT(lqt.Contains(&objects[1])); - ASSERT(lqt.Contains(&objects[2])); - ASSERT(lqt.GetLooseBoundingBox().Intersects(objects[0])); - ASSERT(lqt.GetLooseBoundingBox().Intersects(objects[1])); - ASSERT(lqt.GetLooseBoundingBox().Intersects(objects[2])); - ASSERT(!objects[0].Contains(lqt.GetLooseBoundingBox())); - ASSERT(!objects[1].Contains(lqt.GetLooseBoundingBox())); - ASSERT(!objects[2].Contains(lqt.GetLooseBoundingBox())); - lqt.Remove(&objects[0]); - lqt.Remove(&objects[2]); - ASSERT(!lqt.Contains(&objects[0])); - ASSERT(lqt.Contains(&objects[1])); - ASSERT(lqt.GetSize() == 1); - if (reclaim_losses) lqt.ForceCleanup(); - lqt.Remove(&objects[1]); - ASSERT(lqt.GetSize() == 0); - if (reclaim_losses) lqt.ForceCleanup(); -} - -template -void TestContainer() { - TestInsertRemove(false); - TestInsertRemove(true); - TestUpdate(false); - TestUpdate(true); - TestMoreTrees(false); - TestMoreTrees(true); -} - - - -template -void TestQueryIntersects(const std::vector>& objects, - LooseQuadtree, TrivialBBExtractor>& lqt) { - auto query = lqt.QueryIntersectsRegion(BoundingBox(33,33,1,1)); - ASSERT(query.EndOfQuery()); - - query = lqt.QueryIntersectsRegion(BoundingBox(9000,9000,9000,9000)); - int count = 0; - while (!query.EndOfQuery()) { - BoundingBox* obj = query.GetCurrent(); - (void)obj; - count++; - query.Next(); - } - ASSERT(count == 7); - - query = lqt.QueryIntersectsRegion(BoundingBox(10003,10003,3,7)); - count = 0; - while (!query.EndOfQuery()) { - BoundingBox* obj = query.GetCurrent(); - if (obj != &objects[0] && obj != &objects[1] && obj != &objects[2]) { - ASSERT(false); - } - count++; - query.Next(); - } - ASSERT(count == 3); - - query = lqt.QueryIntersectsRegion(BoundingBox(14900,14900,200,200)); - count = 0; - while (!query.EndOfQuery()) { - BoundingBox* obj = query.GetCurrent(); - if (obj != &objects[0] && obj != &objects[1] && obj != &objects[3] && obj != &objects[5]) { - ASSERT(false); - } - count++; - query.Next(); - } - ASSERT(count == 4); -} - -template -void TestQueryInside(const std::vector>& objects, - LooseQuadtree, TrivialBBExtractor>& lqt) { - auto query = lqt.QueryInsideRegion(BoundingBox(33,33,1,1)); - ASSERT(query.EndOfQuery()); - - query = lqt.QueryInsideRegion(BoundingBox(9000,9000,9000,9000)); - int count = 0; - while (!query.EndOfQuery()) { - BoundingBox* obj = query.GetCurrent(); - (void)obj; - count++; - query.Next(); - } - ASSERT(count == 7); - - query = lqt.QueryInsideRegion(BoundingBox(10003,10003,3,7)); - ASSERT(query.EndOfQuery()); - - query = lqt.QueryInsideRegion(BoundingBox(14900,14900,300,300)); - count = 0; - while (!query.EndOfQuery()) { - BoundingBox* obj = query.GetCurrent(); - if (obj != &objects[5] && obj != &objects[6]) { - ASSERT(false); - } - count++; - query.Next(); - } - ASSERT(count == 2); -} - -template -void TestQueryContains(const std::vector>& objects, - LooseQuadtree, TrivialBBExtractor>& lqt) { - auto query = lqt.QueryContainsRegion(BoundingBox(33,33,1,1)); - ASSERT(query.EndOfQuery()); - - query = lqt.QueryContainsRegion(BoundingBox(9000,9000,9000,9000)); - ASSERT(query.EndOfQuery()); - - query = lqt.QueryContainsRegion(BoundingBox(10003,10003,3,7)); - int count = 0; - while (!query.EndOfQuery()) { - BoundingBox* obj = query.GetCurrent(); - if (obj != &objects[0] && obj != &objects[1]) { - ASSERT(false); - } - count++; - query.Next(); - } - ASSERT(count == 2); - - query = lqt.QueryContainsRegion(BoundingBox(14900,14900,200,200)); - count = 0; - while (!query.EndOfQuery()) { - BoundingBox* obj = query.GetCurrent(); - if (obj != &objects[0] && obj != &objects[1]) { - ASSERT(false); - } - count++; - query.Next(); - } - ASSERT(count == 2); - - query = lqt.QueryContainsRegion(BoundingBox(15000,15000,2,2)); - count = 0; - while (!query.EndOfQuery()) { - BoundingBox* obj = query.GetCurrent(); - if (obj != &objects[0] && obj != &objects[1] && obj != &objects[3] && obj != &objects[5]) { - ASSERT(false); - } - count++; - query.Next(); - } - ASSERT(count == 4); -} - -template -void TestQueries() { - std::vector> objects; - objects.emplace_back(10000, 10000, 8000, 8000);//0 - objects.emplace_back(10000, 10000, 7000, 6000);//1 - objects.emplace_back(10000, 10000, 7, 6);//2 - objects.emplace_back(15000, 15000, 500, 600);//3 - objects.emplace_back(15100, 15100, 200, 200);//4 - objects.emplace_back(15000, 15000, 200, 200);//5 - objects.emplace_back(15100, 15100, 2, 2);//6 - LooseQuadtree, TrivialBBExtractor> lqt; - for (auto& obj : objects) { - lqt.Insert(&obj); - } - TestQueryIntersects(objects, lqt); - TestQueryInside(objects, lqt); - TestQueryContains(objects, lqt); -} - -template -[[maybe_unused]] void StressTest() { -#if 0 - const int objects_generated = 100; - const int object_fluctuation = 10; -#else - const int objects_generated = 200000; - const int object_fluctuation = 20000; -#endif - const int full_rounds = 24; - const int query_rounds = 4; - std::minstd_rand rand; - std::uniform_int_distribution index(0, objects_generated - 1); - std::uniform_real_distribution - coordinate(std::is_integral::value ? - (float)(std::is_signed::value ? - -std::numeric_limits::max() / 8 : - std::numeric_limits::max() / 16 * 7) : - -1.0f, - std::is_integral::value ? - (float)(std::is_signed::value ? - std::numeric_limits::max() / 8 : - std::numeric_limits::max() / 16 * 9) : - 1.0f); - std::uniform_real_distribution - distance(0.0f, std::is_integral::value ? - (float)(std::is_signed::value ? - std::numeric_limits::max() / 8 : - std::numeric_limits::max() / 16) : - 0.5f); - - std::vector> objects; - objects.reserve(objects_generated); - std::vector flags(objects_generated, false); - LooseQuadtree, TrivialBBExtractor> lqt; - for (std::size_t i = 0; i < objects_generated; i++) { - objects.emplace_back((NumberT)coordinate(rand), (NumberT)coordinate(rand), - (NumberT)distance(rand), (NumberT)distance(rand)); - lqt.Insert(&objects[i]); - } - ASSERT(objects.size() == objects_generated); - ASSERT(flags.size() == objects_generated); - - for (int round = 0; round < full_rounds; round++) { - for (int fluctobj = 0; fluctobj < object_fluctuation; fluctobj++) { - std::size_t id = index(rand); - objects[id] = BoundingBox((NumberT)coordinate(rand), (NumberT)coordinate(rand), - (NumberT)distance(rand), (NumberT)distance(rand)); - lqt.Update(&objects[id]); - } - for (int query_round = 0; query_round < query_rounds; query_round++) { - BoundingBox query_region((NumberT)coordinate(rand), (NumberT)coordinate(rand), - (NumberT)distance(rand), (NumberT)distance(rand)); - for (std::size_t i = 0; i < objects_generated; i++) { - flags[i] = false; - } - - auto query = lqt.QueryIntersectsRegion(query_region); - while (!query.EndOfQuery()) { - BoundingBox* obj = query.GetCurrent(); - ASSERT(query_region.Intersects(*obj)); - std::size_t id = (std::size_t)(obj - &objects[0]); - ASSERT(id < objects_generated); - flags[id] = true; - query.Next(); - } - for (std::size_t i = 0; i < objects_generated; i++) { - ASSERT(flags[i] == query_region.Intersects(objects[i])); - flags[i] = false; - } - - query = lqt.QueryInsideRegion(query_region); - while (!query.EndOfQuery()) { - BoundingBox* obj = query.GetCurrent(); - ASSERT(query_region.Contains(*obj)); - std::size_t id = (std::size_t)(obj - &objects[0]); - ASSERT(id < objects_generated); - flags[id] = true; - query.Next(); - } - for (std::size_t i = 0; i < objects_generated; i++) { - ASSERT(flags[i] == query_region.Contains(objects[i])); - flags[i] = false; - } - - query = lqt.QueryContainsRegion(query_region); - while (!query.EndOfQuery()) { - BoundingBox* obj = query.GetCurrent(); - ASSERT(obj->Contains(query_region)); - std::size_t id = (std::size_t)(obj - &objects[0]); - ASSERT(id < objects_generated); - flags[id] = true; - query.Next(); - } - for (std::size_t i = 0; i < objects_generated; i++) { - ASSERT(flags[i] == objects[i].Contains(query_region)); - //flags[i] = false; - } - } - } - lqt.ForceCleanup(); -} - -#define FM_NO_QUADTREE_BENCHMARK - -template -void RunTests(const char* type_str) -{ - (void)type_str; -#ifndef FM_NO_QUADTREE_BENCHMARK - printf("quadtree test %13s", type_str); - fflush(stdout); - auto start = std::chrono::high_resolution_clock::now(); -#endif - TestBoundingBox(); - TestTraversals(); - TestContainer(); - TestQueries(); -#ifndef FM_NO_QUADTREE_BENCHMARK - StressTest(); - auto end = std::chrono::high_resolution_clock::now(); - std::chrono::duration time = end - start; - printf(": %.1f ms\n", time.count()); - fflush(stdout); -#endif -} - -} // namespace - -namespace floormat { - -#define RUN_TEST(x) RunTests(#x) - -void test_app::test_quadtree() -{ - RUN_TEST(float); - RUN_TEST(double); - RUN_TEST(long double); - RUN_TEST(std::int16_t); - RUN_TEST(std::int32_t); - RUN_TEST(std::int64_t); - RUN_TEST(std::uint16_t); - RUN_TEST(std::uint32_t); - RUN_TEST(std::uint64_t); -} - -} // namespace floormat -- cgit v1.2.3