4
$\begingroup$

Whats the equation to make sure a set of vertices, in clockwise or counterclockwise winding, actually form a polygon (without overlapping edges)?

  • 1
    Do you care about convexity?2011-07-20

2 Answers 2

6

A slower but easier-to-implement algorithm than that suggested by lhf, is to check each segment against every other, and verify that two segments only intersect at an endpoint they share, and that each vertex is shared by exactly two segments. For this you need only robust segment-segment intersection code, which is available on the web in many locations, including here.

3

There is a linear-time algorithm but it depends on Chazelle's famous solution of polygon triangulation in linear time, and so is not practical. There is an $O(n \log n)$ algorithm in the book by Preparata and Shamos.

  • 0
    @Griffin, it's probably the [Bentley–Ottmann algorithm](http://en.wikipedia.org/wiki/Bentley-Ottmann_algorithm). See also http://stackoverflow.com/questions/4407493/existing-bentley-ottmann-algorithm-implementation2011-07-21