Page 1 of 2
Collision Detection Between Circle Segment and Rectangle
Posted: Sat Dec 29, 2012 8:31 pm
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
Re: Collision Detection Between Circle Segment and Rectangle
Posted: Sun Dec 30, 2012 5:16 am
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...
Re: Collision Detection Between Circle Segment and Rectangle
Posted: Sun Dec 30, 2012 9:52 am
by kikito
You might want to give a look to my
Liang-Barsky implementation.
Re: Collision Detection Between Circle Segment and Rectangle
Posted: Sun Dec 30, 2012 6:45 pm
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.
Re: Collision Detection Between Circle Segment and Rectangle
Posted: Mon Dec 31, 2012 12:29 am
by adnzzzzZ
Well, this is an interesting problem! And I see what you mean, Gravy.
- 8bzwK.png (30.72 KiB) Viewed 1002 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 (58.89 KiB) Viewed 1002 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...
Re: Collision Detection Between Circle Segment and Rectangle
Posted: Mon Dec 31, 2012 2:25 am
by Gravy
adnzzzzZ, I found an example where this wouldn't catch the intersection:
- RXM7R.jpg (8.56 KiB) Viewed 1003 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!
Re: Collision Detection Between Circle Segment and Rectangle
Posted: Mon Dec 31, 2012 4:12 am
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
Re: Collision Detection Between Circle Segment and Rectangle
Posted: Mon Dec 31, 2012 5:12 am
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 (21.1 KiB) Viewed 1004 times
I think besides checking distance PQ, R, S and T, you also need to check line segments PR and PS against the rectangle.
Re: Collision Detection Between Circle Segment and Rectangle
Posted: Mon Dec 31, 2012 5:25 am
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.
Re: Collision Detection Between Circle Segment and Rectangle
Posted: Mon Dec 31, 2012 5:33 am
by adnzzzzZ
Ah, I see. I guess that's it then? Hooray!