4

I have some circles and I know their X, Y, and r. I want to check if ANY of them collide with ANY other...
The way to check is easy:

r1+r2 < sqrt((x1-x2) 2 +(y1-y2)2)

but do I have to check all with all? It gives me O(n2) complexity, and I want to avoid that.

1
  • Do the cycles move, or are they stationary? Mar 3, 2012 at 12:42

4 Answers 4

5

Try looking at KD-tree acc-struct. first you have to consider circles as squares way less complexity for computing intersection , than you put these squares in the modified KD-tree ,it will need some thinking but hopefully nothing too extreme ... Way kd-tree works is that it cancels out half of the possible matches based on some criteria for each tree level. Look it up on wiki. Good luck with your problem :)

1
  • I dont understand this kd-tree at all... But maybe there is easier way... Generaly, I want to check if any unit in my rts is close enough to attack, and I think I can change range to number of points... see "imageshack.us/photo/my-images/4/sthsm.png". So then maybe there is any better way?
    – noisy cat
    Mar 3, 2012 at 11:39
2

You can divide your space into regions, like:

  1. Compute 2D AABB - axis aligned bounding box for all the circles
  2. Divide it into four sub boxes
  3. To each of sub boxes assign circle, if circle even slightly crosses such box then it must be put into such box. This means that circle can be assigned to multiple boxes.
  4. Iterate each circle, then check to which box it was assigned, and compute collision only with circles from that box.

In 2. you can do many subdivisions, depending on your space size, also if to many circles are assigned to one box then subdivide it further.

2

Use square bounding boxes as a simple initial test. Only then move on to circles.

Also

r1+r2 < sqrt((x1-x2)² + (y1-y2)²)

can be re-written as:

(r1+r2)² < (x1-x2)² + (y1-y2)²

which removes that nasty sqrt()

0
0

Are there alot of circles? The best thing in my opinion is to be setting your circles in arrays. So therefore you would have an array of Circles that not only makes them easier to initalise but are all in one place.

Next part is to take the circle and give it a function to test collision. e.g.

void isCol(Array [circles], the current vectors this circle is on. etc);

If a lot of circles

make a for loop that goes through the array checking each ones X, Y and radius values and see whether or not they are in a certain vacinity of the circle. However you should always check whether the circle your looking at is you, if it is then skip that circle. if they are in a region then calculate whether or not any of them are colliding with you and (insert if collision aftermath here).

If theres only a few circles then skip right to checking for collison.

I think what your after is the checking whether the all of the circles are in a range and only dealing with those that are.

Hope this helps.

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.