Re: [Algorithms] self intersecting polygons

[<chr...@pl...>]

Jonathan Blow wrote:
> It is pretty easy to concoct examples that would convince you an O(n)
> algorithm is impossible.

I believe Chazelle's method in "Triangulating a Simple Polygon in
Linear Time" could be used to detect self-intersections in O(n) time.
Of course, that's a theoretical result, not really a practical one.

For Nils: the term you want to search for is "simplicity test."


Christer Ericson, Director of Tools and Technology
Sony Computer Entertainment, Santa Monica