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 <kaapeli@itanic.dy.fi>

diff --git a/quadtree.c b/quadtree.c
index 9cc6821ed561acf9997d34e6b3cc994c1dbca675..60ecd6db737a7640d17811f74799d97ed6f1a7af 100644 (file)
--- 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 619a67574fc045f69ed3f7ea959f42d2e1046e7a..aef487efa0be242942babbfbb8c554eda95108cb 100644 (file)
--- 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);