fast way to compute arc + area of circle ?
aiia...@gmail.com
I want to compute which cells
in a graph are covered by a "pie slice"
of a circle.
with an 11X11 grid for illustration purposes,
I have a circle that is 9 cells in diameter,
centered on cell 6,6
0 0 0 0 0 0 0 0 0 0 0
0 0 0 0 * * * 0 0 0 0
0 0 0 * 0 0 0 * 0 0 0
0 0 * 0 0 0 0 0 * 0 0
0 * 0 0 0 0 0 0 0 * 0
0 * 0 0 0 X 0 0 0 * 0
0 * 0 0 0 0 0 0 0 * 0
0 0 * 0 0 0 0 0 * 0 0
0 0 0 * 0 0 0 * 0 0 0
0 0 0 0 * * * 0 0 0 0
0 0 0 0 0 0 0 0 0 0 0
shown here is what I want to compute,
WHICH cells does an arc (from 0degrees
to 90 degrees) cover, including the
area of the circle outlined by lines
extending from the center of the circle
to the ends of the arc ?
0 0 0 0 0 0 0 0 0 0 0
0 0 0 0 * . . 0 0 0 0
0 0 0 * 0 . . . 0 0 0
0 0 * 0 0 . . . . 0 0
0 * 0 0 0 . . . . . 0
0 * 0 0 0 X . . . . 0
0 * 0 0 0 0 0 0 0 * 0
0 0 * 0 0 0 0 0 * 0 0
0 0 0 * 0 0 0 * 0 0 0
0 0 0 0 * * * 0 0 0 0
0 0 0 0 0 0 0 0 0 0 0
X = center
= = area I want to compute X,y's for
As input for this routine, I have:
#1)degrees which arc covers
#2)radius of circle
as output for this routine, I would like:
X,Y locations on grid which are covered
by the arc.
I've looked at the assembly code and
FP routines which have been posted by
others in the last few months, but
I have no clue on how to get started
using it.
Rich
Andy McFadden
> I don't know the geometry term, but
> I want to compute which cells
> in a graph are covered by a "pie slice"
> of a circle.
> As input for this routine, I have:
>
> #1)degrees which arc covers
> #2)radius of circle
>
> as output for this routine, I would like:
>
> X,Y locations on grid which are covered
> by the arc.
You know it's inside the circle if X^2 + Y^2 < R^2 (or <= if you like).
You know it ends in one of four quadrants. If you can solve the problem
for one quadrant, you can solve it for the other three by reflection. (This
is very useful if you want to make it table-driven. You can do it by
octants too, though at some point the added complexity in the logic
overwhelms the other savings.)
For every point in the quadrant, determine the angle to the point. If the
angle exceeds your input angle, the point is outside the circle. From
trig we get tan(theta) = Y / X (assuming a standard Cartesian plane where
theta is zero pointing to the right, and theta is 90 degrees when pointing
upward), which means that theta = arctan(Y/X).
If you were hoping to do it quickly, you can solve it in the first quadrant
by computing the position of a point at radius R pointed in the designated
angle theta: XE = R * cos(theta), YE = R * sin(theta). Draw a line from
(0,0) to (XE,YE) with Bresenham's algorithm. At each position where
you plot a point, however, you draw a solid horizontal line from (X,Y)
to the edge of the circle. You have to compute the edge of the circle
once for each line (XC = sqrt(R^2 - Y^2), but that's cheaper than arc
tangent on every point.
For the output of the routine you can emit an array of horizontal line
descriptions. Each entry represents the start and end of a horizontal
line segment. For your 90-degree radius 11 example, this might look like:
0 5
0 5
0 4
0 3
0 2
This describes one quadrant. If the angle is greater than 90 degrees
(say 100 degrees), you use the result for 90 degrees in the first quadrant,
and the result for 10 degrees in the second (but flipped around the X-axis).
If you want to skip the higher math functions, you can combine Bresenham's
circle algorithm with the "line painting" described above. Bresenham's
algorithm draws a circle by computing one octant using a few adds and
multiplies for each point on the circle. Since you want a pie slice and
not the whole thing you still need to compute and test for the end condition,
but that's pretty easy.
http://www.gamedev.net/reference/articles/article767.asp
http://www.funducode.com/freec/graphics/graphics2.htm#q2#q2
--
Send mail to fad...@fadden.com (Andy McFadden) - http://www.fadden.com/
CD-Recordable FAQ - http://www.cdrfaq.org/
CiderPress Apple II archive utility for Windows - http://www.faddensoft.com/
Fight Internet Spam - http://spam.abuse.net/spam/ & http://spamcop.net/
aiia...@gmail.com
Thanks for your reply. I am going to have to do
some more google research to fully understand
the content, but this is exactly what I am
looking for.
Thank you Andy!
Rich
The Wizard of Oz
> I don't know the geometry term, but
> I want to compute which cells
> in a graph are covered by a "pie slice"
> of a circle.
<snip>
In the subject line you also mention the area of the circle. I'll give
you a couple of formulae. One is more interesting than the other.
Area = Pi * r^2
Pi is a constant. It is an infinite non-repeating real number. Depending
on the level of accuracy you want you would use different approximations.
Here is a formula which gives a better approximation than is in most
calculators.
Pi = 355 / 113
An engineer friend told me the best way to remember it is doubling the
first three odd numbers (113355) and dividing the second three by the
first.
If you want to figure out the area of a pie slice, you can determine the
length of the arc and compare it to the circumference of the circle. Then
look at what percentage of the entire circumference is occupied by the
arc. Multiply the percentage by the volume of the circle and voila... You
have the area of the pie slice.
I wish they gave us interesting problems like this when I took comp. sci..
Later
Mike