From 27e32d7e608064e7131938b11777c472ca420144 Mon Sep 17 00:00:00 2001
From: Timo Kokkonen <kaapeli@itanic.dy.fi>
Date: Sat, 9 Jul 2011 12:07:34 +0300
Subject: [PATCH] quadtree: Use tree corners from the tree itself

Now that we have the tree corner points stored in the each three node
itself, we can use those corner points when rebalancing the tree. This
allows also removing great deal of clumsy and hard to understand code.

Signed-off-by: Timo Kokkonen <kaapeli@itanic.dy.fi>
---
 quadtree.c | 104 ++---------------------------------------------------
 1 file changed, 2 insertions(+), 102 deletions(-)

diff --git a/quadtree.c b/quadtree.c
index 0515dc6..81552f6 100644
--- a/quadtree.c
+++ b/quadtree.c
@@ -271,107 +271,6 @@ struct quadtree *quadtree_add(struct quadtree *parent, struct quadtree *new,
 	return new;
 }
 
-static double max_by_dir(double a, double b, int direction)
-{
-	switch (direction) {
-	case 0: /* up */
-	case 3: /* left */
-		return MIN(a, b);
-	case 1: /* right */
-	case 2: /* down */
-		return MAX(a, b);
-	}
-
-	trap();
-	return 0;
-}
-
-static double maxv_by_dir(struct quadtree *a, int direction)
-{
-	switch (direction) {
-	case 0: /* up */
-	case 2: /* down */
-		return a->pos.y;
-	case 1: /* right */
-	case 3: /* left */
-		return a->pos.x;
-	}
-
-	trap();
-	return 0;
-}
-
-static double quadtree_get_max_dimension(struct quadtree *node, int direction)
-{
-	struct quadtree *ch1 = NULL, *ch2 = NULL;
-	double a, b;
-
-	switch (direction) {
-	case 0: /* up */
-		ch1 = node->child[0];
-		ch2 = node->child[1];
-		break;
-	case 1: /* right */
-		ch1 = node->child[1];
-		ch2 = node->child[3];
-		break;
-	case 2: /* down */
-		ch1 = node->child[2];
-		ch2 = node->child[3];
-		break;
-	case 3: /* left */
-		ch1 = node->child[0];
-		ch2 = node->child[2];
-		break;
-	default:
-		trap();
-	}
-
-	if (ch1 && ch2) {
-		a = quadtree_get_max_dimension(ch1, direction);
-		b = quadtree_get_max_dimension(ch2, direction);
-		return max_by_dir(a, b, direction);
-	}
-
-	if (ch1) {
-		a = quadtree_get_max_dimension(ch1, direction);
-		b = maxv_by_dir(ch1, direction);
-		return max_by_dir(a, b, direction);
-	}
-	if (ch2) {
-		a = quadtree_get_max_dimension(ch2, direction);
-		b = maxv_by_dir(ch2, direction);
-		return max_by_dir(a, b, direction);
-	}
-
-	return maxv_by_dir(node, direction);
-}
-
-/*
- * Stores the lower right and upper left corner coordinates to the
- * corner vectors
- */
-static void quadtree_get_tree_dimensions(struct quadtree *node,
-					struct vector *corner)
-{
-	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) &&
@@ -767,7 +666,8 @@ struct quadtree *quadtree_del(struct quadtree *node,
 	 * the parent.
 	 */
 
-	quadtree_get_tree_dimensions(node, corner);
+	corner[0] = node->corner[1];
+	corner[1] = node->corner[0];
 	moved = optimally_move_tree(node, parent, corner, ops);
 
 	if (debug) {
-- 
2.45.0