前言 平面点集的凸包算法一文介绍了如何计算平面点集或者任意多边形的凸包。对于随机的平面点集，Graham scan和Andraw's 单调链算法已经是最快的算法了。但是对于没有自相交的封闭的简单多边形，存在线性复杂度的算法。下面介绍这一优雅高效的算法。 一般的2D凸包算法，首先将点进行排序（时间复杂度）,然后利用栈操作在O(n)的时间复杂度内计算凸包。初始的排序决定了最终的时间复杂度。但是本文