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

作者: 日期: 2017年5月22日

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

论文报告,

评论关闭。