summaryrefslogtreecommitdiff
diff options
context:
space:
mode:
Diffstat
-rw-r--r--experimental/tectonics/Makefile2
-rw-r--r--experimental/tectonics/geometry.h71
-rw-r--r--experimental/tectonics/quadtree.c73
-rw-r--r--experimental/tectonics/quadtree.test.c60
-rw-r--r--experimental/tectonics/tectonics.c4
-rw-r--r--experimental/tectonics/tectonics.h52
-rw-r--r--experimental/tectonics/util.c3
-rw-r--r--experimental/tectonics/util.h11
-rw-r--r--experimental/tectonics/world.c68
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));
}
generated by cgit v1.2.1 (git 2.18.0) at 2025-10-30 06:00:36 +0000