Jarvis步进法求凸包

算法原理

接着上一篇的Graham扫描法，现在来讨论求凸包的另一种方法，Jarvis步进法。该方法所运用的技术被成为打包（package wrapping）或包装礼物（gift wrapping）。可以这样来理解，比如说现在找到了一个点集Q中纵坐标最小的点q0（若有多个则为这些点中横坐标最小的点），那么该点一定为点集Q的凸包CH(Q)中的点。将一条绳子的一端固定在改点上，并将另一段沿着x轴方向拉直。然后逆时针方向绕点q0旋转该绳子，并使绳子始终处于紧绷状态。这样绳子在逆时针宣传的过程中所触碰到的点就是凸包CH(Q)上的点，直到绳子再次触碰到点q0。

代码实现

在原算法中给出的例子中，同样没有考虑共线的情况。下面以解决leetcode-587为例来实现寻找凸包的Jarvis步进算法。算法实现时，没有采用《算法导论》中分别构造左链和右链的方法，也没有显示的计算极角。

  1. 找到点集Q中的最低点p0，该点一定是凸包CH(Q)中的点。令pc=p0。
  2. 在点集中找到一个点pn，使点集Q中所有其他的点都在pc和pn所确定直线的“左侧”（或者直线上，在考虑共线的情况下）。
  3. 此时pn也是凸包CH(Q)中的点，另pc=pn，再重复步骤2直到pn==p0。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
// Jarvis步进法
// 计算向量ab(x1, y1), cd(x2, y2)的外积 (x1*y2-x2*y1)
int crossProduct(const vector<int> &a, const vector<int> &b,
                 const vector<int> &c, const vector<int> &d) {
    int x1 = b[0]-a[0];
    int y1 = b[1]-a[1];
    int x2 = d[0]-c[0];
    int y2 = d[1]-c[1];
    return (x1*y2 - x2*y1);
}

// 返回点a到点b距离的平方
int dis2(const vector<int> &a, const vector<int> &b) {
    return (a[1]-b[1])*(a[1]-b[1]) + (a[0]-b[0])*(a[0]-b[0]);
}

class Solution {
public:
    vector<vector<int>> outerTrees(vector<vector<int>>& points) {
        if (points.size() <= 3)
            return points;
        vector<vector<int>> ret;
        int firstIndex = 0;
        for (int i = 1; i < points.size(); ++i) {
            if (points[i][1] < points[firstIndex][1] ||
                (points[i][1] == points[firstIndex][1] && points[i][0] < points[firstIndex][0]))
                firstIndex = i;
        }

        int curIndex = firstIndex;
        do {
            int nextIndex = 0;
            for (int i = 1; i < points.size(); ++i) {
                if (i == curIndex) continue;
                int cp = crossProduct(points[curIndex], points[nextIndex], points[curIndex], points[i]);
                if (nextIndex == curIndex || cp < 0 ||
                    // 解决共线情况
                    (cp == 0 && dis2(points[curIndex], points[i]) > dis2(points[curIndex], points[nextIndex])))
                    nextIndex = i;
            }
            // 解决共线情况
            for (int i = 0;i < points.size(); ++i) {
                if (i == curIndex) continue;
                int cp = crossProduct(points[curIndex], points[i], points[curIndex], points[nextIndex]);
                if (cp == 0)
                    ret.push_back(points[i]);
            }
            curIndex = nextIndex;
        } while (curIndex != firstIndex);
        return ret;
    }
};

参考文献

https://leetcode.com/problems/erect-the-fence/discuss/103299/Java-Solution-Convex-Hull-Algorithm-Gift-wrapping-aka-Jarvis-march

https://en.wikipedia.org/wiki/Convex_hull_algorithms

https://en.wikipedia.org/wiki/Gift_wrapping_algorithm

算法导论第三版