标签：#凸包算法

葛立恆掃描法

葛立恒扫描法（Graham's scan）是一种计算一组的平面点的凸包的演算法，时间复杂度为O(n\log n)。以在1972年发表该算法的葛立恒命名。 算法步骤与图解 第一步：找到最下边的点，如果有多个点纵坐标相同的点都在最下方，则选取最左边的。在右图中这个点是P。这一步只需要扫描一遍所有的点即可，时间复杂度为O(n)。 第二步：将所有的点按照相对于第一步中的得到的点P的极角大小进行排序。注意这一步并不需要真的透过计算反三角函数來得到…