2D凸包算法

hbghlyj

描述单调凸包算法的动画

Andrew's monotone chain convex hull algorithm Andrew算法求凸包的过程。首先把所有点以横坐标为第一关键字，纵坐标为第二关键字排序。 显然排序后最小的元素和最大的元素一定在凸包上。 而且因为是凸多边形，我们如果从一个点出发逆时针走，轨迹总是“左拐”的， 一旦出现右拐，就说明这一段不在凸包上。 因此我们可以用一个单调栈来维护上下凸壳。

OIWiki Rotating Calipers
Luogu wjyyy's blog
旋转卡壳

	Caliper (卡尺)
	首先使用任何一种凸包算法求出给定所有点的凸包，有着最长距离的点对一定在凸包上。 而由于凸包的形状，我们发现，逆时针地遍历凸包上的边，对于每条边都找到离这条边最远的点，那么这时随着边的转动，对应的最远点也在逆时针旋转，不会有反向的情况。
	这意味着我们可以在逆时针枚举凸包上的边时，记录并维护一个当前最远点，并不断计算、更新答案。 求出凸包后的数组自然地是按照逆时针旋转的顺序排列，不过要记得提前将最左下角的 1 节点补到数组最后，这样在挨个枚举边 $[(i,i+1)]$ 时，才能把所有边都枚举到。

hbghlyj

用Asymptote编写一个函数，输入一个点列表，应用Andrew算法按逆时针顺序输出凸包上的点列表。
注意：返回列表中的最后一个点与第一个点相同。

输入5个点的列表$\{(-0.2,0.1),(0.5,0),(-1,-1),(-1,1),(1,0)\}$ 输出凸包

1. pair[] convex_hull(pair[] P){
2.     int n = P.length, k = 0;
3.     if (n <= 3) return P;
4.     pair[] H=new pair[2*n];
5.     P=sort(P,new bool(pair A, pair B){return A.x<B.x||(A.x==B.x&&A.y<B.y);});
6.     for (int i = 0; i < n; ++i) {
7.         while (k >= 2 && orient(H[k-2], H[k-1], P[i]) <= 0) --k;
8.         H[k] = P[i];++k;
9.     }   
10.     for (int i = n-1, t = k+1; i > 0; --i) {
11.         while (k >= t && orient(H[k-2], H[k-1], P[i-1]) <= 0) --k;
12.         H[k] = P[i-1];++k;
13.     }
14.     H.delete(k,H.length-1);
15.     return H;
16. }
17. unitsize(4cm);
18. path p;
19. pair[] points={(-0.2,0.1),(0.5,0),(-1,-1),(-1,1),(1,0)};
20. for(pair P:points){
21.   dot(P);
22.   label((string)P,P);
23. }
24. for(pair P:convex_hull(points)){
25.   p=P--p;
26. }
27. draw(p);

复制代码

hbghlyj

可以计算$(x^2-1)(x^2-2),x∈[-1.5,1.5]$的图象(有2个拐点)的凸包

pair[] convex_hull(pair[] P){     int n = P.length, k = 0;     if (n <= 3) return P;     pair[] H=new pair[2*n];     P=sort(P,new bool(pair A, pair B){return A.x<B.x||(A.x==B.x&&A.y<B.y);});     for (int i = 0; i < n; ++i) {         while (k >= 2 && orient(H[k-2], H[k-1], P[i]) <= 0) --k;         H[k] = P[i];++k;     }        for (int i = n-1, t = k+1; i > 0; --i) {         while (k >= t && orient(H[k-2], H[k-1], P[i-1]) <= 0) --k;         H[k] = P[i-1];++k;     }     H.delete(k,H.length-1);     return H; } unitsize(4cm); path p,q;pair[] points; settings.render=5; for(real x:uniform(-1.5,1.5,30)){   points.push((x,(x^2-1)*(x^2-2))); } for(pair P:points){   q=P--q; } for(pair P:convex_hull(points)){   p=P--p; } fill(p--cycle,lightblue);draw(q,red+linewidth(2)); 复制代码