如何确定多边形点列表的顺时针顺序？

Question

有一组点的列表，如何判断它们是否按顺时针排序？

例如：

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

我会说这是逆时针方向（或者一些人称之为顺时针）。

- Stécy

---

请注意：接受的答案和许多后续答案需要大量的加减乘除计算（它们基于以正数或负数结束的面积计算；例如“鞋带公式”）。在实施其中之一之前，请考虑 lhf 的答案，它更简单/更快-基于维基百科-简单多边形的方向。 - ToolmakerSteve

我总是从两个相邻向量的叉积角度去考虑。如果我沿着多边形的周长行走，我的头指向平面外。我将平面外向量与行走方向向量进行叉乘，以获得坐标系中的第三个方向。如果该向量指向左侧的内部，则为逆时针；如果指向右侧的内部，则为顺时针。 - duffymo

不降低问题的兴趣，对于那些来到这里并且不想重复造轮子的人，您可以查看GEOS/libgeos源代码，如下所述，以及使用Shapely的小Python片段，其中包含此方向检查。 - swiss_knight

Answer 1

一些建议的方法在非凸多边形（例如新月形）的情况下可能失败。这里有一个简单的方法，可以处理非凸多边形（甚至可以处理像8字形这样的自相交多边形），并告诉你它是否是顺时针方向。

对边进行求和，(x₂ − x₁)(y₂ + y₁)。如果结果为正，则曲线为顺时针；如果结果为负，则曲线为逆时针。（结果是封闭面积的两倍，具有 +/- 约定。）

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

- Beta

---

这是应用微积分于一个简单案例。该线段下的面积等于其平均高度（y2+y1）/2 乘以其水平长度（x2-x1）。请注意 x 的符号约定。用一些三角形尝试一下，很快就会明白它是如何工作的。（我没有技能发布图形。） - Beta

小小的提醒：本答案假定使用普通笛卡尔坐标系。值得一提的是，在某些常见的情境中（如HTML5画布），会使用反转的Y轴。那么规则就需要颠倒：如果面积为负数，曲线就是顺时针方向的。 - LarsH

我的方法是有效的，但如果你跳过了关键部分，那么它就不起作用。这并不是什么新闻。 - Beta

@Mr.Qbs：你必须将最后一个点链接到第一个点。如果你有N个从0到N-1编号的点，则必须计算：对于i = 0到N-1，应计算Sum((x[(i+1) mod N] - x[i]) * (y[i] + y[(i+1) mod N]))。即，必须使用模运算将索引取模为N（N≡0）。该公式仅适用于闭合多边形，多边形没有虚构的边缘。 - Olivier Jacot-Descombes

这个网页（http://blog.element84.com/polygon-winding.html）用简单易懂的英语解释了为什么这个解决方案有效。 - David Zorychta

Answer 2

找到y值最小（如果有并列则选择x值最大）的顶点。让这个顶点为A，在列表中前一个顶点是B，后一个顶点是C。现在计算AB和AC的向量积的符号。

---

参考文献：

• 常问问题：comp.graphics.algorithms中的如何确定简单多边形的方向？

• 维基百科上的曲线方向。

- lhf

---

这也在http://en.wikipedia.org/wiki/Curve_orientation中有解释。关键是找到的点必须在凸包上，并且只需要局部查看凸包上单个点（及其相邻点）的方向，就可以确定整个多边形的方向。 - M Katz

震惊并惊叹这个问题没有得到更多的赞。对于简单多边形（在某些领域中是大多数多边形），此答案提供了一个O(1)的解决方案。所有其他答案都为O(n)，其中n是多边形点的数量。要进行更深层次的优化，请参见维基百科的实用考虑子节，该子节是关于曲线方向的精彩文章。 - Cecil Curry

澄清：仅当以下两种情况之一成立时，此解决方案的时间复杂度为O(1)：**(A)** 多边形为凸多边形（在这种情况下，任意一个顶点都位于凸包上，因此足以满足要求）或 (B) 您已经知道具有最小Y坐标的顶点。如果不符合上述情况（即多边形是非凸多边形且您对其一无所知），则需要进行O(n)搜索。然而，由于不需要求和，因此与其他简单多边形的解决方案相比，这仍然快得多。 - Cecil Curry

以下是此答案的实现：c#代码查找角点并计算该顶点处夹角的行列式。 - ToolmakerSteve

@CecilCurry，我认为你的第二条评论解释了为什么这篇文章没有得到更多的赞。在某些情况下，它会给出错误的答案，而没有提及这些限制。 - LarsH

Answer 3

我提供另一种解决方案，它比较直接，不需要进行复杂的数学计算，只需要使用基本的代数知识。 首先计算多边形的有向面积。如果它是负数，则点按顺时针顺序排列；如果它是正数，则点按逆时针顺序排列。这和 Beta 的解决方案非常相似。

计算多边形的有向面积:

A = 1/2 * (x₁*y₂ - x₂*y₁ + x₂*y₃ - x₃*y₂ + ... + x_n*y₁ - x₁*y_n)

或者使用伪代码表示：

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

- Sean the Bean

---

你上面的有符号面积公式中是否打错了一个字？它以“xny1 - x1yn”结尾，但我认为它应该是“x_n y_{n+1} - y_n x_{n-1}”（至少在LaTeX中是这样）。另一方面，我已经十年没有上过任何线性代数课了。 - Michael Macha

不是的。如果你查看源代码，你会发现公式确实在最后一项中再次引用了第一个点（y1和x1）。 （抱歉，我对LaTeX不是很熟悉，但我格式化了下标以使它们更易读。） - Sean the Bean

我使用了这个解决方案，它完美地适用于我的需求。请注意，如果您可以提前计划并在数组中多留出两个向量，您可以通过将第一个向量添加到数组的尾部来摆脱比较（或%）。这样，您只需要循环遍历所有元素，除了最后一个元素（长度-2而不是长度-1）。 - Eric Fortier

@EricFortier - 顺便说一下，与其调整可能很大的数组大小，一个高效的替代方案是每次迭代将其点保存为“previousPoint”以供下一次迭代使用。在开始循环之前，将“previousPoint”设置为数组的最后一个点。权衡是额外的本地变量副本，但较少的数组访问。最重要的是，不必触摸输入数组。 - ToolmakerSteve

@MichaelEricOberlin - 需要“闭合”多边形，即包括最后一个点到第一个点之间的线段。 （正确的计算结果将相同，无论从哪个点开始闭合多边形。） - ToolmakerSteve

@ToolmakerSteve - 很好的观点。除非您事先知道大小并且可以使用额外元素创建数组，否则您的解决方案是快速的并且可以防止调整大小。 - Eric Fortier

Answer 4

叉积测量了两个向量之间垂直的程度。想象一下，你的多边形每条边都是三维(xyz空间中)的x-y平面上的一个向量。然后，在两个相邻边的叉积是一个指向z方向的向量，如果第二条线段是顺时针，则为正z方向，如果是逆时针，则为负z方向。这个向量的大小与两条原始边之间的夹角正弦成比例，因此当它们垂直时达到最大值，并在边共线(平行)时逐渐减小到消失。

因此，对于多边形的每个顶点，请计算相邻两条边的叉积大小:

Using your data:
point[0] = (5, 0)
point[1] = (6, 4)
point[2] = (4, 5)
point[3] = (1, 5)
point[4] = (1, 0)

将边标记为连续的形式，如下：
edgeA 是从 point0 到 point1 的线段，
edgeB 是从 point1 到 point2 的线段，
...
edgeE 是从 point4 到 point0 的线段。

然后，顶点 A（point0）在以下两条边之间：
edgeE [从 point4 到 point0]
edgeA [从 point0 到 point1]

这两条边本身是向量，其 x 和 y 坐标可以通过减去它们的起点和终点的坐标来确定：

edgeE = point0 - point4 = (1, 0) - (5, 0) = (-4, 0) ，
   edgeA = point1 - point0 = (6, 4) - (1, 0) = (5, 4) ，

这两条相邻边的叉积是通过计算以下矩阵的行列式来计算的。该矩阵将表示三个坐标轴（i，j 和 k）的符号下面的两个向量的坐标放置在一起。第三个（值为零）的坐标存在是因为叉积概念是一个三维构造，因此我们将这些二维向量扩展到三维以应用叉积：

 i    j    k 
-4    0    0
 1    4    0    

考虑到所有的叉积都会产生一个垂直于被乘两个向量的平面的向量，上述矩阵的行列式只有一个 k（或z轴）分量。
计算 k 或 z 轴分量大小的公式是
a1*b2 - a2*b1 = -4* 4 - 0* 1 = -16 这个值(-16)的大小是原始两个向量之间夹角的正弦值，再乘以两个向量长度的乘积。
另外一个计算该值的公式为
A X B (叉积) = |A| * |B| * sin(AB) 因此，如果只需要得到角度的测量结果，则需要将该值 (-16) 除以两个向量长度的乘积。 |A| * |B| = 4 * Sqrt(17) = 16.4924... 所以，sin(AB) 的值为 -16 / 16.4924 = -.97014... 这是下一个顶点后线段向左或向右弯曲程度的测量值。不需要使用反正弦函数。我们关心的只是它的大小和符号（正或负）！

对于封闭路径周围的另外4个点都进行这个计算，然后将每个顶点的计算值相加。

如果最终总和为正，则表示按顺时针方向旋转，如果为负，则表示按逆时针方向旋转。

- Charles Bretana

---

实际上，这个解决方案与被接受的解决方案不同。它们是否等效是我正在调查的问题，但我怀疑它们不是等效的... 被接受的答案通过计算多边形的面积来获得，即通过取多边形顶部和底部之间面积的差值来计算。其中一个值将是负数（当你从左到右穿过时），而另一个值将是正数（当你从右到左穿过时）。当沿顺时针方向遍历时，上边缘是从左到右遍历的，且更长，因此总值为正数。 - Charles Bretana

我的解决方案测量每个顶点边角变化的正弦和。当顺时针遍历时，这将是正数，当逆时针遍历时，这将是负数。 - Charles Bretana

这种方法似乎需要进行arcsin计算，除非您假设凸性（在这种情况下，您只需要检查一个顶点）。 - agentp

确实需要取反正弦值。如果不取反正弦值，对于一些随机的非凸多边形，测试会失败。请尝试一下。 - Luke Hutchison

@CharlesBretana - 虽然我没有运行Luke的测试，但我相信他是正确的。这就是求和与非线性比例尺[有arcsin与无arcsin]的本质。考虑一下marsbear建议的，你正确地拒绝了他的建议。他建议你“只是计数”，而你指出少数大值可能会比大量小值更重要。现在考虑每个值的arcsin与否。难道不是如果未采取arcsin，则给每个值错误的权重，因此具有相同的缺陷（尽管少得多）吗？ - ToolmakerSteve

Answer 5

这是一个基于@Beta的答案的简单C#算法实现。

假设我们有一个Vector类型，具有类型为double的X和Y属性。

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) }));
}

- Olivier Jacot-Descombes

---

你可以通过在循环开始前将“v1 = vertices [vertices.Count-1]”设置，并使用“v2 = vertices [i];”，然后在将其加入到“sum”后执行“v1 = v2”，来避免昂贵的百分比和分支。 - Michel Rouzic

如果点位于对称位置，则此方法无效。以正方形的4个点为例：(-5,-5)(-5,5)(5,5)(5,-5)，即使它们明显是顺时针排序，你也会得到零。 - WDUK

@WDUK，我得到了一个总和为200的结果：(-5 - 5) * (-5 + -5) = 100，(-5 - -5) * (5 + -5) = 0，(5 - -5) * (5 + 5) = 100，(5 - 5) * (-5 + 5) = 0。如果你交换最后两个点，那么总和就是0，此时得到的形状看起来像一个无限符号。 - Olivier Jacot-Descombes

(-5 - 5) * (-5 + -5) = 100 ?The first two points are (-5,-5) and (-5,5)So v2.x - v1.x will always be 0 so how did you get 100 for the first two points?((-5) - (-5)) * ((-5) - 5) = 0 - WDUK

@WDUK，我在我的答案中添加了测试。请注意，第一个总和是从最后一个（v1 = vertices [^ 1]）和第一个（v2）点计算的。因此，您提到的零作为测试中的第二行打印出来。 - Olivier Jacot-Descombes

Answer 6

以下是JavaScript实现Sean的回答：

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));

我很确定这是正确的。它似乎正在工作 :-)

如果你想知道，这些多边形看起来像这样:

- mpen

Answer 7

从其中一个顶点开始，计算每条边对应的角度。

第一条边和最后一条边的角度为零（因此跳过它们）；对于其余的边，正弦值由将(point[n]-point[0])和 (point[n-1]-point[0])的单位长度标准化后进行的叉积给出。

如果这些值的总和为正数，则表示您的多边形是按逆时针方向绘制的。

- Steve Gilham

---

由于叉积基本上可以归结为正比于角度正弦值的缩放因子，所以最好只进行叉积运算。这样会更快速和简单。 - ReaperUnreal

Answer 8

就算价值不高，我也使用这个mixin来计算Google Maps API v3应用程序的绕组顺序。

该代码利用多边形面积的副作用：顶点的顺时针绕组顺序产生正面积，而相同顶点的逆时针绕组顺序则产生与负值相同的面积。该代码还使用了Google Maps几何库中私有API的一种。我觉得可以放心使用-风险自负。

示例用法：

var myPolygon = new google.maps.Polygon({/*options*/});
var isCW = myPolygon.isPathClockwise();

这是一个包含单元测试的完整示例，网址为http://jsfiddle.net/stevejansen/bq2ec/

/** Mixin to extend the behavior of the Google Maps JS API Polygon type
 *  to determine if a polygon path has clockwise of counter-clockwise winding order.
 *  
 *  Tested against v3.14 of the GMaps API.
 *
 *  @author  [e-mail]
 *
 *  @license http://opensource.org/licenses/MIT
 *
 *  @version 1.0
 *
 *  @mixin
 *  
 *  @param {(number|Array|google.maps.MVCArray)} [path] - an optional polygon path; defaults to the first path of the polygon
 *  @returns {boolean} true if the path is clockwise; false if the path is counter-clockwise
 */
(function() {
  var category = 'google.maps.Polygon.isPathClockwise';
     // check that the GMaps API was already loaded
  if (null == google || null == google.maps || null == google.maps.Polygon) {
    console.error(category, 'Google Maps API not found');
    return;
  }
  if (typeof(google.maps.geometry.spherical.computeArea) !== 'function') {
    console.error(category, 'Google Maps geometry library not found');
    return;
  }

  if (typeof(google.maps.geometry.spherical.computeSignedArea) !== 'function') {
    console.error(category, 'Google Maps geometry library private function computeSignedArea() is missing; this may break this mixin');
  }

  function isPathClockwise(path) {
    var self = this,
        isCounterClockwise;

    if (null === path)
      throw new Error('Path is optional, but cannot be null');

    // default to the first path
    if (arguments.length === 0)
        path = self.getPath();

    // support for passing an index number to a path
    if (typeof(path) === 'number')
        path = self.getPaths().getAt(path);

    if (!path instanceof Array && !path instanceof google.maps.MVCArray)
      throw new Error('Path must be an Array or MVCArray');

    // negative polygon areas have counter-clockwise paths
    isCounterClockwise = (google.maps.geometry.spherical.computeSignedArea(path) < 0);

    return (!isCounterClockwise);
  }

  if (typeof(google.maps.Polygon.prototype.isPathClockwise) !== 'function') {
    google.maps.Polygon.prototype.isPathClockwise = isPathClockwise;
  }
})();

- Steve Jansen

---

尝试后，我得到了完全相反的结果。顺时针绘制的多边形面积为负数，而逆时针绘制的则为正数。无论哪种情况，这段代码片段仍然非常有用，感谢您五年来的支持。 - Cameron Roberts

@CameronRoberts 标准做法（特别是在地理JSON方面，参见IETF）是遵循“右手定则”。我猜Google正在抱怨这个问题。在这种情况下，外环必须是逆时针的（产生正面积），而内环（孔）则是顺时针的（负面积需要从主面积中移除）。 - allez l'OM

Answer 9

这是OpenLayers 2实现的功能。拥有顺时针多边形的条件是面积 < 0，这在此参考资料中得到了确认。

function IsClockwise(feature)
{
    if(feature.geometry == null)
        return -1;

    var vertices = feature.geometry.getVertices();
    var area = 0;

    for (var i = 0; i < (vertices.length); i++) {
        j = (i + 1) % vertices.length;

        area += vertices[i].x * vertices[j].y;
        area -= vertices[j].x * vertices[i].y;
        // console.log(area);
    }

    return (area < 0);
}

- MSS

---

Openlayers是一个基于JavaScript的地图管理库，类似于Google Maps，它是用Openlayers 2编写和使用的。 - MSS

你能否简单地解释一下你的代码具体是做什么的，以及为什么要这样做？ - nbro

@nbro 这段代码实现了lhf的答案。通过将_vertices_直接作为参数，可以轻松地将非OpenLayer部分保留在纯JavaScript函数中。它运行良好，并且可以适应_multiPolygon_的情况。 - allez l'OM

Answer 10

以下是实现 lhf的答案 的C#代码：

// 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;
}

- ToolmakerSteve

---

这似乎是针对向下为正Y坐标的情况。对于标准坐标，请进行顺时针/逆时针翻转。 - Warwick Allison

“down-is-positive Y” 是标准坐标系。 - Tatarize

@Tatarize - 这取决于上下文。如果没有给出上下文，通常会认为是向上的。另一方面，由于这是一个计算机图形讨论，可以有不同的观点。笛卡尔坐标系：在数学、物理和工程学中，第一个轴通常被定义或描绘为水平并朝右，第二个轴是垂直的并朝上[强调添加]。（然而，在某些计算机图形上下文中，纵坐标轴可能朝下。） - ToolmakerSteve

这有点取决于上下文。大多数图形包括数学图形都是“向上为正y”，但计算机科学中的许多图形系统都是“向下为正y”。实际上，这里并没有一个“标准”。事实上，在很多项目中，我会在文档中写一个坐标系部分来说明。 - Tatarize

没错，现在我们达成了一致。 - ToolmakerSteve