在我正在开发的web应用程序中,我正在检测某些图像的边界并沿着检测到的边界生成坐标点数组。由于数组的生成方式,坐标点不能保证按任何特定顺序排列。我写了一个比较函数,它计算任意两个给定点从一个中心点到向量的叉乘,以确定相对位置。这在chrome中工作得很好,但是在firefox 21.0和IE 10中,一些坐标点没有正确排序。
比较函数和排序函数的代码如下:
function sortCounterClockwise(a, b) {
return ((isALeftOfB(a, b)) ? 1 : -1);
//return ((isALeftOfB(a, b)) ? 1 : ((isALeftOfB(b, a)) ? -1 : 0));
}
function isALeftOfB(a, b) {
var det = (a.x - center.x) * (b.y - center.y) - (b.x - center.x) * (a.y - center.y);
if (det < 0) {
return false;
} else if (det > 0) {
return true;
}
var d1 = (a.x - center.x) * (a.x - center.x) + (a.y - center.y) * (a.y - center.y);
var d2 = (b.x - center.x) * (b.x - center.x) + (b.y - center.y) * (b.y - center.y);
return d1 < d2;
}
我在http://jsfiddle.net/Zsz3K/1/创建了一个完整的工作jsfiddle,如果你在Chrome中查看它,你会看到适当的,如果蒙大拿州的粗轮廓,但在FF和IE中,它会混合坐标点。
我已经尝试了上述算法的许多变体,但我无法让它在FF或IE的所有测试用例中工作,只有chrome。在之前的迭代中,我固定了一个点作为参考点,认为IE和FF被排序的周期性所绊倒。我的测试用例是上传一张美国地图,chrome能够成功检测并正确追踪所有边界。我不能改变程序来保证坐标数组是通过从中心点开始增加或减少来排序的,并且确实需要找到一种一致的方法来对这些坐标进行排序,以便在这里列出的浏览器中正确工作。据我所知,这似乎是FF和IE中的一个bug,因为结果是基于数学结果的,在浏览器中应该是不可变的。
编辑:把我的答案移到一个答案。
我已经创建了一个jsfiddle的更新,我认为它模糊地回答了我自己的问题。http://jsfiddle.net/Zsz3K/3/
我粗略地设计了一个快速的冒泡排序,并在比较函数中添加了一个关于相对于中心点的相对位置的额外条件,它在所有3个浏览器中都有效。我想带走的是。sort()在FF和IE中的实现似乎不能很好地处理这类数据。我希望我有时间深入了解jquery的内部,但是我没有。因此,如果其他人在jquery中遇到空间坐标排序的问题,不要依赖于内置的排序函数,尽管我建议使用比普通冒泡排序更有效的方法,而不是将其作为概念证明。奇怪的是,chrome不仅始终使用内置的。sort()与比较器一起工作,而且它不需要(实际上被绊倒了)使用相对位置到中心作为排序标准。
为了满足链接到jsfiddle的代码要求,这里是工作排序和比较器。
do {
swapped = false;
for (var i=0; i < points.length-1; i++) {
if (isALeftOfB(points[i + 1], points[i])) {
var temp = points[i];
points[i] = points[i+1];
points[i+1] = temp;
swapped = true;
}
}
} while (swapped);
function isALeftOfB(a, b) {
if (a.y <= center.y && b.y > center.y) {
return true;
} else if (a.y == center.y && b.y == center.y) {
return a.x < b.x
}
var det = (a.x - center.x) * (b.y - center.y) - (b.x - center.x) * (a.y - center.y);
if (det < 0) {
return false;
} else if (det > 0) {
return true;
}
var d1 = (a.x - center.x) * (a.x - center.x) + (a.y - center.y) * (a.y - center.y);
var d2 = (b.x - center.x) * (b.x - center.x) + (b.y - center.y) * (b.y - center.y);
return d1 < d2;
}