Jump to content
  • Advertisement
Sign in to follow this  
LonelyStar

Minimal Square around arc

This topic is 4833 days old which is more than the 365 day threshold we allow for new replies. Please post a new topic.

If you intended to correct an error in the post then please contact us.

Recommended Posts

Hi everbody, The Problem: I have a arc (part of circle, going from min_angle to max_angle) with radius r. Now I am trying to get the minmal rectangle into which the arc fits. I tried and got stuck in a lot of if-else loops ... and it does not work :( Anybody a Idea of an aproach to master the task? Thanks for any thoughts, Nathan

Share this post


Link to post
Share on other sites
Advertisement
Quote:
Hi everbody,
The Problem:
I have a arc (part of circle, going from min_angle to max_angle) with radius r.
Now I am trying to get the minmal rectangle into which the arc fits. I tried and got stuck in a lot of if-else loops ... and it does not work :(
Anybody a Idea of an aproach to master the task?
Thanks for any thoughts,
Nathan


I think you are going to have two use at least one if statement. As i see it you have two cases: (1) when the angle of the arc is greater than 180 degrees and (2) when it is less than or equal to 180 degrees.


Taking the second case first. One edge of the rectangle will be the end-to-end distance of the arc. If the angle of the arc is theta, then this length is,

2 * r * tan(theta/2).

The other edge of the rectangle is

r * (1 - cos(theta/2)).


The first case. One of the edges of the rectangle lies along the line between the two ends of the arc like in the previous case, only it must extend further. It must extend fair enough to encompass the whole circle, so the length of this edge is 2 * r (i.e. the diameter). The other side is going to be the diameter of the circle less that small slice taken off, which happens to be the same as the height of the arc in the previous case,

2 * r - r * (1 - cos(theta/2)) = r * (1 + cos(theta/2))

Note that theta here is the same as the angle in the previous case. The actual angle of the arc in this case is 360 - theta.


Now, that is one way you can put a rectangle around an arc but I can't claim to know whether it is minimal in any sense. Perhaps someone else has a better solution.


-Josh




Share this post


Link to post
Share on other sites
Hmm...

Sorry, I'm not sure if I've answered your question: In the subject heading you ask for minimal square, but in your post you ask for a rectangle.


-Josh

Share this post


Link to post
Share on other sites
I could be wrong, it's been a while since I had to do anything with arc and angles (maybe to long).


Couldn't the minimal rectangle not be calculated by the following?

X1 = sin(angle1)
Y1 = cos(angle1)
X2 = sin(angle2)
Y2 = cos(angle2)

W = X2 - X1
H = Y2 - Y1

Though this could result in an inside out rectangle.

So it would be more like this:
W = (X2 > X1 ? X2 - X1 : X1 - X2)
H = (Y2 > Y1 ? Y2 - Y1 : Y1 - Y2)


Again, I could be completly wrong on the math, or your intention

Share this post


Link to post
Share on other sites
Well, I think that works if you assume that the center of the circle is at the origin and the angle of the arc is less than or equal to 180. However, the size of the rectangle using your method will depend upon the absolute position of the arc as well.

For instance, suppose you have an arc from a circle of radius 1.0 centered at the origin that starts at (0,1) proceeds anti-clockwise (or counter-clockwise, whichever you prefer [smile]) to (1,0). Using you method we get a 1-by-1 square. If I rotate this arc 45 degrees about the origin so that it begins at (1/sqrt(2),1/sqrt(2)) and finishes at (-1/sqrt(2),1/sqrt(2)) we get a rectangle that is sqrt(2)-by-(1 - 1/sqrt(2)).


-Josh

Share this post


Link to post
Share on other sites
There are six points that are potentially the axis-aligned outliers. Two of those points are the endpoints of the arc. The other four points are the four intersection of the circle with the axes; that is, the points at 0, 90, 180, and 270 degrees; each of these is only in the potential set if it is within the arc. Build this list of points, and then find the maximum and minimum x and y. There's your bounding box.

Share this post


Link to post
Share on other sites
If you want a non-axis-aligned bounding box, simply rotate the arc so that it is reflected on an axis, find the axis-aligned box, then rotate it back by the same amount.

Share this post


Link to post
Share on other sites
I see that I did not give enough information:
The rectangle should be axis aligned!
The origin of the arc is not (0,0). BUt that should not be a problem, or? I can just find the min-rectangle of a arc with origin of (0,0) and than translate it by the arcs position.
THanks for all you answers! I will try your Ideas!

Share this post


Link to post
Share on other sites
Sign in to follow this  

  • Advertisement
×

Important Information

By using GameDev.net, you agree to our community Guidelines, Terms of Use, and Privacy Policy.

We are the game development community.

Whether you are an indie, hobbyist, AAA developer, or just trying to learn, GameDev.net is the place for you to learn, share, and connect with the games industry. Learn more About Us or sign up!

Sign me up!