From a36c6583ae1f860989959e2dd606fb90504e7beb Mon Sep 17 00:00:00 2001 From: Timo Kokkonen Date: Tue, 19 Jul 2011 19:32:37 +0300 Subject: [PATCH] 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 --- quadtree.c | 9 +++++++++ 1 file changed, 9 insertions(+) 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 " -- 2.45.0