我读了一些关于计算凸包的算法。它们中的大多数都需要O(n*log(n))时间，其中n是输入点的数量。
令S = {p_1, p_2, ..., p_n}为一组按x坐标排序的点，即p_1.x <= p_2.x <= ... <= p_n.x。
我必须描述一种算法，该算法以S时间计算CH(S)，O(n)的凸包。此外，我还必须分析算法的运行时间。
最佳答案
我无法抗拒解释程序。
这些点按字典顺序(x，y)排序。
假设我们已经建立了K个第一点的上 shell 。如果要获取K + 1个第一点的上层 shell ，则必须找到新点和上层 shell 之间的“桥梁”。这是通过在船体上回溯直到新的点和船体的边缘形成凸角来完成的。
回溯时，我们丢弃形成凹角的边，最后将新点链接到自由端点。 (在图上，我们尝试三个边缘，并丢弃其中两个。)现在，我们有了K + 1点的上 shell 体。
通过存在N个向前的步长(添加了N个顶点)和N-H个向后的步长(丢弃了N-H个边，其中H是最终船体顶点的数量)这一事实，就可以简单地证明线性行为是合理的。
对称过程将构建下部船体，并通过串联获得整个凸船体。
关于algorithm - 如何在O(n)时间内计算按x坐标排序的一组点的凸包？，我们在Stack Overflow上找到一个类似的问题：https://stackoverflow.com/questions/44135328/