aiiadict@gmail.com wrote: > 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 fadden@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/