有了一个点列表,我如何确定它们是否是顺时针顺序的?
例如:
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)
会说它是逆时针的(对某些人来说是逆时针的)
当前回答
我将提出另一个解决方案,因为它很简单,不需要大量的数学运算,它只是使用了基本的代数。计算多边形的带符号面积。如果是负的,点是顺时针的,如果是正的,点是逆时针的。(这与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
其他回答
我认为为了使某些点顺时针方向,所有的边都必须是正的而不仅仅是边的和。如果一条边是负的,则逆时针方向给出至少3个点。
如果使用Matlab,如果多边形顶点按顺时针顺序排列,函数ispolycw将返回true。
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));
我很确定这是对的。这似乎是有效的:-)
这些多边形看起来是这样的,如果你想知道的话:
我将提出另一个解决方案,因为它很简单,不需要大量的数学运算,它只是使用了基本的代数。计算多边形的带符号面积。如果是负的,点是顺时针的,如果是正的,点是逆时针的。(这与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
一个计算上更简单的方法,如果你已经知道多边形内的一个点:
从原始多边形中选择任意线段,按此顺序选择点及其坐标。 加上一个已知的“内部”点,形成一个三角形。 根据以上三点计算CW或CCW。