有了一个点列表,我如何确定它们是否是顺时针顺序的?
例如:
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)
会说它是逆时针的(对某些人来说是逆时针的)
当前回答
Javascript实现的lhf的答案 (再次强调,这只适用于简单的多边形,即不适用于图8)
let polygon = [ {x:5,y:0}, {x:6,y:4}, {x:4,y:5}, {x:1,y:5}, {x:1,y:0} ] document.body.innerHTML += `Polygon ${polygon.map(p=>`(${p.x}, ${p.y})`).join(", ")} is clockwise? ${isPolygonClockwise(polygon)}` let reversePolygon = [] polygon.forEach(point=>reversePolygon.unshift(point)) document.body.innerHTML += `<br/>Polygon ${reversePolygon.map(p=>`(${p.x}, ${p.y})`).join(", ")} is clockwise? ${isPolygonClockwise(reversePolygon)}` function isPolygonClockwise (polygon) { // From http://www.faqs.org/faqs/graphics/algorithms-faq/ "How do I find the orientation of a simple polygon?" // THIS SOMETIMES FAILS if the polygon is a figure 8, or similar shape where it crosses over itself // Take the lowest point (break ties with the right-most). if (polygon.length < 3) { return true // A single point or two points can't be clockwise/counterclockwise } let previousPoint = polygon[0] let lowestPoint = polygon[1] let nextPoint = polygon[2] polygon.forEach((point, index)=>{ if (point.y > lowestPoint.y || (point.y === lowestPoint.y && point.x > lowestPoint.x)) { // larger y values are lower, in svgs // Break ties with furthest right previousPoint = polygon[(index-1) >= (0) ? (index-1) : (polygon.length-1)] lowestPoint = polygon[index] nextPoint = polygon[(index+1) <= (polygon.length-1) ? (index+1) : (0)] } }) // Check the angle between the previous point, that point, and the next point. // If the angle is less than PI radians, the polygon is clockwise let angle = findAngle(previousPoint, lowestPoint, nextPoint) return angle < Math.PI } function findAngle(A,B,C) { var AB = Math.atan2(B.y-A.y, B.x-A.x); var BC = Math.atan2(C.y-B.y, C.x-B.x); if (AB < 0) AB += Math.PI*2 if (BC < 0) BC += Math.PI*2 return BC-AB; }
其他回答
下面是一个基于@Beta答案的算法的简单c#实现。
让我们假设我们有一个Vector类型,它的X和Y属性为double类型。
public bool IsClockwise(IList<Vector> vertices)
{
double sum = 0.0;
for (int i = 0; i < vertices.Count; i++) {
Vector v1 = vertices[i];
Vector v2 = vertices[(i + 1) % vertices.Count];
sum += (v2.X - v1.X) * (v2.Y + v1.Y);
}
return sum > 0.0;
}
%是执行模运算的模运算符或余数运算符,该运算符(根据维基百科)在一个数除以另一个数后求余数。
根据@MichelRouzic评论的优化版本:
double sum = 0.0;
Vector v1 = vertices[vertices.Count - 1]; // or vertices[^1] with
// C# 8.0+ and .NET Core
for (int i = 0; i < vertices.Count; i++) {
Vector v2 = vertices[i];
sum += (v2.X - v1.X) * (v2.Y + v1.Y);
v1 = v2;
}
return sum > 0.0;
这不仅节省了模运算%,还节省了数组索引。
测试(参见与@WDUK的讨论)
public static bool IsClockwise(IList<(double X, double Y)> vertices)
{
double sum = 0.0;
var v1 = vertices[^1];
for (int i = 0; i < vertices.Count; i++) {
var v2 = vertices[i];
sum += (v2.X - v1.X) * (v2.Y + v1.Y);
Console.WriteLine($"(({v2.X,2}) - ({v1.X,2})) * (({v2.Y,2}) + ({v1.Y,2})) = {(v2.X - v1.X) * (v2.Y + v1.Y)}");
v1 = v2;
}
Console.WriteLine(sum);
return sum > 0.0;
}
public static void Test()
{
Console.WriteLine(IsClockwise(new[] { (-5.0, -5.0), (-5.0, 5.0), (5.0, 5.0), (5.0, -5.0) }));
// infinity Symbol
//Console.WriteLine(IsClockwise(new[] { (-5.0, -5.0), (-5.0, 5.0), (5.0, -5.0), (5.0, 5.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
解决方案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
另一个解决方案是;
const isClockwise = (vertices=[]) => {
const len = vertices.length;
const sum = vertices.map(({x, y}, index) => {
let nextIndex = index + 1;
if (nextIndex === len) nextIndex = 0;
return {
x1: x,
x2: vertices[nextIndex].x,
y1: x,
y2: vertices[nextIndex].x
}
}).map(({ x1, x2, y1, y2}) => ((x2 - x1) * (y1 + y2))).reduce((a, b) => a + b);
if (sum > -1) return true;
if (sum < 0) return false;
}
把所有的顶点作为一个数组;
const vertices = [{x: 5, y: 0}, {x: 6, y: 4}, {x: 4, y: 5}, {x: 1, y: 5}, {x: 1, y: 0}];
isClockwise(vertices);
在测试了几个不可靠的实现之后,在CW/CCW方向方面提供令人满意结果的算法是由OP在这个线程(shoelace_formula_3)中发布的算法。
与往常一样,正数表示CW方向,而负数表示CCW方向。