From 5c983b1907b46be33357817c082257a059ca4c41 Mon Sep 17 00:00:00 2001 From: Tavian Barnes Date: Fri, 7 May 2010 11:59:23 -0600 Subject: Don't store unbounded objects (planes, etc.) in the PR-tree. Keep them in a dmnsn_array* instead. This makes the tree better and saves us some search time. --- libdimension/prtree.h | 11 ++++++++--- 1 file changed, 8 insertions(+), 3 deletions(-) (limited to 'libdimension/prtree.h') diff --git a/libdimension/prtree.h b/libdimension/prtree.h index 999bc14..1f2dd29 100644 --- a/libdimension/prtree.h +++ b/libdimension/prtree.h @@ -21,8 +21,8 @@ /* * Priority R-Trees for storing bounding box hierarchies. PR-trees are a data * structure introduced by Arge, de Berg, Haverkort, and Yi, which provides - * asymptotically optimal worst-case lookup, while remaining efficient with real-world - * data. Their structure is derived from B-trees. + * asymptotically optimal worst-case lookup, while remaining efficient with + * real-world data. Their structure is derived from B-trees. */ #ifndef DIMENSION_IMPL_PRTREE_H @@ -33,13 +33,18 @@ /* Number of children per node */ #define DMNSN_PRTREE_B 6 -typedef struct dmnsn_prtree { +typedef struct dmnsn_prtree_node { /* Children (objects or subtrees) */ void *children[DMNSN_PRTREE_B]; bool is_leaf; /* Bounding box */ dmnsn_bounding_box bounding_box; +} dmnsn_prtree_node; + +typedef struct dmnsn_prtree { + dmnsn_prtree_node *root; + dmnsn_array *unbounded; } dmnsn_prtree; dmnsn_prtree *dmnsn_new_prtree(const dmnsn_array *objects); -- cgit v1.2.3