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