Let's say, we have... 50k points randomly allocated in 3D space, according to some volumetric function, so that in some parts of the space, points are closer together, but in other parts, they are further away. Every point has a random color (represented by an integer, for example)
I would like to find all points that:
- Are within a certain (general) distance of each other, and
- are of different color.
What is the fastest way to compute this?
Further, non-mandatory details:
My end goal, is to remove all points with the same color, until there are no more collisions. I would like to remove as few colors as possible, however, this is not mandatory I could simply remove all colors that are involved in any collisions AT ALL, though, it could result in a lower quality result.
The distance does not need to be exact. For instance, if an exact "collision radius" represents a perfect sphere, then I would be fine with the collision radius being the shape of, say, a cube. I am also fine with a trigger-happy solution. That is, I am fine if points get "detected" even if they are not too close. I just don't want this to happen very often, and I cannot accept points that are to close not being detected.
Also, I'm sure there is a family of algorithms devoted to this, but I can't for the life of me come up with any names... Knowing the name of an algorithm of this type would be immensely helpful.