位于道路网中某个顶点的用户想要到达某个地方。事实上用户的确切目的地可能与计划路径关系不大,因为确切的目的地并不会影响我们的初始方向。我们到达目的地有很多的条路径,其实绝大部分路径是重合的。许多目的地对于用户来说是等效的。我们提出了一种自动找到这些等价目的地的方法,并通过所得到的这些集群来简化路网。我们将这个问题模型化为有根,边缘加权的树中的聚类问题。我们计算出的聚类网络提供了一个常数等价度因子。通过我们这种方法可以简化节点和边,使得我们寻找最短路径的时候能够不被整个地图所干扰,能够高效的找出最短路径[1]。
预备知识
图1:基于最短路径由图得到生成树: A. 路网G,用户的位置在s点; B. 计算s点到其他点的最短路径,得到一棵生成树
问题定义
定义1: 对于一棵根为s的树T =(V,E),对于任意的节点u和v我们计算它们之间的相似度∂(u,v) = w(Psx)/w(Psu). 其中x是u和v共同的最近父节点。我们可以理解为它们公共的路径部分越多,那么它们之间的相似度越大。(a和b是图中的节点。Pab指的是从a点b点的最短路径长度)
定义2: 对于节点u和v,如果∂(u,v)≥α并且∂(v,u)≥α,我们称他们α相似。我们将他们记为u⊕v。
定义3: 对于图G=(V,E),如果对于任意的两个节点u和v都有u⊕v,我们称该图为相似图。


- 详细连接:对于节点c和它的父节点p,我们使用最短路径连接这两个节点。这种连接方法能够保存原有的拓扑结构不变,但是会产生很多内部分支。
- 直接连接:对于节点c和它的父节点p,我们直接连接他们。这种连接方法很简单直接,但是失去了原有的拓扑结构。
- 简化连接:对于详细连接,使用简化算法[2]去除节点度大于2的边。
图6:三种连接方法的结果
以下是实验结果
图7:(a)表示原始输入的地图,红色点代表起始点;(b)详细连接;(c)简化的连接。在(b)(c)中,相似度值α大于0.8.
图7:(a)输入地图;(b)使用参数0.5的详细连接
这篇文章提出了一个对于树节点的聚类方法,该算法能在线性的时间内完成。 还提出了详细连接,直接连接和简化连接这三种连接方法。这种方法可以帮组我们简化图中的节点和边,在我们查询最短路径的时候能够避免很多不重要的节点和边,可以帮组我们高效快速的找到最短路径。
参考文献:
[1] van Dijk T C, Haunert J H, Oehrlein J. Location‐dependent generalization of road networks based on equivalent destinations[C], Computer Graphics Forum. 2016, 35(3): 451-460.
[2] Dyken C, Dæhlen M, Sevaldrud T. Simultaneous curve simplification[J]. Journal of geographical systems, 2009, 11(3): 273-289.
评论关闭。