quadtree: Add subtree area into tree statistics

Two corner coordinates are stored into each quadtree nodes. These
corner coordinates indicate the area where all the subnodes of the
tree are located in.

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

diff --git a/quadtree.c b/quadtree.c
index 1417c54ca132583eb20e392809147a9089e7cf15..5edee753abaff4a33b93f6fed86da149944169e9 100644 (file)
--- a/quadtree.c
+++ b/quadtree.c
@@ -211,6 +211,25 @@ static void quadtree_recalculate_parent_stats(struct quadtree *node,
                        node->children += node->child[i]->children + 1;
                }
 
+               /* The space covered by the parent node's corner
+                * points needs be as wide as its widest child node's
+                * corners.
+                */
+#define CHILD_CORNER_SAFE(node, ch_idx, cor_idx, axis)              \
+               (node)->child[ch_idx] ?                              \
+                       (node)->child[ch_idx]->corner[cor_idx].axis : \
+                       (node)->pos.axis
+
+               node->corner[0].x = MIN(CHILD_CORNER_SAFE(node, 0, 0, x),
+                                       CHILD_CORNER_SAFE(node, 2, 0, x));
+               node->corner[0].y = MIN(CHILD_CORNER_SAFE(node, 0, 0, y),
+                                       CHILD_CORNER_SAFE(node, 1, 0, y));
+               node->corner[1].x = MAX(CHILD_CORNER_SAFE(node, 1, 1, x),
+                                       CHILD_CORNER_SAFE(node, 3, 1, x));
+               node->corner[1].y = MAX(CHILD_CORNER_SAFE(node, 2, 1, y),
+                                       CHILD_CORNER_SAFE(node, 3, 1, y));
+#undef CHILD_CORNER_SAFE
+
                if (ops->recalculate_stats)
                        ops->recalculate_stats(node);
 

diff --git a/quadtree.h b/quadtree.h
index f69f34d0784198d169d6de735cb266a09d4eda03..6959beaa4af18f6190f689e10306e1d8636b52aa 100644 (file)
--- a/quadtree.h
+++ b/quadtree.h
@@ -22,6 +22,12 @@ struct quadtree {
        /* statistics */
        long int children;      /* The total number of children */
        long int depth;         /* The deepest subtree branch */
+
+       /*
+        * Corner points that indicate the space that is covered by
+        * the tree. Upper left and lower right points are stored.
+        */
+       struct vector corner[2];
 };
 
 struct quadtree_ops {