Advanced Graphics 孙 晓 鹏 博士 教授 2011年 11月 16日第二章 二维凸包2.4 凸包的快速算法 主要思想 点集S 的凸包是取决于凸包边界附近的点 逐步丢掉凸包内部的点，只关注凸包附近的点，从而 提高算法的效率 最好情况O(nlogn) 、 最坏情况O(n 2 )2.4 凸包的快速算法 算法过 程 取两个极端点，它们 是最右最下点p dr 和最左最上点p ul 有向直线 p dr p ul 将整个凸包被划分为 右凸包和左凸包 对 右凸包和左凸包分别进 行递归 递归 设S 1 是严 格在直线 p dr p ul 右边 的点集（S 1 可能是空集） 在S 1 中寻 找距离直线 p dr p ul 最远 的点，作为p dr p ul 右边 的一个极端点b 连 接p dr 和b ，及b 和p ul 把p dr 右侧 的点集记为 A ， p ul 右侧 的点集的点记为 B 对边 p dr b和点集A 、对边 b p ul 和点集B 分别递归调 用 依次连 接凸包上的顶 点，得点集S 1 的凸包，即点集S 的右凸包 类 似地，计 算出点集S 的左凸包，从而得到整个点集S
