Collision Detection Between Circle Segment and Rectangle

Questions about the LÖVE API, installing LÖVE and other support related questions go here.
Forum rules
Before you make a thread asking for help, read this.
Gravy
Citizen
Posts: 80
Joined: Sun Jan 22, 2012 10:15 pm
Location: CA, USA

Collision Detection Between Circle Segment and Rectangle

Post by Gravy »

I've been trying to figure out how to detect collisions between a circle segment and a rectangle, but so far haven't found an easy solution. There are nine inputs: circle segment x and y coordinates, radius, angle, and width, and the rectangle's coordinates, width and height. So, for example, a circle with angle 0 and width pi/4 would be a right-facing quarter circle.

Checking circle and rectangle collision is easy, but this method doesn't seem useful for segments.

Code: Select all

--check if circle and rectangle intersect
function Circle_Rect_Intersect(cX,cY, cR, rX, rY, rW, rH)
	if Point_Rect_Intersect(cX, cY, rX, rY, rW, rH) then
		return true
	else
		local closestX = clamp(cX, rX, rX + rW)
		local closestY = clamp(cY, rY, rY + rH)
		local distX = cX - closestX
		local distY = cY - closestY
		local sqrDist = (distX * distX) + (distY * distY)
		return sqrDist < cR * cR
	end
end

--Check if point is inside rectangle
function Point_Rect_Intersect(pX, pY, rX, rY, rW, rH)
	return pX > rX and pX < rX + rW and pY > rY and pY < rY + rH
end

function clamp(v, min, max)
	if v < min then return min 
	elseif v > max then return max
	else return v end
end
User avatar
adnzzzzZ
Party member
Posts: 305
Joined: Sun Dec 26, 2010 11:04 pm
Location: Porto Alegre, Brazil

Re: Collision Detection Between Circle Segment and Rectangle

Post by adnzzzzZ »

1. Find closest point Q in rectangle from circle's center P.
2. Find distance PQ = d. If d > circle's radius R then they aren't intersecting, else:
3. Find angle PQ = r. If r between [-width/2, width/2] then they are intersecting, else no intersection.

? I haven't tested this at all but I feel it should work...
User avatar
kikito
Inner party member
Posts: 3153
Joined: Sat Oct 03, 2009 5:22 pm
Location: Madrid, Spain
Contact:

Re: Collision Detection Between Circle Segment and Rectangle

Post by kikito »

You might want to give a look to my Liang-Barsky implementation.
When I write def I mean function.
Gravy
Citizen
Posts: 80
Joined: Sun Jan 22, 2012 10:15 pm
Location: CA, USA

Re: Collision Detection Between Circle Segment and Rectangle

Post by Gravy »

adnzzzzZ, that approach was the first thing I tried, but it doesn't work, since the closest point might not be in the angle, but another point of the rectangle might. I played around with special cases to see if I could test a small number of points, but I don't think it works.

kikito, Liang-Barsky seems to be for testing line segments against boxes, not circle segments. I would have to run this for a large number of line segments from the center of the circle to points along the radius, and it wouldn't be 100% effective.
User avatar
adnzzzzZ
Party member
Posts: 305
Joined: Sun Dec 26, 2010 11:04 pm
Location: Porto Alegre, Brazil

Re: Collision Detection Between Circle Segment and Rectangle

Post by adnzzzzZ »

Well, this is an interesting problem! And I see what you mean, Gravy.
8bzwK.png
8bzwK.png (30.72 KiB) Viewed 1003 times
So, the problem you pointed out with the algorithm can be seen on the left side, I guess. I'd be finding d to be < R, so I'd move to seeing if q is between [-width/2, width/2] and since it isn't, I would conclude that there's no collision when the area outlined in blue is obviously colliding.

So I thought about probing for points r and s and seeing if one of them is colliding or not, and in the left case it works, since r is intersecting. But then it doesn't work on the right case: r and s aren't intersecting but there's still a section between them that is.

To fix this, you can also probe an additional point t that points in the direction of your angle.
fUSnh.png
fUSnh.png (58.89 KiB) Viewed 1003 times
In the image above you can see that regardless of your angle and width, whenever there's a collision at least one of r, s or t is intersecting. So probing for those points will give you the answer.

So the solution would now be:

1. Find closest point Q in rectangle from circle's center P.
2. Find distance PQ = d. If d > circle's radius R then they aren't intersecting, else: (this needs to still be found so we can rule out early, and a segment will only be colliding if this distance is < R anyway)
3. Find point T and check for collision. If intersecting then you're done, else:
4. Find points R and S and check for collision. If intersecting then you're done, else my algorithm is wrong...
Gravy
Citizen
Posts: 80
Joined: Sun Jan 22, 2012 10:15 pm
Location: CA, USA

Re: Collision Detection Between Circle Segment and Rectangle

Post by Gravy »

adnzzzzZ, I found an example where this wouldn't catch the intersection:
RXM7R.jpg
RXM7R.jpg (8.56 KiB) Viewed 1004 times
But if we then check to see whether any of the corners of the rectangle are within the cone, this would be caught. So we check the closest point, R, S, and T, and the four corners, for a total of 8 calculations. That's not too bad. (Although we should also check to see whether the center of the circle is within the rectangle in the first place.)

I've been trying to come up with another counterexample, but I haven't been able to. I think it is true that either one of R,S, or T is within the rectangle or one of the corners is within the cone, or else the closest point is within the cone (this last case occurs when the rectangle passes between a small chord of the circle that does not contain R,S, or T).

Awesome! I think we did it. I'm fairly confident that there are no more counterexamples, but I might keep trying to find one :)

Thanks for your help!
scutheotaku
Party member
Posts: 235
Joined: Sat Dec 15, 2012 6:54 am

Re: Collision Detection Between Circle Segment and Rectangle

Post by scutheotaku »

What about using something like the Circle-line intersection test from here: http://devmag.org.za/2009/04/17/basic-c ... 2d-part-2/
Then if it's colliding with only one point (delta = 0), then you use the method adnzzzzZ described to check if its colliding with that particular circle segment.
If it's colliding at two points (delta > 0), then you simply have to compare the two points to your circle segment.

To my sleepy brain, this seems like it would work ^^
User avatar
adnzzzzZ
Party member
Posts: 305
Joined: Sun Dec 26, 2010 11:04 pm
Location: Porto Alegre, Brazil

Re: Collision Detection Between Circle Segment and Rectangle

Post by adnzzzzZ »

I don't think checking the four corners will work (I guess it works but it misses this case), for instance:
a0rem.png
a0rem.png (21.1 KiB) Viewed 1005 times
I think besides checking distance PQ, R, S and T, you also need to check line segments PR and PS against the rectangle.
Gravy
Citizen
Posts: 80
Joined: Sun Jan 22, 2012 10:15 pm
Location: CA, USA

Re: Collision Detection Between Circle Segment and Rectangle

Post by Gravy »

Scu, the problem is that there could be places inside the circle where the rectangle intersects the segment, not just on the perimeter, like in the picture I attached.

adnz, I am assuming that the circle segment always starts in the center of the circle. But even in this case, the closest point to the bottom dot is inside the cone, so this should get caught.
User avatar
adnzzzzZ
Party member
Posts: 305
Joined: Sun Dec 26, 2010 11:04 pm
Location: Porto Alegre, Brazil

Re: Collision Detection Between Circle Segment and Rectangle

Post by adnzzzzZ »

Ah, I see. I guess that's it then? Hooray!
Post Reply

Who is online

Users browsing this forum: Ahrefs [Bot] and 3 guests