带线段障碍的城市Voronoi图生成算法研究

ON GENERATION ALGORITHM OF CITY VORONOI DIAGRAM WITH LINE SEGMENT OBSTACLE

带线段障碍的城市Voronoi图是城市Voronoi图的扩展。在步行或使用一般交通工具的情况下,客观世界中存在着许多不能逾越的障碍,甚至连交通网络也时常被一些障碍隔开。许多障碍可简化为线段障碍来处理。给出带线段障碍的城市Voronoi图的定义、性质,结晶生长算法和实例。算法简单,可扩展性好,具有较高的理论价值和应用价值。

The city Voronoi diagram with line segment obstacle is the development of the city Voronoi diagram. In real world when walking or general transportation vehicles are the common situation, there are lots of impassable obstacles, even traffic network can be spaced by obstacles either. Many obstacles can be handled as the simplified line segment obstacles, This text gives the definition, the nature, crystal growth algorithm of the city Voronoi diagram with line segment obstacles and its practice program. The method is simple, good in scalability, and is of high value in practice and theory.