continuing..

diff --git a/quadtree.c b/quadtree.c
index 930a8f6ae5435ee00115ab9be7211ebcbf39860d..c3b28106052ecd30fc52b84a33330a2f53b39301 100644 (file)
--- a/quadtree.c
+++ b/quadtree.c
@@ -112,7 +112,7 @@ static void validate_tree(const struct quadtree *node)
 struct quadtree *quadtree_add(struct quadtree *parent, struct quadtree *new,
                              struct quadtree_ops *ops)
 {
-       int ret;
+       int ret, i;
        if (parent == new)
                trap();
 
@@ -130,6 +130,8 @@ struct quadtree *quadtree_add(struct quadtree *parent, struct quadtree *new,
 
        parent->child[ret] = new;
        new->parent = parent;
+       for (i = 0; i < 4; i++)
+               new->child[i] = 0;
 
        quadtree_recalculate_parent_stats(new, ops);
 
@@ -201,18 +203,19 @@ _quadtree_reposition_reqursively(struct quadtree *root,
        }
 }
 
-static _qt_optimal_del(struct quadtree *parent, struct quadtree *node,
+static void _qt_optimal_del(struct quadtree *parent, struct quadtree *node,
                       struct quadtree_ops *ops, int parents)
 {
        struct quadtree *child[4];
-       int i, nodes_left = 0, children = 0;
+       int i, children = 0, max_c, max_i;
 
        for (i = 0; i < 4; i++) {
-               if (!node->child[i])
+               if (!node->child[i]) {
+                       child[i] = 0;
                        continue;
+               }
 
                child[children] = node->child[i];
-               nodes_left += child[children]->children + 1;
                node->child[i] = NULL;
                children++;
        }
@@ -224,12 +227,34 @@ static _qt_optimal_del(struct quadtree *parent, struct quadtree *node,
         */
 
        if (node->children <= parents / 4) {
+               validate_tree(parent);
                quadtree_add(parent, node, ops);
                node = NULL;
+               parents /= 4;
        }
 
        while(children) {
+               max_c = -1;
+               max_i = -1;
+               for (i = 0; i < 4; i++) {
+                       if (!child[i])
+                               continue;
 
+                       if (max_c < child[i]->children) {
+                               max_c = child[i]->children;
+                               max_i = i;
+                       }
+               }
+
+               _qt_optimal_del(parent, child[max_i], ops, parents / 4);
+               child[max_i] = 0;
+               children--;
+       }
+
+       if (node) {
+               validate_tree(parent);
+               quadtree_add(parent, node, ops);
+       }
 }
 
 /*
@@ -243,7 +268,6 @@ struct quadtree *quadtree_del(struct quadtree *node,
                              struct quadtree_ops *ops)
 {
        struct quadtree *parent = 0;
-       struct quadtree *n;
        int i;
 
        /*
@@ -292,7 +316,7 @@ struct quadtree *quadtree_del(struct quadtree *node,
        quadtree_recalculate_parent_stats(node->parent, ops);
 
        if (node->children)
-               _qt_del_optimal(parent, node, ops, node->children);
+               _qt_optimal_del(parent, node, ops, node->children);
 
        node->parent = 0;