0
$\begingroup$

I have a set of points A in my space (geo points but I can assume they are on a 2D plane).

I have another set of points B.

For every point in B I want to find every point in A inside a radius R with center in the considered point from B set.

I did it with KDTree, this provide me a very fast and easy algorithm to create the data structure and find neighbours but it doens't find every point in a radius because it could avoid a path which contains element in my radius but not in the same subset of the radius center.

Minimal example of KDTree failing:

While exploring KDTree the target point (red) is under the line of point number 1. This will proceed to exploration of point under the line, this will miss the real point inside the red point radius.

enter image description here

What algorithm or data structure allow 100% correctness?

I know for sure I will performe worse but I am look for a balance between search speed and full correctness.

| cite | improve this question | |
$\endgroup$
  • 2
    $\begingroup$ I don't understand why K-d trees don't work. I don't understand what you mean by "avoid a path". What path are you referring to? I don't understand what is meant by "not in the same subset of the radius center". Can you edit your question to explain that? Perhaps you can use mathematics to help explain, or give a concrete example? $\endgroup$ – D.W.♦ Apr 11 at 20:41
  • $\begingroup$ @D.W. minimal example added $\endgroup$ – Tway101 Apr 12 at 15:45
1
$\begingroup$

The K-D tree is a good data structure for solving this. However you can't blindly apply the search procedure only to the center point, you must be a bit smarter.

While searching the K-D tree for your points, every time you must choose the left or right child to search in, check whether the splitting plane is to the left of your circle, intersects it, or is to the right of the circle.

If the splitting plane is to the left of your circle you must continue searching in the right child, and vice versa. However when the splitting plane intersects your circle you must search both children.

| cite | improve this answer | |
$\endgroup$
  • $\begingroup$ The problem is bigger. I reported a minimal case but sometimes happens that I am checking right child and left but only the child of the child of the child right (or left) is near the center. The minimal example could be avoided just checking if the other child not selected is near the center, but it is not always possible if there other children between $\endgroup$ – Tway101 Apr 12 at 16:18
  • 1
    $\begingroup$ @Tway101 I don't understand what you mean, sorry. $\endgroup$ – orlp Apr 12 at 16:20
  • $\begingroup$ could you provide a minimal example pseudo code to solve the problem? Maybe I didn't understand $\endgroup$ – Tway101 Apr 12 at 16:21
  • $\begingroup$ I think I solved the problem and understand your answer $\endgroup$ – Tway101 Apr 12 at 18:15

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.