论文部分内容阅读
Voronoi图是一个关于空间分割的基础数据结构,它以某种距离作为度量,以近邻原则对空间点集进行剖分。这种剖分结果能够很好地表达点与点之间的邻近关系以及点的影响范围等重要的空间关系信息,在求解点集或其它几何对象与距离有关的问题时起重要作用。城市Voronoi图是以L1平面上任意两点之间花费的最短时间为距离的一种新型Voronoi图,它解决了人们如何利用交通网络(如城市中的街道、地铁等)进行快速移动的问题。使用这样的交通网络寻找最短(时间)路径是相当重要的,因为人们总是倾向于用最短的时间来移动。在这种情况下,我们假设存在若干服务场所(如邮局、超市等),其中每一个服务场所都能满足需要,利用城市Voronoi图便可以解决借助交通网络到达所需时间最短的那个服务场所的问题。然而,城市Voronoi图要求交通网络路线仅为水平或垂直方向,这使它的应用受到了很大程度的限制,因为在客观世界中存在大量的具有一定倾斜度的交通路线,曲线交通路线则更具有一般性。为了使城市Voronoi图理论研究进一步贴近现实,进而应用于实际,本文将交通路线扩展为曲线,提出了一种新的城市Voronoi图——一般城市Voronoi图。主要工作如下:1.在城市Voronoi图的基础上,将交通路线由仅为水平或垂直方向的线段扩展为曲线,得到一般城市Voronoi图,给出了一般城市Voronoi图的定义、性质。2.给出了基于结晶生长方式构造一般城市Voronoi图的基本思想和生成算法,并用VC++编程实现。为了既能满足L1平面中距离的要求,又能够有效地跟踪曲线交通路线,本文采用了4-邻域结晶生长和8-邻域结晶生长相结合的结晶生长方式。算法思路清晰,可读性好,易于理解。3.给出了一种在一般城市Voronoi图中得到最短路径的简单方法。最短路径图是对空间的一个细分,它用于找到一个源点和一个查询点之间的最短路径。由于在一般城市Voronoi图结晶生长的过程中存在一条从源点到各个生长点的最短路径,故只要从查询点开始逆向跟踪生长点的生长过程,直至到达源点,便可以找到源点和查询点之间的最短路径。4.给出了一般城市Voronoi图的具体应用实例。