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
|
