有了一个点列表,我如何确定它们是否是顺时针顺序的?
例如:
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)
会说它是逆时针的(对某些人来说是逆时针的)
当前回答
求出这些点的质心。
假设有直线从这个点到你们的点。
求line0 line1的两条直线夹角
而不是直线1和直线2
...
...
如果这个角是单调递增的,而不是逆时针递增的,
如果是单调递减,则是顺时针递减
Else(它不是单调的)
你不能决定,所以这是不明智的
其他回答
如果使用Matlab,如果多边形顶点按顺时针顺序排列,函数ispolycw将返回true。
我的c# / LINQ解决方案是基于下面@charlesbretana的交叉积建议的。你可以为线圈指定一个参考法线。只要曲线大部分在向上向量所定义的平面内,它就可以工作。
using System.Collections.Generic;
using System.Linq;
using System.Numerics;
namespace SolidworksAddinFramework.Geometry
{
public static class PlanePolygon
{
/// <summary>
/// Assumes that polygon is closed, ie first and last points are the same
/// </summary>
public static bool Orientation
(this IEnumerable<Vector3> polygon, Vector3 up)
{
var sum = polygon
.Buffer(2, 1) // from Interactive Extensions Nuget Pkg
.Where(b => b.Count == 2)
.Aggregate
( Vector3.Zero
, (p, b) => p + Vector3.Cross(b[0], b[1])
/b[0].Length()/b[1].Length());
return Vector3.Dot(up, sum) > 0;
}
}
}
使用单元测试
namespace SolidworksAddinFramework.Spec.Geometry
{
public class PlanePolygonSpec
{
[Fact]
public void OrientationShouldWork()
{
var points = Sequences.LinSpace(0, Math.PI*2, 100)
.Select(t => new Vector3((float) Math.Cos(t), (float) Math.Sin(t), 0))
.ToList();
points.Orientation(Vector3.UnitZ).Should().BeTrue();
points.Reverse();
points.Orientation(Vector3.UnitZ).Should().BeFalse();
}
}
}
下面是基于这个答案的一个简单的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
一些建议的方法在非凸多边形(如新月形)的情况下会失败。这里有一个简单的方法,它可以用于非凸多边形(它甚至可以用于自相交的多边形,如数字8,告诉你它是否主要是顺时针)。
对边求和,(x2−x1)(y2 + y1)如果结果是正的,曲线是顺时针的,如果结果是负的,曲线是逆时针的。(结果是封闭面积的两倍,采用+/-惯例。)
point[0] = (5,0) edge[0]: (6-5)(4+0) = 4
point[1] = (6,4) edge[1]: (4-6)(5+4) = -18
point[2] = (4,5) edge[2]: (1-4)(5+5) = -30
point[3] = (1,5) edge[3]: (1-1)(0+5) = 0
point[4] = (1,0) edge[4]: (5-1)(0+0) = 0
---
-44 counter-clockwise
正如这篇维基百科文章中所解释的曲线方向,给定平面上的3个点p, q和r(即x和y坐标),您可以计算以下行列式的符号
如果行列式为负(即定向(p, q, r) < 0),则多边形是顺时针方向(CW)。如果行列式为正(即定向(p, q, r) > 0),则多边形是逆时针方向(CCW)。如果点p, q和r共线,行列式为零(即定向(p, q, r) == 0)。
在上面的公式中,由于我们使用的是齐次坐标,我们将1放在p, q和r的坐标前面。