Sign in to follow this  
Headkaze

2D polygon winding order

Recommended Posts

Headkaze    607
According to this link
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 Poly Area 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 this post


Link to post
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 this post


Link to post
Share on other sites
Headkaze    607
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 this post


Link to post
Share on other sites
Headkaze    607
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 this post


Link to post
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);

Share this post


Link to post
Share on other sites

Create an account or sign in to comment

You need to be a member in order to leave a comment

Create an account

Sign up for a new account in our community. It's easy!

Register a new account

Sign in

Already have an account? Sign in here.

Sign In Now

Sign in to follow this