From 9b04b4e2a1147ed2a30e4f86dd403851036b3b51 Mon Sep 17 00:00:00 2001 From: Tavian Barnes Date: Tue, 27 Apr 2010 21:25:50 -0600 Subject: Replace BVSTs with priority R-trees. --- libdimension/prtree.h | 51 +++++++++++++++++++++++++++++++++++++++++++++++++++ 1 file changed, 51 insertions(+) create mode 100644 libdimension/prtree.h (limited to 'libdimension/prtree.h') 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 * + * * + * 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 * + * . * + *************************************************************************/ + +/* + * 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 + +/* 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 */ -- cgit v1.2.3