首页 文章

凸壳功能

提问于
浏览 次
1

我是StackOverflow的新手，这是我在这里的第一个问题 .

我在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的方法有什么不同？

convex-hull

1 回答

  • 0

    上面的代码使用了与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的计算几何算法和应用

    回复于

相关问题