steger算法 c++

Steger算法是一种计算凸包的算法，它的时间复杂度为O(nlogn)。该算法首先找到点集中最左边和最右边的点，并将这两个点分别作为凸包的起点和终点，然后根据极角排序将其他点分为两个集合，一个在起点右侧，另一个在终点左侧。接着，通过迭代合并这两个集合的凸包，最终得到整个点集的凸包。

具体实现时，Steger算法通过快速排序对点集进行极角排序，并选择一个起始点作为极角最小的点。接着，对剩余点按照与起始点的极角排序，得到点集P={p1,p2,...,pn}。然后，通过以下步骤计算凸包：

(1)令PH={p1,p2}和PT={pn-1,pn}分别表示凸包的起点和终点。

(2)按顺序遍历点集P中的点，将每个点插入凸包中。插入时，需要在PH和PT之间的凸包中查找支持该点的点对，然后删除这些点对并插入新的点对。

(3)合并PH和PT中的凸包，得到整个点集的凸包。

与其他凸包算法相比，Steger算法的时间复杂度比较优秀，同时也较为简洁。它在计算小型凸包时具有很好的效率，但如果数据量非常庞大时，还需要优化以提高计算效率。