更准确的顺时针顶点排序

Question

我使用了很少的顺时针顶点排序算法，但仍然无法排序，因为它应该排序。

多边形总是正方形，切下相同大小的较小正方形（让我们将它们命名为块）。所以说我有 6x6 的正方形，块是 1x1。更具体地说：正方形有顶点：[0,0]、[5,0]、[5,5]、[0,5]。如果我将在位置 [0,0] 处切掉块（就像在从 [0,0] 到 [1,1] 的顶点上用较小的正方形进行交集），正方形看起来像这样：

他的顶点现在是：[0,1], [1,1], [1,0], [5,0], [5,5], [0,5]

没关系。但是让我们再做一些交集。我不会在位置 [1,0] 显示块的第二个交集，因为一切都很好。现在，如果我要做第三个交集，在位置 [0,1] 处，它看起来像这样：

当然，它应该是这样的：

所以正如你所见，它只是排序失败，它在 [0,2]

之前对顶点 [1,2] 进行排序

我想知道当我添加诸如检查与质心的距离之类的东西时它是否会排序。好吧..这是这种排序的代码：

function (a, b) {

    var distance1 = Math.sqrt(Math.pow(a.x - centroid.x, 2) + Math.pow(a.y - centroid.y, 2));
    var distance2 = Math.sqrt(Math.pow(b.x - centroid.x, 2) + Math.pow(b.y - centroid.y, 2));
    var a1 = Math.acos((a.x - centroid.x) / distance1);
    var a2 = Math.acos((b.x - centroid.x) / distance2);

    if (a.y > centroid.y)
        a1 = Math.PI + Math.PI - a1;

    if (b.y > centroid.y)
        a2 = Math.PI + Math.PI - a2;

    return a1 - a2;

}

和质心：

function (vertices) {
    var 
        x = 0,
        y = 0,
        pointCount = vertices.length;

    for (var i = 0; i < pointCount; i++){
        x += vertices[i].x;
        y += vertices[i].y;
    }

    x = x/pointCount;
    y = y/pointCount;

    return new vec2(x, y);
}

Answer 1

我没有真正检查你的比较功能是否有任何错误，但它太复杂了。您可以只使用 Math.atan2 来获取两点之间的角度。你的函数应该看起来像

function(a, b) {
    return Math.atan2(a.y - centroid.y, a.x - centroid.x)
         - Math.atan2(b.y - centroid.y, b.x - centroid.x);
}

Answer 2

好的，顺时针排序后我实现了新的功能，那就是角度优化。整个算法是这样的：

如有任何建议，请随时提出

这里是角度优化的代码：

for (var i = 1; i < vertices.length; i++) {
        var a = vertices[i - 1];
        var b = vertices[i];
        var j = i;

        do {
            var distanceAngle = Math.abs(Math.atan2(a.y - b.y, a.x - b.x));
            if (
                distanceAngle == Math.PI / 2 ||
                distanceAngle == Math.PI ||
                distanceAngle == 3 * Math.PI / 2 ||
                distanceAngle == 2 * Math.PI ||
                distanceAngle == 0
            )
            {
                var tmp = vertices[i];
                vertices[i] = vertices[j];
                vertices[j] = tmp;
                break;
            }
            j++;
            b = vertices[j];
        } while (j < vertices.length);
    }

更准确的顺时针顶点排序

More accurate clockwise vertices sorting

javascript

sorting

algorithm

vertices