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$ Commented Nov 11, 2021 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$ Commented Nov 12, 2021 at 5:15
  • $\begingroup$ @DMGregory Thank you, I'll have a look into this :) $\endgroup$ Commented Nov 15, 2021 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$ Commented Nov 15, 2021 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$ Commented Nov 15, 2021 at 14:08

1 Answer 1

Reset to default
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$ Commented Nov 15, 2021 at 8:14
  • 1
    $\begingroup$ @iago-lito, spatial partitioning is one approach to nearest neighbor search, particularly fixed-radius nearest neighbor search. $\endgroup$ Commented Nov 15, 2021 at 8:17

Start asking to get answers

Find the answer to your question by asking.

Ask question

Explore related questions

See similar questions with these tags.