Re: [Algorithms] Draw & fill regular polygon?

[Fabian G. <ry...@gm...>]

On 10.08.2011 23:05, Martin Gladnishki wrote:
> There are also a number of line rasterizing algorithms that do 2, even 3
> pixels per iteration, i.e. with them you will be able to fill the arrays
> faster. Lookup for double-step rasterizing algorithms.
>
> Also, in my experience the extrema arrays are not needed: for convex
> polygons there are only two active edges at a time, therefore you just
> need to traverse the poly in clockwise and anti-clockwise order to
> switch the active edges until they meet at the maximum Y coordinate.

Even for general polygons, the auxiliary arrays aren't necessary; you 
keep a linked list of active edges sorted by their current x coordinate 
(in the last processed scanline). This is fairly simple to code (and 
keep up to date).

 From there, you just need to count the current winding based on the 
orientation of active edges. That allows you to implement all popular 
fill rules.

-Fabian