quadtre: Fix nearest neighborhood search

The search was missing a check whether the current node is the
nearest. Obviously without this check we never found anything else
except the initial node as the nearest node.

Signed-off-by: Timo Kokkonen <kaapeli@itanic.dy.fi>

diff --git a/quadtree.c b/quadtree.c
index 5412b8031cf2fe3007aa8a350105473931a5ca50..72973c8bba7ae35049f087057790db577719edb6 100644 (file)
--- a/quadtree.c
+++ b/quadtree.c
@@ -353,6 +353,15 @@ static struct quadtree *quadtree_find_nearest(struct quadtree *tree,
        vector_sub(&nearest->pos, pos, &tmp);
        distance = vector_abs(&tmp);
 
+       if (tree != nearest) {
+               vector_sub(&tree->pos, pos, &tmp);
+               dist = vector_abs(&tmp);
+               if (dist < distance) {
+                       nearest = tree;
+                       distance = dist;
+               }
+       }
+
        if (!is_within(&nearest->pos, corner)) {
                if (debug)
                        printf("Discarding nearest %p "