programming: fill a circle segment

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

On Tue, 13 Sep 2005 aiiadict@gmail.com wrote:


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

http://www.xcprod.com/titan/XCSB  - optimising PIC compiler
FREE for personal non-commercial use



.