Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

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

share|cite|improve this question
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
up vote 5 down vote accepted

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.

share|cite|improve this answer

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.

share|cite|improve this answer
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… – lhf Jul 21 '11 at 1:45

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.