3
\$\begingroup\$

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.

Improve this question
\$\endgroup\$
6
  • \$\begingroup\$ If you know how to implement them, the best thing would be to just test it and see which one is faster. Run 100k iterations or so of both and see who wins. \$\endgroup\$
    – ashes999
    Dec 4, 2012 at 11:01
  • \$\begingroup\$ I do know how to implement them, I just though someone had already tried, also because it might return different results based language, platform, etc. just to have a little more information \$\endgroup\$
    – john smith
    Dec 4, 2012 at 12:06
  • \$\begingroup\$ Have you looked at these at all? \$\endgroup\$
    – ssb
    Dec 4, 2012 at 12:10
  • \$\begingroup\$ Wrong question. You never have "a" circle and "a" rectangle. You probably have many of at least one of these. You should state your exact situation, not a subproblem that will not get you the optimal answer. \$\endgroup\$
    – sam hocevar
    Dec 4, 2012 at 17:08
  • \$\begingroup\$ @SamHocevar I don't see why a general rectangle-circle intersecting algorithm couldn't work here. He most likely has multiple circles and rectangles, but the intersecting algorithm stays same always, no matter what the rectangles or circles are. \$\endgroup\$
    – user9790
    Dec 4, 2012 at 17:09

1 Answer 1

Reset to default
4
\$\begingroup\$

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.

Improve this answer
\$\endgroup\$
2
  • \$\begingroup\$ +1 for cascadingly expensive but more accurate operations as required, this is the way to go \$\endgroup\$
    – ashes999
    Dec 4, 2012 at 14:21
  • 4
    \$\begingroup\$ Also, method B does not require square roots - you can just as well compare to the square of the radius (r^2 <= dx^2 + dy^2), so you have a multiplication instead of a square root. Much faster. \$\endgroup\$
    – opatut
    Dec 4, 2012 at 16:03

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .