From: Timo Kokkonen <kaapeli@itanic.dy.fi>
Date: Tue, 19 Jul 2011 16:32:37 +0000 (+0300)
Subject: quadtre: Fix nearest neighborhood search
X-Git-Url: http://git.itanic.dy.fi/?p=sdl-planets;a=commitdiff_plain;h=a36c6583ae1f860989959e2dd606fb90504e7beb

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 5412b80..72973c8 100644
--- 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 "