From 3b718d00d299ba1260930624387ea58b5705ab21 Mon Sep 17 00:00:00 2001 From: Timo Kokkonen Date: Fri, 24 Dec 2010 22:27:35 +0200 Subject: [PATCH] quadtree: Add quadtree_move() function This function will do necessary steps to keep the tree in correct spatial order when a node is moved. Signed-off-by: Timo Kokkonen --- quadtree.c | 102 +++++++++++++++++++++++++++++++++++++++++++++++++++++ quadtree.h | 2 ++ 2 files changed, 104 insertions(+) diff --git a/quadtree.c b/quadtree.c index 9cc6821..60ecd6d 100644 --- a/quadtree.c +++ b/quadtree.c @@ -745,6 +745,108 @@ out: return quadtree_find_parent(parent); } +static void check_for_crossed_subnodes(struct quadtree *node, + 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) + left = 1; + else + right = 1; + if (limit[i].y < node->pos.y) + up = 1; + else + down = 1; + } + + if (left || up) + direction |= QUADTREE_UPLEFT; + if (right || up) + direction |= QUADTREE_UPRIGHT; + if (left || down) + direction |= QUADTREE_DOWNLEFT; + if (right || down) + direction |= QUADTREE_DOWNRIGHT; + 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); + + if (direction & QUADTREE_SELF) { + struct quadtree *parent; + + parent = quadtree_del(node, ops); + quadtree_add(parent, node, ops); + } +} + +struct quadtree *quadtree_move(struct quadtree *node, struct vector new_pos, + struct quadtree_ops *ops) +{ + struct quadtree *parent, *tree_parent; + int modify; + + /* 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) + modify = 1; + if (node->pos.x > parent->pos.x && new_pos.x < parent->pos.x) + modify = 1; + if (node->pos.y < parent->pos.y && new_pos.y > parent->pos.y) + modify = 1; + if (node->pos.y > parent->pos.y && new_pos.y < parent->pos.y) + modify = 1; + + if (!modify) { + parent = parent->parent; + continue; + } + + /* + * 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); + return tree_parent; + } + + /* Move the node into its new location */ + node->pos = new_pos; + + if(node->children) { + /* + * Now, search the subtree for any children that are + * located in wrong place and move them into correct + * place within the tree. + */ + struct vector limit[2]; + + limit[0] = node->pos; + limit[1] = new_pos; + check_for_crossed_subnodes(node, limit, ops); + } + + return quadtree_find_parent(node); + +} static int _walk_tree(struct quadtree *head, const struct quadtree_iterator *it) { diff --git a/quadtree.h b/quadtree.h index 619a675..aef487e 100644 --- a/quadtree.h +++ b/quadtree.h @@ -46,6 +46,8 @@ struct quadtree *quadtree_add(struct quadtree *parent, struct quadtree *new, struct quadtree_ops *ops); struct quadtree *quadtree_del(struct quadtree *node, struct quadtree_ops *ops); +struct quadtree *quadtree_move(struct quadtree *node, struct vector new_pos, + struct quadtree_ops *ops); int walk_quadtree(const struct quadtree_iterator *iterator); -- 2.45.0