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>

diff --git a/quadtree.c b/quadtree.c
index 0515dc6ed5ebcd7edf4d560c799e2743869e6e60..81552f6e89312a40ec0073df386c53539e11b189 100644 (file)
--- 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) {