Re: [Algorithms] self intersecting polygons
Brought to you by:
vexxed72
|
From: <chr...@pl...> - 2006-03-13 21:31:11
|
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 |