programming: fill a circle segment

I am looking for description of how to fill a circle segment. The current method I am using fills cells more than once.

the code:

************************************ Input:

Angle (in degrees) Radius (of circle)

output: X,Y's of coordinates that make up the circle segment.

the circle segment is always a 45 degree slice of the circle.

************************************

I don't want just the code. I would like to have some understanding of it.

I have found information about "scan-converting triangles" but the information isn't clear or easy to understand.

the current method I use:

I can calculate the coordinate of a cell with the angle and radius.

*************************************** for RadiusCount = 0 to Radius

for Angle = inputAngle-22.5 to inputAngle + 22.5

;calc pt in circle ar = angle * (3.14/180) x1 = RadiusCount * cos (AR) y1 = RadiusCount * sin (AR)

;do something with the point coordinates

next Angle

next RadiusCount

****************************************

when radiusCount = 1, one cell gets calculated

45 times. I only want the coordinates ONCE.

Rich

Reply to
aiiadict
Loading thread data ...

Here's an idea for a simple algorithm that's also fairly efficient.

Currently (if I understand correctly), you're tracing out an arc, then seeing which cells it intercepts. Instead, this method starts with a subset of cells and eliminates those that aren't inside the arc. The first subset is a square area centered at the arc's focus. This is the square that would bound a circle the size of your radius. All cells outside that bounding box are outside the arc. You don't need to consider them.

Next, divide the square in half. Since your arc is 45 degrees, it will fit completely inside one of four possible semicircles - either the top half, the left half, the bottom, or the right of your initial circle. Choose the semicircle that contains it. Now you can eliminate all cells in the half of the square you discarded. None of them are inside the arc.

The next step will depend on whether you've split the circle vertically or horizontally. I'll just go through the steps for the split that puts your arc in the top half of the initial square. The idea's exactly the same for the other three cases.

Find the furthest left and furthest right extremes of your arc. To do that, consider three points: 1) the focus, 2) the intersection of your arc's lefthand ray with the bounding box and 3) the intersection the arc's righthand ray with the bounding box. The furthest left and furthest right coordinates of these three arc points mark the horizontal extent of the arc. (It might help if you draw this.) You don't need to consider any cells that lie to the left of the leftmost arc point or to the right of the rightmost arc point. You can eliminate those. Pull in the left and right sides of your bounding box. Just to clarify, your bounding box is now as high as your initial square, but the bottom edge has been raised by 1/2 the initial square's height. And the left and right sides (one or both) have been pulled in to just contain the horizontal extent of your arc.

To finish this elimination process, lower the top border of the bounding box one row of cells at a time. For each cell in the row you've just eliminated, look to see if it's within the radius distance from the arc's focus. If it is, it's within the arc. If not, eliminate it. Then recompute the arc's horizontal extent for the new top border and draw in the sides of the bounding box. Repeat until only one cell remains. Add that cell to the list of cells within the arc and stop. You're done.

I've made two assumptions here. First, I've assumed your arc's focus is centered in a cell. Second, I've assumed your cells are square cells in a grid pattern.

I haven't actually coded and tested this. But the basic idea should work. You may have to make a few adjustments.

Hope this helps. Susan

Reply to
Susan Saint Paul

Take the ends of the arc to be A and B and the centre to be C.

Describe the arc AB recording the list of cooridinates for each cell that the arc crosses.

Describe the lines AC and BC recording the list of cooridinates for each cell that the lines cross.

Combine the lists into one list.

Sort this list in Y,X order

Work through this sorted list looking for groups of coordinates for the same Y.

Use the min X coordinate in the group as the start of a horizontal line and the max X in the same group as the end of the line.

repeat the process for all horizontal lines in the sorted list and you will have a list of cells which are only visited once.

This technique also works with polygons, circles and elipses.

Regards Sergio Masci

formatting link
- optimising PIC compiler FREE for personal non-commercial use

.
Reply to
Sergio Masci

PolyTech Forum website is not affiliated with any of the manufacturers or service providers discussed here. All logos and trade names are the property of their respective owners.