From 5e47071bca89d7cd776ba628f56133f74856fd69 Mon Sep 17 00:00:00 2001 From: Timo Kokkonen Date: Wed, 20 Jul 2011 16:02:01 +0300 Subject: [PATCH] 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 --- quadtree.c | 104 ++++++++++++++++++++++++++++++++++++++++++----------- 1 file changed, 83 insertions(+), 21 deletions(-) diff --git a/quadtree.c b/quadtree.c index 3f621f1..9d5c56d 100644 --- 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); } -- 2.44.0