有了一个点列表,我如何确定它们是否是顺时针顺序的?

例如:

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的坐标前面。