一个凸包函数

Question

我是 Whosebug 的新手，这是我的第一个问题。

我在Convex Hull上解决了几个问题，在Codechef上看到vjudges提交的答案，我发现他们重复使用以下函数来找出一组点的凸包。

int n = (int)p.size();
if (n <= 1)
    return p;
sort(p.begin(), p.end());
int cnt = 0;
vector<Pint> q(n * 2);
for (int i = 0; i < n; q[cnt++] = p[i++])
    for (; cnt >= 2 && !cw(q[cnt - 2], q[cnt - 1], p[i]); --cnt)
        ;
for (int i = n - 2, t = cnt; i >= 0; q[cnt++] = p[i--])
    for (; cnt > t && !cw(q[cnt - 2], q[cnt - 1], p[i]); --cnt)
        ;
q.resize(cnt - 1 - (q[0] == q[1]));
return q;

谁能解释一下这个函数背后的逻辑是什么，它与 Jarvis 或 Graham 的方法有什么不同吗？

Answer 1

以上代码使用了与 Grahm 或 Jarvis 算法略有不同的算法。它首先以相反的顺序应用相同的算法找到上半壳，然后找到下半壳。最后，它结合了两者。

输入：平面上的一组 P 点。输出：包含顺时针顺序的 CH(P) 顶点的列表。

 1. Sort the points by x-coordinate, resulting in a sequence p1,p2.....pn
 2. Put the points p1 and p2 in a list Lupper, with p1 as the first point
 3. for i from 3 to n
 4.     do Append pi to Lupper
 5.          while length(Lupper)>2 and last three points in Lupper make left turn
 6.               do delete middle of last three points from Lupper

现在将点 pn,pn-1 放入列表 Llower 中，pn 作为第一个点

 7. for i from n-2 to 1
 8.     do Append pi to Llower
 9.          while length(Llower)>2 and last three points in Llower make left turn
 10.               do delete middle of last three points from Llower
 11. Remove the first and last point from Llower to avoid duplication of the points where upper and lower hull meet.
 12. Append Llower to Lupper and call the resulting list L
 13. return L

例如：- points = (0,0),(1,1),(2,5),(8,9),(10,0),(1,-1),(2 ,-5),(8,-9)

Lupper

Llower

Final Hull

算法来源：Mark de Berg 的 Computational Geometry Algorithms and Applications

一个凸包函数

A Convex Hull function

convex-hull