Dave is right that Bentley Ottmann is a good choice. It is O(n*log n) which is an improvement over a simplistic approach which would be O(n^2). Do be careful in implementation to ensure that it catches cases where two points are coincident or one edge passes exactly through another vertex. I saw an implementation which worked fine in all other cases but missed polygons which intersected with itself at a vertex. Don
On Jan 20, 7:27 pm, Dave <[email protected]> wrote: > @Shady: Seehttp://en.wikipedia.org/wiki/Bentley%E2%80%93Ottmann_algorithm. > > Dave > > > > > > > > On Sunday, January 20, 2013 10:02:19 AM UTC-6, shady wrote: > > How to check if polygon is simple based on given list of points ? --
