nuclear@48: /* nuclear@48: This file is part of ``kdtree'', a library for working with kd-trees. nuclear@48: Copyright (C) 2007-2011 John Tsiombikas nuclear@48: nuclear@48: Redistribution and use in source and binary forms, with or without nuclear@48: modification, are permitted provided that the following conditions are met: nuclear@48: nuclear@48: 1. Redistributions of source code must retain the above copyright notice, this nuclear@48: list of conditions and the following disclaimer. nuclear@48: 2. Redistributions in binary form must reproduce the above copyright notice, nuclear@48: this list of conditions and the following disclaimer in the documentation nuclear@48: and/or other materials provided with the distribution. nuclear@48: 3. The name of the author may not be used to endorse or promote products nuclear@48: derived from this software without specific prior written permission. nuclear@48: nuclear@48: THIS SOFTWARE IS PROVIDED BY THE AUTHOR ``AS IS'' AND ANY EXPRESS OR IMPLIED nuclear@48: WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE IMPLIED WARRANTIES OF nuclear@48: MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO nuclear@48: EVENT SHALL THE AUTHOR BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, nuclear@48: EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT nuclear@48: OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS nuclear@48: INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN nuclear@48: CONTRACT, STRICT LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING nuclear@48: IN ANY WAY OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY nuclear@48: OF SUCH DAMAGE. nuclear@48: */ nuclear@48: #ifndef _KDTREE_H_ nuclear@48: #define _KDTREE_H_ nuclear@48: nuclear@48: #ifdef __cplusplus nuclear@48: extern "C" { nuclear@48: #endif nuclear@48: nuclear@48: struct kdtree; nuclear@48: struct kdres; nuclear@48: nuclear@48: nuclear@48: /* create a kd-tree for "k"-dimensional data */ nuclear@48: struct kdtree *kd_create(int k); nuclear@48: nuclear@48: /* free the struct kdtree */ nuclear@48: void kd_free(struct kdtree *tree); nuclear@48: nuclear@48: /* remove all the elements from the tree */ nuclear@48: void kd_clear(struct kdtree *tree); nuclear@48: nuclear@48: /* if called with non-null 2nd argument, the function provided nuclear@48: * will be called on data pointers (see kd_insert) when nodes nuclear@48: * are to be removed from the tree. nuclear@48: */ nuclear@48: void kd_data_destructor(struct kdtree *tree, void (*destr)(void*)); nuclear@48: nuclear@48: /* insert a node, specifying its position, and optional data */ nuclear@48: int kd_insert(struct kdtree *tree, const double *pos, void *data); nuclear@48: int kd_insertf(struct kdtree *tree, const float *pos, void *data); nuclear@48: int kd_insert3(struct kdtree *tree, double x, double y, double z, void *data); nuclear@48: int kd_insert3f(struct kdtree *tree, float x, float y, float z, void *data); nuclear@48: nuclear@48: /* Find the nearest node from a given point. nuclear@48: * nuclear@48: * This function returns a pointer to a result set with at most one element. nuclear@48: */ nuclear@48: struct kdres *kd_nearest(struct kdtree *tree, const double *pos); nuclear@48: struct kdres *kd_nearestf(struct kdtree *tree, const float *pos); nuclear@48: struct kdres *kd_nearest3(struct kdtree *tree, double x, double y, double z); nuclear@48: struct kdres *kd_nearest3f(struct kdtree *tree, float x, float y, float z); nuclear@48: nuclear@48: /* Find the N nearest nodes from a given point. nuclear@48: * nuclear@48: * This function returns a pointer to a result set, with at most N elements, nuclear@48: * which can be manipulated with the kd_res_* functions. nuclear@48: * The returned pointer can be null as an indication of an error. Otherwise nuclear@48: * a valid result set is always returned which may contain 0 or more elements. nuclear@48: * The result set must be deallocated with kd_res_free after use. nuclear@48: */ nuclear@48: /* nuclear@48: struct kdres *kd_nearest_n(struct kdtree *tree, const double *pos, int num); nuclear@48: struct kdres *kd_nearest_nf(struct kdtree *tree, const float *pos, int num); nuclear@48: struct kdres *kd_nearest_n3(struct kdtree *tree, double x, double y, double z); nuclear@48: struct kdres *kd_nearest_n3f(struct kdtree *tree, float x, float y, float z); nuclear@48: */ nuclear@48: nuclear@48: /* Find any nearest nodes from a given point within a range. nuclear@48: * nuclear@48: * This function returns a pointer to a result set, which can be manipulated nuclear@48: * by the kd_res_* functions. nuclear@48: * The returned pointer can be null as an indication of an error. Otherwise nuclear@48: * a valid result set is always returned which may contain 0 or more elements. nuclear@48: * The result set must be deallocated with kd_res_free after use. nuclear@48: */ nuclear@48: struct kdres *kd_nearest_range(struct kdtree *tree, const double *pos, double range); nuclear@48: struct kdres *kd_nearest_rangef(struct kdtree *tree, const float *pos, float range); nuclear@48: struct kdres *kd_nearest_range3(struct kdtree *tree, double x, double y, double z, double range); nuclear@48: struct kdres *kd_nearest_range3f(struct kdtree *tree, float x, float y, float z, float range); nuclear@48: nuclear@48: /* frees a result set returned by kd_nearest_range() */ nuclear@48: void kd_res_free(struct kdres *set); nuclear@48: nuclear@48: /* returns the size of the result set (in elements) */ nuclear@48: int kd_res_size(struct kdres *set); nuclear@48: nuclear@48: /* rewinds the result set iterator */ nuclear@48: void kd_res_rewind(struct kdres *set); nuclear@48: nuclear@48: /* returns non-zero if the set iterator reached the end after the last element */ nuclear@48: int kd_res_end(struct kdres *set); nuclear@48: nuclear@48: /* advances the result set iterator, returns non-zero on success, zero if nuclear@48: * there are no more elements in the result set. nuclear@48: */ nuclear@48: int kd_res_next(struct kdres *set); nuclear@48: nuclear@48: /* returns the data pointer (can be null) of the current result set item nuclear@48: * and optionally sets its position to the pointers(s) if not null. nuclear@48: */ nuclear@48: void *kd_res_item(struct kdres *set, double *pos); nuclear@48: void *kd_res_itemf(struct kdres *set, float *pos); nuclear@48: void *kd_res_item3(struct kdres *set, double *x, double *y, double *z); nuclear@48: void *kd_res_item3f(struct kdres *set, float *x, float *y, float *z); nuclear@48: nuclear@48: /* equivalent to kd_res_item(set, 0) */ nuclear@48: void *kd_res_item_data(struct kdres *set); nuclear@48: nuclear@48: nuclear@48: #ifdef __cplusplus nuclear@48: } nuclear@48: #endif nuclear@48: nuclear@48: #endif /* _KDTREE_H_ */