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