search_nn seems to hang (kdtree version 0.8)

[vincefernando]

import kdtree A=[(5.1,3.5,1.4,0.2), (4.9,3.0,1.4,0.2), (4.7,3.2,1.3,0.2), (4.6,3.1,1.5,0.2), (5.0,3.6,1.4,0.2), (5.4,3.9,1.7,0.4), (4.6,3.4,1.4,0.3), (5.0,3.4,1.5,0.2), (4.4,2.9,1.4,0.2), (4.9,3.1,1.5,0.1), (5.4,3.7,1.5,0.2), (4.8,3.4,1.6,0.2), (4.8,3.0,1.4,0.1), (4.3,3.0,1.1,0.1), (5.8,4.0,1.2,0.2), (5.7,4.4,1.5,0.4), (5.4,3.9,1.3,0.4), (5.1,3.5,1.4,0.3), (5.7,3.8,1.7,0.3), (5.1,3.8,1.5,0.3), (5.4,3.4,1.7,0.2), (5.1,3.7,1.5,0.4), (4.6,3.6,1.0,0.2), (5.1,3.3,1.7,0.5), (4.8,3.4,1.9,0.2), (5.0,3.0,1.6,0.2), (5.0,3.4,1.6,0.4), (5.2,3.5,1.5,0.2), (5.2,3.4,1.4,0.2), (4.7,3.2,1.6,0.2), (4.8,3.1,1.6,0.2), (5.4,3.4,1.5,0.4), (5.2,4.1,1.5,0.1), (5.5,4.2,1.4,0.2), (4.9,3.1,1.5,0.1), (5.0,3.2,1.2,0.2), (5.5,3.5,1.3,0.2), (4.9,3.1,1.5,0.1), (4.4,3.0,1.3,0.2), (5.1,3.4,1.5,0.2), (5.0,3.5,1.3,0.3), (4.5,2.3,1.3,0.3), (4.4,3.2,1.3,0.2), (5.0,3.5,1.6,0.6), (5.1,3.8,1.9,0.4), (4.8,3.0,1.4,0.3), (5.1,3.8,1.6,0.2), (4.6,3.2,1.4,0.2), (5.3,3.7,1.5,0.2), (5.0,3.3,1.4,0.2)]

p is the 12th element of A

p = ( 4.8,3.0,1.4,0.1) T=kdtree.create(A) print T nn=T.search_nn(p) ~

[stefankoegl]

Thanks for the report! This was caused by the fact that you used duplicate tuples as points (which should be allowed). I've fixed this in 328f6e2449acf0a904fc130908e7f197b7dfdc83 and will release a new version soon.

[vincefernando]

Thanks for the email. Document says that " point must be a location, not a node" in search_nn. As you seem to agree, except perhaps in trivial cases, the user would not know whether a point is identical to a node (to within machine precision). Perhaps, you should include a test to determine whether a point is a node. I noted that the point is the 12th entry of the tree when I complained but I should have emphasized it.

On 1 April 2014 21:37, Stefan Kögl notifications@github.com wrote:

Thanks for the report! This was caused by the fact that you used duplicate tuples as points (which should be allowed). I've fixed this in 328f6e2https://github.com/stefankoegl/kdtree/commit/328f6e2449acf0a904fc130908e7f197b7dfdc83and will release a new version soon.

Reply to this email directly or view it on GitHubhttps://github.com/stefankoegl/kdtree/issues/13#issuecomment-39255553 .

[stefankoegl]

This wasn't the problem. The problem was caused by the fact that points ((4.9,3.1,1.5,0.1)) were contained multiple times in the tree. Nevertheless, this is now fixed in version 0.9 which I just released.

[vincefernando]

Thanks for your corrections. After writing to you, I realised my mistake. At that time I have forgotten that the data set has duplicates.

Unfortunately, I have an array of 199x11 which fails. It has only 138 unique records. I will raise this issue soon after doing more tests. The program seem to work if I remove the duplicates.

I have also tried large data sets (e.g. 10000x16) and they all worked in version 0.9.

On 2 April 2014 18:58, Stefan Kögl notifications@github.com wrote:

This wasn't the problem. The problem was caused by the fact that points ( (4.9,3.1,1.5,0.1)) were contained multiple times in the tree. Nevertheless, this is now fixed in version 0.9 which I just released.

Reply to this email directly or view it on GitHubhttps://github.com/stefankoegl/kdtree/issues/13#issuecomment-39362445 .