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

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

-
How do you define clockwise or counterclockwise winding? Can you give an example of a set of vertices satisfying this condition without forming a polygon? –  t.b. Jul 20 '11 at 20:44
Do you care about convexity? –  Yuval Filmus Jul 20 '11 at 21:40
add comment

## 2 Answers

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.

-
add comment

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.

-
could you maybe write out the algorithm you think would transfer best to c++ application? Even if i could find a pdf of computational geometry I don't think i would be able to find the equations you speak of... –  Griffin Jul 21 '11 at 0:36
@Griffin, it's probably the Bentley–Ottmann algorithm. See also stackoverflow.com/questions/4407493/… –  lhf Jul 21 '11 at 1:45
add comment