Revert "Revert "Try to optimze""

This reverts commit 1ae3efb2dde3e86ab4cfcbaea15222ab65389787.

diff --git a/quadtree.c b/quadtree.c
index a914f66324a8e0a6ba09d5ccfc50bd6d0c3c1128..63f56970ef927c06540f1833f52e84229185bd2b 100644 (file)
--- a/quadtree.c
+++ b/quadtree.c
@@ -148,22 +148,39 @@ _quadtree_reposition_reqursively(struct quadtree *root,
                                 struct quadtree *node,
                                 struct quadtree_ops *ops)
 {
-       int i;
+       int i, max_child, max_child_idx;
 
        validate_tree(root);
 
        /* 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], ops);
-               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],
+                                                ops);
+               node->child[max_child_idx] = 0;
        }
 
        /* There are no children left, reset stats */