diff options
author | Tavian Barnes <tavianator@gmail.com> | 2010-04-27 21:25:50 -0600 |
---|---|---|
committer | Tavian Barnes <tavianator@gmail.com> | 2010-05-05 22:33:24 -0600 |
commit | 9b04b4e2a1147ed2a30e4f86dd403851036b3b51 (patch) | |
tree | ee0b612746e2a4acaeadf40bbac76fdad939cf6b /libdimension/prtree.h | |
parent | 72a0b0d511822d7521e2d44f6e468f3d1870521e (diff) | |
download | dimension-9b04b4e2a1147ed2a30e4f86dd403851036b3b51.tar.xz |
Replace BVSTs with priority R-trees.
Diffstat (limited to 'libdimension/prtree.h')
-rw-r--r-- | libdimension/prtree.h | 51 |
1 files changed, 51 insertions, 0 deletions
diff --git a/libdimension/prtree.h b/libdimension/prtree.h new file mode 100644 index 0000000..999bc14 --- /dev/null +++ b/libdimension/prtree.h @@ -0,0 +1,51 @@ +/************************************************************************* + * Copyright (C) 2010 Tavian Barnes <tavianator@gmail.com> * + * * + * This file is part of The Dimension Library. * + * * + * The Dimension Library is free software; you can redistribute it and/ * + * or modify it under the terms of the GNU Lesser General Public License * + * as published by the Free Software Foundation; either version 3 of the * + * License, or (at your option) any later version. * + * * + * The Dimension Library is distributed in the hope that it will be * + * useful, but WITHOUT ANY WARRANTY; without even the implied warranty * + * of MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU * + * Lesser General Public License for more details. * + * * + * You should have received a copy of the GNU Lesser General Public * + * License along with this program. If not, see * + * <http://www.gnu.org/licenses/>. * + *************************************************************************/ + +/* + * 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. + */ + +#ifndef DIMENSION_IMPL_PRTREE_H +#define DIMENSION_IMPL_PRTREE_H + +#include <stdbool.h> + +/* Number of children per node */ +#define DMNSN_PRTREE_B 6 + +typedef struct dmnsn_prtree { + /* Children (objects or subtrees) */ + void *children[DMNSN_PRTREE_B]; + bool is_leaf; + + /* Bounding box */ + dmnsn_bounding_box bounding_box; +} dmnsn_prtree; + +dmnsn_prtree *dmnsn_new_prtree(const dmnsn_array *objects); +void dmnsn_delete_prtree(dmnsn_prtree *tree); + +bool dmnsn_prtree_search(const dmnsn_prtree *tree, dmnsn_line ray, + dmnsn_intersection *intersection); + +#endif /* DIMENSION_IMPL_PRTREE_H */ |