Circle - Square Collision Detection
guitar...@gmail.com
a circle and a square?
Luc The Perverse
> Anyone have any quick and simple code for collision detection between
> a circle and a square?
>
Convert to polar coordinates against the orientation of the square from
the center of the square to the center of the circle.
Use trig functions to calculate the exit point of the square on the line
between the two centers and the compare the distances.
I would need to know the orientation and size of your square and circle
to give hard numbers.
But remember the trick is polar coordinates.
On the other hand if you always know that the circle will intersect a
horizontal or vertical wall (no corners hitting) then you can just model
it as the intersection of two squares :)
--
LTP
:)
John Nagle
> Anyone have any quick and simple code for collision detection between
> a circle and a square?
Check the distances between the centers first; eliminate the case
where the circle and square are far enough apart that they can't
possibly touch. After that, do a signed point to line distance calculation
for each edge of the square vs. the center of the circle. If the
signed distance is less than the radius of the circle for all edges,
you have a collision.
Work with squared distances; don't bother with the square roots.
See "http://mathworld.wolfram.com/Point-LineDistance2-Dimensional.html",
eq. (11), but don't bother with the absolute value. Pick a consistent
winding order (clockwise or counterclockwise) for the edges of your squares,
so a positive signed distance will always indicate "outside". It's
mostly adds and multiplies; few divides, no trig functions.
If you have to rotate and translate the square and circle, find
a site that explains basic graphics math and learn how to use rotation
matrices.
John Nagle
Luc The Perverse
This . . . is a much better answer than mine was
--
LTP
:)
Miss Elaine Eos
John Nagle <na...@animats.com> wrote:
> guitar...@gmail.com wrote:
> > Anyone have any quick and simple code for collision detection between
> > a circle and a square?
>
> Check the distances between the centers first; eliminate the case
> where the circle and square are far enough apart that they can't
> possibly touch. After that, do a signed point to line distance calculation
> for each edge of the square vs. the center of the circle. If the
> signed distance is less than the radius of the circle for all edges,
> you have a collision.
If the signed distance is less for ANY edge of the square, right? "All
edges" gives you "square contained in circle" -- right?
(Just checking...)
--
Please take off your pants or I won't read your e-mail.
I will not, no matter how "good" the deal, patronise any business which sends
unsolicited commercial e-mail or that advertises in discussion newsgroups.
John Nagle
> In article <jKeRi.13363$JD....@newssvr21.news.prodigy.net>,
> John Nagle <na...@animats.com> wrote:
>
>> guitar...@gmail.com wrote:
>>> Anyone have any quick and simple code for collision detection between
>>> a circle and a square?
>> Check the distances between the centers first; eliminate the case
>> where the circle and square are far enough apart that they can't
>> possibly touch. After that, do a signed point to line distance calculation
>> for each edge of the square vs. the center of the circle. If the
>> signed distance is less than the radius of the circle for all edges,
>> you have a collision.
>
> If the signed distance is less for ANY edge of the square, right? "All
> edges" gives you "square contained in circle" -- right?
>
> (Just checking...)
Point to line distance, which is just a dot product, is for an
infinite line, not a line segment. It tells you which side of an
infinite line you're on. So you have to check all the edge lines.
(This would be clearer if I could attach an image.)
John Nagle
Miss Elaine Eos
John Nagle <na...@animats.com> wrote:
Even still -- if any two lines are nearer than radius of circle, that's
an intersection, right? You don't need the other two to be inside.
Imagine a circle with a square 45° from it, at the 10:30 position, just
barely intersecting. 1 lines in, 2 lines out.
Right? Am I missing something?
John Nagle
I missed something.
The test I described tests one square against another, or a point against
a square. That's not right for square vs. circle.
The correct test for a circle is
- center of circle inside all four edge lines (in the signed distance
sense). Radius of the circle doesn't matter here.
OR - distance between center of circle and any vertex of the square is
less than the radius of the circle.
The first test determines whether the center of the circle is inside the
square. The second test handles the cases where the circle is near a corner
of the square.
See: http://www.animats.com/private/geometry/boxinsidecircle.gif
John Nagle
Animats
Miss Elaine Eos
John Nagle <na...@animats.com> wrote:
Sorry to keep harping on this -- I don't MEAN to seem argumentative
(it's just a gift! :D)
Imagine this circle/square combo:
+-----------------------+
| |
| |
| |
| |
| |
| |
| |
| |
| |
| |
| _ |
+---------/ \-----------+
\_/
In this,
* Center of circle is outside box
* Distance from center to any corner is > radius.
Yet circle intersects.
I believe the test you gave works for unit circles & squares.
Real Soon Now, I'll dig out code where I did this intersection thing, a
while back... I remember doing it, jsut can't find it!
Richard James
> Anyone have any quick and simple code for collision detection between
> a circle and a square?
How accurate do you need to be?
It might be easier to turn the circle into a square and test for square to
square collisions. Then if that doesn't work for your gameplay mechanics
move to a more complicated solution that does circle to square.
Richard James
John Nagle
> In article <feLRi.4699$wF3....@nlpi061.nbdc.sbc.com>,
> John Nagle <na...@animats.com> wrote:
>
>> The correct test for a circle is
>>
>> - center of circle inside all four edge lines (in the signed distance
>> sense). Radius of the circle doesn't matter here.
>> OR - distance between center of circle and any vertex of the square is
>> less than the radius of the circle.
>>
>> The first test determines whether the center of the circle is inside the
>> square. The second test handles the cases where the circle is near a corner
>> of the square.
>>
>> See: http://www.animats.com/private/geometry/boxinsidecircle.gif
>>
>> John Nagle
>> Animats
>
> Sorry to keep harping on this -- I don't MEAN to seem argumentative
> (it's just a gift! :D)
You're right. The algorithms I've outlined get some cases wrong.
More later.
John Nagle
Anton
Here's my perverted algorithm
__ __ * Cc
Dl = (O,A); Dr = (O,B), \
A,B -- any two adjacent vertexes of the square. \
Cc -- center of the circle \
Rc -- its radius. \
|V| -- stands for length of vector V. '. A \ B .
'.----\--------------.'
1. Quick check (as suggested above by John |'. \ .'|
Nagle) | '. \ .' |
Suspicious for intersention: | '. \ I .' |
| '.\ .' |
|(O,Cc)| <= Rc + |(O,A)| | '.' |
| IV .'O'. II |
If this is satisfied then further | .' '. |
calculation needed. Otherwise there's | .' III '. |
no collision. | .' '. |
.'-----------------'.
2. Precise calculation .' '.
2.1 Find the sign of scalar products:
Sl = sign[(O,Cc)X(Dl)];
Sr = sign[(O,Cc)X(Dr)];
2.2 Then find out in which quadrand the circle's center is located:
Case (Sl, Sr) of
(+,+): I;
(+,-): IV;
(-,+): II;
(-,-): III;
2.3 Now that we know the quadrant, we can just find the distance
between Cc and the corresponding side of the square:
If this_distance <= Rc then collision.
// If you need to check for the circle being fully inside
// the square -- then check whther it's center is inside after
// step 1. Then, if there's no intersection and and center is
// inside, the whole circle is inside.
^
Another way is to calculate only point-line distances: |n1
+-------+
(Choose normal vectors so that they all n4 | | n2
point outside the square) <---| | --->
| |
Using these normals, calculate: +-------+
(Di - signed distance from side i using normal |n3
vector ni) '
(normal vectors)
1. IF [((D1 <Rc) or (D3<Rc)) and
((D4<Rc ) and (D2<Rc] or
[((Abs(D2)<Rc) or (Abs(D4)<Rc)) and
((D1>0) and (D3>0))]
THEN Collision // including the "inside" case!
ELSE No_Collision;
This expression can be rewritten:
(let's designate boolean values of Di<=Rc as Ai)
Collided = A1*A2*A4 + A3*A2*A4 + A2*A1*A3 + A4*A1*A3;
//(* = AND)
//(+ = OR )
This may speed up boolean evaluation.
You begin to calculate this variables one by one,
sequentially, and as soon as you gat Ai = FALSE, you
may be sure that collision is possible only when
the three other variables are TRUE.
IF not A1 then COLLISION = (A2 and A3 and A4) else
IF not A2 then COLLISION = (A1 and A3 and A4) else
IF not A3 then COLLISION = (A1 and A2 and A4) else
IF not A4 then COLLISION = (A1 and A2 and A3) else
COLLISION = TRUE; //...or the circle is inside the square