#ifndef GEOMETRY_H
#define GEOMETRY_H

#include <stdbool.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);

/* free a quadtree structure
 *
 * note that this will *NOT* free any point userdata!
 */
void quadtree_free(struct quadtree_node_t *root);

#endif