Whats the equation to make sure a set of vertices, in clockwise or counterclockwise winding, actually form a polygon (without overlapping edges)?
Equation to check if a set of vertices form a real polygon?
4
$\begingroup$
geometry
computational-geometry
-
1How do you define clockwise or counterclockwise winding? Can you give an example of a set of vertices satisfying this condition without forming a polygon? – 2011-07-20
-
1Do you care about convexity? – 2011-07-20
2 Answers
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.
-
0could 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... – 2011-07-21
-
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-implementation – 2011-07-21