java - 有没有办法进一步优化格雷厄姆扫描算法以找到凸包？

Question

我经历了chan的算法。对我来说似乎并没有好多少。有没有办法可以用其他任何东西替换 graham scan 中的排序部分？这样可以进一步减少 O(nlogn) 时间。Java 实现是首选。

Answer 1

优化排序步骤的最佳方法是避免考虑不属于凸包的点。这称为 Akl-Toussaint 启发式http://www-cgrl.cs.mcgill.ca/~godfried/publications/fast.convex.hull.algorithm.pdf。您可以快速扫描所有顶点并找到形成点集的四边形（您可以将这四个点作为±（x + y），±（xy）中所有顶点的极值），然后删除其中的所有顶点四边形。

在此之后，您可以使用 Graham 的扫描或 Andrew 的单调链算法——我最喜欢，两者都是 O(n log n) 复杂度。请注意，就像上面评论中提到的@Chill 一样，Chan 的方法是最佳的。

在实践中，这种方法比在没有任何过滤的情况下将其中一种算法应用于点集要快得多。

我在上面链接的论文在结论部分提到了一个“丢弃”的想法。这是一个轻微的改进，因为我们可以在搜索四边形本身时丢弃大部分顶点。我为这个启发式附加了一个片段。

/**
 * Given verts: Array(Points).
 */

/*
 * if we have more than 100 points use Akl-Toussaint heuristic to remove
 *  points that we know are surely not part of the hull.
 * S.G. Akl & Godfried Toussaint, 1977,  "A Fast Convex-hull Algorithm"
 */
if (verts.length > 100) {
    var min = Math.min,
        max = Math.max;
    var minU = minL = maxU = maxL = verts[0];
    var minUval = minU.x - minU.y;
    var minLval = minL.x + minL.y;
    var maxUval = maxU.x + maxU.y;
    var maxLval = maxL.x - maxL.y;
    var xMin = yMin = xMax = yMax = 0;
    var vertList = [];
    for (i = 0 ; i < verts.length; ++i) {
        var v = verts[i];
        var x = v.x;
        var y = v.y;
        if (!(x > xMin && x < xMax && y > yMin && y < yMax)) {
            vertList.push(v);
            var sum = x + y;
            var diff = x - y;
            if (diff < minUval) minU = v;
            if (diff > maxLval) maxL = v;
            if (sum < minLval) minL = v;
            if (sum > maxUval) maxU = v;
            minUval = minU.x - minU.y;
            maxLval = maxL.x - maxL.y;
            minLval = minL.x + minL.y;
            maxUval = maxU.x + maxU.y;
            xMin = max(minU.x, minL.x);
            yMin = max(minL.y, maxL.y);
            xMax = min(maxU.x, maxL.x);
            yMax = min(minU.y, maxU.y);
        }
    }

    // reset the vert's array, and do one more filtering pass 
    // on vertList
    verts.length = 0;
    for (i = 0 ; i < vertList.length; ++i) {
        var v = vertList[i];
        var x = v.x;
        var y = v.y;
        if (!(x > xMin && x < xMax && y > yMin && y < yMax))
            verts.push(v);
    }
    // verts now only contains a subset of vertices.
}
// Run a convexhull algorithm on verts.
// ...