Circular arc bounding box
CLAUSTRES LUC
compute the axis aligned bounding box
of a circular arc ?
That is a portion of a circle defined using
a start and a end angle.
Thanks.
Ron Capelli
You have radius R, start angle S, end angle T, and I'll
assume that the arc is swept counterclockwise from S to T.
start.x = R * cos(S)
start.y = R * sin(S)
end.x = R * cos(T)
end.y = R * sin(T)
Determine the axis crossings by analyzing the start and
end angles. For discussion sake, I'll describe angles
using degrees. Provide a function, wrap(angle), that
returns an angle in the range [0 to 360).
cross0 = wrap(S) > wrap(T)
cross90 = wrap(S-90) > wrap(T-90)
cross180 = wrap(S-180) > wrap(T-180)
cross270 = wrap(S-270) > wrap(T-270)
Now the axis aligned bounding box is defined by:
right = cross0 ? +R : max(start.x, end.x)
top = cross90 ? +R : max(start.y, end.y)
left = cross180 ? -R : min(start.x, end.x)
bottom = cross270 ? -R : min(start.y, end.y)
I won't claim this is the most efficient algorithm
because there are always tradeoffs. But I hope it's
helpful...
...Ron Capelli (Austin)
Richard J Kinch
> Does somebody know how to efficiently
> compute the axis aligned bounding box
> of a circular arc ?
Locate tangents and endpoints, and sort them.
Horst Kraemer
s: start angle e: end angle
Assuming that the arc is the counterclockwise arc from s to e.
Precondition: 0<=s<360 and 0<=e<360
if (e<s) e=e+360;
xs = r*cos(s);
ys = r*sin(s);
xe = r*cos(e);
ye = r*sin(e);
if (xs<xe)
{
xmin=xs;xmax=xe;
}
else
{
xmin=xe;xmax=xs;
}
if (ys<ye)
{
ymin=ys;ymax=ye;
}
else
{
ymin<=ye;ymax=ys;
}
if (e>90 )
{
if (s<90) ymax=r;
if (e>180)
{
if (s<180) xmin=-r;
if (e>270)
{
if (s<270) ymin=-r;
if (e>360)
{
xmax=r;
if (e>450)
{
ymax=r;
if (e>540)
{
xmin=-r;
if (e>630)
ymin=-r;
}
}
}
}
}
}
--
Horst
Just d' FAQs
First devise a method, then optimize it for specific use. The essence
of any method is that the full circle has x extremes at known angles
and y extremes at known angles. By looking at the start and end angles
alone we can decide which two of the four values is relevant, for x
and for y: the circle minimum, the circle maximum, the start value,
and the end value.
For example, suppose the starting angle is 36.87 degrees, the ending
angle 233.13 degrees. Then we know that we start in the first quadrant
(between 0 and 90 degrees) and end in the third quadrant (between 180
and 270 degrees). Since the minimum circle x is at 180 degrees, that
will be our minimum arc x as well. The maximum circle x, at 0 degrees,
is not part of our arc, and any x value in the first quadrant will be
greater than any in the third, so the maximum arc x will be that of
the start point, 0.8. Similarly, the minimum arc y will be that of the
end point, -0.8; and the maximum arc y will be the circle maximum. Of
course, all the values must be scaled by the radius and offset by the
center.
Making this efficient is an exercise that cannot properly be done in
the absence of a known environment. Should we minimize instructions?
Memory accesses? Unpredictable branches? What is the cost of a test
versus a trig function versus a multiply versus ...?
But here's one possibility. Represent the angle as a fixed point
fraction between 0 and 1. This can be done, for example, by dividing
an angle in degrees by 360 and discarding any integer part. In this
form the top two bits give the quadrant. After choosing one of 16
possible combinations of start and end quadrant, we can again use the
fixed point fraction for a fast table lookup to approximate the trig
functions. We probably don't need large trig tables because bounding
boxes usually don't have to be very precise.
The worst case will be an arc confined to a single quadrant, for which
we must compute four trig functions. However, if we do not need tight
bounds we can avoid all trig, substituting the quadrant extremes for
the true arc extremes.
But before spending much time trying to make this efficient, remember
the 80/20 rule. Put your effort into the 20 percent of the code that
consumes 80 percent of the execution time. This is almost certainly
not in that category, and is better kept simple and clear.