Headkaze 607 Report post Posted March 10, 2010 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 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} 0 Share this post Link to post Share on other sites
Sneftel 1788 Report post Posted March 10, 2010 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? 0 Share this post Link to post Share on other sites
Headkaze 607 Report post Posted March 10, 2010 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 expect0,-2640,-2562048,-2562048,-264=false-8,-256-8,5120,5120,-256=false2048,-2562048,5122056,5122056,-256=false0,5040,5122048,5122048,504=false156,93204,93217,98221,108146,108147,97=true70,43570,44255,4440,4450,42743,42864,431=true 0 Share this post Link to post Share on other sites
Headkaze 607 Report post Posted March 10, 2010 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); } 0 Share this post Link to post Share on other sites
oliii 2196 Report post Posted March 11, 2010 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); 0 Share this post Link to post Share on other sites