javascript - 更准确的顺时针顶点排序

标签 javascript algorithm sorting vertices

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

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

Beautiful chunk intersection

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

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

Ugly intersection

当然,它应该是这样的:

enter image description here

正如您所见,它只是排序失败,它在 [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);
}

最佳答案

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

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

关于javascript - 更准确的顺时针顶点排序,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/37779308/

相关文章:

java - 如何识别属于最大堆的元素和属于最小堆的元素?

java - 我如何找到以下功能的时间复杂度?

java - 使用抽象类对列表进行排序

javascript - 如何让我的应用程序在单击 Alt 按钮时打开 url

javascript - jQuery UI 对话框位置固定居中

java - Dijkstra最短路径算法: finding number of checked vertices

c++ - 检查数字是否为素数的算法

php - call_user_func_array 和 array_multisort

javascript - Angular 5不显示用户从formarray输入的值

javascript - 如何在不通过 javascript 进行任何元素注入(inject)的情况下将图标放置到每个 jquery ui 自动完成中