Ahead

10.6.2018

算法5（GS）

最优算法O（nlogn）

实现

1.预处理排序
选取LTL与第二LTL 对剩下的点进行极角排序 （ToLeft Text）

2.开两个栈T与S （开头相对！！！ ，为了好看）将已连接的边放入S，其余的按极角大小放入T

3.三个指针指向S的栈顶与次栈顶以及T的栈顶S[0],S[1],T[0]

代码

   while(!T.empty()) 
    {
        ToLeft(S[1],S[0],T[0])?S.push(T.pop()):S.pop(); 
    }    

4.最后对S栈自底向上是凸包的环路描述

这是大概的流程图

理解

每次退S栈表示一次回溯，否则是一次加边，那么对于弹S 表示S栈顶的元素偏内，而新节点更外面，就目前而言应该往右拐 （模拟一下就可以看出了）

正确性

下一个拓展点一定位于黄区或者蓝区，如果黄区直接拓展，如果蓝区，那么显然就是一个退栈的过程 也就是把在右边的退了，从而达到我们需要的状态

【学习笔记：计算几何基础3】 Convex Hull

原文：https://www.cnblogs.com/PiCaHor/p/9746986.html