一起写写这个算法“凸包”

eachy

http://www.xdcad.net/forum/showthread.php?s=&threadid=148502

1. 凸包的求法：
   
2. 
   
3.     现在已经证明了凸包算法的时间复杂度下界是O(n*logn),但是当凸包的顶点数h也被考虑进去的话，Krikpatrick和Seidel的
   
4. 剪枝搜索算法可以达到O(n*logh)，在渐进意义下达到最优。最常用的凸包算法是Graham扫描法和Jarvis步进法。本文只简单
   
5. 介绍一下Graham扫描法，其正确性的证明和Jarvis步进法的过程大家可以参考《算法导论》。
   
6. 
   
7.     对于一个有三个或以上点的点集Q，Graham扫描法的过程如下：
   
8. 
   
9.     令p0为Q中Y-X坐标排序下最小的点
   
10.     设<p1,p2,...pm>为对其余点按以p0为中心的极角逆时针排序所得的点集（如果有多个点有相同的极角，除了距p0最
    
11. 远的点外全部移除
    
12.     压p0进栈S
    
13.     压p1进栈S
    
14.     压p2进栈S
    
15.     for i ← 3 to m
    
16.       do while 由S的栈顶元素的下一个元素、S的栈顶元素以及pi构成的折线段不拐向左侧
    
17.         对S弹栈
    
18.       压pi进栈S
    
19.     return S;
    
20. 
    
21. 
    
22.     此过程执行后，栈S由底至顶的元素就是Q的凸包顶点按逆时针排列的点序列。需要注意的是，我们对点按极角逆时针
    
23. 排序时，并不需要真正求出极角，只需要求出任意两点的次序就可以了。而这个步骤可以用前述的矢量叉积性质实现。
    

复制代码

aeo

应该不难，
就是写出来的代码执行快慢.
无非是排序，再排序，一直回到起点.(令p0为Q中Y-X坐标排序下最小的点
)-->保证能回去

wyj_007

1:点归入选择集ss0,先取出最左点P1，最上点P2，最右点P3，最下点P4四个关键点，P1P2左上角归入集ss1，
P2P3右上角归入集ss2，P3P4右下角归入集ss3，P3P4左下角归入集ss4，把p1,p2,p3,p4点围成的区域内的
点移出选择集，
2:[在ss1取出最左点P11,把p1,p2,p11点围成的区域内的点移出选择集ss1],重复[****]步调直到ss1为nil,
3:[在ss2取出最上点P21,把p2,p3,p21点围成的区域内的点移出选择集ss2],重复[****]步调直到ss2为nil,
4:[在ss3取出最右点P31,把p3,p4,p31点围成的区域内的点移出选择集ss3],重复[****]步调直到ss3为nil,
5:[在ss4取出最下点P41,把p4,p1,p41点围成的区域内的点移出选择集ss4],重复[****]步调直到ss4为nil,
6:把P1-->历次P11-->P2-->历次P21-->P3-->历次P31-->P4-->历次P41-->P1围起来即成你要的凸包线。