1
$\begingroup$

I have a set of $N$ points randomly positionned on a rectangular space (btw with either absorbing, reflecting or wrapping boundaries), and I need to obtain the distances between every 2 points whose distance is at most $2\,r$.

This is akin to consider every point as a disk with radius $r$ and only consider distances between centers of intersecting disks. I know that people doing collision detection are very much into optimizing the detection of intersecting shapes, but it seems that I can make hypotheses that they cannot make in general, and that would maybe help me not to test every 2 points together:

  • There is no motion, only the set of static disks.
  • All shapes are disks.
  • All disks have the same radius $r$.
  • I have a hint that the average distance between 2 neighbouring points is much smaller than $r$, so it will be frequent that numerous disks overlap together.

Are there clever ways to prune among the $\left(\begin{array}{c}N \\ 2\end{array}\right)$ pairs of points and (at best) only calculate distance between points whose disks are intersecting.. or likely to intersect together?

Improve this question
$\endgroup$
5
  • 2
    $\begingroup$ This looks like a job for a spatial partition. $\endgroup$
    – DMGregory
    Nov 11 at 14:32
  • 1
    $\begingroup$ On top of @DMGregory's comment, given that the disks are static, a regular partition (i.e. splitting the rectangular space into a grid rectangles) may well be the most efficient method here. Ideally, you would use a grid where the cells are as close to square in shape as possible, and where the number of cells is roughly $N$. $\endgroup$
    – Pseudonym
    Nov 12 at 5:15
  • $\begingroup$ @DMGregory Thank you, I'll have a look into this :) $\endgroup$
    – iago-lito
    Nov 15 at 8:12
  • $\begingroup$ @Pseudonym Thank you as well. Do you have any explanation why $N$ regular and squared cells would be the most beneficial? $\endgroup$
    – iago-lito
    Nov 15 at 8:13
  • 1
    $\begingroup$ @iago-lito Using $N$ cells means the space usage, and amortised search time, is linear. Using square-shaped cells makes the cell shape as close as practical to a circle, which is the shape that you actually want to search. $\endgroup$
    – Pseudonym
    Nov 15 at 14:08
1
$\begingroup$

Use any standard data structure / algorithm for nearest neighbor search. In particular, you are interested in the fixed-radius nearest neighbor problem, for which there are many algorithms.

Improve this answer
$\endgroup$
2
  • $\begingroup$ I'll also have a look into these, thank you :) Do you happen to know how the nearest neighbour approach compares to spatial partitionning? $\endgroup$
    – iago-lito
    Nov 15 at 8:14
  • 1
    $\begingroup$ @iago-lito, spatial partitioning is one approach to nearest neighbor search, particularly fixed-radius nearest neighbor search. $\endgroup$
    – D.W. ♦
    Nov 15 at 8:17

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.