From 87dcb56224eb827fb014cdc5129197c887cb3fcc Mon Sep 17 00:00:00 2001 From: Timo Kokkonen Date: Tue, 19 Jul 2011 21:40:33 +0300 Subject: [PATCH] quadtree: Optimize distance calculation All of the distance values needed here are only used for comparing between different distances. The actual distance itself is not used at all. Thus, the distance calculation can be optimized by leaving out all of the square root calculations and the end result is still the same. Signed-off-by: Timo Kokkonen --- quadtree.c | 10 +++++----- 1 file changed, 5 insertions(+), 5 deletions(-) diff --git a/quadtree.c b/quadtree.c index cb4add6..0e9b426 100644 --- a/quadtree.c +++ b/quadtree.c @@ -362,11 +362,11 @@ static struct quadtree *quadtree_find_nearest(struct quadtree *tree, nearest = tree; vector_sub(&nearest->pos, pos, &tmp); - distance = vector_abs(&tmp); + distance = vector_abs_squared(&tmp); if (tree != nearest) { vector_sub(&tree->pos, pos, &tmp); - dist = vector_abs(&tmp); + dist = vector_abs_squared(&tmp); if (dist < distance) { nearest = tree; distance = dist; @@ -400,7 +400,7 @@ static struct quadtree *quadtree_find_nearest(struct quadtree *tree, if (node != nearest) { vector_sub(&node->pos, pos, &tmp); - dist = vector_abs(&tmp); + dist = vector_abs_squared(&tmp); if (dist < distance || !nearest) { nearest = node; distance = dist; @@ -467,7 +467,7 @@ static struct quadtree *quadtree_find_nearest_noparent(struct quadtree *tree, continue; vector_sub(pos, &nearest->pos, &sub); - dist = vector_abs(&sub); + dist = vector_abs_squared(&sub); continue; } node = quadtree_find_nearest(tree->child[i], pos, corner, @@ -477,7 +477,7 @@ static struct quadtree *quadtree_find_nearest_noparent(struct quadtree *tree, continue; vector_sub(pos, &node->pos, &sub); - dist2 = vector_abs(&sub); + dist2 = vector_abs_squared(&sub); if (dist2 < dist) { nearest = node; -- 2.45.0