From db01e6c302682eff257c674eb2392e71b9f705cf Mon Sep 17 00:00:00 2001 From: Timo Kokkonen Date: Fri, 8 Jul 2011 12:51:36 +0300 Subject: [PATCH] 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 --- quadtree.c | 19 +++++++++++++++++++ quadtree.h | 6 ++++++ 2 files changed, 25 insertions(+) diff --git a/quadtree.c b/quadtree.c index 1417c54..5edee75 100644 --- 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 f69f34d..6959bea 100644 --- 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 { -- 2.44.0