基于等价目的地的位置相关路网概括(Location-dependent generalization of road networks based on equivalent destinations)

位于道路网中某个顶点的用户想要到达某个地方。事实上用户的确切目的地可能与计划路径关系不大,因为确切的目的地并不会影响我们的初始方向。我们到达目的地有很多的条路径,其实绝大部分路径是重合的。许多目的地对于用户来说是等效的。我们提出了一种自动找到这些等价目的地的方法,并通过所得到的这些集群来简化路网。我们将这个问题模型化为有根,边缘加权的树中的聚类问题。我们计算出的聚类网络提供了一个常数等价度因子。通过我们这种方法可以简化节点和边,使得我们寻找最短路径的时候能够不被整个地图所干扰,能够高效的找出最短路径[1]。

预备知识

prerequisites

图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,我们称该图为相似图。

explain

图2:分别对定义1,定义2和定义3进行解释
对于根为s的带权的边的树,对于某一α阈值,我们希望能够对树中的节点进行划分,每个集合内的节点都满足α相似。
定理
定理1:对于任意的节点u和v,其中x是u和v共同的最近父节点,那么我们可以得到u⊕v⟺u⊕x∧v⊕x。其实将u⊕v的含义就是s到节点u和v的共有部分占总长度的比例,和u⊕x∧v⊕x的意思是一致的。该定理可以概括为如果两个节点相似那么它们分别和父节点也相似,反之亦然。
定理2:如果节点a和b是x的子节点,那么有w(Psa)≤ w(Psb) ∧ b⊕x ⟹ a⊕x 。其实对于Psa和Psb来说他们重合的路径长度是一样的,故由相似度计算公式可以得到,路径长度短的分母也小,值大,故如果b⊕x≥α,那么a⊕x≥α,因此有b⊕x ⟹ a⊕x。该定理可以概括为对于同一个父节点的两子节点,如果较长路径长度的子节点和父节点相似那么较短的也相似。
 dingli图3:分别对定理1和定理3进行解释
合并节点算法
该算法首先将每个节点都认为是一个集合,然后使用定理1和定理2对节点进行合并,然后对树得到很多划分块。

algorithm

图4:合并节点算法
merge
图5:节点合并后的结果
现在我们对节点进行了合并,减少了节点的数目,我们如何连接聚集后的这些节点呢?在这片文章中提出了三种连接的方法。
  1. 详细连接:对于节点c和它的父节点p,我们使用最短路径连接这两个节点。这种连接方法能够保存原有的拓扑结构不变,但是会产生很多内部分支。
  2. 直接连接:对于节点c和它的父节点p,我们直接连接他们。这种连接方法很简单直接,但是失去了原有的拓扑结构。
  3. 简化连接:对于详细连接,使用简化算法[2]去除节点度大于2的边。

method

图6:三种连接方法的结果

以下是实验结果

result1

图7:(a)表示原始输入的地图,红色点代表起始点;(b)详细连接;(c)简化的连接。在(b)(c)中,相似度值α大于0.8.

result2

图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.

评论关闭。