From 672819693ddf1d203c304697b63f44059cff09b6 Mon Sep 17 00:00:00 2001
From: sanine <sanine.not@pm.me>
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/geometry.h | 71 +++++++++++++++++++++++++++++++++++++++
 1 file changed, 71 insertions(+)
 create mode 100644 experimental/tectonics/geometry.h

(limited to 'experimental/tectonics/geometry.h')

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
-- 
cgit v1.2.1