diff options
author | Tavian Barnes <tavianator@gmail.com> | 2010-05-07 11:59:23 -0600 |
---|---|---|
committer | Tavian Barnes <tavianator@gmail.com> | 2010-05-07 13:03:06 -0600 |
commit | 5c983b1907b46be33357817c082257a059ca4c41 (patch) | |
tree | 29c0703b3a20c39e1aa20d436e6aa45248db025e /libdimension/prtree.h | |
parent | 9adb64786e6aa8f5f0fca39a67e96c495058fd1e (diff) | |
download | dimension-5c983b1907b46be33357817c082257a059ca4c41.tar.xz |
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.
Diffstat (limited to 'libdimension/prtree.h')
-rw-r--r-- | libdimension/prtree.h | 11 |
1 files changed, 8 insertions, 3 deletions
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); |