1

在我正在开发的 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混合坐标点。

我已经尝试了上述算法的许多变体，但我无法让它在我在 FF 或 IE 中的所有测试用例中工作，只有 chrome。在之前的迭代中，我将一个点固定为参考点，认为 IE 和 FF 被排序的循环特性绊倒了。我的测试用例正在上传美国地图，chrome 能够成功检测并正确跟踪所有边界。我无法更改程序以保证坐标数组是通过从中心点增加或减少 theta 来排序的，并且确实需要找到一种一致的方法来对这些坐标进行排序，以便在此处列出的浏览器中正常工作。据我所知，这似乎是 FF 和 IE 中的一个错误，因为结果是基于在浏览器之间应该是不可变的数学结果。

编辑：将我的答案移至答案。

4

1 回答 1

0

我创建了对 jsfiddle 的更新，我想它模糊地回答了我自己的问题。 http://jsfiddle.net/Zsz3K/3/

我粗略地进行了快速冒泡排序，并在比较器函数中添加了一个关于相对于中心点的相对位置的附加条件，它适用于所有 3 个浏览器。我猜想，FF 和 IE 中的 .sort() 实现似乎不适用于此类数据。我希望我有时间深入了解 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;
}
于 2013-05-21T09:44:53.430 回答