有了一个点列表,我如何确定它们是否是顺时针顺序的?
例如:
point[0] = (5,0)
point[1] = (6,4)
point[2] = (4,5)
point[3] = (1,5)
point[4] = (1,0)
会说它是逆时针的(对某些人来说是逆时针的)
有了一个点列表,我如何确定它们是否是顺时针顺序的?
例如:
point[0] = (5,0)
point[1] = (6,4)
point[2] = (4,5)
point[3] = (1,5)
point[4] = (1,0)
会说它是逆时针的(对某些人来说是逆时针的)
当前回答
在测试了几个不可靠的实现之后,在CW/CCW方向方面提供令人满意结果的算法是由OP在这个线程(shoelace_formula_3)中发布的算法。
与往常一样,正数表示CW方向,而负数表示CCW方向。
其他回答
我将提出另一个解决方案,因为它很简单,不需要大量的数学运算,它只是使用了基本的代数。计算多边形的带符号面积。如果是负的,点是顺时针的,如果是正的,点是逆时针的。(这与Beta的解决方案非常相似。)
计算带符号的面积: A = 1/2 * (x1*y2 - x2*y1 + x2*y3 - x3*y2 +…+ xn*y1 - x1*yn)
或者在伪代码中:
signedArea = 0
for each point in points:
x1 = point[0]
y1 = point[1]
if point is last point
x2 = firstPoint[0]
y2 = firstPoint[1]
else
x2 = nextPoint[0]
y2 = nextPoint[1]
end if
signedArea += (x1 * y2 - x2 * y1)
end for
return signedArea / 2
注意,如果你只是检查顺序,你不需要麻烦除以2。
来源:http://mathworld.wolfram.com/PolygonArea.html
Sean的答案的JavaScript实现:
function calcArea(poly) { if(!poly || poly.length < 3) return null; let end = poly.length - 1; let sum = poly[end][0]*poly[0][1] - poly[0][0]*poly[end][1]; for(let i=0; i<end; ++i) { const n=i+1; sum += poly[i][0]*poly[n][1] - poly[n][0]*poly[i][1]; } return sum; } function isClockwise(poly) { return calcArea(poly) > 0; } let poly = [[352,168],[305,208],[312,256],[366,287],[434,248],[416,186]]; console.log(isClockwise(poly)); let poly2 = [[618,186],[650,170],[701,179],[716,207],[708,247],[666,259],[637,246],[615,219]]; console.log(isClockwise(poly2));
我很确定这是对的。这似乎是有效的:-)
这些多边形看起来是这样的,如果你想知道的话:
解决方案R确定方向和反向如果顺时针(发现这是必要的owin对象):
coords <- cbind(x = c(5,6,4,1,1),y = c(0,4,5,5,0))
a <- numeric()
for (i in 1:dim(coords)[1]){
#print(i)
q <- i + 1
if (i == (dim(coords)[1])) q <- 1
out <- ((coords[q,1]) - (coords[i,1])) * ((coords[q,2]) + (coords[i,2]))
a[q] <- out
rm(q,out)
} #end i loop
rm(i)
a <- sum(a) #-ve is anti-clockwise
b <- cbind(x = rev(coords[,1]), y = rev(coords[,2]))
if (a>0) coords <- b #reverses coords if polygon not traced in anti-clockwise direction
c#代码实现lhf的答案:
// https://en.wikipedia.org/wiki/Curve_orientation#Orientation_of_a_simple_polygon
public static WindingOrder DetermineWindingOrder(IList<Vector2> vertices)
{
int nVerts = vertices.Count;
// If vertices duplicates first as last to represent closed polygon,
// skip last.
Vector2 lastV = vertices[nVerts - 1];
if (lastV.Equals(vertices[0]))
nVerts -= 1;
int iMinVertex = FindCornerVertex(vertices);
// Orientation matrix:
// [ 1 xa ya ]
// O = | 1 xb yb |
// [ 1 xc yc ]
Vector2 a = vertices[WrapAt(iMinVertex - 1, nVerts)];
Vector2 b = vertices[iMinVertex];
Vector2 c = vertices[WrapAt(iMinVertex + 1, nVerts)];
// determinant(O) = (xb*yc + xa*yb + ya*xc) - (ya*xb + yb*xc + xa*yc)
double detOrient = (b.X * c.Y + a.X * b.Y + a.Y * c.X) - (a.Y * b.X + b.Y * c.X + a.X * c.Y);
// TBD: check for "==0", in which case is not defined?
// Can that happen? Do we need to check other vertices / eliminate duplicate vertices?
WindingOrder result = detOrient > 0
? WindingOrder.Clockwise
: WindingOrder.CounterClockwise;
return result;
}
public enum WindingOrder
{
Clockwise,
CounterClockwise
}
// Find vertex along one edge of bounding box.
// In this case, we find smallest y; in case of tie also smallest x.
private static int FindCornerVertex(IList<Vector2> vertices)
{
int iMinVertex = -1;
float minY = float.MaxValue;
float minXAtMinY = float.MaxValue;
for (int i = 0; i < vertices.Count; i++)
{
Vector2 vert = vertices[i];
float y = vert.Y;
if (y > minY)
continue;
if (y == minY)
if (vert.X >= minXAtMinY)
continue;
// Minimum so far.
iMinVertex = i;
minY = y;
minXAtMinY = vert.X;
}
return iMinVertex;
}
// Return value in (0..n-1).
// Works for i in (-n..+infinity).
// If need to allow more negative values, need more complex formula.
private static int WrapAt(int i, int n)
{
// "+n": Moves (-n..) up to (0..).
return (i + n) % n;
}
这是我使用其他答案中的解释的解决方案:
def segments(poly):
"""A sequence of (x,y) numeric coordinates pairs """
return zip(poly, poly[1:] + [poly[0]])
def check_clockwise(poly):
clockwise = False
if (sum(x0*y1 - x1*y0 for ((x0, y0), (x1, y1)) in segments(poly))) < 0:
clockwise = not clockwise
return clockwise
poly = [(2,2),(6,2),(6,6),(2,6)]
check_clockwise(poly)
False
poly = [(2, 6), (6, 6), (6, 2), (2, 2)]
check_clockwise(poly)
True