34

北京联合大学学报(自然科学版)2009年9月

3 程序设计

311 编程环境

本程序用VC++610来实现,可以在Win-dows98P2000Pxp为操作平台的计算机上运行,并在机器上调试通过。

312 数据结构

为了提高算法的执行效率和节约内存,本文的算法引入了数据结构。

1)有序点表 用于保存散乱点和排序后的点序列,表中每个元素的结构为:

typedefstruct{ doublex;

doubley; PP点的坐标 doublearCos; PP点的余弦值}Point;

2)存储器定义 用于存储点集分块之后的信息的类型实例,表中每个元素的结构为:

typedefstruct{

intpoint-index[MAXN];PP点属于的区间 intmember-count;PP点数 intminy,maxy;PP区间最大最小值

inttag;PP点的余切值

}Point-memo;313 凸包算法程序设计

程序输入:平面上n个点P1,P2,,,Pn的坐标(xi,yi)。

程序输出:点集凸包顶点。程序流程图如图4所示:

4 运行结果

用随机实数生成函数产生范围为(0~100)的给定点集,实验中选择点数为1000。分别用经典的Graham算法及本文算法对同一点集进行多次凸包运算,并比较它们的运算速度。使用Matlab6对实验结果进行绘图,如图5所示:

图5(a) 输入数据

图5(b) 凸包曲线

在程序中多次比较传统算法与改进算法的运行时间,结果如表1所示:

表1 传统算法与改进算法运行时间比较顶点数(1000)经典的Graham算法

450

图4 程序流程图

平均运算时间Pms

本文算法

100

(下转第43页)