whether clockwise or counterclockwise

picbuddy님의 블로그(Mesh Generation) | 서캐
http://blog.naver.com/picbuddy/80021589591

Determining whether or not a polygon (2D) has its vertices ordered clockwise or counterclockwise

Written by Paul Bourke
March 1998

---

The following describes a method for determining whether or not a polygon has its vertices ordered clockwise or anticlockwise for both convex and concave polygons.
A polygon will be assumed to be described by N vertices, ordered
$$ (x_0,y_0),(x_1,y_1),(x_2,y_2),...(x_{n-1},y_{n-1}) $$ A simple test of vertex ordering for convex polygons is based on considerations of the cross product between adjacent edges.
If the crossproduct is positive then it rises above the plane (z axis up out of the plane) and if negative then the cross product is into the plane.
$$ \begin{aligned} cross product &= ((x_i - x_{i-1}),(y_i - y_{i-1})) \times ((x_{i+1} - x_i),(y_{i+1} - y_i))\\ &= (x_i - x_{i-1}) * (y_{i+1} - y_i) - (y_i - y_{i-1}) * (x_{i+1} - x_i) \end{aligned} $$ A positive cross product means we have a counterclockwise polygon.
To determine the vertex ordering for concave polygons one can use a result from the calculation of polygon areas, where the area is given by

If the above expression is positive then the polygon is ordered counter clockwise otherwise if it is negative then the polygon vertices are ordered clockwise.

Test for concave/convex polygon

For a convex polygon all the cross products of adjacent edges will be the same sign, a concave polygon will have a mixture of cross product signs.

Source Code

Example and test program for testing whether a polygon is convex or concave.
For MS, contributed by G. Adam Stanislav. Source Code

Private Function WhichSide(xp As Long, yp As Long, x1 As Long, y1 As Long, x2 As Long, y2 As Long) As Integer

'Determines which side of a line the point (xp,yp) lies.
'The line goes from (x1,y1) to (x2,y2)
'Returns -1 for a point to the left
'         0 for a point on the line
'        +1 for a point to the right
 
'cross product = ((xi - xi-1),(yi - yi-1)) x ((xi+1 - xi),(yi+1 - yi))
'= (xi - xi-1) * (yi+1 - yi) - (yi - yi-1) * (xi+1 - xi)

'A positive cross product means we have a counterclockwise polygon.

Dim equation As Double

equation = ((yp - y1) * (x2 - x1)) - ((y2 - y1) * (xp - x1))

If equation > 0 Then
    WhichSide = -1
ElseIf equation = 0 Then
    WhichSide = 0
Else
    WhichSide = 1
End If

End Function