From 7dd0604d57fb0941b87cc944f46afa68e386d99f Mon Sep 17 00:00:00 2001 From: Stanislaw Halik Date: Sun, 4 Dec 2022 14:39:47 +0100 Subject: add loose quadtree --- test/LooseQuadtreeTest.cpp | 729 +++++++++++++++++++++++++++++++++++++++++++++ 1 file changed, 729 insertions(+) create mode 100644 test/LooseQuadtreeTest.cpp (limited to 'test') diff --git a/test/LooseQuadtreeTest.cpp b/test/LooseQuadtreeTest.cpp new file mode 100644 index 00000000..ca1e935d --- /dev/null +++ b/test/LooseQuadtreeTest.cpp @@ -0,0 +1,729 @@ +#include "LooseQuadtree.h" + +#include +#include +#include +#include +#include + +using namespace loose_quadtree; + + + +#define ASSERT(CONDITION) if (!(CONDITION)) {\ + printf("Assertion failure %s:%d ASSERT(%s)\n", __FILE__, __LINE__, #CONDITION);\ + abort();\ + } + + +template +class TrivialBBExtractor { +public: + static void ExtractBoundingBox(const BoundingBox *object, BoundingBox *bbox) { + bbox->left = object->left; + bbox->top = object->top; + bbox->width = object->width; + bbox->height = object->height; + } +}; + + + +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 +void StressTest() { +#ifndef NDEBUG + const int objects_generated = 10000; + const int object_fluctuation = 1000; +#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 >= 0 && 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 >= 0 && 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 >= 0 && 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(); +} + + + +template +void RunTests(const char* type_str) { + printf("***** Running tests for %s (%lu-bit)... ", type_str, sizeof(NumberT) * 8); + auto start = std::chrono::high_resolution_clock::now(); + TestBoundingBox(); + TestTraversals(); + TestContainer(); + TestQueries(); + StressTest(); + auto end = std::chrono::high_resolution_clock::now(); + std::chrono::duration time = end - start; + printf("took %f seconds\n", time.count()); +} + + + +int main(int, char*[]) { + puts("***** Testing is about to start *****"); + printf("***** This system is %lu-bit\n", sizeof(void*) * 8); + RunTests("float"); + RunTests("double"); + RunTests("long double"); + RunTests("int"); + RunTests("long"); + RunTests("short"); + RunTests("unsigned int"); + RunTests("unsigned long"); + RunTests("unsigned short"); + RunTests("long long"); + puts("***** Testing is successfully finished *****"); + return 0; +} + -- cgit v1.2.3