From f325cc73cdefd980ac221dc39a46e67ff5292e89 Mon Sep 17 00:00:00 2001 From: Timo Kokkonen Date: Tue, 7 Dec 2010 22:06:17 +0200 Subject: [PATCH] quadtree: tree validator: Add spatial validation This will catch errors when the tree is not in spatial order. Signed-off-by: Timo Kokkonen --- quadtree.c | 17 ++++++++++++++++- 1 file changed, 16 insertions(+), 1 deletion(-) diff --git a/quadtree.c b/quadtree.c index 79039c6..b392e63 100644 --- 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]); -- 2.45.0