1.1 --- /dev/null	Thu Jan 01 00:00:00 1970 +0000
     1.2 +++ b/prototype/kdtree/kdtree.h	Mon Sep 17 08:40:59 2012 +0300
     1.3 @@ -0,0 +1,129 @@
     1.4 +/*
     1.5 +This file is part of ``kdtree'', a library for working with kd-trees.
     1.6 +Copyright (C) 2007-2011 John Tsiombikas <nuclear@member.fsf.org>
     1.7 +
     1.8 +Redistribution and use in source and binary forms, with or without
     1.9 +modification, are permitted provided that the following conditions are met:
    1.10 +
    1.11 +1. Redistributions of source code must retain the above copyright notice, this
    1.12 +   list of conditions and the following disclaimer.
    1.13 +2. Redistributions in binary form must reproduce the above copyright notice,
    1.14 +   this list of conditions and the following disclaimer in the documentation
    1.15 +   and/or other materials provided with the distribution.
    1.16 +3. The name of the author may not be used to endorse or promote products
    1.17 +   derived from this software without specific prior written permission.
    1.18 +
    1.19 +THIS SOFTWARE IS PROVIDED BY THE AUTHOR ``AS IS'' AND ANY EXPRESS OR IMPLIED
    1.20 +WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE IMPLIED WARRANTIES OF
    1.21 +MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO
    1.22 +EVENT SHALL THE AUTHOR BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL,
    1.23 +EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT
    1.24 +OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS
    1.25 +INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN
    1.26 +CONTRACT, STRICT LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING
    1.27 +IN ANY WAY OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY
    1.28 +OF SUCH DAMAGE.
    1.29 +*/
    1.30 +#ifndef _KDTREE_H_
    1.31 +#define _KDTREE_H_
    1.32 +
    1.33 +#ifdef __cplusplus
    1.34 +extern "C" {
    1.35 +#endif
    1.36 +
    1.37 +struct kdtree;
    1.38 +struct kdres;
    1.39 +
    1.40 +
    1.41 +/* create a kd-tree for "k"-dimensional data */
    1.42 +struct kdtree *kd_create(int k);
    1.43 +
    1.44 +/* free the struct kdtree */
    1.45 +void kd_free(struct kdtree *tree);
    1.46 +
    1.47 +/* remove all the elements from the tree */
    1.48 +void kd_clear(struct kdtree *tree);
    1.49 +
    1.50 +/* if called with non-null 2nd argument, the function provided
    1.51 + * will be called on data pointers (see kd_insert) when nodes
    1.52 + * are to be removed from the tree.
    1.53 + */
    1.54 +void kd_data_destructor(struct kdtree *tree, void (*destr)(void*));
    1.55 +
    1.56 +/* insert a node, specifying its position, and optional data */
    1.57 +int kd_insert(struct kdtree *tree, const double *pos, void *data);
    1.58 +int kd_insertf(struct kdtree *tree, const float *pos, void *data);
    1.59 +int kd_insert3(struct kdtree *tree, double x, double y, double z, void *data);
    1.60 +int kd_insert3f(struct kdtree *tree, float x, float y, float z, void *data);
    1.61 +
    1.62 +/* Find the nearest node from a given point.
    1.63 + *
    1.64 + * This function returns a pointer to a result set with at most one element.
    1.65 + */
    1.66 +struct kdres *kd_nearest(struct kdtree *tree, const double *pos);
    1.67 +struct kdres *kd_nearestf(struct kdtree *tree, const float *pos);
    1.68 +struct kdres *kd_nearest3(struct kdtree *tree, double x, double y, double z);
    1.69 +struct kdres *kd_nearest3f(struct kdtree *tree, float x, float y, float z);
    1.70 +
    1.71 +/* Find the N nearest nodes from a given point.
    1.72 + *
    1.73 + * This function returns a pointer to a result set, with at most N elements,
    1.74 + * which can be manipulated with the kd_res_* functions.
    1.75 + * The returned pointer can be null as an indication of an error. Otherwise
    1.76 + * a valid result set is always returned which may contain 0 or more elements.
    1.77 + * The result set must be deallocated with kd_res_free after use.
    1.78 + */
    1.79 +/*
    1.80 +struct kdres *kd_nearest_n(struct kdtree *tree, const double *pos, int num);
    1.81 +struct kdres *kd_nearest_nf(struct kdtree *tree, const float *pos, int num);
    1.82 +struct kdres *kd_nearest_n3(struct kdtree *tree, double x, double y, double z);
    1.83 +struct kdres *kd_nearest_n3f(struct kdtree *tree, float x, float y, float z);
    1.84 +*/
    1.85 +
    1.86 +/* Find any nearest nodes from a given point within a range.
    1.87 + *
    1.88 + * This function returns a pointer to a result set, which can be manipulated
    1.89 + * by the kd_res_* functions.
    1.90 + * The returned pointer can be null as an indication of an error. Otherwise
    1.91 + * a valid result set is always returned which may contain 0 or more elements.
    1.92 + * The result set must be deallocated with kd_res_free after use.
    1.93 + */
    1.94 +struct kdres *kd_nearest_range(struct kdtree *tree, const double *pos, double range);
    1.95 +struct kdres *kd_nearest_rangef(struct kdtree *tree, const float *pos, float range);
    1.96 +struct kdres *kd_nearest_range3(struct kdtree *tree, double x, double y, double z, double range);
    1.97 +struct kdres *kd_nearest_range3f(struct kdtree *tree, float x, float y, float z, float range);
    1.98 +
    1.99 +/* frees a result set returned by kd_nearest_range() */
   1.100 +void kd_res_free(struct kdres *set);
   1.101 +
   1.102 +/* returns the size of the result set (in elements) */
   1.103 +int kd_res_size(struct kdres *set);
   1.104 +
   1.105 +/* rewinds the result set iterator */
   1.106 +void kd_res_rewind(struct kdres *set);
   1.107 +
   1.108 +/* returns non-zero if the set iterator reached the end after the last element */
   1.109 +int kd_res_end(struct kdres *set);
   1.110 +
   1.111 +/* advances the result set iterator, returns non-zero on success, zero if
   1.112 + * there are no more elements in the result set.
   1.113 + */
   1.114 +int kd_res_next(struct kdres *set);
   1.115 +
   1.116 +/* returns the data pointer (can be null) of the current result set item
   1.117 + * and optionally sets its position to the pointers(s) if not null.
   1.118 + */
   1.119 +void *kd_res_item(struct kdres *set, double *pos);
   1.120 +void *kd_res_itemf(struct kdres *set, float *pos);
   1.121 +void *kd_res_item3(struct kdres *set, double *x, double *y, double *z);
   1.122 +void *kd_res_item3f(struct kdres *set, float *x, float *y, float *z);
   1.123 +
   1.124 +/* equivalent to kd_res_item(set, 0) */
   1.125 +void *kd_res_item_data(struct kdres *set);
   1.126 +
   1.127 +
   1.128 +#ifdef __cplusplus
   1.129 +}
   1.130 +#endif
   1.131 +
   1.132 +#endif	/* _KDTREE_H_ */