水流扩展思想的网络空间Voronoi图生成

摘要

顾及城市网络空间中设施点的网络路径距离而非传统的欧式距离的服务功能及相互联系,针对网络空间Voronoi图模型,建立了一种网络空间Voronoi图生成的栅格扩展算法.首先将图结构的边目标剖分为细小的线性单元,称做网络空间的栅格化,引入水流扩展思想,将事件点发生源视为“水源”,以栅格单元长度为扩展步长,让水流方向沿着网络上的可通行路径同时向外蔓延,直至与其他水流相遇或者到达边的尽头.该算法可方便地加入网络图结构中的多种约束,如街道边的单向行驶、节点的限制性连接等实际空间限制条件.通过大规模实际数据的数字城市POI点服务范围的试验,表明了该算法的高效率.