Power图扫描生成算法的研究

论文摘要

Voronoi图是计算几何的重要分支,Power图是Voronoi图的一种重要推广,它是将欧氏距离推广到Power距离而形成的一种加权Voronoi图,具有很大的实用价值。本文在现有Power图理论的基础上,给出了一种生成Power图的新算法—扫描生成法,该算法隶属于离散生成方法。它利用屏幕的光栅特性,计算屏幕上每个像素点与生成元的Power距离,然后比较、排序,根据Power边上的点到某两生成元的Power距离相等这一特点,从而画出Power边,生成Power图。相比Power图的其他算法,该算法不仅思路清晰,程序设计简单,而且无需复杂的辅助数据结构,节省了大量的预处理时间和存储时间,并且可推广到高阶Power图的情况。作为应用举例,利用该算法生成的Power图,分析了石家庄市某区网通营业厅的覆盖区域问题,并就其分布的合理性进行了讨论。

论文目录

• 摘要
• Abstract
• 第一章 绪论
• 1.1 计算几何与Voronoi 图
• 1.2 Voronoi 图与Power 图
• 1.3 论文的研究内容
• 1.4 论文的结构安排
• 第二章 Voronoi 图
• 2.1 Voronoi 图的历史
• 2.2 Voronoi 图的定义及其性质
• 2.2.1 Voronoi 图的定义
• 2.2.2 Voronoi 图的性质
• 2.3 Voronoi 图的构造法
• 2.4 Voronoi 图的应用
• 第三章 Power 图及其应用
• 3.1 Power 图的定义
• 3.1.1 加权Voronoi 图的定义
• 3.1.2 Power 距离的定义
• 3.1.3 Power 图的定义
• 3.1.4 Power 球
• 3.2 Power 图的性质
• 3.3 Power 图已有生成算法
• 3.3.1 正则三角化构造法
• 3.3.2 离散生成法
• 3.4 Power 图的应用
• 第四章 Power 图的扫描生成算法
• 4.1 算法的基本思想
• 4.2 Power 图的扫描生成算法描述
• 4.3 算法中的两个重要影响因素
• 4.3.1 相邻生成元间的距离对Power 图的影响
• 4.3.2 动态确定阈值
• 4.3.3 相邻生成元的权重对Power 图的影响
• 4.4 与其它算法的比较
• 4.5 作图实例
• 第五章 Power 图的应用实例
• 5.1 应用实例
• 5.2 应用前景
• 第六章 总结与展望
• 6.1 本文工作总结
• 6.2 进一步研究工作
• 参考文献
• 致谢
• 附录