[cairo] Survey of polygon rasterization techniques

[Behdad Esfahbod]

On Tue, 2007-07-31 at 15:42 -0400, Carl Worth wrote:
> 
> You might take a closer look at these polygons. If I remember
> correctly, polygons 2 and 3 are very large and consist of mostly
> random edges so they have an enormously large number of
> intersections. Cairo's tessellator is an attempt to implement an
> algorithm that is O(Nlog(N+k)) where N is number of edges and k is
> number of intersections. So, if k starts approaching N*N then its
> performance can degrade into O(N*N). 

Humm, Nlog(N+N*N) looks to me more like 2Nlog(N), not N*N.

-- 
behdad
http://behdad.org/

"Those who would give up Essential Liberty to purchase a little
 Temporary Safety, deserve neither Liberty nor Safety."
        -- Benjamin Franklin, 1759