From 672819693ddf1d203c304697b63f44059cff09b6 Mon Sep 17 00:00:00 2001 From: sanine Date: Wed, 26 Jan 2022 02:23:20 -0600 Subject: refactor: move quadtree and util functions into separate headers and clean up names --- experimental/tectonics/Makefile | 2 +- experimental/tectonics/geometry.h | 71 +++++++++++++++++++++++++++++++++ experimental/tectonics/quadtree.c | 73 +++++++++++++++++++--------------- experimental/tectonics/quadtree.test.c | 60 +++++++++++++++++----------- experimental/tectonics/tectonics.c | 4 +- experimental/tectonics/tectonics.h | 52 +----------------------- experimental/tectonics/util.c | 3 +- experimental/tectonics/util.h | 11 +++++ experimental/tectonics/world.c | 68 ++++++++++++++++++++----------- 9 files changed, 210 insertions(+), 134 deletions(-) create mode 100644 experimental/tectonics/geometry.h create mode 100644 experimental/tectonics/util.h 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 +#include + +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 -#include "tectonics.h" +#include +#include +#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 #include -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; @@ -33,36 +13,6 @@ struct world_t { int n_points; }; -/* ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~ - * - * 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 +#include -#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 +#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 #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; in_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; in_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; itree), - 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; in_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; ipoints + 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)); } -- cgit v1.2.1