如何检测由数组中若干个点组成的复杂多边形的顶点是按照顺时针还是逆时针排序定义的？

Question

编辑：我已经更新了程序，这个答案很好用！

我正在制作一个程序（欢迎试用），它可以让用户绘制多边形并将其三角化。他们可以点击添加顶点并按回车键进行三角剖分。不管怎样，只要我告诉算法多边形是顺时针或逆时针绘制的（现在它只能处理顺时针多边形），算法就正常工作。我已经试了几天，但不知道如何确定这些点是顺时针还是逆时针绘制的。您可以使用前面提到的程序尝试绘制图形以更好地了解这一点，您可以亲身体验我所说的内容，效果比我解释更好。

这里是如何定义这些点的：

function Point(x, y) {
    this.x = x;
    this.y = y;
}

var vertices = [];

// Called on click
function addPoint(mouseX, mouseY) {
    vertices.push(new Point(mouseX, mouseY));
}

这是一个顺时针的多边形图像：

这是一个逆时针的多边形图像：

如果你能帮助我找出如何确定点的“顺时针性”，我将不胜感激！

- Conner Ruhl

---

测量每三个点之间的角度，并对整个多边形求和。在一个方向上，您将得到一个正数，在另一个方向上，您将得到一个负数总和。这与您的多边形的顺时针性相对应。 - TMB

刚刚发现了这个问题：https://dev59.com/r3M_5IYBdhLWcg3w6X5e 接受的答案有一个类似的解决方案，但可能比我的更简单。 - kodkod

Answer 1

使用鞋带公式计算多边形面积，但不使用绝对值符号。如果结果为正，则点是逆时针顺序排列的，如果为负则是顺时针。

function polygonArea() { 
    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;
    }
    return area / 2;
}
var clockwise = polygonArea() > 0;

- kodkod

---

完美运行！我添加了一些代码供未来的观众使用。非常感谢！ - Conner Ruhl

既然我们只关心符号，所以没有必要除以二；虽然这并没有太大的区别。 - Samuel Edwin Ward

如果结果为正数，...逆时针旋转，但是clockwise = ... > 0不是说相反的吗？ - Sander Verhagen

Answer 2

如果有人正在使用three.js，则ShapeUtils内置了一个isClockWise方法，该方法在内部使用area方法来确定计算出的面积的符号。

isClockWise: function ( pts ) {

    return ShapeUtils.area( pts ) < 0;

}

您可以在此处找到ShapeUtils.isClockWise方法的代码：这里。

area: function ( contour ) {

    var n = contour.length;
    var a = 0.0;

    for ( var p = n - 1, q = 0; q < n; p = q ++ ) {

        a += contour[ p ].x * contour[ q ].y - contour[ q ].x * contour[ p ].y;

    }

    return a * 0.5;

},

ShapeUtils.area 方法可以在这里找到：这里。

- Wilt

Answer 3

你对顺时针方向的直观定义并不清晰。例如，如果我画一个马蹄铁：

   /---a-b--\
  /   _d_c_  \
 /  /       \ \
 | |        | |
 | |        | |
  \ \       / /
   \ \     / /
    --     --

如果0 = a < b < b < d，我观察a和b，从你的描述中可以得出这个形状是顺时针绘制的，但如果0 = c < d < a < b，我会得出这个形状是逆时针绘制的。由于这两种情况都涉及点绘制的相同方向，只是从不同的起点开始，因此我只能得出你的定义存在缺陷。

我画的马蹄铁不是最好的；想法是它几乎是一个圆，只有在底部有一个小孔，以允许另一侧以相反的方向绘制。

如果您有兴趣更严格地定义事物，那么我建议按以下方式进行：

将任何有限的简单多边形视为将平面分成两个不同的区域（一个有限，一个无限），我们总是可以将有限区域视为多边形的内部。在这种情况下，我们将顶点排序定义为顺时针，当点的顺序沿着其右侧的外部运行时。这被称为curve orientation。

一旦你有了更加明确的定义，实现起来就可以简单地通过计算绕数来完成。取任意有序对的中点，比如0和1，向右取一个线段（在任何角度上，比如垂直），并计算它与其他线段的交点数量：如果数量为奇数，则曲线是顺时针的。

这个实现简单易行，时间复杂度为线性的O(n)，空间复杂度为常数的O(1)。

- davin

---

你可以始终“走”在多边形上，使内部位于左侧。如果编号与此“行走”方向一致，则为逆时针（数学中的正数），否则为顺时针。因此，这个概念是明确定义的！ - Dr_Sam

@Dr_Sam，你说得没错，但这不是OP定义的。如果问题中没有定义内部和外部在哪里，我会同意你的观点。如果没有定义，就像我的例子所解释的那样，就没有方向。 - davin

正如您在编辑后的答案中所说，有一个有界区域和一个无界区域，它们隐含地定义了内部和外部。而问题是关于三角化多边形的，所以我猜测是指内部，即有界部分。顺便说一句，回答得非常好！ - Dr_Sam

Answer 4

一般的想法是查看您多边形的凸包并从那里猜测方向。但是，我认为您不需要建立整个凸包来找到方向，而只需要一个属于它的线段即可。

因此：

- 找到您多边形的两个点，使得所有其他点都位于这条线的一侧。 - 如果所有点都在左侧（只需检查其中一个点），则为逆时针。如果它们在右侧，则为顺时针。

例如：

在上图中：4-5使右图，5-11使右图，... 在下面的图中：6-7使左图，7-14使左图，...

警告：在“走”多边形时，请勿重新开始编号，否则将出错。在上图中，4 -（n-1）使左图！

- Dr_Sam

Answer 5

这是一个专门针对OpenLayers的函数。正如您所看到的，顺时针多边形的条件是area<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