+ corner[0].y = quadtree_get_max_dimension(node, 2);
+ corner[0].x = quadtree_get_max_dimension(node, 1);
+ corner[1].y = quadtree_get_max_dimension(node, 0);
+ corner[1].x = quadtree_get_max_dimension(node, 3);
+
+ if (debug) {
+ printf("\nInitial Search rectangle (%f %f) (%f %f), (%f %f)\n",
+ corner[0].x, corner[0].y,
+ corner[1].x, corner[1].y,
+ node->pos.x, node->pos.y);
+ fflush(stdout);
+ }
+
+ if ((corner[0].x < corner[1].x) ||
+ (corner[0].y < corner[1].y))
+ trap();
+}
+
+static int is_within(struct vector *pos, struct vector *corner)
+{
+ if ((pos->x >= corner[1].x) && (pos->x <= corner[0].x) &&
+ (pos->y >= corner[1].y) && (pos->y <= corner[0].y))
+ return 1;
+ return 0;
+}
+
+static int quadrants_to_search(struct quadtree *node, struct vector *corner)
+{
+ int direction = 0, i;
+ int up = 0, left = 0, right = 0, down = 0;
+
+ for (i = 0; i < 2; i++) {
+ if (corner[i].x <= node->pos.x)
+ left = 1;
+ else if (corner[i].x >= node->pos.x)
+ right = 1;
+ if (corner[i].y <= node->pos.y)
+ up = 1;
+ else if (corner[i].y >= node->pos.y)
+ down = 1;
+ }
+
+ if (left || up)
+ direction |= QUADTREE_UPLEFT;
+ if (right || up)
+ direction |= QUADTREE_UPRIGHT;
+ if (left || down)
+ direction |= QUADTREE_DOWNLEFT;
+ if (right || down)
+ direction |= QUADTREE_DOWNRIGHT;
+
+ return direction;
+}
+
+static struct quadtree *quadtree_find_nearest(struct quadtree *tree,
+ struct vector *pos,
+ struct vector *corner)
+{
+ struct vector tmp;
+ struct quadtree *nearest, *node;
+ double distance, dist;
+ int ret, i, directions;
+
+ if (!is_within(pos, corner)) {
+ if (debug) {
+ printf("No nearest to be found from (%f %f) (%f %f) "
+ "pos (%f %f)\n",
+ corner[0].x, corner[0].y,
+ corner[1].x, corner[1].y,
+ pos->x, pos->y);
+ fflush(stdout);
+ }
+ return NULL;
+ }
+
+ if (is_within(&tree->pos, corner)) {
+ vector_sub(pos, &tree->pos, &tmp);
+ distance = vector_abs(&tmp);
+ nearest = tree;
+ } else {
+ nearest = NULL;
+ }
+
+ directions = quadrants_to_search(tree, corner);