John Fraser Computer Contest Club

Forums

Post Reply
Forum Home > Turing > Collision Test - Circle to Rectangle

Rui Lin
Moderator
Posts: 8

How to Check Collision Between a Circle and a Rectangle


Theory


It is recommended to understand circle to circle collision first. This will build upon that knowledge.

We'll define the circle and rectangle as follows. Note that x1 <= x2, and y1 <= y2.



Believe it or not we can actually break this down to a much simpler problem, a collision between a circle and a point (which is just a circle of radius 0). We can do this by finding the closest point on the rectangle to the center of the circle.


We'll tackle the x coordinate first.

 

  • if the center of the circle is left of rectangle, then the closest x coordinate is x1
  • if the center of the circle is right of rectangle, then the closest x coordinate is x2
  • if its somewhere between, then the closest x coordinate inside the rectangle is cx
The y coordinate is very similar
  • if the center of the circle is below the rectangle, then the closest y coordinate is y1
  • if the center of the circle is above the rectangle, then the closest y coordinate is y2
  • if its somewhere in between, then the closest y coordinate inside the rectangle is cy
A diagram might help:

In Diagram A, since cx is between the two sides of the rectangle, the closest point on the rectangle must have an x coordinate of cx. Next, since the center of the circle is above the rectangle, then the closest y coordinate on the rectangle is the top y coordinate, ie. y1. We have now found the point on the rectangle closest to the circle (cx, y1)

In Diagram B, since cx is left of the rectangle, then the closest y coordinate is the left side of the rectangle, ie, x1. For the y coordinate, since cy is between y1 and y2, it must be cy. Our newfound closest point is (x1, cy)

We have now reduced the problem to checking if the circle touches the rectangle at its closest point. We can do this easily by checking if the distance between the center of the circle and the closest point of the rectangle is less than or equal to the radius.

Sample Program

% Circle To Rectangle Collision
% Author: Rui Lin

% Checks if a circle intersects a rectangle

function circleIntersectsRectangle (cx : int, cy : int, cr : int, x1 : int, y1 : int, x2 : int, y2 : int) : boolean

var Rx1, Ry1, Rx2, Ry2 : int

var closestX, closestY : int

var deltaX, deltaY : int


% Makes sure x1 <= x2, and y1 <= y2 for the rectangle

Rx1 := min (x1, x2)

Ry1 := min (y1, y2)

Rx2 := max (x1, x2)

Ry2 := max (y1, y2)


% Get the point inside the rectangle closest to the circle

if cx < Rx1 then

closestX := Rx1

elsif cx > Rx2 then

closestX := Rx2

else

closestX := cx

end if

if cy < Ry1 then

closestY := Ry1

elsif cy > Ry2 then

closestY := Ry2

else

closestY := cy

end if


% Use Pythagorean theorem to calculate the distance from the closestXY

% to the centre of the circle.

% If its less than/equal to the radius, collision, else, none.

deltaX := closestX - cx

deltaY := closestY - cy


result (deltaX * deltaX + deltaY * deltaY <= cr * cr)

end circleIntersectsRectangle


proc display

var info : array 1 .. 7 of int

for i : 1 .. 7

info (i) := Rand.Int (0, 400)

end for

info (3) := Rand.Int (1, 100)

drawoval (info (1), info (2), info (3), info (3), red)

drawbox (info (4), info (5), info (6), info (7), blue)

if circleIntersectsRectangle (info (1), info (2), info (3), info (4), info (5), info (6), info (7)) then

put "COLLISION DETECTED!"

else

put "NO COLLISION DETECTED"

end if

end display


loop

cls

display

delay (1000)

end loop
October 10, 2010 at 8:01 PM Flag Quote & Reply

You must login to post.

Members Area