Voronoi区域重心计算的研究

论文摘要

对公共设施进行选址是城市规划中经常遇到的问题。在选址过程中,我们希望既要充分体现该设施的利用价值、最大范围地服务社会,又要减少或避免由于各设施的重复覆盖所造成的资源浪费。Voronoi图在区域分割方面有着非常重要的应用。本文针对这一问题,对Voronoi区域重心的计算方法进行了研究。因为平面图形的重心通常被认为是该区域的平衡位置,若公共设施越接近平衡位置,在分布上显然应该是越均匀的。此结论可为选址位置的调整提供适当的参考和理论依据。随后,本文以石家庄市长安区附近的中学为例对本问题进行了说明和讨论。在文章的结尾处提出了有待解决的问题:考虑到一些实际因素（如人口分布、经济发展状况等）,选址的最佳位置就不一定是区域的几何重心,而更应该是带有实际意义属性值的重心。本文给出了解决该问题的一些设想。最后,对涉及到的算法,在附录中给出了用Visual C++语言实现的主要源程序。

论文目录

• 摘要
• Abstract
• 第一章 绪论
• 1.1 Voronoi 图的历史与发展
• 1.2 计算几何与Voronoi 图
• 1.3 论文的研究内容
• 1.4 论文的结构安排
• 第二章 Voronoi 图
• 2.1 Voronoi 图的定义
• 2.2 Voronoi 图的基本性质
• 2.3 Voronoi 图的应用
• 2.3.1 在计算几何理论中的应用
• 2.3.2 在最优化配置领域的应用
• 2.3.3 在几何形体重构中的应用
• 2.3.4 在物理、化学和分子生物学中的应用
• 2.3.5 其他应用
• 第三章 离散Voronoi 图
• 3.1 离散 V 图的定义
• 3.2 离散Voronoi 图的生成方法
• 3.2.1 基本思想
• 3.2.2 制作距离表
• 3.2.3 Voronoi 边的近似抽出
• 3.3 Voronoi 区域涂满的判定
• 3.3.1 圆的画法
• 3.3.2 涂满的判定
• 第四章 Voronoi 区域重心计算的研究
• 4.1 重心的计算法
• 4.1.1 两质点的重心
• 4.1.2 质点系的重心
• 4.1.3 凸图形的重心
• 4.2 Voronoi 区域重心的计算
• 4.2.1 基本思想
• 4.2.2 算法描述
• 4.2.3 算法说明
• 4.2.4 结果分析
• 4.3 Voronoi 区域重心的应用
• 4.4 问题的进一步扩展
• 致谢
• 参考文献
• 附录