How to detect if object collide with each other if all I have is a list of their positions and their size?

Question

I have a lot of circles and I store their position in a list. All circles have the same radius.

How can I detect if any circle collides with another circle? What would be the fastest way?

Answer 1

Given the Pythagorean Theorem, a^2 + b^2 = c^2, if you take dx = circle[0].x - circle[1].x, dy = circle[0].y - circle[1].y, then you can get the hypotenuse which is the straight-line distance between centers by hypotenuse = Mathf.Sqrt(dx^2 + dy^2);.

However, you don't actually need the distance/hypotenuse, you just need to know if that value is less than 2*r, or two radii, because if the distance between the two circles is less than that then you know they're colliding.

This means that you don't need to take the square root, you can just leave it squared and compare it to the collision distance squared, or (2*r)^2. That is, you are colliding when:

(dx^2 + dy^2) <= (2*r)^2

In code, it looks like:

public class Circle
{
    public float R { get; private set; }
    public float X { get; private set; }
    public float Y { get; private set; }
}
public static bool IsColliding(Circle c0, Circle c1)
{
    var collisionDistance = (c0.R + c1.R)*(c0.R + c1.R);
    var dx = c0.X - c1.X;
    var dy = c0.Y - c1.Y;
    return dx*dx + dy*dy <= collisionDistance;
}

If the radii are all the same then you can cache collisionDistance and not need to recalculate it on each step.

NOTE: My solution here assumes the radii aren't the same; the "2*r" term is replaced by c0.R + c1.R. If they're the same then it reduces to c0.R + c0.R or 2*c0.R.

:EDIT: To check collisions, if you have 4 circles, you'd need to check 1 against 2, 3, and 4. Then, because you already checked 1 against 2 you can skip 2 against 1. You just need to check 2 against 3 and 4, then just 3 against 4.

That is, if you have a List<Circle> circles, you would get:

var nCircles = circles.Count;
for(int i=0; i<nCircles-1; i++)
{
    for(int j=i+1; j<nCircles; j++)
    {
        if(IsColliding(circles[i], circles[j]))
        {
            // Do something
        }
    }
}

This would check 0 against 1,2,3; then 1 against 2,3; then 2 against 3.

Answer 2

Assuming you have a lot of circles (e.g. at least 10,000) and you want to find all circle collisions, you can check each circle against all remaining circles, starting with the first. You can optimize the check by using the bounding box around each circle to filter in only nearby circles, and then test against a diamond inside to filter in close circles and finally test against the full circle to filter out corner circles. Since we know the radius is the same in all cases, we are filtering the centers against a circle of 2*r.

Testing only the circles inside the bounding box is about a 10% speedup, filtering in the circles inside the diamond is about another 1% speedup, and testing in the order given is fastest for collisions of 0.15% to 62% of the total list, but if your list is much smaller, extra tests may cost more time than just the simple test against the bounding circle.

Also if you only care for the first collision for each circle, you can add a break statement after the Add in the if to stop testing once a collision is found.

var r = 3.0;

var ans = new List<(int, int)>();
var r2 = 2 * r;
var r_sq = r2 * r2;

for (int j1 = 0; j1 < circles.Count - 1; ++j1) {
    var c1 = circles[j1];
    for (int j2 = j1 + 1; j2 < circles.Count; ++j2) {
        var c2 = circles[j2];
        var dx = Math.Abs(c1.x - c2.x);
        var dy = Math.Abs(c1.y - c2.y);
        if (dx <= r2 && dy <= r2 && ((dx + dy <= r2) || (dx * dx + dy * dy <= r_sq))) {
            ans.Add((j1, j2));
        }
    }
}

If this isn't sufficient, and you can store your circles in a different structure, it is probably time to look at something like k-d trees.