dungeon_crawler

annotate prototype/kdtree/kdtree.h @ 50:c40efa9cf844

find changesets by author, revision, files, or words in the commit message
torches sound
author John Tsiombikas <nuclear@member.fsf.org>
date Tue, 18 Sep 2012 04:45:46 +0300
parents
children
rev   line source
nuclear@48 1 /*
nuclear@48 2 This file is part of ``kdtree'', a library for working with kd-trees.
nuclear@48 3 Copyright (C) 2007-2011 John Tsiombikas <nuclear@member.fsf.org>
nuclear@48 4
nuclear@48 5 Redistribution and use in source and binary forms, with or without
nuclear@48 6 modification, are permitted provided that the following conditions are met:
nuclear@48 7
nuclear@48 8 1. Redistributions of source code must retain the above copyright notice, this
nuclear@48 9 list of conditions and the following disclaimer.
nuclear@48 10 2. Redistributions in binary form must reproduce the above copyright notice,
nuclear@48 11 this list of conditions and the following disclaimer in the documentation
nuclear@48 12 and/or other materials provided with the distribution.
nuclear@48 13 3. The name of the author may not be used to endorse or promote products
nuclear@48 14 derived from this software without specific prior written permission.
nuclear@48 15
nuclear@48 16 THIS SOFTWARE IS PROVIDED BY THE AUTHOR ``AS IS'' AND ANY EXPRESS OR IMPLIED
nuclear@48 17 WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE IMPLIED WARRANTIES OF
nuclear@48 18 MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO
nuclear@48 19 EVENT SHALL THE AUTHOR BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL,
nuclear@48 20 EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT
nuclear@48 21 OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS
nuclear@48 22 INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN
nuclear@48 23 CONTRACT, STRICT LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING
nuclear@48 24 IN ANY WAY OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY
nuclear@48 25 OF SUCH DAMAGE.
nuclear@48 26 */
nuclear@48 27 #ifndef _KDTREE_H_
nuclear@48 28 #define _KDTREE_H_
nuclear@48 29
nuclear@48 30 #ifdef __cplusplus
nuclear@48 31 extern "C" {
nuclear@48 32 #endif
nuclear@48 33
nuclear@48 34 struct kdtree;
nuclear@48 35 struct kdres;
nuclear@48 36
nuclear@48 37
nuclear@48 38 /* create a kd-tree for "k"-dimensional data */
nuclear@48 39 struct kdtree *kd_create(int k);
nuclear@48 40
nuclear@48 41 /* free the struct kdtree */
nuclear@48 42 void kd_free(struct kdtree *tree);
nuclear@48 43
nuclear@48 44 /* remove all the elements from the tree */
nuclear@48 45 void kd_clear(struct kdtree *tree);
nuclear@48 46
nuclear@48 47 /* if called with non-null 2nd argument, the function provided
nuclear@48 48 * will be called on data pointers (see kd_insert) when nodes
nuclear@48 49 * are to be removed from the tree.
nuclear@48 50 */
nuclear@48 51 void kd_data_destructor(struct kdtree *tree, void (*destr)(void*));
nuclear@48 52
nuclear@48 53 /* insert a node, specifying its position, and optional data */
nuclear@48 54 int kd_insert(struct kdtree *tree, const double *pos, void *data);
nuclear@48 55 int kd_insertf(struct kdtree *tree, const float *pos, void *data);
nuclear@48 56 int kd_insert3(struct kdtree *tree, double x, double y, double z, void *data);
nuclear@48 57 int kd_insert3f(struct kdtree *tree, float x, float y, float z, void *data);
nuclear@48 58
nuclear@48 59 /* Find the nearest node from a given point.
nuclear@48 60 *
nuclear@48 61 * This function returns a pointer to a result set with at most one element.
nuclear@48 62 */
nuclear@48 63 struct kdres *kd_nearest(struct kdtree *tree, const double *pos);
nuclear@48 64 struct kdres *kd_nearestf(struct kdtree *tree, const float *pos);
nuclear@48 65 struct kdres *kd_nearest3(struct kdtree *tree, double x, double y, double z);
nuclear@48 66 struct kdres *kd_nearest3f(struct kdtree *tree, float x, float y, float z);
nuclear@48 67
nuclear@48 68 /* Find the N nearest nodes from a given point.
nuclear@48 69 *
nuclear@48 70 * This function returns a pointer to a result set, with at most N elements,
nuclear@48 71 * which can be manipulated with the kd_res_* functions.
nuclear@48 72 * The returned pointer can be null as an indication of an error. Otherwise
nuclear@48 73 * a valid result set is always returned which may contain 0 or more elements.
nuclear@48 74 * The result set must be deallocated with kd_res_free after use.
nuclear@48 75 */
nuclear@48 76 /*
nuclear@48 77 struct kdres *kd_nearest_n(struct kdtree *tree, const double *pos, int num);
nuclear@48 78 struct kdres *kd_nearest_nf(struct kdtree *tree, const float *pos, int num);
nuclear@48 79 struct kdres *kd_nearest_n3(struct kdtree *tree, double x, double y, double z);
nuclear@48 80 struct kdres *kd_nearest_n3f(struct kdtree *tree, float x, float y, float z);
nuclear@48 81 */
nuclear@48 82
nuclear@48 83 /* Find any nearest nodes from a given point within a range.
nuclear@48 84 *
nuclear@48 85 * This function returns a pointer to a result set, which can be manipulated
nuclear@48 86 * by the kd_res_* functions.
nuclear@48 87 * The returned pointer can be null as an indication of an error. Otherwise
nuclear@48 88 * a valid result set is always returned which may contain 0 or more elements.
nuclear@48 89 * The result set must be deallocated with kd_res_free after use.
nuclear@48 90 */
nuclear@48 91 struct kdres *kd_nearest_range(struct kdtree *tree, const double *pos, double range);
nuclear@48 92 struct kdres *kd_nearest_rangef(struct kdtree *tree, const float *pos, float range);
nuclear@48 93 struct kdres *kd_nearest_range3(struct kdtree *tree, double x, double y, double z, double range);
nuclear@48 94 struct kdres *kd_nearest_range3f(struct kdtree *tree, float x, float y, float z, float range);
nuclear@48 95
nuclear@48 96 /* frees a result set returned by kd_nearest_range() */
nuclear@48 97 void kd_res_free(struct kdres *set);
nuclear@48 98
nuclear@48 99 /* returns the size of the result set (in elements) */
nuclear@48 100 int kd_res_size(struct kdres *set);
nuclear@48 101
nuclear@48 102 /* rewinds the result set iterator */
nuclear@48 103 void kd_res_rewind(struct kdres *set);
nuclear@48 104
nuclear@48 105 /* returns non-zero if the set iterator reached the end after the last element */
nuclear@48 106 int kd_res_end(struct kdres *set);
nuclear@48 107
nuclear@48 108 /* advances the result set iterator, returns non-zero on success, zero if
nuclear@48 109 * there are no more elements in the result set.
nuclear@48 110 */
nuclear@48 111 int kd_res_next(struct kdres *set);
nuclear@48 112
nuclear@48 113 /* returns the data pointer (can be null) of the current result set item
nuclear@48 114 * and optionally sets its position to the pointers(s) if not null.
nuclear@48 115 */
nuclear@48 116 void *kd_res_item(struct kdres *set, double *pos);
nuclear@48 117 void *kd_res_itemf(struct kdres *set, float *pos);
nuclear@48 118 void *kd_res_item3(struct kdres *set, double *x, double *y, double *z);
nuclear@48 119 void *kd_res_item3f(struct kdres *set, float *x, float *y, float *z);
nuclear@48 120
nuclear@48 121 /* equivalent to kd_res_item(set, 0) */
nuclear@48 122 void *kd_res_item_data(struct kdres *set);
nuclear@48 123
nuclear@48 124
nuclear@48 125 #ifdef __cplusplus
nuclear@48 126 }
nuclear@48 127 #endif
nuclear@48 128
nuclear@48 129 #endif /* _KDTREE_H_ */