留言板

尊敬的读者、作者、审稿人, 关于本刊的投稿、审稿、编辑和出版的任何问题, 您可以本页添加留言。我们将尽快给您答复。谢谢您的支持!

姓名
邮箱
手机号码
标题
留言内容
验证码

利用化简分割生成示意性网络地图

李佳田 贾成林 张蓝 李显凯 李应芸 罗富丽

李佳田, 贾成林, 张蓝, 李显凯, 李应芸, 罗富丽. 利用化简分割生成示意性网络地图[J]. 武汉大学学报 ● 信息科学版, 2017, 42(6): 721-725. doi: 10.13203/j.whugis20150010
引用本文: 李佳田, 贾成林, 张蓝, 李显凯, 李应芸, 罗富丽. 利用化简分割生成示意性网络地图[J]. 武汉大学学报 ● 信息科学版, 2017, 42(6): 721-725. doi: 10.13203/j.whugis20150010
LI Jiatian, JIA Chenglin, ZHANG Lan, LI Xiankai, LI Yingyun, LUO Fuli. Generating Schematic Network Maps by Simplification and Partition[J]. Geomatics and Information Science of Wuhan University, 2017, 42(6): 721-725. doi: 10.13203/j.whugis20150010
Citation: LI Jiatian, JIA Chenglin, ZHANG Lan, LI Xiankai, LI Yingyun, LUO Fuli. Generating Schematic Network Maps by Simplification and Partition[J]. Geomatics and Information Science of Wuhan University, 2017, 42(6): 721-725. doi: 10.13203/j.whugis20150010

利用化简分割生成示意性网络地图

doi: 10.13203/j.whugis20150010
基金项目: 

国家自然科学基金 41561082

国家自然科学基金 41161061

详细信息
    作者简介:

    李佳田, 博士, 教授, 主要研究方向为数值最优化方法与机器场景理解。ljtwcx@163.com

  • 中图分类号: P208

Generating Schematic Network Maps by Simplification and Partition

Funds: 

The National Natural Science Foundation of China 41561082

The National Natural Science Foundation of China 41161061

More Information
    Author Bio:

    LI Jiatian, PhD, professor, specializes in numerical optimization and scene understanding for robot.ljtwcx@163.com

图(5)
计量
  • 文章访问数:  1124
  • HTML全文浏览量:  100
  • PDF下载量:  423
  • 被引次数: 0
出版历程
  • 收稿日期:  2015-08-18
  • 刊出日期:  2017-06-05

利用化简分割生成示意性网络地图

doi: 10.13203/j.whugis20150010
    基金项目:

    国家自然科学基金 41561082

    国家自然科学基金 41161061

    作者简介:

    李佳田, 博士, 教授, 主要研究方向为数值最优化方法与机器场景理解。ljtwcx@163.com

  • 中图分类号: P208

摘要: 从整体到局部相互协调是示意性网络地图的关键所在,已有方法多是单纯地将线段作为示意基本单元,当空间要素分布不均衡时,容易产生示意结果全局表达不一致以及局部要素过于紧凑而变形的现象。考虑网络连通与网络闭合这两个性质,提出了一种化简分割生成方法,核心思想是根据连通化简网络,进而依据闭合构建网眼与线段两种基本示意单元。首先,对网络节点化简以及方向、长度调整,形成整体一致的化简网络;其次,将化简网络分割为网眼集合与线段集合;第三,建立从网眼至线段的示意化过程,通过网眼局部控制以避免要素过于紧凑。实验讨论了本文方法在不同示意约束规则之下的表现效果,与经典迭代寻优方法的对比分析表明,在网络整体形态保持与局部要素布置方面具有一定的优势。

English Abstract

李佳田, 贾成林, 张蓝, 李显凯, 李应芸, 罗富丽. 利用化简分割生成示意性网络地图[J]. 武汉大学学报 ● 信息科学版, 2017, 42(6): 721-725. doi: 10.13203/j.whugis20150010
引用本文: 李佳田, 贾成林, 张蓝, 李显凯, 李应芸, 罗富丽. 利用化简分割生成示意性网络地图[J]. 武汉大学学报 ● 信息科学版, 2017, 42(6): 721-725. doi: 10.13203/j.whugis20150010
LI Jiatian, JIA Chenglin, ZHANG Lan, LI Xiankai, LI Yingyun, LUO Fuli. Generating Schematic Network Maps by Simplification and Partition[J]. Geomatics and Information Science of Wuhan University, 2017, 42(6): 721-725. doi: 10.13203/j.whugis20150010
Citation: LI Jiatian, JIA Chenglin, ZHANG Lan, LI Xiankai, LI Yingyun, LUO Fuli. Generating Schematic Network Maps by Simplification and Partition[J]. Geomatics and Information Science of Wuhan University, 2017, 42(6): 721-725. doi: 10.13203/j.whugis20150010
  • 传统地图超出了一般用户的认知负荷,而示意性网络地图简单的地物表达可提供有利于心像对象形成的感知刺激,作为贴近空间认知的制图表达,能够帮助人们更快、更准确地解决网络相关问题[1-3]。示意性网络地图专注于网络结构主体,忽略无关细节,能够有效传递所关注区域的特定信息。然而,这种简洁的地图表达却缺少较为成熟的绘制模式,地图设计人员往往根据经验确定各节点、线段的位置。示意化网络中线段的长度、方向并不与实际网络一致,其概括性、抽象性决定了制作示意性网络地图是一个复杂且精细的过程,示意性网络地图的自动生成问题已经引起了国内外许多学者的关注[4-15]

    示意性网络地图生成方法多以线段为基本单元,可分为线段化简[4-6]与迭代寻优[7-15]两种类型。前者将网络中的线段以一系列满足约束的限定方向折线替代,并限制替代折线与原始线段的距离,保持与原始网络的相似性,其较难维持拓扑一致性或是未提供拓扑冲突处理方法导致示意化不完全,示意化要素易产生锯齿,不够简洁。后者在节点周围一定空间范围内迭代地为该节点寻找更符合示意化原则的新位置,并度量新位置与多个示意化约束的符合程度,新位置可能具有更低的符合程度或引起拓扑冲突,因此,这种方法具有不确定性。文献[13-15]认为基于线段的示意化算法拘束于点、线原始空间位置,违背了示意性网络地图的基本出发点,提出了以路径为单位的示意化算法,得到了更为美观、易读的示意性地图。

    本文提出一种化简分割思想的生成方法,将网络示意化过程转化为网络化简、网络分割、网眼/线段示意化及网络重组4个步聚。网络化简以形成整体一致的化简网络,网络分割以分离网络为网眼与线段,依据网眼之间拓扑邻接关系控制要素示意化以避免局部过于紧凑或出现拓扑冲突。

    • 示意性网络地图一般仅考虑原始网络的位置与结构信息,因此,必要的输入数据为网络节点坐标及其节点间连接关系。原始网络通常被组织为矢量格式,可经由拓扑检查与改正等操作得到所需数据。

      网络可以被自然地表达为图结构,描述为G=(VE),V代表节点,而E用来表示节点间的有序拓扑连接,在逻辑上对应于原始网络中的线状要素,但不表示要素实际形状。度为节点所连接线段的个数,度为2的节点为可删除节点,删除这些节点并不会改变网络拓扑结构。示意性网络地图中的线状要素应尽可能地平直避免不必要的弯曲。因此,可以调节线段的长度,使得删除节点操作不会引起线段相交拓扑错误[10],如图 1所示。此外,对于一些拓扑等价的网络结构,如自环(相当于一个节点)及具有相同节点的不同线段,需要添加辅助节点加以区分。

      图  1  连通化简

      Figure 1.  Connection Simplification

    • 示意化要素需要满足线段方向约束与长度约束。输入线段的方向、长度由其首尾节点位置决定,线段l(pipj)方向为pi指向pj的矢量,长度为pipj之间的欧氏距离。通常,示意性网络地图以水平与竖直四个方向为主要方向,即O= {oi = (i-1)π/ 2,i = 1,…,4},或者添加对角线四个方向构成八方向,即O= {oi = (i-1)π/ 4,i = 1,…,8}。将网络线段方向规范到最邻近方向以与网络原始形态保持相似。依据约束方向的不同,可以采用以下三种类型之一进行线段方向调整:① 四方向,即调整线段方向至水平(垂直)四个方向;② 增强四方向,水平(垂直)方向为主、对角线方向为辅,将线段调整至水平(垂直)四个方向,当出现角度冲突时可考虑调整至对角线方向;③ 八方向,八个方向作用相等,将线段方向调整至最邻近方向,出现角度冲突时考虑次邻近方向。

      调整线段方向后,依据式(1) 调整线段长度,

      $$len\left( {{p_i},{p_j}} \right) = \left[ {\frac{{{\rm{dis}}\left( {{p_i},{p_j} \times \cos \left( {o' - o} \right)} \right)}}{{\alpha \times le{n_{\min }}}}} \right]$$ (1)

      式中,[·]表示取整;dis(pipj)为输入长度;o为输入方向;o′为约束方向;lenmin为原始网络中最短线段在其约束方向的投影长度;α为示意化长度参数。式(1) 以各线段输入长度在其约束方向投影与α×lenmin的比值调整线段长度,α越大,示意化网络长度抽象程度越大,网络中各线段长度初始值越接近。

    • 网眼[16]指网络中线段围成的闭合面域,网眼内部不存在其它线段对其产生裁剪,也不存在其它网眼。如图 2所示,包含m1m2m3m4四个网眼,网眼的边界是闭合、非自相交的有序线段集合。定义复合网眼为由若干共享公共线段的网眼组成。网眼将网络主体离散为互不重叠的面域。

      图  2  网眼

      Figure 2.  Meshes

      网络中的线段或者属于网眼边界,或者是某一条独立线段,如图 3所示,网络被最终分割为若干网眼及线段。部分网络中不仅包含一个复合网眼,非闭合线段不属于任意网眼。

      图  3  网络分割

      Figure 3.  Network Partition

    • 网眼示意化即在不引起拓扑冲突条件下调整网眼边界线段的形状,使其满足示意化约束并且闭合。设网眼的边界线段为(l1l2,…,ln),边界闭合即各线段在水平(竖直)正方向投影总长度等于其在水平(竖直)负方向投影总长度,形式化描述如式(2):

      $$\begin{array}{l} \sum\limits_{i = 1}^n {len\left( {{l_i}} \right)} \cdot \cos \left( {o\left( {{l_i}} \right)} \right) = 0且\\ \quad \sum\limits_{i = 1}^n {len\left( {{l_i}} \right)} \cdot \sin \left( {o\left( {{l_i}} \right)} \right) = 0 \end{array}$$ (2)

      调节各线段长度以满足式(2),若边界线段中缺少方向为oi(i=1,3,5,7) 的线段(如图 4(b)中缺少方向为o5的线段),则边界示意化后网眼无法闭合,可通过查找边界中方向与oi最邻近的线段lj(方向oj),添加单位长度方向为oi的线段lilj之前或之后辅助闭合边界,如图 4(c)所示。oi最邻近方向是对称的,可以从角度增大与减小两个方面接近oi,因此,边界中对应线段lj也可能不只一条,如图 4(c)中线段lj1lj2,根据方向oj确定li

      图  4  通过辅助线段使边界闭合

      Figure 4.  Close Boundary by Assistant Line

    • 网眼之间通过公共边界相互拼合构成复合网眼,示意化过程如下。

      (1) 自复合网眼G中选择一个网眼作为起始ms,依据§1.3所述示意化得到m′s

      (2) 查找与G′(G′=m′s)邻接的网眼,依§1.3示意化网眼并检查拓扑,完成网眼示意化后更新G′,称这个过程为一次查找循环;

      (3) 重复步骤(2),直至完成所有网眼的示意化;

      (4) 结束。

      随着示意化过程进行,示意化网格空间被占用,已示意化的要素会影响后续要素的示意化,因此,需要考虑网眼示意化顺序。基于线段或路径的示意化算法中常依据线性结构的重要程度或是沿某一方向(如自上而下)确定示意化顺序。本文选择具有最小查找循环次数、最大邻接网眼数及最大面积的基本网眼作为起始。分布较均匀的网络中可以近似的选择位于网络中央的邻接度或面积较大的网眼作为起始。邻接网眼中首先示意化面积最大者,然后,顺时针示意化其余各网眼。

      网眼间仅存在公共边,其余非相邻节点若示意化后相对位置错误则可能导致示意化前后要素变形较大或拓扑冲突。已示意化各节点位置受限于示意化要素G′的边界b′,本文方法以b′上各相关节点作为参考点纠正当前网眼mi的示意化要素m′i中各待定点坐标,具体做法如下。

      (1) 组成m′i各点坐标域为Sm

      (2) 自m′i起分别逆时针、顺时针排列b′上各点得到b1b2

      (3) 依次检索b1b2上各点加入集合R,直到其坐标域为SRSm= Sm

      (4) 对于每个点pmi,示意化后为p′,若p不属于mi的已定位相邻点,对于每个已定位点q∈R, 示意值后为q′;

      对于每个点qR,示意化后为q′,若(px-qx)(p′x-q′x)<0,则调整m′i中相关线段长度,使p′x=q′x

      若(py-qy)(p′y-q′y)<0,则调整m′i中相关线段长度,使p′y=q′y

      (5) 结束。

      此外,当示意化空间不足以摆放当前网眼mi的示意化要素m′i时,网眼间存在拓扑冲突(示意化要素重叠)。首先令组成mi各线段长度为1并重新示意化,若仍冲突则维持m′i各线段长度并放大示意化格网空间,后续待示意化线段长度要同等放大。

    • 经过网络简化及网眼示意化得到示意化后的复合网眼集合及非闭合线段集合,网眼及线段间通过公共节点连接。选取结构最复杂的复合网眼G′作为基准将其他结构拼接于其上得到示意化的网络整体。拼接非闭合线段集于G′上时,若产生交叉则调整线段长度为不产生拓扑冲突的最大长度。拼接复合网眼G′iG′上时,若G′中对应位置不足以容纳G′i,则放大G′。

    • 实验环境为Matlab 2012b,实验数据为墨西哥市铁路运输网络(http://www.cityrailtransit.com/maps/mexico_map.htm),原始网络如图 5(a)所示,节点为站点分布,网络共包含161个节点,178条线段,提取得到18个网眼。

      图  5  示意化结果的比较

      Figure 5.  Comparison of Schematization Result

      图 5(b)5(c)分别为增强四方向约束与八方向约束下的本文方法示意化结果。结果对比如下:增强四方向约束与八方向约束结果均没有产生拓扑冲突,说明以网眼为单位的示意化及纠正过程是有效的;增强四方向仍是以四方向为主要约束,由于网眼边界线段多被约束为四方向,使得那些边界包含过多斜向线段的网眼容易产生较大变形,例如17、12、13、6号网眼;八方向约束能够与原始网络保持较高形态相似,上述4个网眼均没有产生不良变形,优于四方向约束;对于网络中的线段集,八方向约束同样具有优势。

      图 5(d)为Stott等提出的迭代寻优算法[11]示意化结果与八方向约束结果的对比分析。① 迭代寻优思想算法是在节点的邻域确定最优位置,因此,部分线段示意结果呈现不满足八方向的倾斜状态,使得结果表达一致性较差,如18、17、10号网眼顶部边界线段;② 由于网络化简使得八方向约束结果具有更好的网络整体面积、长度与方向一致性,而Stott算法结果在16号、13号网眼位置面积相对过大,在部分线段集位置长度与方向与原始网络相差较大;③ 与以网眼为单位相比,以线段为单位的示意化较难顾及到局部要素形态,更容易出现不良变形,例如1、4与10号网眼位置。

    • 本文在网络化简的基础之上以“网眼+线段”为基本单位建立一种新的网络示意化方法。从实验结果看,化简步骤使得示意结果在网络整体表现上具有一致性,引入网眼能够顾及局部要素形态,使得计算结果更加合理。在分析方法的结果时,只是从现象上予以解释说明,没有严谨地经过理论分析得出结论,这将是以后的工作方向。

参考文献 (16)

目录

    /

    返回文章
    返回