quadtree: quadtree_move(): Avoid excess rebalancing

The most obvious bug here was that the "modify" variable was
uninitialized, thus the search for crossed parents resulted always
true for the very first parent. Therefore, every time a node was
moved, the tree was rebalanced below the node.

Fixing the uninitialzed variable bug revealed other problems in the
crossed subnodes search, which was broken too. This patch modifies the
crossed subnode search a slight. It will now return true if it finds
any subnode that the movement would cross, stopping the search
instantly as soon as such node is found.

If either crossed parent or subnode is found, the node is removed and
added back to the tree in order to ensure it will be put in the
correct place.

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

diff --git a/quadtree.c b/quadtree.c
index 3f621f12c19f5e9794b6dc381c101c4a1d9ffdb6..9d5c56d6a6039c778c4aec6557c627eb2fd7b68d 100644 (file)
--- a/quadtree.c
+++ b/quadtree.c
@@ -760,11 +760,13 @@ out:
        return quadtree_find_parent(parent);
 }
 
-static void check_for_crossed_subnodes(struct quadtree *node,
+static int check_for_crossed_subnodes(struct quadtree *node,
+                               struct quadtree *skip,
                                struct vector *limit, struct quadtree_ops *ops)
 {
        int direction = 0, i;
        int up = 0, left = 0, right = 0, down = 0;
+       int cross = 0;
 
        for (i = 0; i < 2; i++) {
                if (limit[i].x < node->pos.x)
@@ -788,65 +790,114 @@ static void check_for_crossed_subnodes(struct quadtree *node,
        if ((left && right) || (up && down))
                direction |= QUADTREE_SELF;
 
-       if ((direction & QUADTREE_UPLEFT) && node->child[0])
-               check_for_crossed_subnodes(node->child[0], limit, ops);
-
-       if ((direction & QUADTREE_UPRIGHT) && node->child[1])
-               check_for_crossed_subnodes(node->child[0], limit, ops);
 
-       if ((direction & QUADTREE_DOWNLEFT) && node->child[2])
-               check_for_crossed_subnodes(node->child[0], limit, ops);
-
-       if ((direction & QUADTREE_DOWNRIGHT) && node->child[3])
-               check_for_crossed_subnodes(node->child[0], limit, ops);
+       /*
+        * We need to skip the topmost node (the one that was actually
+        * moved), otherwise we would trigger rebalance every time
+        */
+       if (node == skip)
+               goto child_check;
 
        if (direction & QUADTREE_SELF) {
                struct quadtree *parent;
 
+               if (debug)
+                       printf("Rebalanced because crossed child %p: "
+                               "node (%f %f) limits (%f %f) (%f %f)\n",
+                               node,
+                               node->pos.x, node->pos.y,
+                               limit[0].x, limit[0].y,
+                               limit[1].x, limit[1].y);
+               return 1;
                parent = quadtree_del(node, ops);
                quadtree_add(parent, node, ops);
        }
+
+child_check:
+       if ((direction & QUADTREE_UPLEFT) && node->child[0])
+               cross += check_for_crossed_subnodes(node->child[0], skip,
+                                               limit, ops);
+
+       if (cross)
+               goto out;
+
+       if ((direction & QUADTREE_UPRIGHT) && node->child[1])
+               cross += check_for_crossed_subnodes(node->child[1], skip,
+                                               limit, ops);
+
+       if (cross)
+               goto out;
+
+       if ((direction & QUADTREE_DOWNLEFT) && node->child[2])
+               cross += check_for_crossed_subnodes(node->child[2], skip,
+                                               limit, ops);
+
+       if (cross)
+               goto out;
+
+       if ((direction & QUADTREE_DOWNRIGHT) && node->child[3])
+               cross += check_for_crossed_subnodes(node->child[3], skip,
+                                               limit, ops);
+out:
+       return cross;
 }
 
 struct quadtree *quadtree_move(struct quadtree *node, struct vector new_pos,
                        struct quadtree_ops *ops)
 {
        struct quadtree *parent, *tree_parent;
-       int modify;
+       int modify = 0;
+       int parents = 0, all_parents = 0;
+
+       if (debug) {
+               parent = node->parent;
+               while (parent) {
+                       parent = parent->parent;
+                       all_parents++;
+               }
+       }
 
        /* Check if we have crossed any of the parents */
        parent = node->parent;
        while (parent) {
+               parents++;
                if (node->pos.x < parent->pos.x && new_pos.x > parent->pos.x)
-                       modify = 1;
+                       modify |= 1;
                if (node->pos.x > parent->pos.x && new_pos.x < parent->pos.x)
-                       modify = 1;
+                       modify |= 2;
                if (node->pos.y < parent->pos.y && new_pos.y > parent->pos.y)
-                       modify = 1;
+                       modify |= 4;
                if (node->pos.y > parent->pos.y && new_pos.y < parent->pos.y)
-                       modify = 1;
+                       modify |= 8;
 
                if (!modify) {
                        parent = parent->parent;
                        continue;
                }
 
+               if (debug)
+                       printf("Rebalanced because crossed parent: node %p, "
+                               "%d/%d %x "
+                               "old (%f %f) new (%f %f) parent (%f %f)\n",
+                               node, parents, all_parents, modify,
+                               node->pos.x, node->pos.y,
+                               new_pos.x, new_pos.y,
+                               parent->pos.x, parent->pos.y);
                /*
                 * If the node has crossed the boundaries, remove it
                 * from the tree and add it again to it. It is then
                 * guaranteed to be in the correct position of the
                 * tree.
                 */
+               validate_tree(node);
                tree_parent = quadtree_del(node, ops);
                node->pos = new_pos;
                quadtree_add(tree_parent, node, ops);
+               validate_tree(node);
+
                return tree_parent;
        }
 
-       /* Move the node into its new location */
-       node->pos = new_pos;
-       recalculate_parent_area_stats(node);
-
        if (node->children) {
                /*
                 * Now, search the subtree for any children that are
@@ -857,9 +908,20 @@ struct quadtree *quadtree_move(struct quadtree *node, struct vector new_pos,
 
                limit[0] = node->pos;
                limit[1] = new_pos;
-               check_for_crossed_subnodes(node, limit, ops);
+               modify = check_for_crossed_subnodes(node, node, limit, ops);
        }
 
+       /* Move the node into its new location */
+
+       validate_tree(node);
+       if (modify)
+               tree_parent = quadtree_del(node, ops);
+       node->pos = new_pos;
+       if (!modify)
+               recalculate_parent_area_stats(node);
+       if (modify)
+               quadtree_add(tree_parent, node, ops);
+       validate_tree(node);
        return quadtree_find_parent(node);
 
 }