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>
return quadtree_find_parent(parent);
}
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;
struct vector *limit, struct quadtree_ops *ops)
{
int direction = 0, i;
int up = 0, left = 0, right = 0, down = 0;
for (i = 0; i < 2; i++) {
if (limit[i].x < node->pos.x)
for (i = 0; i < 2; i++) {
if (limit[i].x < node->pos.x)
if ((left && right) || (up && down))
direction |= QUADTREE_SELF;
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 (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);
}
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;
}
struct quadtree *quadtree_move(struct quadtree *node, struct vector new_pos,
struct quadtree_ops *ops)
{
struct quadtree *parent, *tree_parent;
+ 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) {
/* Check if we have crossed any of the parents */
parent = node->parent;
while (parent) {
if (node->pos.x < parent->pos.x && new_pos.x > parent->pos.x)
if (node->pos.x < parent->pos.x && new_pos.x > parent->pos.x)
if (node->pos.x > parent->pos.x && new_pos.x < parent->pos.x)
if (node->pos.x > parent->pos.x && new_pos.x < parent->pos.x)
if (node->pos.y < parent->pos.y && new_pos.y > parent->pos.y)
if (node->pos.y < parent->pos.y && new_pos.y > parent->pos.y)
if (node->pos.y > parent->pos.y && new_pos.y < parent->pos.y)
if (node->pos.y > parent->pos.y && new_pos.y < parent->pos.y)
if (!modify) {
parent = parent->parent;
continue;
}
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.
*/
/*
* 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.
*/
tree_parent = quadtree_del(node, ops);
node->pos = new_pos;
quadtree_add(tree_parent, node, ops);
tree_parent = quadtree_del(node, ops);
node->pos = new_pos;
quadtree_add(tree_parent, node, ops);
- /* 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
if (node->children) {
/*
* Now, search the subtree for any children that are
limit[0] = node->pos;
limit[1] = 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);
}
return quadtree_find_parent(node);
}