[cairo] Survey of polygon rasterization techniques
cworth at cworth.org
Tue Jul 31 16:03:30 PDT 2007
On Tue, 31 Jul 2007 18:21:22 -0400, Behdad Esfahbod wrote:
> > 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.
Sorry, I totally botched that.
Bentley-Ottmann is O((N+k)logN). Meanwhile, the optimal, (but
"complicated enough to be unattractive in practice", according to
Hobby), Chazelle and Edelsbrunner algorithm is O(NlogN+k).
For references, see:
John D. Hobby, Practical Segment Intersection with Finite
Precision Output, Computation Geometry Theory and
Applications, 13(4), 1999.
-------------- next part --------------
A non-text attachment was scrubbed...
Name: not available
Size: 189 bytes
Desc: not available
Url : http://lists.cairographics.org/archives/cairo/attachments/20070731/b77d5a3a/attachment.pgp
More information about the cairo