论文部分内容阅读
本文在概括介绍Voronoi图与Delaunay三角化的基础上，引出Power图和限定Voronoi图，针对Power图和限定Voronoi图现有生成算法中存在的缺点，对Power图和限定Voronoi图生成技术进行系统的研究。在对Power图生成技术研究方面，提出了一种实现简单、生成快速的Power图生成算法——Power图光栅扫描算法。在对限定Voronoi图生成技术研究方面，分析限定条件在限定Voronoi图中存在的充要条件，对已有的Voronoi梯形检测带细分算法进行了改进。在研究Power图和限定Voronoi图生成算法的基础上，本文还研究了Power图在物流路径规划中的应用和限定Voronoi图在煤层气数值试井中的应用。 本文主要完成的工作如下: (1)针对已有的Power图生成算法的缺点，提出一种思路简洁、结构简单、效率较高且易推广到高维空间的Power图生成算法——Power图光栅扫描算法，并实现该算法，最后给出算法实例证明其正确性和有效性。 (2)研究基于Power图和Google Maps的物流路径规划问题的解决方案，主要包括Google Maps中Power图可视化问题的研究和Google Maps中道路信息提取方法的研究。在以上研究的基础上，确定物流路径规划解决方案:使用本文提出的Power图光栅扫描算法构造出Power图，在Google Maps中对物流配送区域进行划分，并使用Dijkstra算法在提取出的Google Maps道路网中寻找最短路径。 (3)针对已有的限定Voronoi图生成算法的缺点，对已有的Voronoi梯形检测带细化算法进行改进，引入几个控制因子，使得在不影响算法收敛速度的情况下，生成的限定Voronoi图网格单元具有更好的质量。基于CGAL（Computational GeometryAlgorithms Library）实现该算法，最后给出算法实例证明其正确性和有效性。 (4)基于使用本文改进的限定Voronoi图生成算法构造的限定Voronoi图(PEBI网格)，实现对煤层气试井控制方程的数值求解，并与基于Delaunay三角形网格的试井方程求解结果进行比较，证明了限定Voronoi图可以更加精确地模拟复杂煤层气藏且能提高试井方程求解速度。