diff options
author | sanine <sanine.not@pm.me> | 2022-01-26 02:23:20 -0600 |
---|---|---|
committer | sanine <sanine.not@pm.me> | 2022-01-26 02:23:20 -0600 |
commit | 672819693ddf1d203c304697b63f44059cff09b6 (patch) | |
tree | 258319d46efa5297162bc1179b5c9c34bd3c23c7 /experimental/tectonics/geometry.h | |
parent | c5fae17327c585ec09ad01066e3f24a4e7be1fed (diff) |
refactor: move quadtree and util functions into separate headers and clean up names
Diffstat (limited to 'experimental/tectonics/geometry.h')
-rw-r--r-- | experimental/tectonics/geometry.h | 71 |
1 files changed, 71 insertions, 0 deletions
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 |