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?