quadtree.c: Fix a lot of bugs

Signed-off-by: Timo Kokkonen <kaapeli@itanic.dy.fi>

diff --git a/quadtree.c b/quadtree.c
index 52a07355f329cab17e0a7d9844ca43a6af7fd839..f7513462cf77f4823550bf2cc93e7e467e4c8966 100644 (file)
--- a/quadtree.c
+++ b/quadtree.c
@@ -181,11 +181,11 @@ static double max_by_dir(double a, double b, int direction)
 {
        switch (direction) {
        case 0: /* up */
-       case 1: /* right */
-               return MAX(a, b);
-       case 2: /* down */
        case 3: /* left */
                return MIN(a, b);
+       case 1: /* right */
+       case 2: /* down */
+               return MAX(a, b);
        }
 
        trap();
@@ -217,7 +217,7 @@ static double quadtree_get_max_dimension(struct quadtree *node, int direction)
                ch1 = node->child[0];
                ch2 = node->child[1];
                break;
-       case 1: /* left */
+       case 1: /* right */
                ch1 = node->child[1];
                ch2 = node->child[3];
                break;
@@ -225,7 +225,7 @@ static double quadtree_get_max_dimension(struct quadtree *node, int direction)
                ch1 = node->child[2];
                ch2 = node->child[3];
                break;
-       case 3: /* right */
+       case 3: /* left */
                ch1 = node->child[0];
                ch2 = node->child[2];
                break;
@@ -240,9 +240,9 @@ static double quadtree_get_max_dimension(struct quadtree *node, int direction)
        }
 
        if (ch1)
-               return maxv_by_dir(ch1, direction);
+               return quadtree_get_max_dimension(ch1, direction);
        if (ch2)
-               return maxv_by_dir(ch2, direction);
+               return quadtree_get_max_dimension(ch2, direction);
 
        return maxv_by_dir(node, direction);
 }
@@ -254,16 +254,16 @@ static double quadtree_get_max_dimension(struct quadtree *node, int direction)
 static void quadtree_get_tree_dimensions(struct quadtree *node,
                                        struct vector *corner)
 {
-       corner[0].y = quadtree_get_max_dimension(node, 0);
+       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, 2);
+       corner[1].y = quadtree_get_max_dimension(node, 0);
        corner[1].x = quadtree_get_max_dimension(node, 3);
 }
 
 static int is_within(struct vector *pos, struct vector *corner)
 {
-       if (pos->x > corner[1].x && pos->x < corner[0].x &&
-           pos->y > corner[1].y && pos->y < corner[0].y)
+       if ((pos->x >= corner[1].x) && (pos->x <= corner[0].x) &&
+           (pos->y >= corner[1].y) && (pos->y <= corner[0].y))
                return 1;
        return 0;
 }
@@ -300,18 +300,18 @@ static void quadtree_split_by_node(struct quadtree *node,
 {
        switch (dir) {
        case QUADTREE_UPLEFT:
-               corner[0].x = node->pos.x;
-               corner[1].y = node->pos.y;
+               corner[0] = node->pos;
                break;
        case QUADTREE_UPRIGHT:
-               corner[1] = node->pos;
+               corner[0].x = node->pos.x;
+               corner[1].y = node->pos.y;
                break;
        case QUADTREE_DOWNRIGHT:
-               corner[0].y = node->pos.y;
-               corner[1].x = node->pos.x;
+               corner[1] = node->pos;
                break;
        case QUADTREE_DOWNLEFT:
-               corner[0] = node->pos;
+               corner[0].x = node->pos.x;
+               corner[1].y = node->pos.y;
                break;
        default:
                trap();
@@ -328,12 +328,13 @@ static int _quadtree_del(struct quadtree *node, struct quadtree *parent)
        int i;
 
        /* Detach from the tree */
-       for (i = 0; i < 4; i++) {
-               if (node->parent->child[i] == node) {
-                       node->parent->child[i] = 0;
-                       break;
+       if (node->parent)
+               for (i = 0; i < 4; i++) {
+                       if (node->parent->child[i] == node) {
+                               node->parent->child[i] = 0;
+                               break;
+                       }
                }
-       }
 
        if (i == 4)
                trap();
@@ -410,6 +411,9 @@ static void optimally_move_tree(struct quadtree *tree, struct quadtree *parent,
                                        dist = dist2;
                                }
                        }
+
+                       if (t == NULL)
+                               return;
                }
        }
 
@@ -418,9 +422,18 @@ static void optimally_move_tree(struct quadtree *tree, struct quadtree *parent,
         * spatial middle coordinates of the tree.
         */
 
+       if (debug) {
+               printf("Relocating node %p under parent %p\n", t, parent);
+               printf("There are %d child nodes left\n", tree->children);
+               fflush(stdout);
+       }
        _quadtree_del(t, tree);
        quadtree_add(parent, t, ops);
 
+       tree->children--;
+       if (!tree->children)
+               return;
+
        /*
         * Now split the search rectangle in quadtres and do the same
         * with all of the quarters.
@@ -470,21 +483,25 @@ struct quadtree *quadtree_del(struct quadtree *node,
                fflush(stdout);
        }
 
-       /* Get the outer limits of the area belongin to the node */
-       quadtree_get_tree_dimensions(node, corner);
-
-       /*
-        * We are deleting the root node. This means we have to select
-        * a new root node and reconstruct the entire tree under it
-        * again.
-        */
        if (!node->parent) {
+               /*
+                * We are deleting the root node. This means we have
+                * to select a new root node and reconstruct the
+                * entire tree under it again.
+                */
+               if (debug) {
+                       printf("Deleting root node\n");
+                       fflush(stdout);
+               }
                for (i = 0; i < 4; i++) {
                        if (!node->child[i])
                                continue;
 
                        parent = node->child[i];
+                       _quadtree_del(parent, node);
                        parent->parent = 0;
+                       quadtree_recalculate_parent_stats(parent, ops);
+                       break;
                }
        } else {
                /*
@@ -509,10 +526,12 @@ struct quadtree *quadtree_del(struct quadtree *node,
                 * tree. Fix the stats.
                 */
                quadtree_recalculate_parent_stats(node->parent, ops);
-
-               parent = quadtree_find_parent(parent);
        }
 
+       validate_tree(parent);
+
+       if (!node->children)
+               goto out;
        /*
         * Now we are ready to prepare for relocating the nodes under
         * the parent.
@@ -521,6 +540,13 @@ struct quadtree *quadtree_del(struct quadtree *node,
        quadtree_get_tree_dimensions(node, corner);
        optimally_move_tree(node, parent, corner, ops);
 
+       if (debug) {
+               printf("Delete done, returning parent %p\n", parent);
+               fflush(stdout);
+       }
+
+out:
+       parent = quadtree_find_parent(parent);
        validate_tree(parent);
        return parent;
 }