summaryrefslogtreecommitdiffstats
path: root/libdimension/prtree.h
diff options
context:
space:
mode:
authorTavian Barnes <tavianator@gmail.com>2010-05-07 11:59:23 -0600
committerTavian Barnes <tavianator@gmail.com>2010-05-07 13:03:06 -0600
commit5c983b1907b46be33357817c082257a059ca4c41 (patch)
tree29c0703b3a20c39e1aa20d436e6aa45248db025e /libdimension/prtree.h
parent9adb64786e6aa8f5f0fca39a67e96c495058fd1e (diff)
downloaddimension-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.h11
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);