有了一个点列表,我如何确定它们是否是顺时针顺序的?
例如:
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答案的算法的简单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) }));
}
其他回答
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));
我很确定这是对的。这似乎是有效的:-)
这些多边形看起来是这样的,如果你想知道的话:
下面是基于这个答案的一个简单的Python 3实现(反过来,它是基于已接受答案中提出的解决方案)
def is_clockwise(points):
# points is your list (or array) of 2d points.
assert len(points) > 0
s = 0.0
for p1, p2 in zip(points, points[1:] + [points[0]]):
s += (p2[0] - p1[0]) * (p2[1] + p1[1])
return s > 0.0
对于那些不想“重新发明轮子”的人,我认为值得一提的是,这个检查是在一个名为Shapely (github)的漂亮的Python包中实现的(它基于GEOS C/ c++库):
Shapely is a BSD-licensed Python package for manipulation and analysis of planar geometric objects. It is using the widely deployed open-source geometry library GEOS (the engine of PostGIS, and a port of JTS). Shapely wraps GEOS geometries and operations to provide both a feature rich Geometry interface for singular (scalar) geometries and higher-performance NumPy ufuncs for operations using arrays of geometries. Shapely is not primarily focused on data serialization formats or coordinate systems, but can be readily integrated with packages that are.
来源:https://shapely.readthedocs.io/en/stable/
一个给出OP坐标的小例子:
import numpy as np
from shapely.geometry import Polygon
points = np.array([
(5,0),
(6,4),
(4,5),
(1,5),
(1,0)
])
P = Polygon(points)
这是新构造的多边形:
import matplotlib.pyplot as plt
x,y = P.exterior.coords.xy
plt.plot(x,y)
plt.axis('equal')
plt.grid()
plt.show()
你可以直接使用LinearRing的is_ccw属性来检查多边形是CW还是CCW:
type(P.exterior)
>: shapely.geometry.polygon.LinearRing
P.exterior.is_ccw
>: True
如果颠倒:
points = np.flipud(points)
points
>:
array([[1, 0],
[1, 5],
[4, 5],
[6, 4],
[5, 0]])
P1 = Polygon(points)
P1.exterior.is_ccw
>: True
进一步阅读的文档和参考资料:
shaely is_ccw (github): https://github.com/shapely/shapely/blob/eba985c6e0170ecdd90c83592fd0afa7ae793cb8/shapely/predicates.py#L72-L108 Libgeos (github): https://github.com/libgeos/geos GEOS API参考:https://libgeos.org/doxygen/classgeos_1_1algorithm_1_1Orientation.html#a5af93795969b80f97d7997195974d7c8 GEOS实现(github): https://github.com/libgeos/geos/blob/ab0ce6dafdf7f75ec6d234b6c65bb209037dda17/src/algorithm/Orientation.cpp#L43-L133
在测试了几个不可靠的实现之后,在CW/CCW方向方面提供令人满意结果的算法是由OP在这个线程(shoelace_formula_3)中发布的算法。
与往常一样,正数表示CW方向,而负数表示CCW方向。
求出这些点的质心。
假设有直线从这个点到你们的点。
求line0 line1的两条直线夹角
而不是直线1和直线2
...
...
如果这个角是单调递增的,而不是逆时针递增的,
如果是单调递减,则是顺时针递减
Else(它不是单调的)
你不能决定,所以这是不明智的