0

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?

florian03
  • 21
  • 4
  • Please clarify your specific problem or provide additional details to highlight exactly what you need. As it's currently written, it's hard to tell exactly what you're asking. – Community May 17 '22 at 00:40

1 Answers1

2

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?

Jack Punt
  • 342
  • 1
  • 14