Sign in to follow this  
CTar

Rectangle inside circular segment

Recommended Posts

If I had a rectangle and a circular segment, how would I determine whether the rectangle is inside the circular segment? I have tried searching, but couldn't find anything. I would also really appreciate it if someone had a reference (book or website) with these kinds of algorithms.

Share this post


Link to post
Share on other sites
If the rectangle must be completely within the circle, it's easy. If the distance from all the rectangles vertices to the circle's center are less than the circle's radius, then the rectangle is inside the circle.

Collision is a bit trickier. First check if any of the vertices are inside the circle. Then, for each line segment of the rectangle, if a line segment perpendicular to the segment, with a length of the circle's diameter whose midpoint is the circle's center intersects with the original segment, the circle and rect collide. I'm not sure if that's the most efficient way or anything, but it should work :P

Share this post


Link to post
Share on other sites
Quote:
Original post by CTar
If I had a rectangle and a circular segment, how would I determine whether the rectangle is inside the circular segment? I have tried searching, but couldn't find anything. I would also really appreciate it if someone had a reference (book or website) with these kinds of algorithms.
What exactly do you mean by circular segment? If you mean part of a circle (an arc), then I'm not sure how a rectangle can be 'inside' such a segment.

As for the boolean circle-rectangle test, it's pretty simple (pseudocode):
bool IntersectCircleRect(Vector2 center, float radius, Vector2 min, Vector2 max)
{
Vector2 closest;
for (int i = 0; i < 2; ++i) {
if (center[i] < min[i]) closest[i] = min[i];
else if (center[i] > max[i]) closest[i] = max[i];
else closest[i] = center[i];
}
return lengthSquared(center - closest) <= radius * radius;
}

Share this post


Link to post
Share on other sites
Quote:
Original post by jonahrowley
The method jyk posted will only work for axis-aligned rects.
True (but the oriented version is almost as simple).

Share this post


Link to post
Share on other sites
Sorry for the late reply. Anyway I mean a part of a circle, didn't know the correct term so looked it up on Wikipedia. I would like it to work with oriented rectangles, but if such an algorithm doesn't exist (very unlikely) I could have to use one with axis aligned rectangles.

Quote:
then I'm not sure how a rectangle can be 'inside' such a segment.

It could be inside it like this:

Share this post


Link to post
Share on other sites
Quote:
Original post by CTar
Sorry for the late reply. Anyway I mean a part of a circle, didn't know the correct term so looked it up on Wikipedia. I would like it to work with oriented rectangles, but if such an algorithm doesn't exist (very unlikely) I could have to use one with axis aligned rectangles.

Quote:
then I'm not sure how a rectangle can be 'inside' such a segment.

It could be inside it like this:
Ah, I see. I think the easiest way to do this test would be to break it down into three parts: test the box against the (complete) circle, and also against the two (infinite) lines forming the 'wedge' of the circle segment. If the box is completely included in the circle, and is on the 'front' side of both lines, the test passes.

The box vs. line test is a simple application of the SAT. For the box vs. circle inclusion test, the fastest way might be (as previously suggested) to test the squared distance between each box corner and the circle center. There might be more elegant methods, but I can't think of any at the moment.

Share this post


Link to post
Share on other sites
Your arc is defined by a center point, two angles referenced from 0 degrees (straight up) and a radius. For each line segment from the verts of the rect to the arc's center, the vert is within the arc if the angle is greater than angle 1, and less than angle 2 of the arc. If the distance between the vert and the arcs center is less than the radius, it's within the arc. If all points pass this test, the rect is inside the arc.

It doesn't matter how irregular or concave the set of points are, it will always work. So this will work for axis-aligned or oriented bounding boxes. Again, I have no idea if this is efficient.

A good resouce for these things are the Graphics Gems series of books.

Share this post


Link to post
Share on other sites

Create an account or sign in to comment

You need to be a member in order to leave a comment

Create an account

Sign up for a new account in our community. It's easy!

Register a new account

Sign in

Already have an account? Sign in here.

Sign In Now

Sign in to follow this