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