jtsiomb / kdtree

A simple C library for working with KD-Trees

kdtree

Overview

kdtree is a simple, easy to use C library for working with kd-trees.

Kd-trees are an extension of binary search trees to k-dimensional data. They facilitate very fast searching, and nearest-neighbor queries.

This particular implementation is designed to be efficient and very easy to use. It is completely written in ANSI/ISO C, and thus completely cross-platform.

See under the doc/ and examples/ directories to find out how to use the kdtree library.

License

Author: John Tsiombikas <[email protected]>

kdtree is free software. You may use, modify, and redistribute it under the terms of the 3-clause BSD license.

Download

Latest release (0.5.7): http://nuclear.mutantstargoat.com/sw/kdtree/files/kdtree-0.5.7.tar.gz

You can find previous releases here: http://nuclear.mutantstargoat.com/sw/kdtree/files/

You can also grab a copy of the source from github: https://github.com/jtsiomb/kdtree

kdtree's Issues

When Insert 7950 nodes, the debug version crash.

What steps will reproduce the problem?

   Check the code attachment.
   When run in VS2010, Win7 64Bit System, debug version will crash, release version no problem.

   After delete the last line "vecTest.push_back(testStruct(3076.0f,2939.0f));" ,  debug will ok.

What is the expected output? What do you see instead?
   debug run success as release version.

What version of the product are you using? On what operating system?


Please provide any additional information below.

Original issue reported on code.google.com by [email protected] on 26 Dec 2014 at 3:27

Attachments:

• test.cpp

kd_res_item3(f) functions don't return node data

What steps will reproduce the problem?
1. call kd_res_item or kd_res_item3 on valid result set
2. check return value


What is the expected output? What do you see instead?
Should return the data value of the node, returns 0


What version of the product are you using? On what operating system?
r32 from svn


Please provide any additional information below.
I attached a patch that fixes the issue.
Also, directly above there are checks like "if(*x)" -- if they are meant to
check for valid x, y, z pointers they should be "if(x)", otherwise the code
segfaults (if you pass in 0). Feel free to change that too. I didn't include it
in the patch since it's not relevant to the problem at hand, and I'm not sure 
whether
the current behaviour is intended.

Original issue reported on code.google.com by [email protected] on 5 Apr 2014 at 9:42

Attachments:

• patch.txt

kd_res_item(f/3/3f)

I don't see these functions defined in kdtree.c.  Am I overlooking
something obvious?

Original issue reported on code.google.com by dound07 on 24 Jul 2007 at 12:34

implemented N nearest neighbors search doesn't work

commented and does't work at all.

Original issue reported on code.google.com by [email protected] on 19 Jul 2010 at 8:39

kd_res_item doesn't properly copy pos

Within the function is a commented description of the problem as well as a
suggested patch.  Hope this helps.

void *kd_res_item(void *set, double *pos)
{
  struct result_set *rset = (struct result_set*)set;

  if(rset->riter) {
    if(pos) {
      //The number of bytes copied is d.  However, this assumes one byte 
      //  per double.  The third argument to memcpy should be 
      //  rset->tree->dim * sizeof(double) so that the correct number 
      //  of bytes are copied
      //original: memcpy(pos, rset->riter->item->pos, rset->tree->dim);
      memcpy(pos, rset->riter->item->pos, rset->tree->dim *
sizeof(double));       
    }
    return rset->riter->item->data;
  }
  return 0;
}

Original issue reported on code.google.com by dound07 on 24 Jul 2007 at 7:20

float versions send buf instead of bptr (pointer to buffer)

What steps will reproduce the problem?
1. use ndim < 16 and float version: insertf, nearestf, nearest_rangef
2.
3.

What is the expected output? What do you see instead?

It segfaults


What version of the product are you using? On what operating system?

svn trunk (rev 29)

Please provide any additional information below.

Attached a patch to fix. There's already two patches but they only fix two of 
the three problem areas. The problem is that, when the dimension is less than 
16 the code does not allocate a new buffer to store the double'd copy of the 
point. Instead, it uses a statically allocated buffer. However, when the double 
version of the same function is called, the pointer that is passed is "buf" 
which is the pointer to the allocated buffer. Instead it should be "bptr" which 
is a pointer to either "buf" or "sbuf" depending on whether or not a new buffer 
was allocated (in the case that dim > 16).

Original issue reported on code.google.com by [email protected] on 6 Apr 2011 at 1:42

Attachments:

• kdtree.c

kd_insertf causes segfault with less then 16 dimensions

What steps will reproduce the problem?
1. Use of kd_insertf with less then 16 dimensions

What version of the product are you using? On what operating system?
0.5.4

Please provide any additional information below.

buf is not set in the path where dim <= 16

Fix:
Line 231:
bptr = buf = sbuf;

Original issue reported on code.google.com by [email protected] on 29 May 2009 at 6:42

kd_nearest_n commented out

Just curious as to why the kd_nearest_n methods are commented out? Are they methods that could be made to work with a little work, or is the reason they are commented out because they are broken?

kd_nearest_i function

the paramter struct kdhyperrect* rect is no change all the time.it's obvious wrong

When Insert 7950 nodes, the debug version crash.

What steps will reproduce the problem?

   Check the code attachment.
   When run in VS2010, Win7 64Bit System, debug version will crash, release version no problem.

   After delete the last line "vecTest.push_back(testStruct(3076.0f,2939.0f));" ,  debug will ok.

What is the expected output? What do you see instead?
   debug run success as release version.

What version of the product are you using? On what operating system?


Please provide any additional information below.

Original issue reported on code.google.com by [email protected] on 26 Dec 2014 at 3:22

the nearest node

Thank you for your code. If I want to get the closet one node, how should I set the radius? Only one nearest node I want to get. Looking forward to your reply.

version numbers

I was wondering why there is a conflict in version numbers? Can you generate a new Makefile.in with the latest major/minor/patch (0.5.6?)

ps. Thanks for sharing and maintaining this library, I've been using it for a while and find it really practical and easy to use :)

free_nodes have a memory leak using node allocator

What steps will reproduce the problem?
1. Port the library to MSCV environment as static library (MT and MD).
2. Use windows threads to allocate and free the result nodes.
3. Debug displayed memory leaks with no details.

What is the expected output? What do you see instead?
-Expected: No memory leaks using allocator.
-Just one of many (Memory leak of 24bytes at 0x057f8ae0) 



What version of the product are you using? On what operating system?
kd-tree lib 0.55/MS Windows XP 

Please provide any additional information below.
I tracked the leak and found that the free_nodes global static variable is
not freed after the use. So

I have solve the problem (added a clear free_node when freeing the kdtree
if there are free_nodes), I will send the code to the project owner the
modifications and the ported code If he/she wants. I've also test the code
in MinGW. Further unitary testing is required. 

Thank you for the lib is very useful. 
I'm new to this Google code stuff, so If I've made any mistake I beg your
pardon. Just needed to contact with the owner and collaborate.

Regards.

Original issue reported on code.google.com by [email protected] on 21 Dec 2009 at 7:44

kd_nearest_rangef causes segfault when dimnsions <= 16

In kd_nearest_rangef, buf is not set to sbuf when dim < 16

Line 301:
bptr = buf = sbuf;

Original issue reported on code.google.com by [email protected] on 29 May 2009 at 10:44

same node problem

What steps will reproduce the problem?
1. insert 10000 same node into kd-tree, d=3, the kd tree can not be built
2.
3.

What is the expected output? What do you see instead?
should be able to finish building the tree, <= nodes should be on the left 
side, but is inserting large number of same nodes, the program is not able 
to finish.(maybe depth problem?)

What version of the product are you using? On what operating system?
5.5, under visual studio 2008 on win xp.

Please provide any additional information below.

Original issue reported on code.google.com by [email protected] on 14 Sep 2009 at 2:37

bug in realse mode

the following test code acts differently in release and debug mode under
visual studio 2008.

int main(int argc, char **argv)
{
    int i, vcount = 10;
    kdtree *kd;

    kdres *set;
    unsigned int msec=0, start=0;

    if(argc > 1 && isdigit(argv[1][0])) {
        vcount = atoi(argv[1]);
    }
    printf("inserting %d random vectors... ", vcount);
    fflush(stdout);

    kd = kd_create(3);

            assert(kd_insert3(kd, 42.1f,44.1f,44.1f, 0)==0);
        assert(kd_insert3(kd, 43.2f,44.1f,44.1f, 0)==0);
        assert(kd_insert3(kd, 44.1f,43.1f,44.1f, 0)==0);
        assert(kd_insert3(kd, 44.1f,45.1f,44.1f, 0)==0);
        assert(kd_insert3(kd, 44.1f,42.1f,44.1f, 0)==0);
        assert(kd_insert3(kd, 44.1f,47.1f,44.1f, 0)==0);

            set = kd_nearest_range3(kd, 44.0f, 44.0f, 44.0f, 10.0f);



    printf("range query returned %d items in %.5f sec\n", kd_res_size(set),
(float)msec / 1000.0);
    kd_res_free(set);

    kd_free(kd);

    getchar();
    return 0;
} 


in the debug mode, there will be 6 nearby neighbors returned by the query,
which is correct. but in the release mode, 0 neighbor will return.

Original issue reported on code.google.com by [email protected] on 11 Aug 2009 at 4:04

find_nearest function

i find that something wrong with find_nearest method,One of the reasons why kdtree saves time is to use the distance from the nearest point to the point to be queried as the radius. If there is no intersection with the hyperplane, you do not need to go to the sibling nodes again. However, this method does not have this crucial step。

Installation with prefix assumes lib and include exist

Installation with prefix failed because it assumed that directories lib and include are already created. I needed to create them by hand and then run make install again.