Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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

share|improve this question
1  
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
1  
Do you care about convexity? –  Yuval Filmus Jul 20 '11 at 21:40
add comment

2 Answers

up vote 4 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|improve this answer
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.

share|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 stackoverflow.com/questions/4407493/… –  lhf Jul 21 '11 at 1:45
add comment

Your Answer

 
discard

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.