探求二维凸包与其应用.pdf

探求二维凸包及其应用 许瑞广，余志伟 中国矿业大学(北京)资源学院(100083) E-mail：lucky_xrg@163.com 摘 要：凸包是计算几何中最普遍、最基本的一种结构，本文介绍了二维凸包的概念和性质， 并介绍几种求二维凸包的方法:Gift-Wrapping、Graham-Scan 算法，以及这几种算法的正确性和 时间复杂度的分析，最后通过两个实例来简要介绍二维凸包的应用。 关键字：凸包、Gift-Wrapping 、Graham-Scan 作为计算几何中第一个被深入研究的几何模型，凸包以其优美的性质带来了广泛的应用， 本文将对这个几何模型进行简要的介绍。 1. 凸包的概念和性质 我们首先从一个实例来引入凸包：假设你种了很多树，想用一个篱笆把所有的树都包在里 面，出于经济考虑，显然这个篱笆应该是越小越好。给出树的坐标，求出篱笆的最小周长。如 图1－1 所示的篱笆是一个最小的篱笆，而这个篱笆就是这些树的凸包(Convex Hull)。 图1－1 凸包(Convex Hull) 要定义凸包，首先我们来研究一下凸多边形。 定义1 凸多边形 整个图形在任一条边的一侧。 x1 +x2 定义2 D 是凸多边形 ∀ , ∈D , ∈D ，即对于一个凸多边形任意两个 x1 x2 2 内点的中点也在此图形内。我们不仅考虑中点，还考虑所有内分点，于是有如下定义。 [ ] 定义3 D 是凸多边形∀ , ∈D ,∀λ∈0,1,λ +(1−λ) ∈D x x x x 1 2 1 2 因此定义2 是定义3 的一种特殊形式。如图1－2 给出了凸图形和凹图形的图示： 图2－2 凸图形和凹图形 2 设S是平面(E )上的点集，用CH(S)表示点集S的凸包，BCH(S)表示S的凸包边界。 定义4 平面点集S 的凸包CH(S)是包含S 的最小凸集，凸包上的顶点称为极点。 -1- 点集S 的凸包是包含S 的所有凸集的并，或者CH(S)是包含S 的所有半空间的交。二维中 的半空间是半平面，它是指位于一条直线上及该线一侧的点的集合。 定义5 平面点集S 的凸包边界BCH(S)是一凸多边形，其顶点为S 中的点。 BCH(S)是包围S 的最小凸多边形P ，即不存在多边形P ，使得P ⊃P⊃S 成立。 BCH(S)是具有最小面积并且封闭的凸多边形西P，或者是具有最小周长并封闭的凸多边形 P 。 由此也验证了实例中最省材料的篱笆即为这些树的凸包。 2. 凸包的实现 2.1 Gift-Wrapping 算法 Gift-Wrapping算法是凸包问题的最直观的一种解法，它是Chand和Kapur于1970 年提出的， 其基本思想如下：首先过y坐标最小的点p1，画一水平直线l，显然该点是凸包的一个顶点。然 后l绕p 按逆时针方向旋转，碰到S中的第二个点p 时，直线l改绕p 按逆时针方向旋转而在p 与p 1