Circle Collision Detection HTML5 Canvas

Question

I want to check if circles are colliding with each other.

I know I can do this by getting a distance between the two centers of the circles and subtracting the radius of each circle from that distance and seeing if 'distance' is > 1.

How can I do this efficiently though with say, 1000 circles? Maybe I can somehow get the nearest 20 circles or something like that and check these? I don't know how I would begin to go about that efficiently though either..

Any ideas?

Here is an example:

http://experiments.lionel.me/blocs/

Answer 1

Before you start calculating exact differences in distances, you can at least compare the x/y positions of the centers v.s. the radii. That information is implicitly available in the circle and requires just some simple comparisons and addition/subtraction.

That'll let you compare the simple distances in x/y between all the circle pairs, and throw away any that are obviously not collision candidates, e.g.

abs(x2 - x1) > (r2 + r1)
abs(y2 - y1) > (r2 + r1)

... if the distance in X or Y between the circle centers is greater than the sum of the radii, then they cannot be colliding.

Once you've whittled down the possible colliders, THEN you do the formal exact cartesian distance, which is where the 'heavy' multiplication/division stuff comes in.