结合网格保刚性的多目的地地图布局优化方法

发布时间：2020-05-30 11:39

【摘要】：多目的地地图是一种根据多个目的地来简化城市道路显示的导航地图,可以引导用户前往多个目的地。多目的地地图要尽可能详细地显示目的地周围的道路信息尤其是细节信息,同时保证调整某些道路后拓扑结构受到的影响要最小,使得用户能够把握地图的整体和局部内容之间的联系。当前越来越多的用户使用移动设备进行城市道路的导航,而城市道路网有分布密度大、拓扑结构复杂等特点。因此,如何在有限显示空间上高效地显示多目的地地图是一项具有挑战性的工作。本文提出了一种利用三角网格刚性的多目的地地图生成方法。该方法通过用户选择多个关注区域,系统自动简化出相关的道路网信息并利用路网上的地图元素生成delaunay三角网格,然后以关注区域的凸包点为界将该三角网格划分为上下文区域网格和关注区域网格。布局优化过程中本文通过对关注区域凸包点的操作以调整某个道路区域的显示空间大小,随后对上下文区域的三角网格做保刚性算法以及对关注区域的网格做保相似算法来确保调整后的关注区域和上下文区域的道路网络结构尽量不变。最后,本文利用拓扑错误的量化方法来控制系统的优化过程。本文的主要贡献有:(1)提出了一种结合三角网格特性和道路特性的城市地图布局优化方法,该方法生成的地图保持了输入地图的总体的拓扑结构同时,也优化了地图上目的地区域道路的布局。(2)针对特殊的非均匀平滑网格,提出了一种保刚性的多策略二次优化方法,该方法可以有效地保持非均匀平滑网格的刚性。本文经过若干实验结果算法的比较测评,验证了本文工作的有效性。使用本文方法可以快速生成多目的地地图,该地图保持了地图总体的拓扑结构的同时,有效地调整了地图上部分道路的布局。使得用户可以在有限的显示空间内快速地浏览自己关注区域的详细信息。
【图文】：

过程图,地图,预处理,过程

即该射线可以穿越小的道路射到等级高的道路上，而等级高的道路无法被穿透射逡逑到等级低的道路上，比如射线能穿过主干道射到高速公路上却射不到主千道外的逡逑街道上，如图３．５（ａ）中所示的红色射线就不能穿过主干道射在高速公路上：在逡逑实际导航过程中，用户总会把离自己最近的道路作为首选，因此可见环方法有一逡逑定的实用性。逡逑由可见图算法搜索出来的道路并不相连，因此在这里本文运用Ａ＊搜索算法逡逑将可见图算法得出的各个道路环进行相连并计算所有道路环的并集去除重复的逡逑道路。这里得到的地图本文设为图Ｇ＝（Ｖ，Ｅ），邋Ｖ表示图中地点的集合，Ｅ表示道逡逑路的集合。得到简化地图后，本文仍要对地图数据进行压缩，这是因为在道路地逡逑图中原有很多地点并不是路径中的关键节点，即使去除也不会对道路的形状有太逡逑大的影响。反之利用这些点生成的三角网格必定有很多狭长面片，影响后续的计逡逑算，因此本文利用道格拉斯－普克算法［２２］来压缩道路数据，本文对一段道路中的逡逑各个路点进行采样

网格图,网格,道路,传统图形

逦（ｂ）逦（ｃ）逡逑图３．邋２：地图预处理的过程。（ａ）图为原始图像，（ｂ）图为经过道路简化和网逡逑格化的地图，图中蓝色网格为关注区域网格，红色网格为上下文区域网格。（ｃ）逡逑图为提取的凸包点逡逑ＯｐｅｎＳｔｒｅｅｔＭａｐ的数据结构将地图上的道路根据功能规划分为三种等级，，分逡逑别是高速公路、主干道和街道。因此本文对每种等级的道路设置“可见优先性”，逡逑即该射线可以穿越小的道路射到等级高的道路上，而等级高的道路无法被穿透射逡逑到等级低的道路上，比如射线能穿过主干道射到高速公路上却射不到主千道外的逡逑街道上，如图３．５（ａ）中所示的红色射线就不能穿过主干道射在高速公路上：在逡逑实际导航过程中，用户总会把离自己最近的道路作为首选，因此可见环方法有一逡逑定的实用性。逡逑由可见图算法搜索出来的道路并不相连
【学位授予单位】：厦门大学
【学位级别】：硕士
【学位授予年份】：2018
【分类号】：TP391.41;P283

【参考文献】