javascript - 检测数组中作为复杂多边形顶点的一组点是否按顺时针或逆时针顺序定义？

Question

编辑:我更新了 program有了答案，效果很好!

我正在制作 program (请随意尝试)让用户绘制多边形，然后对其进行三 Angular 剖分。他们可以单击以添加顶点并按 Enter 键进行三 Angular 剖分。无论如何，只要我告诉它这些点是以顺时针还是逆时针方式绘制的，该算法就可以正常工作(现在我将其设置为仅适用于顺时针多边形)。几天来我一直在努力解决这个问题，但不知道如何确定这些点是顺时针还是逆时针。尝试使用前面提到的程序绘制形状以获得更好的想法，你可以更好地体验我在说什么，而不是我试图解释它。

点的定义如下:

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

这是顺时针多边形的图像:

这是逆时针多边形的图像:

如果你能帮我弄清楚如何确定点的“顺时针方向”，我将不胜感激!

Answer 1

使用 shoelace formula 计算多边形面积, 但没有绝对值符号。如果结果为正，则点逆时针排序，如果为负，则顺时针排序。

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;