发现一篇很好的介绍凸包的文章,通俗易懂还有配套的程序提供下载
凸包(Convex Hull)
引言
欢迎光临本网页。在这个网页中,你可以学习到计算几何(Computational Geometry)中的「凸包」(Convex Hull)概念,以及求凸包的基本原理。你亦可试用本人编写的用来求凸包的应用程序。
甚么是凸包?
在了解凸包之前,须先认识何谓「凸多边形」(Convex Polygon)。从直观上说,一个凸多边形就是没有任何凹 陷位的多边形。我们在低年级数学所学习的三角形、正方形、长方形、平行四边形、正五边形、正六边形等等 ,都是凸多边形的例子。但是以下这个「凸」字形却并非凸多边形,因为箭头指着的地方实际是一个凹陷位。



求凸包的应用程序
本人编写了三个求凸包的应用程序,包括一个Visual Basic版和两个Flash版。Visual Basic版为EXE档,请点 击下列连结,下载有关档案(该EXE档连同其它必要档案已压缩在一个ZIP档案中,下载后必须解压缩),然后便 可在你的计算机上执行。两个Flash版分别为SWF和EXE档,你只需点击下列有关连结,便可执行程序。上述程序 都包含「使用说明」或”Instructions”,浏览者只需依照说明上的指示便可使用该程序,请选择适合你计算机 的程式。
连结:
- 凸包应用程序(Visual Basic版-英文界面) (须解压缩)
- 凸包应用程序(Flash版SWF文件-中文界面)(你的计算机须安装Shockwave Flash软件,档案较小)
- 凸包应用程序(Flash版EXE文件-中文界 面)(无需预先安装其它软件,但档案较大)
求凸包的基本原理
本程序采用循序渐进的方式求取给定点集的凸包,首先把使用者最初输入的3个不共线(Non-collinear)的点按 逆时针方向构成一个三角形(注1),这就是这3点的凸包。接着程序便会考察第4点,看看这个点是否位于前述三 角形之内或三角形的边上。若是,则这第4点并非凸包上的点,前述三角形保持不变。若否,则把这前述的三角 形扩大为一个四边形,并把不适用的边擦去。这个四边形便是这首4点的凸包。接着程序又会考察第5点,如此 类推,直至所有点均已被考察为止。使用者在使用本程序时可以清楚看到上述从最初的三角形逐步扩大为最终 的凸包的过程。
这里涉及到判断一点是否被包围在某一多边形内的问题,人类凭肉眼很容易便能作出此一判断。可是计算机没有 眼睛,它所具备的信息只有给定点的坐标,我们应如何「教」计算机作出上述判断呢?其实方法并不太复杂。且 来看看一个简单的例子。

看到这里,读者不禁要问,计算机如何判断某一点是位于某条直线的左边还是右边呢?其实只要看看上图,我们 容易发现,左转相当于逆时针方向,右转则相当于顺时针方向。因此我们可以利用逆时针和顺时针这一组概念 来代替左、右这两个概念。这里我们可以用向量代数中一条有关平面三角形面积的公式。给定平面上3点 P1、P2、P3的坐标(x1, y1)、(x2, y2)和(x3, y3),这3点所构成三角形的面积可表达为一个名为Area的函 数:
Area(P1, P2, P3)= | ![]() |
此一公式使用行列式(Determinant)来定义三角形面积,可以展开并化简为:
注2:我们说「当我们在CA在线时E点位于我们的左边」,是指当我们把CA线无限延长并且面向着A点时,E点位 于这条无限延长线的左边。