add quadtree and basic world model

1 files changed, 225 insertions, 0 deletions

diff --git a/experimental/tectonics/quadtree.test.c b/experimental/tectonics/quadtree.test.c
new file mode 100644
index 0000000..273087b
--- /dev/null
+++ b/experimental/tectonics/quadtree.test.c
@@ -0,0 +1,225 @@
+#include "minunit.h"
+#include "tests.h"
+#include "tectonics.h"
+
+mu_test test_contains_point();
+mu_test test_subdivide();
+mu_test test_insert();
+mu_test test_insert_two();
+mu_test test_get_closest();
+
+void quadtree_tests()
+{
+   mu_run_test("check if contains_point() works",
+	       test_contains_point);
+   mu_run_test("subdivide quadtree node",
+	       test_subdivide);
+   mu_run_test("insert second point",
+	       test_insert);
+   mu_run_test("insert two more points",
+	       test_insert_two);
+   mu_run_test("look up nearest point",
+	       test_get_closest);
+}
+
+
+/* ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~ */
+
+mu_test test_contains_point()
+{
+   struct quad_region_t region;
+   region.center = (struct point_t){ 0.5, 0.5 };
+   region.half_dim = 0.5;
+
+   mu_assert(contains_point(region, (struct point_t){ 0.5, 0.5 }));
+   mu_assert(contains_point(region, (struct point_t){ 0.25, 0.5 }));
+   mu_assert(contains_point(region, (struct point_t){ 0.5, 0.25 }));
+   mu_assert(contains_point(region, (struct point_t){ 0, 0 }));
+
+
+   mu_assert(!contains_point(region, (struct point_t){ 1.25, 0.5 }));
+   mu_assert(!contains_point(region, (struct point_t){ 0.25, 1.5 }));
+   mu_assert(!contains_point(region, (struct point_t){ 1, 1 }));
+
+   return 0;
+}
+
+
+mu_test test_subdivide()
+{
+   struct quadtree_node_t node;
+   struct point_t pts[1] = { { 0.75, 0.75 } };
+
+   node.region = (struct quad_region_t){ { 0.5, 0.5 }, 0.5 };
+   node.id = 0;
+   node.nw = NULL;
+   node.ne = NULL;
+   node.sw = NULL;
+   node.se = NULL;
+
+   subdivide(&node, pts);
+
+   mu_assert_equal(node.id, -1);
+
+   mu_assert_equal(node.nw->region.center.x, 0.25);
+   mu_assert_equal(node.nw->region.center.y, 0.25);
+   mu_assert_equal(node.nw->region.half_dim, 0.25);
+   mu_assert_equal(node.nw->nw, NULL);
+   mu_assert_equal(node.nw->id, -1);
+
+   mu_assert_equal(node.ne->region.center.x, 0.75);
+   mu_assert_equal(node.ne->region.center.y, 0.25);
+   mu_assert_equal(node.ne->region.half_dim, 0.25);
+   mu_assert_equal(node.ne->nw, NULL);
+   mu_assert_equal(node.ne->id, -1);
+
+   mu_assert_equal(node.sw->region.center.x, 0.25);
+   mu_assert_equal(node.sw->region.center.y, 0.75);
+   mu_assert_equal(node.sw->region.half_dim, 0.25);
+   mu_assert_equal(node.sw->nw, NULL);
+   mu_assert_equal(node.sw->id, -1);
+
+   mu_assert_equal(node.se->region.center.x, 0.75);
+   mu_assert_equal(node.se->region.center.y, 0.75);
+   mu_assert_equal(node.se->region.half_dim, 0.25);
+   mu_assert_equal(node.se->nw, NULL);
+   mu_assert_equal(node.se->id, 0);
+
+   return 0;
+}
+
+
+mu_test test_insert()
+{
+   struct quadtree_node_t node;
+   struct point_t pts[2] = { {0.75, 0.75}, {0.25, 0.25} };
+
+   node.region = (struct quad_region_t){ { 0.5, 0.5 }, 0.5 };
+   node.id = 0;
+   node.nw = NULL;
+   node.ne = NULL;
+   node.sw = NULL;
+   node.se = NULL;
+
+   insert(&node, pts, 1);
+
+   mu_assert_equal(node.id, -1);
+
+   mu_assert_equal(node.nw->region.center.x, 0.25);
+   mu_assert_equal(node.nw->region.center.y, 0.25);
+   mu_assert_equal(node.nw->region.half_dim, 0.25);
+   mu_assert_equal(node.nw->nw, NULL);
+   mu_assert_equal(node.nw->id, 1);
+
+   mu_assert_equal(node.ne->region.center.x, 0.75);
+   mu_assert_equal(node.ne->region.center.y, 0.25);
+   mu_assert_equal(node.ne->region.half_dim, 0.25);
+   mu_assert_equal(node.ne->nw, NULL);
+   mu_assert_equal(node.ne->id, -1);
+
+   mu_assert_equal(node.sw->region.center.x, 0.25);
+   mu_assert_equal(node.sw->region.center.y, 0.75);
+   mu_assert_equal(node.sw->region.half_dim, 0.25);
+   mu_assert_equal(node.sw->nw, NULL);
+   mu_assert_equal(node.sw->id, -1);
+
+   mu_assert_equal(node.se->region.center.x, 0.75);
+   mu_assert_equal(node.se->region.center.y, 0.75);
+   mu_assert_equal(node.se->region.half_dim, 0.25);
+   mu_assert_equal(node.se->nw, NULL);
+   mu_assert_equal(node.se->id, 0);
+
+   return 0;
+}
+
+
+mu_test test_insert_two()
+{
+   struct quadtree_node_t node;
+   struct point_t pts[3] =
+      { {0.75, 0.75}, {0.3, 0.3}, {0.2, 0.2} };
+
+   node.region = (struct quad_region_t){ { 0.5, 0.5 }, 0.5 };
+   node.id = 0;
+   node.nw = NULL;
+   node.ne = NULL;
+   node.sw = NULL;
+   node.se = NULL;
+
+   insert(&node, pts, 1);
+   insert(&node, pts, 2);
+
+   mu_assert_equal(node.id, -1);
+
+   mu_assert_equal(node.nw->region.center.x, 0.25);
+   mu_assert_equal(node.nw->region.center.y, 0.25);
+   mu_assert_equal(node.nw->region.half_dim, 0.25);
+   mu_assert_equal(node.nw->id, -1);
+
+   /*printf("%d, %d, %d, %d\n",
+	  node.nw->nw->id,
+	  node.nw->ne->id,
+	  node.nw->sw->id,
+	  node.nw->se->id);*/
+
+   mu_assert_equal(node.nw->nw->id,  2);
+   mu_assert_equal(node.nw->nw->nw,  NULL);
+   mu_assert_equal(node.nw->ne->id, -1);
+   mu_assert_equal(node.nw->ne->nw,  NULL);
+   mu_assert_equal(node.nw->sw->id, -1);
+   mu_assert_equal(node.nw->sw->nw,  NULL);
+   mu_assert_equal(node.nw->se->id,  1);
+   mu_assert_equal(node.nw->se->nw,  NULL);
+
+   mu_assert_equal(node.ne->region.center.x, 0.75);
+   mu_assert_equal(node.ne->region.center.y, 0.25);
+   mu_assert_equal(node.ne->region.half_dim, 0.25);
+   mu_assert_equal(node.ne->nw, NULL);
+   mu_assert_equal(node.ne->id, -1);
+
+   mu_assert_equal(node.sw->region.center.x, 0.25);
+   mu_assert_equal(node.sw->region.center.y, 0.75);
+   mu_assert_equal(node.sw->region.half_dim, 0.25);
+   mu_assert_equal(node.sw->nw, NULL);
+   mu_assert_equal(node.sw->id, -1);
+
+   mu_assert_equal(node.se->region.center.x, 0.75);
+   mu_assert_equal(node.se->region.center.y, 0.75);
+   mu_assert_equal(node.se->region.half_dim, 0.25);
+   mu_assert_equal(node.se->nw, NULL);
+   mu_assert_equal(node.se->id, 0);
+
+   return 0;
+}
+
+
+mu_test test_get_closest()
+{
+   struct quadtree_node_t node;
+   struct point_t pts[3] =
+      { {0.75, 0.75}, {0.3, 0.3}, {0.2, 0.2} };
+
+   node.region = (struct quad_region_t){ { 0.5, 0.5 }, 0.5 };
+   node.id = 0;
+   node.nw = NULL;
+   node.ne = NULL;
+   node.sw = NULL;
+   node.se = NULL;
+
+   insert(&node, pts, 1);
+   insert(&node, pts, 2);
+
+   int closest_75 = get_closest(&node, (struct point_t){0.75, 0.75});
+   mu_assert_equal(closest_75, 0);
+
+   int closest_33 = get_closest(&node, (struct point_t){0.3, 0.3});
+   mu_assert_equal(closest_33, 1);
+
+   int closest_22 = get_closest(&node, (struct point_t){0.2, 0.2});
+   mu_assert_equal(closest_22, 2);
+
+   int closest_nil = get_closest(&node, (struct point_t){100, 100});
+   mu_assert_equal(closest_nil, -1);
+
+   return 0;
+}