CODEWITHSUNDEEP
c#algorithmcollision-detection
florian03
florian03

Reputation: 21

Best way to calculate which circles collide

I have a List of about 200 circles.

A circle has a X- and a Y-Coordinate. All circles have the same radius. The range of the coordinates is amount 800 by 400.

Now all circles get moved (the X and Y coordinate changes).

I have to check whether two circles touch each other. I can calculate the distance between two circles and if this ist lower than the double-radius they collide. But if I do this for 200 circles it would take too much time...

Has somebody an more efficient way to find out which circles are touching?

Upvotes: 1

Views: 118

Answers (1)

Jack Punt
Jack Punt

Reputation: 492

There's an algorithm for that (collision detection).

The basic idea is to avoid comparing ALL the circle to ALL the others.

So: divide your space in half: two areas of 400 x 400, then you would likely have only [n/2]^2 comparisons to make.

Then make smaller buckets and it just gets better! In each bucket include those circles that are within 'radius' of the edges of that region.

Basically: make a map from mod([x,y], resolution) => list of circles. Then process each of the [smallish] list entries in the map.

see also: Resources of techniques use for collision detection in 2D?

Upvotes: 3

Related Questions