Equation to check if a set of vertices form a real polygon?

Question

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

Answer 1

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.

Answer 2

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.