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

例如:

point[0] = (5,0)
point[1] = (6,4)
point[2] = (4,5)
point[3] = (1,5)
point[4] = (1,0)

会说它是逆时针的(对某些人来说是逆时针的)


当前回答

c#代码实现lhf的答案:

// https://en.wikipedia.org/wiki/Curve_orientation#Orientation_of_a_simple_polygon
public static WindingOrder DetermineWindingOrder(IList<Vector2> vertices)
{
    int nVerts = vertices.Count;
    // If vertices duplicates first as last to represent closed polygon,
    // skip last.
    Vector2 lastV = vertices[nVerts - 1];
    if (lastV.Equals(vertices[0]))
        nVerts -= 1;
    int iMinVertex = FindCornerVertex(vertices);
    // Orientation matrix:
    //     [ 1  xa  ya ]
    // O = | 1  xb  yb |
    //     [ 1  xc  yc ]
    Vector2 a = vertices[WrapAt(iMinVertex - 1, nVerts)];
    Vector2 b = vertices[iMinVertex];
    Vector2 c = vertices[WrapAt(iMinVertex + 1, nVerts)];
    // determinant(O) = (xb*yc + xa*yb + ya*xc) - (ya*xb + yb*xc + xa*yc)
    double detOrient = (b.X * c.Y + a.X * b.Y + a.Y * c.X) - (a.Y * b.X + b.Y * c.X + a.X * c.Y);

    // TBD: check for "==0", in which case is not defined?
    // Can that happen?  Do we need to check other vertices / eliminate duplicate vertices?
    WindingOrder result = detOrient > 0
            ? WindingOrder.Clockwise
            : WindingOrder.CounterClockwise;
    return result;
}

public enum WindingOrder
{
    Clockwise,
    CounterClockwise
}

// Find vertex along one edge of bounding box.
// In this case, we find smallest y; in case of tie also smallest x.
private static int FindCornerVertex(IList<Vector2> vertices)
{
    int iMinVertex = -1;
    float minY = float.MaxValue;
    float minXAtMinY = float.MaxValue;
    for (int i = 0; i < vertices.Count; i++)
    {
        Vector2 vert = vertices[i];
        float y = vert.Y;
        if (y > minY)
            continue;
        if (y == minY)
            if (vert.X >= minXAtMinY)
                continue;

        // Minimum so far.
        iMinVertex = i;
        minY = y;
        minXAtMinY = vert.X;
    }

    return iMinVertex;
}

// Return value in (0..n-1).
// Works for i in (-n..+infinity).
// If need to allow more negative values, need more complex formula.
private static int WrapAt(int i, int n)
{
    // "+n": Moves (-n..) up to (0..).
    return (i + n) % n;
}

其他回答

在测试了几个不可靠的实现之后,在CW/CCW方向方面提供令人满意结果的算法是由OP在这个线程(shoelace_formula_3)中发布的算法。

与往常一样,正数表示CW方向,而负数表示CCW方向。

下面是一个基于@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) }));
}

我的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();



        } 
    }
}

对于那些不想“重新发明轮子”的人,我认为值得一提的是,这个检查是在一个名为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

求出这些点的质心。

假设有直线从这个点到你们的点。

求line0 line1的两条直线夹角

而不是直线1和直线2

...

...

如果这个角是单调递增的,而不是逆时针递增的,

如果是单调递减,则是顺时针递减

Else(它不是单调的)

你不能决定,所以这是不明智的