License Public Domain
Keywords
kdtree (1) python (33) python 3.x (1)
Permissions
Owner: flow
Viewable by Everyone
Editable by All Siafoo Users
Hide
Bored? Check out the Recent Activity on Siafoo Join Siafoo Now or Learn More

GOMERA: a (hopefully) fast, standalone kd-tree implementation for Python 3.x Atom Feed 1

GOMERA aims to become a (hopefully) fast, standalone kd-tree implementation for Python 3.x, built with Cython and an underlying C library. I will also probably integrate my already-working Damerau/Levenshtein Edit Distance library into this project.

1   GOMERA: a (hopefully) fast, standalone kd-tree implementation for Python 3.x

GOMERA aims to become a (hopefully) fast, standalone kd-tree implementation for Python 3.x, built with Cython and an underlying C library. I will also probably integrate my already-working Damerau/Levenshtein Edit Distance library into this project.

1.1   State of Project

1.1.1   2010-09-13: "how to write wrapping code for a promising kdtree implementation"

I wrote the following message to http://groups.google.com/group/cython-users, from which you can glean i am right now stuck at a very basic level—namely, importing the C source functions into a custom *.pyx wrapper. I believe wrapping the underlying C library with Cython is better than doing it with ctypes (because you can do so much more with Cython), but of course, in a case a ctypes should just work, i'd take it.


hi,

sadly, there is no kdtree in Python's standard library. i believe that, among a lot of other things, it would be very helpful for a lot of people if at least a working, fast, standalone, Python 3.x-compatible kdtree implementation was available on pypi.

i stumbled across http://code.google.com/p/kdtree/ in my search for usable code. of course, looking at the source code alone will not tell me whether this solution will work well and fast, so i tried to wrap it in Cython.

now when i try to run (basically)

/flower/bin/python3.1 ./setup.py build_ext --inplace; kdtree-demo.py

i am getting the following error:

running build_ext
cythoning kdtree_cython.pyx to kdtree_cython.c

Error converting Pyrex file to C:
------------------------------------------------------------
...
cdef extern from "Python.h":
        void      *PyMem_Malloc( size_t n )
        void      PyMem_Free( void *p )

#import kdtree
from kdtree cimport kd_create
^
------------------------------------------------------------

/adventures/GOMERA/kdtree055/kdtree_cython.pyx:46:0: 'kdtree.pxd' not found

Error converting Pyrex file to C:
------------------------------------------------------------
...
cdef extern from "Python.h":
        void      *PyMem_Malloc( size_t n )
        void      PyMem_Free( void *p )

#import kdtree
from kdtree cimport kd_create
^
------------------------------------------------------------

/adventures/GOMERA/kdtree055/kdtree_cython.pyx:46:0: 'kd_create.pxd' not found

Error converting Pyrex file to C:
------------------------------------------------------------
...
cdef extern from "Python.h":
        void      *PyMem_Malloc( size_t n )
        void      PyMem_Free( void *p )

#import kdtree
from kdtree cimport kd_create

Name 'kd_create' not declared in module 'kdtree'

however, that does not seem to be correct: i have indeed one file kdtree.pxd:

cdef extern from "kdtree.h":
        ctypedef struct kdnode
        ctypedef struct kdtree
        ctypedef struct kdtree *kd_create( int k )

where that method is referenced; there is also a kdtree.h that defines, among other things:

struct kdtree;
struct kdres;

/* create a kd-tree for "k"-dimensional data */
struct kdtree *kd_create(int k);

and of course, there is a sourcefile kdtree.c:

struct kdtree *kd_create(int k)
{
        struct kdtree *tree;

        if(!(tree = malloc(sizeof *tree))) {
                return 0;
        }

        tree->dim = k;
        tree->root = 0;
        tree->destr = 0;
        tree->rect = 0;

        return tree;
}

any ideas what is going wrong here?


1.2   Files

1.2.1   Main

1.2.1.1   GOMERA/kdtree055/kdtree-demo.py

Source of GOMERA/kdtree055/kdtree-demo.py (5 lines)

# 's
1#from kdtree_cython import dlv_distance_reference
2from kdtree_cython import GO_kd_create
3
4say( dlv_distance_reference )
5say( GO_kd_create( 42 ) )
1.2.1.2   GOMERA/kdtree055/kdtree_cython.pyx

Source of GOMERA/kdtree055/kdtree_cython.pyx (67 lines)

# 's
 1###WARN###
2#
3### In the current Cython version, ``from xy.pyx import *`` is not supported:
4###
5### GOMERA/kdtree055/WASH-N-GO ./~CAN-boot-DENIS GOMERA/kdtree055/kdtree-demo.py
6###
7### leads to
8###
9### 000000000000.40536594[....##########..........######] ~CAN-boot/RUN/run-command-line-scripts/START: GOMERA/kdtree055/kdtree-demo.py()
10### Traceback (most recent call last):
11### File "~CAN-boot.py", line 3261, in <module>
12### RUN.run_command_line()
13### File "~CAN-boot.py", line 3071, in run_command_line
14### module = self.run( route, is_toplevel = true )
15### File "~CAN-boot.py", line 2796, in run
16### exec( R[ '%code' ], context )
17### File "GOMERA/kdtree055/kdtree-demo.py", line 3, in <module>
18### from kdtree_cython import dlv_distance_reference
19### ImportError: GOMERA/kdtree055/kdtree_cython.so: undefined symbol: PyUnicode_AsString
20###
21### Inspection of the compilation messages (right above the ``~CAN-boot`` printout just shown) yields::
22###
23### kdtree_cython.c: In function ‘__pyx_import_star’:
24### kdtree_cython.c:501: warning: implicit declaration of function ‘PyUnicode_AsString’
25### kdtree_cython.c:501: warning: assignment makes pointer from integer without a cast
26###
27### So don't do that.
28
29
30############################################################################################################
31cdef extern from "stdlib.h":
32 ctypedef unsigned int size_t
33# void *malloc(size_t size)
34# void *realloc( void *ptr, size_t size )
35# void free(void *ptr)
36
37#-----------------------------------------------------------------------------------------------------------
38cdef extern from "Python.h":
39 void *PyMem_Malloc( size_t n )
40 void PyMem_Free( void *p )
41
42#import kdtree
43from kdtree cimport kd_create
44
45
46
47
48cpdef GO_kd_create( int dimension_count ):
49 import sys; return sys.path
50 pass #return kd_create( 3 )
51
52
53
54# # # /* returns the size of the result set (in elements) */
55# # int kd_res_size( <struct kdres *>set);
56# cdef extern from "kdtree.h":
57#
58# ctypedef struct kdtree:
59# pass
60# #ctypedef void* QueueValue
61#
62# # /* create a kd-tree for "k"-dimensional data */
63# kdtree *kd_create(int k)
64#
65#
66# # /* returns the size of the result set (in elements) */
67# int kd_res_size( <struct kdres *>set)

1.2.2   Library

1.2.2.1   GOMERA/kdtree055/kdtree.c

Source of GOMERA/kdtree055/kdtree.c (761 lines)

# 's
  1/*
2This file is part of ``kdtree'', a library for working with kd-trees.
3Copyright (C) 2007-2009 John Tsiombikas <nuclear@siggraph.org>
4
5Redistribution and use in source and binary forms, with or without
6modification, are permitted provided that the following conditions are met:
7
81. Redistributions of source code must retain the above copyright notice, this
9 list of conditions and the following disclaimer.
102. 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.
133. 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
16THIS SOFTWARE IS PROVIDED BY THE AUTHOR ``AS IS'' AND ANY EXPRESS OR IMPLIED
17WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE IMPLIED WARRANTIES OF
18MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO
19EVENT SHALL THE AUTHOR BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL,
20EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT
21OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS
22INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN
23CONTRACT, STRICT LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING
24IN ANY WAY OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY
25OF SUCH DAMAGE.
26*/
27/* single nearest neighbor search written by Tamas Nepusz <tamas@cs.rhul.ac.uk> */
28#include <stdio.h>
29#include <stdlib.h>
30#include <string.h>
31#include <math.h>
32#include "kdtree.h"
33
34#if defined(WIN32) || defined(__WIN32__)
35#include <malloc.h>
36#endif
37
38#ifdef USE_LIST_NODE_ALLOCATOR
39
40#ifndef NO_PTHREADS
41#include <pthread.h>
42#else
43
44#ifndef I_WANT_THREAD_BUGS
45#error "You are compiling with the fast list node allocator, with pthreads disabled! This WILL break if used from multiple threads."
46#endif /* I want thread bugs */
47
48#endif /* pthread support */
49#endif /* use list node allocator */
50
51struct kdhyperrect {
52 int dim;
53 double *min, *max; /* minimum/maximum coords */
54};
55
56struct kdnode {
57 double *pos;
58 int dir;
59 void *data;
60
61 struct kdnode *left, *right; /* negative/positive side */
62};
63
64struct res_node {
65 struct kdnode *item;
66 double dist_sq;
67 struct res_node *next;
68};
69
70struct kdtree {
71 int dim;
72 struct kdnode *root;
73 struct kdhyperrect *rect;
74 void (*destr)(void*);
75};
76
77struct kdres {
78 struct kdtree *tree;
79 struct res_node *rlist, *riter;
80 int size;
81};
82
83#define SQ(x) ((x) * (x))
84
85
86static void clear_rec(struct kdnode *node, void (*destr)(void*));
87static int insert_rec(struct kdnode **node, const double *pos, void *data, int dir, int dim);
88static int rlist_insert(struct res_node *list, struct kdnode *item, double dist_sq);
89static void clear_results(struct kdres *set);
90
91static struct kdhyperrect* hyperrect_create(int dim, const double *min, const double *max);
92static void hyperrect_free(struct kdhyperrect *rect);
93static struct kdhyperrect* hyperrect_duplicate(const struct kdhyperrect *rect);
94static void hyperrect_extend(struct kdhyperrect *rect, const double *pos);
95static double hyperrect_dist_sq(struct kdhyperrect *rect, const double *pos);
96
97#ifdef USE_LIST_NODE_ALLOCATOR
98static struct res_node *alloc_resnode(void);
99static void free_resnode(struct res_node*);
100#else
101#define alloc_resnode() malloc(sizeof(struct res_node))
102#define free_resnode(n) free(n)
103#endif
104
105
106
107struct kdtree *kd_create(int k)
108{
109 struct kdtree *tree;
110
111 if(!(tree = malloc(sizeof *tree))) {
112 return 0;
113 }
114
115 tree->dim = k;
116 tree->root = 0;
117 tree->destr = 0;
118 tree->rect = 0;
119
120 return tree;
121}
122
123void kd_free(struct kdtree *tree)
124{
125 if(tree) {
126 kd_clear(tree);
127 free(tree);
128 }
129}
130
131static void clear_rec(struct kdnode *node, void (*destr)(void*))
132{
133 if(!node) return;
134
135 clear_rec(node->left, destr);
136 clear_rec(node->right, destr);
137
138 if(destr) {
139 destr(node->data);
140 }
141 free(node->pos);
142 free(node);
143}
144
145void kd_clear(struct kdtree *tree)
146{
147 clear_rec(tree->root, tree->destr);
148 tree->root = 0;
149
150 if (tree->rect) {
151 hyperrect_free(tree->rect);
152 tree->rect = 0;
153 }
154}
155
156void kd_data_destructor(struct kdtree *tree, void (*destr)(void*))
157{
158 tree->destr = destr;
159}
160
161
162static int insert_rec(struct kdnode **nptr, const double *pos, void *data, int dir, int dim)
163{
164 int new_dir;
165 struct kdnode *node;
166
167 if(!*nptr) {
168 if(!(node = malloc(sizeof *node))) {
169 return -1;
170 }
171 if(!(node->pos = malloc(dim * sizeof *node->pos))) {
172 free(node);
173 return -1;
174 }
175 memcpy(node->pos, pos, dim * sizeof *node->pos);
176 node->data = data;
177 node->dir = dir;
178 node->left = node->right = 0;
179 *nptr = node;
180 return 0;
181 }
182
183 node = *nptr;
184 new_dir = (node->dir + 1) % dim;
185 if(pos[node->dir] < node->pos[node->dir]) {
186 return insert_rec(&(*nptr)->left, pos, data, new_dir, dim);
187 }
188 return insert_rec(&(*nptr)->right, pos, data, new_dir, dim);
189}
190
191int kd_insert(struct kdtree *tree, const double *pos, void *data)
192{
193 if (insert_rec(&tree->root, pos, data, 0, tree->dim)) {
194 return -1;
195 }
196
197 if (tree->rect == 0) {
198 tree->rect = hyperrect_create(tree->dim, pos, pos);
199 } else {
200 hyperrect_extend(tree->rect, pos);
201 }
202
203 return 0;
204}
205
206int kd_insertf(struct kdtree *tree, const float *pos, void *data)
207{
208 static double sbuf[16];
209 double *bptr, *buf = 0;
210 int res, dim = tree->dim;
211
212 if(dim > 16) {
213#ifndef NO_ALLOCA
214 if(dim <= 256)
215 bptr = buf = alloca(dim * sizeof *bptr);
216 else
217#endif
218 if(!(bptr = buf = malloc(dim * sizeof *bptr))) {
219 return -1;
220 }
221 } else {
222 bptr = sbuf;
223 }
224
225 while(dim-- > 0) {
226 *bptr++ = *pos++;
227 }
228
229 res = kd_insert(tree, buf, data);
230#ifndef NO_ALLOCA
231 if(tree->dim > 256)
232#else
233 if(tree->dim > 16)
234#endif
235 free(buf);
236 return res;
237}
238
239int kd_insert3(struct kdtree *tree, double x, double y, double z, void *data)
240{
241 double buf[3];
242 buf[0] = x;
243 buf[1] = y;
244 buf[2] = z;
245 return kd_insert(tree, buf, data);
246}
247
248int kd_insert3f(struct kdtree *tree, float x, float y, float z, void *data)
249{
250 double buf[3];
251 buf[0] = x;
252 buf[1] = y;
253 buf[2] = z;
254 return kd_insert(tree, buf, data);
255}
256
257static int find_nearest(struct kdnode *node, const double *pos, double range, struct res_node *list, int ordered, int dim)
258{
259 double dist_sq, dx;
260 int i, ret, added_res = 0;
261
262 if(!node) return 0;
263
264 dist_sq = 0;
265 for(i=0; i<dim; i++) {
266 dist_sq += SQ(node->pos[i] - pos[i]);
267 }
268 if(dist_sq <= SQ(range)) {
269 if(rlist_insert(list, node, ordered ? dist_sq : -1.0) == -1) {
270 return -1;
271 }
272 added_res = 1;
273 }
274
275 dx = pos[node->dir] - node->pos[node->dir];
276
277 ret = find_nearest(dx <= 0.0 ? node->left : node->right, pos, range, list, ordered, dim);
278 if(ret >= 0 && fabs(dx) < range) {
279 added_res += ret;
280 ret = find_nearest(dx <= 0.0 ? node->right : node->left, pos, range, list, ordered, dim);
281 }
282 if(ret == -1) {
283 return -1;
284 }
285 added_res += ret;
286
287 return added_res;
288}
289
290static void kd_nearest_i(struct kdnode *node, const double *pos, struct kdnode **result, double *result_dist_sq, struct kdhyperrect* rect)
291{
292 int dir = node->dir;
293 int i, side;
294 double dummy, dist_sq;
295 struct kdnode *nearer_subtree, *farther_subtree;
296 double *nearer_hyperrect_coord, *farther_hyperrect_coord;
297
298 /* Decide whether to go left or right in the tree */
299 dummy = pos[dir] - node->pos[dir];
300 if (dummy <= 0) {
301 nearer_subtree = node->left;
302 farther_subtree = node->right;
303 nearer_hyperrect_coord = rect->max + dir;
304 farther_hyperrect_coord = rect->min + dir;
305 side = 0;
306 } else {
307 nearer_subtree = node->right;
308 farther_subtree = node->left;
309 nearer_hyperrect_coord = rect->min + dir;
310 farther_hyperrect_coord = rect->max + dir;
311 side = 1;
312 }
313
314 if (nearer_subtree) {
315 /* Slice the hyperrect to get the hyperrect of the nearer subtree */
316 dummy = *nearer_hyperrect_coord;
317 *nearer_hyperrect_coord = node->pos[dir];
318 /* Recurse down into nearer subtree */
319 kd_nearest_i(nearer_subtree, pos, result, result_dist_sq, rect);
320 /* Undo the slice */
321 *nearer_hyperrect_coord = dummy;
322 }
323
324 /* Check the distance of the point at the current node, compare it
325 * with our best so far */
326 dist_sq = 0;
327 for(i=0; i < rect->dim; i++) {
328 dist_sq += SQ(node->pos[i] - pos[i]);
329 }
330 if (dist_sq < *result_dist_sq) {
331 *result = node;
332 *result_dist_sq = dist_sq;
333 }
334
335 if (farther_subtree) {
336 /* Get the hyperrect of the farther subtree */
337 dummy = *farther_hyperrect_coord;
338 *farther_hyperrect_coord = node->pos[dir];
339 /* Check if we have to recurse down by calculating the closest
340 * point of the hyperrect and see if it's closer than our
341 * minimum distance in result_dist_sq. */
342 if (hyperrect_dist_sq(rect, pos) < *result_dist_sq) {
343 /* Recurse down into farther subtree */
344 kd_nearest_i(farther_subtree, pos, result, result_dist_sq, rect);
345 }
346 /* Undo the slice on the hyperrect */
347 *farther_hyperrect_coord = dummy;
348 }
349}
350
351struct kdres *kd_nearest(struct kdtree *kd, const double *pos)
352{
353 struct kdhyperrect *rect;
354 struct kdnode *result;
355 struct kdres *rset;
356 double dist_sq;
357 int i;
358
359 if (!kd) return 0;
360 if (!kd->rect) return 0;
361
362 /* Allocate result set */
363 if(!(rset = malloc(sizeof *rset))) {
364 return 0;
365 }
366 if(!(rset->rlist = alloc_resnode())) {
367 free(rset);
368 return 0;
369 }
370 rset->rlist->next = 0;
371 rset->tree = kd;
372
373 /* Duplicate the bounding hyperrectangle, we will work on the copy */
374 if (!(rect = hyperrect_duplicate(kd->rect))) {
375 kd_res_free(rset);
376 return 0;
377 }
378
379 /* Our first guesstimate is the root node */
380 result = kd->root;
381 dist_sq = 0;
382 for (i = 0; i < kd->dim; i++)
383 dist_sq += SQ(result->pos[i] - pos[i]);
384
385 /* Search for the nearest neighbour recursively */
386 kd_nearest_i(kd->root, pos, &result, &dist_sq, rect);
387
388 /* Free the copy of the hyperrect */
389 hyperrect_free(rect);
390
391 /* Store the result */
392 if (result) {
393 if (rlist_insert(rset->rlist, result, -1.0) == -1) {
394 kd_res_free(rset);
395 return 0;
396 }
397 rset->size = 1;
398 kd_res_rewind(rset);
399 return rset;
400 } else {
401 kd_res_free(rset);
402 return 0;
403 }
404}
405
406struct kdres *kd_nearestf(struct kdtree *tree, const float *pos)
407{
408 static double sbuf[16];
409 double *bptr, *buf = 0;
410 int dim = tree->dim;
411 struct kdres *res;
412
413 if(dim > 16) {
414#ifndef NO_ALLOCA
415 if(dim <= 256)
416 bptr = buf = alloca(dim * sizeof *bptr);
417 else
418#endif
419 if(!(bptr = buf = malloc(dim * sizeof *bptr))) {
420 return 0;
421 }
422 } else {
423 bptr = sbuf;
424 }
425
426 while(dim-- > 0) {
427 *bptr++ = *pos++;
428 }
429
430 res = kd_nearest(tree, buf);
431#ifndef NO_ALLOCA
432 if(tree->dim > 256)
433#else
434 if(tree->dim > 16)
435#endif
436 free(buf);
437 return res;
438}
439
440struct kdres *kd_nearest3(struct kdtree *tree, double x, double y, double z)
441{
442 double pos[3];
443 pos[0] = x;
444 pos[1] = y;
445 pos[2] = z;
446 return kd_nearest(tree, pos);
447}
448
449struct kdres *kd_nearest3f(struct kdtree *tree, float x, float y, float z)
450{
451 double pos[3];
452 pos[0] = x;
453 pos[1] = y;
454 pos[2] = z;
455 return kd_nearest(tree, pos);
456}
457
458struct kdres *kd_nearest_range(struct kdtree *kd, const double *pos, double range)
459{
460 int ret;
461 struct kdres *rset;
462
463 if(!(rset = malloc(sizeof *rset))) {
464 return 0;
465 }
466 if(!(rset->rlist = alloc_resnode())) {
467 free(rset);
468 return 0;
469 }
470 rset->rlist->next = 0;
471 rset->tree = kd;
472
473 if((ret = find_nearest(kd->root, pos, range, rset->rlist, 0, kd->dim)) == -1) {
474 kd_res_free(rset);
475 return 0;
476 }
477 rset->size = ret;
478 kd_res_rewind(rset);
479 return rset;
480}
481
482struct kdres *kd_nearest_rangef(struct kdtree *kd, const float *pos, float range)
483{
484 static double sbuf[16];
485 double *bptr, *buf = 0;
486 int dim = kd->dim;
487 struct kdres *res;
488
489 if(dim > 16) {
490#ifndef NO_ALLOCA
491 if(dim <= 256)
492 bptr = buf = alloca(dim * sizeof *bptr);
493 else
494#endif
495 if(!(bptr = buf = malloc(dim * sizeof *bptr))) {
496 return 0;
497 }
498 } else {
499 bptr = sbuf;
500 }
501
502 while(dim-- > 0) {
503 *bptr++ = *pos++;
504 }
505
506 res = kd_nearest_range(kd, buf, range);
507#ifndef NO_ALLOCA
508 if(kd->dim > 256)
509#else
510 if(kd->dim > 16)
511#endif
512 free(buf);
513 return res;
514}
515
516struct kdres *kd_nearest_range3(struct kdtree *tree, double x, double y, double z, double range)
517{
518 double buf[3];
519 buf[0] = x;
520 buf[1] = y;
521 buf[2] = z;
522 return kd_nearest_range(tree, buf, range);
523}
524
525struct kdres *kd_nearest_range3f(struct kdtree *tree, float x, float y, float z, float range)
526{
527 double buf[3];
528 buf[0] = x;
529 buf[1] = y;
530 buf[2] = z;
531 return kd_nearest_range(tree, buf, range);
532}
533
534void kd_res_free(struct kdres *rset)
535{
536 clear_results(rset);
537 free_resnode(rset->rlist);
538 free(rset);
539}
540
541int kd_res_size(struct kdres *set)
542{
543 return (set->size);
544}
545
546void kd_res_rewind(struct kdres *rset)
547{
548 rset->riter = rset->rlist->next;
549}
550
551int kd_res_end(struct kdres *rset)
552{
553 return rset->riter == 0;
554}
555
556int kd_res_next(struct kdres *rset)
557{
558 rset->riter = rset->riter->next;
559 return rset->riter != 0;
560}
561
562void *kd_res_item(struct kdres *rset, double *pos)
563{
564 if(rset->riter) {
565 if(pos) {
566 memcpy(pos, rset->riter->item->pos, rset->tree->dim * sizeof *pos);
567 }
568 return rset->riter->item->data;
569 }
570 return 0;
571}
572
573void *kd_res_itemf(struct kdres *rset, float *pos)
574{
575 if(rset->riter) {
576 if(pos) {
577 int i;
578 for(i=0; i<rset->tree->dim; i++) {
579 pos[i] = rset->riter->item->pos[i];
580 }
581 }
582 return rset->riter->item->data;
583 }
584 return 0;
585}
586
587void *kd_res_item3(struct kdres *rset, double *x, double *y, double *z)
588{
589 if(rset->riter) {
590 if(*x) *x = rset->riter->item->pos[0];
591 if(*y) *y = rset->riter->item->pos[1];
592 if(*z) *z = rset->riter->item->pos[2];
593 }
594 return 0;
595}
596
597void *kd_res_item3f(struct kdres *rset, float *x, float *y, float *z)
598{
599 if(rset->riter) {
600 if(*x) *x = rset->riter->item->pos[0];
601 if(*y) *y = rset->riter->item->pos[1];
602 if(*z) *z = rset->riter->item->pos[2];
603 }
604 return 0;
605}
606
607void *kd_res_item_data(struct kdres *set)
608{
609 return kd_res_item(set, 0);
610}
611
612/* ---- hyperrectangle helpers ---- */
613static struct kdhyperrect* hyperrect_create(int dim, const double *min, const double *max)
614{
615 size_t size = dim * sizeof(double);
616 struct kdhyperrect* rect = 0;
617
618 if (!(rect = malloc(sizeof(struct kdhyperrect)))) {
619 return 0;
620 }
621
622 rect->dim = dim;
623 if (!(rect->min = malloc(size))) {
624 free(rect);
625 return 0;
626 }
627 if (!(rect->max = malloc(size))) {
628 free(rect->min);
629 free(rect);
630 return 0;
631 }
632 memcpy(rect->min, min, size);
633 memcpy(rect->max, max, size);
634
635 return rect;
636}
637
638static void hyperrect_free(struct kdhyperrect *rect)
639{
640 free(rect->min);
641 free(rect->max);
642 free(rect);
643}
644
645static struct kdhyperrect* hyperrect_duplicate(const struct kdhyperrect *rect)
646{
647 return hyperrect_create(rect->dim, rect->min, rect->max);
648}
649
650static void hyperrect_extend(struct kdhyperrect *rect, const double *pos)
651{
652 int i;
653
654 for (i=0; i < rect->dim; i++) {
655 if (pos[i] < rect->min[i]) {
656 rect->min[i] = pos[i];
657 }
658 if (pos[i] > rect->max[i]) {
659 rect->max[i] = pos[i];
660 }
661 }
662}
663
664static double hyperrect_dist_sq(struct kdhyperrect *rect, const double *pos)
665{
666 int i;
667 double result = 0;
668
669 for (i=0; i < rect->dim; i++) {
670 if (pos[i] < rect->min[i]) {
671 result += SQ(rect->min[i] - pos[i]);
672 } else if (pos[i] > rect->max[i]) {
673 result += SQ(rect->max[i] - pos[i]);
674 }
675 }
676
677 return result;
678}
679
680/* ---- static helpers ---- */
681
682#ifdef USE_LIST_NODE_ALLOCATOR
683/* special list node allocators. */
684static struct res_node *free_nodes;
685
686#ifndef NO_PTHREADS
687static pthread_mutex_t alloc_mutex = PTHREAD_MUTEX_INITIALIZER;
688#endif
689
690static struct res_node *alloc_resnode(void)
691{
692 struct res_node *node;
693
694#ifndef NO_PTHREADS
695 pthread_mutex_lock(&alloc_mutex);
696#endif
697
698 if(!free_nodes) {
699 node = malloc(sizeof *node);
700 } else {
701 node = free_nodes;
702 free_nodes = free_nodes->next;
703 node->next = 0;
704 }
705
706#ifndef NO_PTHREADS
707 pthread_mutex_unlock(&alloc_mutex);
708#endif
709
710 return node;
711}
712
713static void free_resnode(struct res_node *node)
714{
715#ifndef NO_PTHREADS
716 pthread_mutex_lock(&alloc_mutex);
717#endif
718
719 node->next = free_nodes;
720 free_nodes = node;
721
722#ifndef NO_PTHREADS
723 pthread_mutex_unlock(&alloc_mutex);
724#endif
725}
726#endif /* list node allocator or not */
727
728
729/* inserts the item. if dist_sq is >= 0, then do an ordered insert */
730static int rlist_insert(struct res_node *list, struct kdnode *item, double dist_sq)
731{
732 struct res_node *rnode;
733
734 if(!(rnode = alloc_resnode())) {
735 return -1;
736 }
737 rnode->item = item;
738 rnode->dist_sq = dist_sq;
739
740 if(dist_sq >= 0.0) {
741 while(list->next && list->next->dist_sq < dist_sq) {
742 list = list->next;
743 }
744 }
745 rnode->next = list->next;
746 list->next = rnode;
747 return 0;
748}
749
750static void clear_results(struct kdres *rset)
751{
752 struct res_node *tmp, *node = rset->rlist->next;
753
754 while(node) {
755 tmp = node;
756 node = node->next;
757 free_resnode(tmp);
758 }
759
760 rset->rlist->next = 0;
761}
1.2.2.2   GOMERA/kdtree055/kdtree.h

Source of GOMERA/kdtree055/kdtree.h (114 lines)

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

Source of GOMERA/kdtree055/kdtree.pxd (28 lines)

#     cdef extern from "kdtree.h":
#
#       ctypedef struct kdnode:
#         pass
#     #     double *( pos )
#     #     int ( dir )
#     #     void *( data )
#
#     #   ctypedef struct kdnode *( left )
#     #   ctypedef struct kdnode *( right )  #/* negative/positive side */
#
#       ctypedef struct kdtree
#     #   :
#     #     int dim
#     #     struct kdnode *( root )
#     #     struct kdhyperrect( *rect )
#     #     void (*destr)(void*)
#
#       # /* create a kd-tree for "k"-dimensional data */
#       ctypedef struct kdtree *kd_create(int k)



cdef extern from "kdtree.h":

  ctypedef struct kdnode
  ctypedef struct kdtree
  ctypedef struct kdtree *kd_create( int k )

1.2.3   Administrative

1.2.3.1   GOMERA/kdtree055/setup.py

Source of GOMERA/kdtree055/setup.py (26 lines)

# 's
 1# from distutils.core import setup
2# from distutils.extension import Extension
3# from Cython.Distutils import build_ext
4#
5# setup(
6# name = 'kdtree_cython',
7# ext_modules = [
8# Extension( 'kdtree', [ 'kdtree.c', ] ),
9# Extension( 'BLAIDDDRWG', [ 'BLAIDDDRWG.pyx', ] ),
10# Extension( 'kdtree_cython', [ 'kdtree_cython.pyx', ] ), ],
11# cmdclass = {
12# 'build_ext': build_ext }, )
13#
14
15
16from distutils.core import setup
17from distutils.extension import Extension
18from Cython.Distutils import build_ext
19
20sourcefiles = [ 'kdtree_cython.pyx', 'BLAIDDDRWG.pyx', 'kdtree.c', ]
21
22setup(
23 name = 'kdtree_cython',
24 ext_modules = [ Extension( 'kdtree_cython', sourcefiles ), ],
25 cmdclass = {
26 'build_ext': build_ext }, )
1.2.3.2   GOMERA/kdtree055/configure

Source of GOMERA/kdtree055/configure (96 lines)

#!/bin/sh

echo 'configuring kdtree ...'

PREFIX=/usr/local
OPT=yes
DBG=yes
FALLOC=yes
PTHREAD=yes

for arg; do
      case "$arg" in
      --prefix=*)
              value=`echo $arg | sed 's/--prefix=//'`
              PREFIX=${value:-$prefix}
              ;;

      --enable-opt)
              OPT=yes;;
      --disable-opt)
              OPT=no;;

      --enable-debug)
              DBG=yes;;
      --disable-debug)
              DBG=no;;

      --enable-pthread)
              PTHREAD=yes;;
      --disable-pthread)
              PTHREAD=no;;

      --enable-fastalloc)
              FALLOC=yes;;
      --disable-fastalloc)
              FALLOC=no;;

      --help)
              echo 'usage: ./configure [options]'
              echo 'options:'
              echo '  --prefix=<path>: installation path (default: /usr/local)'
              echo '  --enable-fastalloc: enable fast result node allocator (default)'
              echo '  --disable-fastalloc: disable fast result node allocator'
              echo '  --enable-pthread: enable pthread support (default if fastalloc is enabled)'
              echo "  --disable-pthread: disable pthread support (don't)"
              echo '  --enable-opt: enable speed optimizations (default)'
              echo '  --disable-opt: disable speed optimizations'
              echo '  --enable-debug: include debugging symbols (default)'
              echo '  --disable-debug: do not include debugging symbols'
              echo 'all invalid options are silently ignored'
              exit 0
              ;;
      esac
done

echo "prefix: $PREFIX"
echo "optimize for speed: $OPT"
echo "include debugging symbols: $DBG"
echo "fast node allocator: $FALLOC"
if [ "$FALLOC" = "yes" ]; then
      echo "pthread support: $PTHREAD"
fi

# create makefile
echo 'creating makefile ...'
echo "PREFIX = $PREFIX" >Makefile
if [ "$DBG" = 'yes' ]; then
      echo 'dbg = -g' >>Makefile
fi
if [ "$OPT" = 'yes' ]; then
      echo 'opt = -O3' >>Makefile
fi
if [ "$FALLOC" = 'yes' ]; then
      echo 'falloc = -DUSE_LIST_NODE_ALLOCATOR' >>Makefile
fi
if [ "$PTHREAD" = 'no' ]; then
      echo 'pthreads = -DNO_PTHREADS' >>Makefile
else
      echo 'ldpthread = -lpthread' >>Makefile
fi

if [ "`uname -s`" = Darwin ]; then
      echo 'shared = -dynamiclib' >>Makefile
      echo 'so_suffix = dylib' >>Makefile
else
      echo 'shared = -shared' >>Makefile
      echo 'so_suffix = so' >>Makefile
fi

if [ "`uname -s`" != MINGW32 ]; then
      echo 'pic = -fPIC' >>Makefile
fi

cat Makefile.in >>Makefile

echo 'configuration completed, type make (or gmake) to build.'
1.2.3.3   GOMERA/kdtree055/WASH-N-GO

Source of GOMERA/kdtree055/WASH-N-GO (27 lines)

#!/bin/sh

clear
echo ""
echo "############################################################################################################"
echo ""

cd /adventures/GOMERA/kdtree055
if /flower/bin/python3.1 ./setup.py build_ext --inplace; then
      echo ""
      echo "------------------------------------------------------------------------------------------------------------"
      echo ""
      echo "COMPILATION SUCCESSFUL"
      echo ""
      echo "------------------------------------------------------------------------------------------------------------"
      echo ""
      cd -
      $*
else
      echo ""
      echo "------------------------------------------------------------------------------------------------------------"
      echo ""
      echo "COMPILATION FAILED"
      echo ""
      echo "------------------------------------------------------------------------------------------------------------"
      echo ""
fi
1.2.3.4   GOMERA/kdtree055/WASH-N-GO.howto.txt

Source of GOMERA/kdtree055/WASH-N-GO.howto.txt (26 lines)

WASH-N-GO makes living with C a little easyier: Using Cython's capabilities and a little bash,
WASH-N-GO makes it so that you can always painlessly test your code, almost like a Python script,
buy having WASH-N-GO compile your C, C++ and Cython source transparently, stops if anything
went wrong so you can train your eyes on seemingly endless lines with very little to say,
and if everything is fine then executes a demonstration script to test that everything can not
only compile but is actually usable. Conceptually, this takes 'compilation' out of C.

Call it like::

      GOMERA/kdtree055/WASH-N-GO ./~CAN-boot-SVG GOMERA/kdtree055/demo.py

In the near future, it is planned to simplify these incantations a lot, by moving a step forward
towards using urJSON in the command line::

      GOMERA/kdtree055/WASH-N-GO site: SVG, run: demo.py

and

      GOMERA/kdtree055/WASH-N-GO SVG, demo.py

and

      GOMERA/kdtree055/WASH-N-GO( SVG, demo.py )

and so on. Also, a move to IPython (http://ipython.scipy.org/moin/Download) would be conceivable,
but the project is still stuck to Python 2.x.
1.2.3.5   GOMERA/kdtree055/__init__.py

Source of GOMERA/kdtree055/__init__.py (omitted; file empty)