circle - rectangle collision in 2D, most efficient way

Question

Suppose I have a circle intersecting a rectangle, what is ideally the least cpu intensive way between the two?

1. method A

   1. calculate rectangle boundaries
   2. loop through all points of the circle and, for each of those, check if inside the rect.

2. method B

   1. calculate rectangle boundaries
   2. check where the center of the circle is, compared to the rectangle

   3. make 9 switch/case statements for the following positions:

      • top, bottom, left, right
      • top left, top right, bottom left, bottom right
      • inside rectangle

   4. check only one distance using the circle's radius depending on where the circle happens t be.

I know there are other ways that are definitely better than these two, and if could point me a link to them, would be great but, exactly between those two, which one would you consider to be better, regarding both performance and quality/precision?

Thanks in advance.

Answer 1

Method B is more precise for a perfect circle. You are talking about running through every point in the circle, in Method A, and I'm assuming that's not small number of points (probably at least 12). Consider, then, that you are looping through points -- and conditionals are slower than non-conditional operations.

On the other hand, method B uses square roots. This is not cheap, but a single square root is almost certainly better than n conditionals.

Having said all of that, I'm pretty certain method B is going to be your best bet if you want both accuracy and good speed.

The correct and standard approach is actually this:

Method C

1. Calculate rectangle bounds (either their own bounds if no rectangle rotation, or their bounding boxes if they are rotated in the plane).
2. Calculate each circle's rectangular bounds.
3. Apply a fast range overlap test in each of x and y axes to check for intersection of bound between object A and B (maybe a rectangle and a circle). If overlap, continue, else break as there is no way they can overlap if their bounds don't overlap.
4. Apply the more expensive test circle-circle or rect-circle intersection test to see if they actually do overlap. This is where the somewhat costly square root ops come in, to determine whether each of the 4 points of the given rect are within the radius of the circle.

A hierarchical approach like this, where you test successive possibilities for elimination, by order of increasing cost (of conditional), is ubiquitous in all forms of collision detection.

Ultimately, you want to avoid conditionals, particularly lengthy loops, inasmuch as possible. See this thread for an idea of precedence. This is why lower level languages such as C offer loop-unrolling as a compile-time optimisation.

EDIT opatut has kindly noted that square roots are not a requirement for methods B & C (see comments), leaving method A as the clear worst method.