[cairo] Survey of polygon rasterization techniques

[Carl Worth]

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:

	http://cm.bell-labs.com/who/hobby/93_2-27.pdf

	John D. Hobby, Practical Segment Intersection with Finite
	Precision Output, Computation Geometry Theory and
	Applications, 13(4), 1999.

-Carl

-------------- next part --------------
A non-text attachment was scrubbed...
Name: not available
Type: application/pgp-signature
Size: 189 bytes
Desc: not available
Url : http://lists.cairographics.org/archives/cairo/attachments/20070731/b77d5a3a/attachment.pgp