quadtree: tree validator: Add spatial validation

This will catch errors when the tree is not in spatial order.

Signed-off-by: Timo Kokkonen <kaapeli@itanic.dy.fi>

diff --git a/quadtree.c b/quadtree.c
index 79039c64833c221480b49c6c1050ebe8d9d3593b..b392e639b84f8c8f045f4136ebee2a16d2fcd3a8 100644 (file)
--- a/quadtree.c
+++ b/quadtree.c
@@ -45,7 +45,7 @@ static int quadtree_compare(const struct quadtree *a, const struct quadtree *b)
 
 static void validate_subtree(const struct quadtree *node)
 {
-       int i;
+       int i, dir;
        long int children;
        children = 0;
 
@@ -78,6 +78,21 @@ static void validate_subtree(const struct quadtree *node)
                        }
                }
 
+               dir = quadtree_compare(node, node->child[i]);
+
+               if (dir != i) {
+                       printf("%s:%d Fatal! Spatial inconsistency detected "
+                               "at child %d in node %p\n"
+                               "parent: (%f %f), child (%f %f), "
+                               "dir %d != %d\n",
+                               __func__, __LINE__, i, node,
+                               node->pos.x, node->pos.y,
+                               node->child[i]->pos.x, node->child[i]->pos.y,
+                               dir, i);
+                       fflush(stdout);
+                       trap();
+               }
+
                children += node->child[i]->children + 1;
 
                validate_subtree(node->child[i]);