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.
Basic vector algebra suffices here!
[Rewritten on 2016-06-01, using more general solution with the same "cost", number of multiplications, additions, etc.]
Let's assume the blue parallelogram is your bounding box, and the red one (on the right) is the test rectangle -- or, really, any set of points you might wish to test:
You pick one corner of the parallelogram as its origin ($\vec{b}_0 = (x_0, y_0)$). We don't use the point diagonally opposite. We call one edge $\vec{n}_u = (x_u, y_u)$, and another $\vec{n}_v = (x_v, y_v)$; both start at the $\vec{b}_0 = (x_0, y_0)$ point.
Note that this means the other points on the parallelogram are
$$\vec{b}_w = \vec{b}_0 + \vec{n}_u = (x_0 + x_u, \; y_0 + y_u) \\
\vec{b}_h = \vec{b}_0 + \vec{n}_v = (x_0 + x_v, \; y_0 + y_v)$$
and the unmarked fourth point is at $(x_0 + x_u + x_v, \; y_0 + y_u + y_v)$.
We can transform to a coordinate system that is rotated, translated, scaled, and skewed so that the original parallelogram is at coordinates $(0,0)$-$(1,0)$-$(1,1)$-$(0,1)$. Let's call these coordinates $(u,v)$.
To convert back to ordinary coordinates we use
$$\begin{cases}
x = x_0 + u x_u + v x_v \\
y = y_0 + u y_u + v y_v
\end{cases}$$
Solving the above for $u$ and $v$ gives us the interesting conversion to the $(u,v)$ coordinates:
$$\begin{cases}
u = \frac{(x - x_0)y_v - (y - y_0)x_v}{x_u y_v - y_u x_v} \\
v = \frac{(y - y_0)x_u - (x - x_0)y_u}{x_u y_v - y_u x_v} \\
\end{cases}$$
Combining the conversion with the limits shown earlier, we can condense the test. Do note that the divisor (or limit),
$$L = x_u y_v - y_u x_v$$
may be positive or negative. A point $(x,y)$ is inside our bounding parallelogram if and only if
$$L \gt 0: \begin{cases}
0 \le (x - x_0)y_v - (y - y_0)x_v \le L \\
0 \le (y - y_0)x_u - (x - x_0)y_u \le L
\end{cases} \\
L \lt 0: \begin{cases}
0 \le (y - y_0)x_v - (x - x_0)y_v \le -L \\
0 \le (x - x_0)y_u - (y - y_0)x_u \le -L
\end{cases}$$
$L \ne 0$ unless one or both edges are zero length, or if they are parallel. In fact, $L$ is actually the area of the parallelogram; zero $L$ means the parallelogram has zero area (vanishes).
Now, I originally had a "simpler" test using direct projection (dot product, also known as projection product), but it only works if the edges are perpendicular to each other. This one works for squares, rectangles, and parallelograms -- and has exactly the same number of multiplications and additions; only the sign check is extra -- so this one is clearly better choice.
Let's look at OP's example bounding box, with corners at $(1,6)$, $(-6,-5)$, $(2,-9)$, and $(9,3)$. I'll choose, arbitrarily,
$$\begin{cases}
\vec{b}_0 = (-6, -5) \\
\vec{b}_w = (1, 6) \\
\vec{b}_h = (2, -9)
\end{cases} \iff \left\lbrace\begin{array}{ll}
x_0 = -6, & y_0 = -5 \\
x_u = 7, & y_u = 11 \\
x_v = 8, & y_v = -4 \end{array}\right.$$
This means that the fourth point is actually $(-6+7+8,-5+11-4) = (9,2)$, and not $(9,3)$; OP's bounding region is a quadrilateral, not a parallelogram. (Because $\vec{n}_u\cdot\vec{n}_v = 7\cdot8-11\cdot4 = 12 \ne 0$, the edges are not perpendicular; the box is not rectangular either way.)
So, assuming the fourth corner of the bounding parallelogram is at $(9,2)$, we can test for some points. We have
$$L = 7(-4) - 8(11) = -116$$and therefore the inclusion tests are
$$\begin{cases}
0 \; \le \; (y + 5)8 + (x + 6)4 \; \le \; 116\\
0 \; \le \; (x + 6)11 - (y + 5)7 \; \le \; 116
\end{cases}$$
Let's check point $(x,y) = (12, 16)$ first. (We know it has to be outside.)
$$\begin{cases}
(y+5)8 + (x+6)4 = (16+5)8 + (12+6)4 = 240 \\
(x+6)11 - (y+5)7 = (12+6)11 - (16+5)7 = 51
\end{cases}$$
the first is greater than $116$, so the point is definitely outside.
Let's check point $(x,y) = (3,3)$. Remember, OP's diagram has a quadrilateral, which should be fixed to put the fourth corner at $(9,2)$, to make it a quadrilateral.
$$\begin{cases}
(y+5)8 + (x+6)4 = (3+5)8 + (3+6)4 = 100 \\
(x+6)11 - (y+5)7 = (3+6)11 - (3+5)7 = 43
\end{cases}$$
But yes, point $(3,3)$ is inside the fixed quadrilateral, too.
If you have an arbitrary quadrilateral, an arbitrary polygon (convex or concave), there are other methods one can do to determine whether a point is inside it or not. Many of these cases have been asked and answered before, and each of them have different efficient numerical solutions, so combining them all into a single answer is not sensible.
Here is some pseudocode to help with implementation.
Let's assume we have variables
x0,y0 # b0, the origin corner of the bounding parallelogram
xw,yw # bw, another corner of the bounding parallelogram
xh,yh # bh, the third corner of the bounding parallelogram
Each time the above change, I would precalculate five variables:
xu = xw - x0
yu = yw - y0
xv = xh - x0
yv = yh - y0
L = xu * yv - xv * yu
if L < 0:
L = -L
xu = -xu
yv = -yv
else:
xv = -xv
yu = -yu
end if
The above negates the constants when necessary, so that only one case, one set of tests, is left: 0 <= (x-x0)*yv + (y-y0)*xv <= L
and 0 <= (x-x0)*yu + (y-y0)*xu <= L
. This means the test for each point (x,y)
is
u = (x - x0)*yv + (y - y0)*xv
if (u < 0 || u > L):
return OUTSIDE
else:
v = (x - x0)*yu + (y - y0)*xu
if (v < 0 || v > L):
return OUTSIDE
else:
return INSIDE
end if
end if
which boils down to four multiplications, four additions and two subtractions, and four comparisons, maximum, to determine point inclusion in the parallelogram.
Best Answer
This sort of problem has a simple solution that requires no case analysis at all! The point on the rectangle closest to the center of the circle is at coordinates $$\begin{align} x^* &= \operatorname{clamp}(x_c, [x_l, x_l+w]),\\ y^* &= \operatorname{clamp}(y_c, [y_l, y_l+h]),\\ \end{align}$$ where $\operatorname{clamp}(x, [a,b]) = \min(\max(x,a),b)$. The circle and the rectangle overlap if the distance between $(x_c,y_c)$ and $(x^*,y^*)$ is not more than the radius of the circle.
(I'm assuming you care about filled circles and filled rectangles, so you count them as overlapping even if one is entirely inside the other and their boundaries don't meet.)