# 2D polygon winding order

## Recommended Posts

Quote:
 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.
So I have written the following code:
private bool PolyClockwise(List<Point> pointList)
{
float area = 0;

for (int i = 0; i < pointList.Count - 1; i++)
area += (pointList[i].X * pointList[i + 1].Y) - (pointList[i + 1].X * pointList[i].Y);

return (area < 0);
}
But for the following polygon it is returning false when it's clearly clockwise. {X=70,Y=435} {X=70,Y=442} {X=55,Y=444} {X=0,Y=445} {X=0,Y=427} {X=43,Y=428} {X=64,Y=431}

##### Share on other sites
Sneftel    1788
No, that's counterclockwise. Do you have your axes set up right? That is, the Y axis is 90 degrees counterclockwise from the X axis?

##### Share on other sites
This is for an editor where you draw poly's over a picture. The internal format stores the point's as pixel coordinates so x=0,y=0 is the top left hand corner running right and down. Left and up from zero go negative. So how can I modify it to work for this situation. I just seem to be getting random results.

These are the results I expect

0,-264
0,-256
2048,-256
2048,-264
=false

-8,-256
-8,512
0,512
0,-256
=false

2048,-256
2048,512
2056,512
2056,-256
=false

0,504
0,512
2048,512
2048,504
=false

156,93
204,93
217,98
221,108
146,108
147,97
=true

70,435
70,442
55,444
0,445
0,427
43,428
64,431
=true

##### Share on other sites
This worked for me

       private bool PolyClockwise(List<Point> pointList)        {            int area = 0;            for (int i = 0; i < pointList.Count - 1; i++)            {                Point pointStart = new Point(pointList[i].X - pointList[0].X, pointList[i].Y - pointList[0].Y);                Point pointEnd = new Point(pointList[i + 1].X - pointList[0].X, pointList[i + 1].Y - pointList[0].Y);                area += (pointStart.X * -pointEnd.Y) - (pointEnd.X * -pointStart.Y);            }            return (area < 0);        }

##### Share on other sites
oliii    2196
If you have a convex polygon, the cross product of two adjacent edges should suffice. If the cross product is negative, clockwise, else counter-clockwise. That's for a right hand coordinate system, where the cross_product(a, b) = (a.x*b.y - a.y*b.x).

basically, you don't need the sum, just the sign of the first iteration. All subsequent iterations will have the same sign, therefore the sum will have the same sign.

If your first edges are somewhat aligned (cross product near 0.0f), you'll want another set of edges.

Point edge0(pointList[1].X - pointList[0].X, pointList[1].Y - pointList[0].Y);Point edge1(pointList[2].X - pointList[1].X, pointList[2].Y - pointList[1].Y);float sign = (edge0.X * edge1.Y) - (edge0.Y * edge1.X);return (sign < 0);