一种在计算机上生成凸包的算法

赵小林　陈朔鹰　刘　然

摘要：在计算机上实现生成凸包的算法很多，笔者设计的这一算法主要是利用了在计算机表示中，任意两个点之间必定是有一定距离的，而数学上两个点之间的距离可以是无限小这一特点。我们总可以在计算机上任意两个点的位置之间插入一个数学上的点，这个点计算机可能无法表示，但它是可以被计算的。利用这一特点设计了本算法。

关键词：凸包；转折点；内点；外点；相交

中图分类号：TP301．6

文献标识码：A

文章编号：1003—6199(2003)03—047—04