Try to optimze

diff --git a/quadtree.c b/quadtree.c
index f188d8069ee38a5426403304c97e5e485eb9186a..0be4dca25fe8fa8238196357d41cc33437eebd72 100644 (file)
--- a/quadtree.c
+++ b/quadtree.c
@@ -151,22 +151,39 @@ _quadtree_reposition_reqursively(struct quadtree *root,
                                 int (*compare)(struct quadtree *a,
                                                struct quadtree *b))
 {
-       int i;
+       int i, max_child, max_child_idx;
 
        validate_tree(node);
 
        /* First remove all children, if any */
+       while (1) {
 
-       for (i = 0; i < 4; i++) {
-               if (!node->child[i])
-                       continue;
+               /*
+                * Attempt to move from the middle of the most dense
+                * branch. That might increase the chances of creating
+                * a tree with better balance.
+                */
 
-               if (node->child[i] == node ||
-                   node->child[i] == node->parent)
-                       trap();
+               max_child = -1;
+               max_child_idx = -1;
+               for (i = 0; i < 4; i++) {
+                       if (!node->child[i])
+                               continue;
 
-               _quadtree_reposition_reqursively(root, node->child[i], compare);
-               node->child[i] = 0;
+                       if (node->child[i]->children > max_child) {
+                               max_child = node->child[i]->children;
+                               max_child_idx = i;
+                       }
+
+               }
+
+               if (max_child < 0)
+                       break;
+
+               _quadtree_reposition_reqursively(root,
+                                                node->child[max_child_idx],
+                                                compare);
+               node->child[max_child_idx] = 0;
        }
 
        /* There are no children left, reset stats */