Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

I have a poor working knowledge of math. I would like to calculate collision detection between a 2D circle and a 2D rectangle for a simple game of Pong.

I thought of splitting the 2D rectangle into 4 separate lines, each with its own equation, and then equating each line equation with the circle's equation to check for intersection points. A search on Math StackExchange turned up this post: solution #1.

(Also: I was wondering why the difference in approach between solution #1 and this solution #2? (EDIT: The difference is that solution #2 solves the intersection of a line segment with a circle while the first solution solves the intersection of a line with a circle.) Why would a person use one over the other? It looks like the first solution is simpler: solving two equations (hey I can do that), whereas the second solution involves parametric equations (which I do not understand)).

I am curious for a different solution though. The solution above checks for an intersection between the equation of a line and the equation of a circle (I think). What about checking the intersection between the equation of a rectangle and a circle? Is that the same thing as saying the intersection between a plane and a circle (is a rectangle a plane)? I thought planes were defined by 3 points ... my rectangle is defined by four. I'm not really sure what I'm saying anymore.

Questions:

  1. Is either solution #1 or solution #2 valid in solving collision detection?
  2. Which solution (#1 or #2) is preferable for what reasons?
  3. How can I calculate the intersection between a 2D rectangle and a 2D circle (without splitting up the rectangle into four separate lines)? Please select the most straightforward solution as its already hard for me to follow the concept of parametric equations. Could you also please explain the solution in some amount of detail? I'm curious as to how the math works.
share|improve this question
1  
Jason, the two solutions you posted are not identical. You are concerned with whether a given line segment intersects a given circle, but "solution 1" is for a general line intersecting a circle. If you draw a picture of it you can see a case where a line may intersect a circle but certainly some segment of that line does not. –  tacos_tacos_tacos Dec 18 '12 at 9:24
    
Ah ok. So it looks like solution "number 2" is really the only solution then. –  Jason Dec 18 '12 at 9:27
    
Is your rectangle allowed to be in any orientation? –  tacos_tacos_tacos Dec 18 '12 at 10:01
    
No. Only horizontal and vertical. What would change if any orientation were allowed? –  Jason Dec 18 '12 at 20:21
    
By the way, if you had many circles and rectangles, it'd be a good idea to first consider circles as the smallest square containing the circle and the, for those who seem to intersect, check if they really intersect. rectangle - rectangle is easy. circle - circle is too because you just need to check the two origins are closer than the sum or the raduises. And for circle - rectangle, you first check square - rectangle and if it says they collide you check circle - rectangle. –  xavierm02 Dec 19 '12 at 12:49

1 Answer 1

up vote 5 down vote accepted

Answers to many questions

is a rectangle a plane?

No, it is not. A plane is infinite in two dimensions, a rectangle has finite size.

I thought planes were defined by 3 points

That is correct but not useful for your application.

my rectangle is defined by four.

As you claim that your rectangle is aligned to the horizontal and vertical directions, two points suffice. For a general rectangle, a third point would be required, or in fact half of a third point (5 real degrees of freedom in total). But this, too, is irrelevant to your question.

the equation of a rectangle

There is no equation for a rectangle, there is only a set of inequalities. Which don't integrate well into the whole setup of dealing with multiple equations.

Is either solution #1 or solution #2 valid in solving collision detection?

Each one will work for a particular use case.

Which solution (#1 or #2) is preferable for what reasons?

As your rectangle is formed by four line segments, solution #2 is the one to take, as your edit in response to the comment by jshin47 already indicates.

The core question

How can I calculate the intersection between a 2D rectangle and a 2D circle (without splitting up the rectangle into four separate lines)?

For the general case of an arbitrary circle and rectangle, I'd go for the intersections between circle and line segments. Avoiding that will only make things more complicated.

Solution #2 sounds like a good starting point. It isn't too hard: If the line segment starts at $(x_1,y_1)$ and ends at $(x_2,y_2)$ and your circle is centered at $(x_C, y_C)$ and has radius $r$, then you have the single non-linear equation

$$ ((1-t)\cdot x_1 + t\cdot x_2 - x_C)^2 + ((1-t)\cdot y_1 + t\cdot y_2 - y_C)^2 = r^2 $$

Solving this equation for $t$, you might find up to two solutions. If these satisfy $0\le t\le1$ then there is an intersection along the line segment. Do this for all four line segments, and if any intersects the circle, then the rectangle intersects the circle.

The above equation originated from the equation of the circle, with a generic point on the line (segment) substituted for $x$ and $y$.

\begin{align*} x &= (1-t)\cdot x_1 + t\cdot x_2 \\ y &= (1-t)\cdot y_1 + t\cdot y_2 \\ r^2 &= (x-x_C)^2 + (y-y_C)^2 \end{align*}

In contrast to this solution, I use $t=0$ to represent the preceived starting point $(x_1,y_1)$ of the line, and $t=1$ for the end point $(x_2,y_2)$. This choice has no impact on your problem, as the direction of your line segments is irrelevant. But it is more useful or common for other applications.

If you have trouble understanding these parametric equations for $x$ and $y$, I suggest you simply choose end points with simple coordinates, and plug in some values of $t$, both from within and outside the specified range. You will see how all of these lie on the connecting line, and the range $0\le t\le 1$ corresponds to the line segment.

Note that all of the above won't deal with the scenario where the circle is fully contained within the rectangle, or vice versa. So you might want to check whether the center of the circle lies within the rectangle, or whether any rectangle corner lies within the circle.

Aligned rectangle

If your rectangle is aligned to the horizontal and vertical axes, you can simplify the intersection checks somewhat. I'd still examine every edge separately, but using a simpler decision making process.

As an example, let's take a horizontal edge, from $(x_1, y)$ to $(x_2, y)$. The circle is still centered at $(x_C, y_C)$ with radius $r$.

  • If $x_1 \le x_C \le x_2$, then the circle intersects the line if $\lvert y - y_C\rvert \le r$. This means that the circle center and the line are no more than $r$ apart.
  • Otherwise, they intersect if $(x_1-x_C)^2+(y-y_C)^2\le r^2$ or $(x_2-x_C)^2+(y-y_C)^2\le r^2$. This means that either endpoint must lie within the circle.
share|improve this answer
    
Wow, thanks for such a detailed response. –  Jason Dec 19 '12 at 21:33

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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