论文部分内容阅读
线段障碍城市Voronoi图是在城市Voronoi图基础上的扩展。城市Voronoi图的提出是基于一种平面为L1的度量,要求交通网络路线是水平和竖直方向,并且可以在任意点自由进出交通网络的具体模型。但客观世界中没有障碍而直接通行的情况是相对较少的,绝大部分交通网络都被一个个各种形状的障碍隔开,在各种形状的障碍中,又以线段障碍最为重要,许多障碍可以近似为线段障碍来处理,因此研究线段障碍的城市Voronoi图是很有必要的。
本文给出了线段障碍城市Voronoi图的定义、性质和相关性质的简单证明,同时,给出了线段障碍城市Voronoi图的结晶生成算法和程序实现,该算法简单,无需复杂的数据结构,可读性好,还可推广到任意障碍的几何图形,文中结合实例给出了线段障碍城市Voronoi图的应用,较好地解决了有障碍的基于平面L1度量、交通路线为水平和竖直方向且以时间距离考虑的对平面区域的分割。