refactor: move quadtree and util functions into separate headers and clean up names

9 files changed, 210 insertions, 134 deletions

diff --git a/experimental/tectonics/Makefile b/experimental/tectonics/Makefile
index dd04325..877fec1 100644
--- a/experimental/tectonics/Makefile
+++ b/experimental/tectonics/Makefile
@@ -8,5 +8,5 @@ DEPS=tectonics.h
 all: world.o util.o tectonics.o quadtree.o
 		$(CC) -o tectonics world.o util.o tectonics.o quadtree.o $(CFLAGS)
 
-test: all quadtree.test.o tests.o
+test: all quadtree.o quadtree.test.o tests.o
 		$(CC) -o tests world.o util.o quadtree.o quadtree.test.o tests.o $(CFLAGS)
diff --git a/experimental/tectonics/geometry.h b/experimental/tectonics/geometry.h
new file mode 100644
index 0000000..09bd7c8
--- /dev/null
+++ b/experimental/tectonics/geometry.h
@@ -0,0 +1,71 @@
+#ifndef GEOMETRY_H
+#define GEOMETRY_H
+
+#include <stdbool.h>
+#include <cairo.h>
+
+struct point_t {
+   double x, y;
+   void *data;
+};
+
+
+struct quad_region_t {
+   struct point_t center;
+   double half_dim;
+};
+
+
+struct quadtree_node_t {
+   struct quad_region_t region;
+
+   int id;
+   
+   /* children */
+   struct quadtree_node_t *nw, *ne, *sw, *se;
+};
+
+
+/* ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
+ *
+ * quadtree
+ *
+ * ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
+ */
+
+/* check if a region contains a point */
+bool quad_contains_point(struct quad_region_t region,
+			 struct point_t pt);
+
+/* initialize a quadtree node */
+struct quadtree_node_t quadtree_new_node(struct point_t center,
+					 double half_dim);
+
+/* subdivide a quadtree node
+ *
+ * if the node already contains a point, it will be moved into
+ * the appropriate child node
+ */
+void quadtree_subdivide(struct quadtree_node_t *node,
+			struct point_t *points);
+
+/* insert a point into a quadtree */
+bool quadtree_insert(struct quadtree_node_t *node,
+		     struct point_t *points, int id);
+
+/* get the closest point to a particular point in
+ * a quadtree
+ */
+int quadtree_get_closest(struct quadtree_node_t *root,
+			 struct point_t *points,
+			 struct point_t pt);
+
+void draw_quadtree(cairo_t *cr, struct quadtree_node_t *root);
+
+/* free a quadtree structure
+ *
+ * note that this will *NOT* free any point userdata!
+ */
+void quadtree_free(struct quadtree_node_t *root);
+
+#endif
diff --git a/experimental/tectonics/quadtree.c b/experimental/tectonics/quadtree.c
index 3cb6639..820844d 100644
--- a/experimental/tectonics/quadtree.c
+++ b/experimental/tectonics/quadtree.c
@@ -1,7 +1,11 @@
 #include <math.h>
-#include "tectonics.h"
+#include <stddef.h>
+#include <stdlib.h>
+#include "util.h"
+#include "geometry.h"
 
-bool contains_point(struct quad_region_t region, struct point_t pt)
+bool quad_contains_point(struct quad_region_t region,
+			 struct point_t pt)
 {
    if (region.center.x - region.half_dim > pt.x ||
        region.center.x + region.half_dim <= pt.x)
@@ -14,7 +18,8 @@ bool contains_point(struct quad_region_t region, struct point_t pt)
 }
 
 
-struct quadtree_node_t new_node(struct point_t center, double half_dim)
+struct quadtree_node_t quadtree_new_node(struct point_t center,
+					 double half_dim)
 {
    struct quadtree_node_t node;
 
@@ -29,7 +34,8 @@ struct quadtree_node_t new_node(struct point_t center, double half_dim)
 }
 
 
-void subdivide(struct quadtree_node_t *node, struct point_t *points)
+void quadtree_subdivide(struct quadtree_node_t *node,
+			struct point_t *points)
 {
    node->nw = malloc(sizeof(struct quadtree_node_t));
    node->ne = malloc(sizeof(struct quadtree_node_t));
@@ -41,27 +47,30 @@ void subdivide(struct quadtree_node_t *node, struct point_t *points)
 
    struct point_t c_nw =
       { center.x - quarter_dim, center.y - quarter_dim };
-   *(node->nw) = new_node(c_nw, quarter_dim);
+   *(node->nw) = quadtree_new_node(c_nw, quarter_dim);
 
    struct point_t c_ne =
       { center.x + quarter_dim, center.y - quarter_dim };
-   *(node->ne) = new_node(c_ne, quarter_dim);
+   *(node->ne) = quadtree_new_node(c_ne, quarter_dim);
 
    struct point_t c_sw =
       { center.x - quarter_dim, center.y + quarter_dim };
-   *(node->sw) = new_node(c_sw, quarter_dim);
+   *(node->sw) = quadtree_new_node(c_sw, quarter_dim);
 
    struct point_t c_se =
       { center.x + quarter_dim, center.y + quarter_dim };
-   *(node->se) = new_node(c_se, quarter_dim);
+   *(node->se) = quadtree_new_node(c_se, quarter_dim);
 
    if (node->id != -1) {
    /* move point to a child */
-      if (contains_point(node->nw->region, points[node->id]))
+      if (quad_contains_point(node->nw->region,
+			      points[node->id]))
 	 node->nw->id = node->id;
-      else if (contains_point(node->ne->region, points[node->id]))
+      else if (quad_contains_point(node->ne->region,
+				   points[node->id]))
 	 node->ne->id = node->id;
-      else if (contains_point(node->sw->region, points[node->id]))
+      else if (quad_contains_point(node->sw->region,
+				   points[node->id]))
 	 node->sw->id = node->id;
       else
 	 node->se->id = node->id;
@@ -69,10 +78,10 @@ void subdivide(struct quadtree_node_t *node, struct point_t *points)
    }
 }
 
-bool insert(struct quadtree_node_t *node,
-	    struct point_t *points, int id)
+bool quadtree_insert(struct quadtree_node_t *node,
+		     struct point_t *points, int id)
 {
-   if (!contains_point(node->region, points[id]))
+   if (!quad_contains_point(node->region, points[id]))
       return false;
 
    if (node->id == -1 && node->nw == NULL) {
@@ -81,12 +90,12 @@ bool insert(struct quadtree_node_t *node,
    }
 
    if (node->nw == NULL)
-      subdivide(node, points);
+      quadtree_subdivide(node, points);
 
-   if (insert(node->nw, points, id)) return true;
-   if (insert(node->ne, points, id)) return true;
-   if (insert(node->sw, points, id)) return true;
-   if (insert(node->se, points, id)) return true;
+   if (quadtree_insert(node->nw, points, id)) return true;
+   if (quadtree_insert(node->ne, points, id)) return true;
+   if (quadtree_insert(node->sw, points, id)) return true;
+   if (quadtree_insert(node->se, points, id)) return true;
 
    return false;
 }
@@ -113,11 +122,11 @@ static int get_points_in_region(struct quadtree_node_t *node,
 }
 
 
-int get_closest(struct quadtree_node_t *node,
-		struct point_t *points,
-		struct point_t pt)
+int quadtree_get_closest(struct quadtree_node_t *node,
+			 struct point_t *points,
+			 struct point_t pt)
 {
-   if (!contains_point(node->region, pt))
+   if (!quad_contains_point(node->region, pt))
       return -1;
 
    if (node->id != -1)
@@ -125,13 +134,13 @@ int get_closest(struct quadtree_node_t *node,
 
    int closest;
    if (node->nw != NULL) {
-      if ((closest = get_closest(node->nw, points, pt)) != -1)
+      if ((closest = quadtree_get_closest(node->nw, points, pt)) != -1)
 	 return closest;
-      if ((closest = get_closest(node->ne, points, pt)) != -1)
+      if ((closest = quadtree_get_closest(node->ne, points, pt)) != -1)
 	 return closest;
-      if ((closest = get_closest(node->sw, points, pt)) != -1)
+      if ((closest = quadtree_get_closest(node->sw, points, pt)) != -1)
 	 return closest;
-      if ((closest = get_closest(node->se, points, pt)) != -1)
+      if ((closest = quadtree_get_closest(node->se, points, pt)) != -1)
 	 return closest;
 
       /* closest point is in a subregion, but not the *same*
@@ -182,13 +191,13 @@ void draw_quadtree(cairo_t *cr, struct quadtree_node_t *node)
 }
 
 
-void free_tree(struct quadtree_node_t *node)
+void quadtree_free(struct quadtree_node_t *node)
 {
    if (node->nw != NULL) {
-      free_tree(node->nw);
-      free_tree(node->ne);
-      free_tree(node->sw);
-      free_tree(node->se);
+      quadtree_free(node->nw);
+      quadtree_free(node->ne);
+      quadtree_free(node->sw);
+      quadtree_free(node->se);
    }
 
    free(node);
diff --git a/experimental/tectonics/quadtree.test.c b/experimental/tectonics/quadtree.test.c
index 472cc0d..ef504c0 100644
--- a/experimental/tectonics/quadtree.test.c
+++ b/experimental/tectonics/quadtree.test.c
@@ -1,6 +1,6 @@
 #include "minunit.h"
 #include "tests.h"
-#include "tectonics.h"
+#include "geometry.h"
 
 mu_test test_contains_point();
 mu_test test_subdivide();
@@ -31,15 +31,22 @@ mu_test test_contains_point()
    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(quad_contains_point(region,
+				 (struct point_t){ 0.5, 0.5 }));
+   mu_assert(quad_contains_point(region,
+				 (struct point_t){ 0.25, 0.5 }));
+   mu_assert(quad_contains_point(region,
+				 (struct point_t){ 0.5, 0.25 }));
+   mu_assert(quad_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 }));
+   mu_assert(!quad_contains_point(region,
+				  (struct point_t){ 1.25, 0.5 }));
+   mu_assert(!quad_contains_point(region,
+				  (struct point_t){ 0.25, 1.5 }));
+   mu_assert(!quad_contains_point(region,
+				  (struct point_t){ 1, 1 }));
 
    return 0;
 }
@@ -57,7 +64,7 @@ mu_test test_subdivide()
    node.sw = NULL;
    node.se = NULL;
 
-   subdivide(&node, pts);
+   quadtree_subdivide(&node, pts);
 
    mu_assert_equal(node.id, -1);
 
@@ -101,7 +108,7 @@ mu_test test_insert()
    node.sw = NULL;
    node.se = NULL;
 
-   insert(&node, pts, 1);
+   quadtree_insert(&node, pts, 1);
 
    mu_assert_equal(node.id, -1);
 
@@ -146,8 +153,8 @@ mu_test test_insert_two()
    node.sw = NULL;
    node.se = NULL;
 
-   insert(&node, pts, 1);
-   insert(&node, pts, 2);
+   quadtree_insert(&node, pts, 1);
+   quadtree_insert(&node, pts, 2);
 
    mu_assert_equal(node.id, -1);
 
@@ -206,8 +213,8 @@ mu_test test_get_closest()
    node.sw = NULL;
    node.se = NULL;
 
-   insert(&node, pts, 1);
-   insert(&node, pts, 2);
+   quadtree_insert(&node, pts, 1);
+   quadtree_insert(&node, pts, 2);
 
    mu_assert_equal(node.nw->nw->id,  2);
    mu_assert_equal(node.nw->nw->nw,  NULL);
@@ -218,24 +225,29 @@ mu_test test_get_closest()
    mu_assert_equal(node.nw->se->id,  1);
    mu_assert_equal(node.nw->se->nw,  NULL);
 
-   int closest_75 = get_closest(&node, pts,
-				(struct point_t){0.75, 0.75});
+   int closest_75 =
+      quadtree_get_closest(&node, pts,
+			   (struct point_t){0.75, 0.75});
    mu_assert_equal(closest_75, 0);
 
-   int closest_33 = get_closest(&node, pts,
-				(struct point_t){0.3, 0.3});
+   int closest_33 =
+      quadtree_get_closest(&node, pts,
+			   (struct point_t){0.3, 0.3});
    mu_assert_equal(closest_33, 1);
 
-   int closest_22 = get_closest(&node, pts,
-				(struct point_t){0.2, 0.2});
+   int closest_22 =
+      quadtree_get_closest(&node, pts,
+			   (struct point_t){0.2, 0.2});
    mu_assert_equal(closest_22, 2);
 
-   int closest_252 = get_closest(&node, pts,
-				 (struct point_t){0.251, 0.21});
+   int closest_252 =
+      quadtree_get_closest(&node, pts,
+			   (struct point_t){0.251, 0.21});
    mu_assert_equal(closest_252, 2);
 
-   int closest_nil = get_closest(&node, pts,
-				 (struct point_t){100, 100});
+   int closest_nil =
+      quadtree_get_closest(&node, pts,
+			   (struct point_t){100, 100});
    mu_assert_equal(closest_nil, -1);
 
    return 0;
diff --git a/experimental/tectonics/tectonics.c b/experimental/tectonics/tectonics.c
index f294944..e43a425 100644
--- a/experimental/tectonics/tectonics.c
+++ b/experimental/tectonics/tectonics.c
@@ -2,7 +2,7 @@
 
 #include "tectonics.h"
 
-#define X_RES 512
+#define X_RES 1024
 #define Y_RES X_RES
 
 int main()
@@ -11,7 +11,7 @@ int main()
    cairo_t *cr = cairo_create(surface);
 
    struct world_t world;
-   create_world(&world, 1000);
+   create_world(&world, 10000);
    if (world.points == NULL)
       return 1;
    render_world(cr, &world);
diff --git a/experimental/tectonics/tectonics.h b/experimental/tectonics/tectonics.h
index b2793e9..de5b18a 100644
--- a/experimental/tectonics/tectonics.h
+++ b/experimental/tectonics/tectonics.h
@@ -5,27 +5,7 @@
 #include <stdbool.h>
 #include <cairo.h>
 
-struct point_t {
-   double x, y;
-   void *data;
-};
-
-
-struct quad_region_t {
-   struct point_t center;
-   double half_dim;
-};
-
-
-struct quadtree_node_t {
-   struct quad_region_t region;
-
-   int id;
-   
-   /* children */
-   struct quadtree_node_t *nw, *ne, *sw, *se;
-};
-
+#include "geometry.h"
 
 struct world_t {
    struct point_t *points;
@@ -35,36 +15,6 @@ struct world_t {
 
 /* ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
  *
- * quadtree
- *
- * ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
- */
-
-bool contains_point(struct quad_region_t region, struct point_t pt);
-struct quadtree_node_t new_node(struct point_t center, double half_dim);
-void subdivide(struct quadtree_node_t *node, struct point_t *points);
-bool insert(struct quadtree_node_t *node,
-	    struct point_t *points, int id);
-int get_closest(struct quadtree_node_t *root,
-		struct point_t *points,
-		struct point_t pt);
-void draw_quadtree(cairo_t *cr, struct quadtree_node_t *root);
-void free_tree(struct quadtree_node_t *root);
-
-/* ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
- *
- * util
- *
- * ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
- */
-
-void get_cairo_size(cairo_t *cr, int *width, int *height);
-double rand01();
-double distance(struct point_t p1, struct point_t p2);
-
-
-/* ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
- *
  * worlds
  *
  * ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
diff --git a/experimental/tectonics/util.c b/experimental/tectonics/util.c
index 991ebc6..0bbe880 100644
--- a/experimental/tectonics/util.c
+++ b/experimental/tectonics/util.c
@@ -1,6 +1,7 @@
 #include <math.h>
+#include <stdlib.h>
 
-#include "tectonics.h"
+#include "util.h"
 
 void get_cairo_size(cairo_t *cr, int *width, int *height)
 {
diff --git a/experimental/tectonics/util.h b/experimental/tectonics/util.h
new file mode 100644
index 0000000..1a5a505
--- /dev/null
+++ b/experimental/tectonics/util.h
@@ -0,0 +1,11 @@
+#ifndef UTIL_H
+#define UTIL_H
+
+#include <cairo.h>
+#include "geometry.h"
+
+void get_cairo_size(cairo_t *cr, int *width, int *height);
+double rand01();
+double distance(struct point_t p1, struct point_t p2);
+
+#endif
diff --git a/experimental/tectonics/world.c b/experimental/tectonics/world.c
index a1dd4de..5aead24 100644
--- a/experimental/tectonics/world.c
+++ b/experimental/tectonics/world.c
@@ -2,19 +2,17 @@
 #include <math.h>
 
 #include "tectonics.h"
-
-struct centroid_t {
-   double x, y;
-   int updates;
-};
+#include "geometry.h"
+#include "util.h"
 
 static void rebuild_tree(struct world_t *world)
 {
+   // remove any existing tree
    if (world->tree.nw != NULL) {
-      free_tree(world->tree.nw);
-      free_tree(world->tree.ne);
-      free_tree(world->tree.sw);
-      free_tree(world->tree.se);
+      quadtree_free(world->tree.nw);
+      quadtree_free(world->tree.ne);
+      quadtree_free(world->tree.sw);
+      quadtree_free(world->tree.se);
       world->tree.nw = NULL;
       world->tree.ne = NULL;
       world->tree.sw = NULL;
@@ -22,16 +20,28 @@ static void rebuild_tree(struct world_t *world)
    }
    world->tree.id = -1;
 
+   // build a new tree
    for (int i=0; i<world->n_points; i++) {
-      insert(&(world->tree), world->points, i);
+      quadtree_insert(&(world->tree), world->points, i);
    }
 }
 
+
+/* ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~ */
+
+struct centroid_t {
+   double x, y;
+   int updates;
+};
+
+// monte-carlo lloyd's algorithm
 static void relax_points(struct world_t *world, int iterations)
 {
+   // centroids to compute
    struct centroid_t *centroid =
       malloc(sizeof(struct centroid_t) * world->n_points);
-   
+
+   // initialize centroids with current locations
    for (int i=0; i<world->n_points; i++) {
       struct point_t *pt = world->points + i;
       struct centroid_t *c = centroid + i;
@@ -40,18 +50,22 @@ static void relax_points(struct world_t *world, int iterations)
       c->updates = 1;
    }
 
+   // approximate centroids
    for (int i=0; i<iterations; i++) {
       printf("%02f%%\n", 100*((double)i+1)/iterations);
+      // generate a random point and find the closest
+      // terrain point
       double x = rand01();
       double y = rand01();
-      int closest = get_closest(&(world->tree),
-				world->points,
-				(struct point_t){x, y});
+      int closest = quadtree_get_closest(&(world->tree),
+					 world->points,
+					 (struct point_t){x, y});
 
       if (closest == -1) {
 	 printf("WARN: bad closest point!\n");
       }
       else {
+	 // average the centroid towards that random point
 	 struct centroid_t *c = centroid + closest;
 	 int u = c->updates;
 	 c->x = (u*c->x + x)/(u+1);
@@ -60,6 +74,7 @@ static void relax_points(struct world_t *world, int iterations)
       }
    }
 
+   // update positions from centroids
    for (int i=0; i<world->n_points; i++) {
       struct point_t *pt = world->points + i;
       struct centroid_t *c = centroid + i;
@@ -72,6 +87,9 @@ static void relax_points(struct world_t *world, int iterations)
    free(centroid);
 }
 
+
+/* ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~ */
+
 void create_world(struct world_t *world, int n_points)
 {
    world->n_points = n_points;
@@ -84,35 +102,39 @@ void create_world(struct world_t *world, int n_points)
    }
 
    struct point_t center = { 0.5, 0.5 };
-   world->tree = new_node(center, 0.5);
+   world->tree = quadtree_new_node(center, 0.5);
 
    for (int i=0; i<n_points; i++) {
       struct point_t *pt = world->points + i;
       pt->x = rand01();
       pt->y = rand01();
 
-      //insert(&(world->tree), world->points, i);
+      //quadtree_insert(&(world->tree), world->points, i);
    }
 
    rebuild_tree(world);
 
-   for (int i=0; i<10; i++)
-      relax_points(world, 100000);
+   for (int i=0; i<3; i++)
+      relax_points(world, 10*world->n_points);
 }
 
 
+/* ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~ */
+
 void free_world(struct world_t *world)
 {
    if (world->tree.nw != NULL) {
-      free_tree(world->tree.nw);
-      free_tree(world->tree.ne);
-      free_tree(world->tree.sw);
-      free_tree(world->tree.se);
+      quadtree_free(world->tree.nw);
+      quadtree_free(world->tree.ne);
+      quadtree_free(world->tree.sw);
+      quadtree_free(world->tree.se);
    }
    free(world->points);
 }
 
 
+/* ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~ */
+
 void render_world(cairo_t *cr, struct world_t *world)
 {
    int width, height;
@@ -128,5 +150,5 @@ void render_world(cairo_t *cr, struct world_t *world)
       cairo_stroke(cr);
    }
 
-   draw_quadtree(cr, &(world->tree));
+   //draw_quadtree(cr, &(world->tree));
 }