Talk:K-d tree: Difference between revisions
→C code bug producing incorrect results from k-d tree queries
Line 127:
again to avoid a hang, again following the Wikipedia pseudocode. (Other differences from the Wikipedia pseudocode are OK, I think, and have to do with the way the C code uses pointers instead of indexes, and keeps <code>end</code> pointing a position after the last element rather than to the last element itself.)
I didn't attempt to edit the example myself, partly because I don't know how :->, partly because I didn't want to be presumptuous or offend anyone. But I'm quite sure that the code as it exists is bad; my empirical testing showed that very clearly. It would be good for the code to more rigorously test itself; once the tree is constructed, it is straightforward enough to recursively check that each left/right subtree obeys the spatial partitioning imposed by the coordinate of the parent node. In fact I wrote such test code in my project, along the path to understanding and fixing this bug, and it did flag the tree constructed by the original RosettaCode version of <code>find_median()</code> as having constructed an incorrect tree, and did pass the tree constructed by the algorithm once fixed as described above. Together with a large test dataset that contains many exact duplicate coordinate values, such test code should allow the bug to be confirmed and then the fix validated.
—[[User:Bhaller|Bhaller]] 17:18, 15 August 2017 (UTC)
: Those sound like good observations. I do not have a strong background in kd trees, myself, so I'll leave the code handling for someone else. That said, I'm wondering if it wouldn't make sense to de-dup the points before running the algorithm against them? (I understand that in some graphics applications you might have duplicate copies of the same points, but I'm wondering why that makes sense in the context of a kd-tree?)
: Also, you should sign your comments on discussion pages. The wiki will fill in the details for you if you use <nowiki>--~~~~</nowiki> when you post the comment. This time, though, I manually constructed your signature from information on the history page. Anyways, thanks for taking the time to think this through - it's always good when we have people exercising the code enough to find where it has problems. --[[User:Rdm|Rdm]] ([[User talk:Rdm|talk]]) 18:03, 15 August 2017 (UTC)
| |||