我已经使用了很少的顺时针顶点排序算法,但仍然无法排序,因为它应该被排序。
多边形总是正方形,并切下相同大小的较小正方形(让我们将它们命名为 block )。所以说我有 6x6 的正方形, block 是 1x1。更具体地说:正方形有顶点:[0,0]、[5,0]、[5,5]、[0,5]。 如果我将在位置 [0,0] 处切掉 block (就像在从 [0,0] 到 [1,1] 的顶点上用较小的正方形进行交集),正方形看起来像这样:
他的顶点现在是:[0,1]、[1,1]、[1,0]、[5,0]、[5,5]、[0,5]
没关系。但是让我们再做一些交集。我不会在位置 [1,0] 显示 block 的第二个交集,因为一切都很好。现在,如果我要做第三个交叉点,在位置 [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);
}
最佳答案
我并没有真正检查你的比较功能是否有任何错误,但它太复杂了。你可以只使用 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/