英语原文共 22 页，剩余内容已隐藏，支付完成后下载完整资料
绘制地铁图：一项调查
亚历山大·伍尔夫
计算机科学，研究和开发的手稿。
2007年7月9日：2007年11月5日收到：/修改/ DOI：10.1007/s00450-007-0036-y
摘要: 本文论述了地铁图的自动绘制。示意地铁图有两个特征使得它们不同于绘制类似于流程图和组织图之类的网络图。首先，大多数示意地铁地图不仅使用水平和垂直的线，而且还有对角线。这给在布局过程更多的灵活性，但同时也可能增加了问题的难度。其次，地铁地图是一个其组成部分有其地图用户大致已知的地理位置的网络的代表。在寻找一个清晰的网络布局时，必须尊重这一知识。由于视觉清晰度的原因，底层的地理位置可能会被扭曲，但它不能被放弃，否则地图用户将会感到迷惑。
在本文中，我们首先给出一系列应该被一个良好的地铁地图遵守的比较普遍接受的规则。接下来，我们研究了三个最新的绘制地铁图的方法，虔诚地分析其与上述规则相关的性能，并比较了彼此之间的结果图和图形设计师绘制的官方地铁图。然后，我们专注于一个基于混合整数线性规划一种被广泛使用的全局优化技术的方法。此方法保证找到一个满足上述提到的规则的一个子集（如果这样的绘图存在）并优化了与剩余的规则一致的加权费用的绘图。如果站标签包括在优化过程中，迄今为止只有中型网络可以绘制。最后，我们提供为什么画好的地铁地图是困难的（甚至没有标签）的证据。
工作赠款支持WO 758／4-2德国研究基金会（DFG）。
wiskunde Faculteit en Informatica、埃因霍温理工大学、邮政巴士旅游局513，5600 MB的埃因霍温，荷兰，WWW：HTTP：/ / www.win。星期二。NL /tilde;awolff
关键词：绘图·图标·地铁地图·octilinear布局·混合整数规划·NP困难
数学主题分类（2000）：05c62·90c90·68q17
1 引言
地铁地图是代表不同站点和地铁线路的地下地理网络示意图。其目的是为了方便线路中的乘客辨别方向。乘客想快速得到回答的问题如：怎样从A到达B？需要在哪里换乘？还剩下多少站？在哪里下车？严格意义上的地理学不仅没有必要回答这些问题，它甚至可以被阻碍。这一事实被哈利·贝克第一个发现和开发、哈利·贝克是一个1993年创造了伦敦第一个地铁示意图的工程绘图员。这张地图和哈利·贝克的命运在他们自己意义上是非常有趣的故事。美国作家加兰已经发表了一本值得一看的关于他们的书。贝克设计这个图是根据一系列简单的规则：蜿蜒的运输线被拉直压缩成水平线、垂直线、45°对角线（我们称这种布局为octilinear）。这种比例在拥挤的市中心区域的规模大于密集较低的郊区，以在相邻站点间创建更多统一规格。尽管存在的所有的失真，例如网络拓扑结构和一般意义上的几何形状，地铁站之间要保留一定的相对位置。这些原则也适用于大多数当代的手动设计的地铁图[21, 26]。传输网络可以很自然地表示为顶点对应站，边缘对应的事件站之间的物理连接的图。车站和轨道的真实位置决定了网络的输入布局。这种布局通常是平面的（如果不是可以利用在路口引入虚拟点来达到平坦化效果），因此，通过指定每个顶点的所有相邻顶点的顺时针顺序定义了一个拓扑输入嵌入。布局算法基本上需要找到平面上顶点的位置，这样一些所需的美学标准才能实现或优化，例如，最后的绘图应保存输入拓扑或沿着个别的地铁线路绕几个弯，大致保存输入几何。由于地铁站必须进行标记，网络布局算法也需要考虑标签既不与其它标签重叠也不与网络布局重叠的空间。
我们讨论的地铁图的概念，在这里是一个顶点位置（大多）固定的严格的路线图和 顶点可以在任何地方的“常规”图的有趣的妥协。第一种方法的目的是维护用户的心理地图，二次方法的目的是最大限度地提高美观度，如对称性。
有趣的是，地铁地图的布局原则不仅在地理环境中使用。三德万等人和斯比特使用地铁地图为比喻的方式来分别设想与互联网和“火车的想法”相关的抽象的信息。地铁地图的隐喻已经激发了艺术家，并已在广告中使用，见图1和2，分别为特别好的例子。斯托特等人提出了一个在地铁地图中绘制项目计划的原型工具。目前以正交设计为主的原理图的设计技术和工程应用，也可以利用octilinear绘图。Octilinear布局的主要好处是，他们可能可以在使用更少的空间和更少的弯曲同时仍然保持整洁。例如在VLSI设计中的X架构是生产octilinear芯片布局的最近的努力。布兰德斯等人介绍了一个概念：一个不同的应用程序是计算示意图的草图。一个草图可以是手工制作，或者是如电话线的真实位置的一个几何网络的物理嵌入。布兰德斯等人给出一个用于计算如何绘制一个正交图的草图有效的算法。然而，他们的算法不能扩展到四个方向以上。这是另一个可以绘制地铁风格的地图的可能的应用领域的方法。
概述：本文结构如下。
首先，我们给出了一系列比较普遍的应该由一个良好的地铁图遵守的规则，见第2部分。
图1: 泰特美术馆的海报
本文的主要贡献是列出了最近已经提出的一项关于绘制地铁地图的三种方法的调查。所有这些都依赖于一些调整以获得图纸来尽可能地满足上述规则的基础的优化机械。 由洪等人发明的这三种方法中的第一种，是基于一个力导向图布局方法的弹簧嵌入。驱动顶点运动的引力和斥力遏制物理模型的运动。他们是由一个类似模拟退火、局部优化算法计算增量的。斯托特和罗杰斯提出的方法二，采用基于爬山的多准则优化，是一个流行的通用的局部优化技术。诺林波拉和沃尔夫提出的第三种方法，依靠混合整数规划，这是一种广泛使用的全局优化技术。混合整数规划是非常强大的，但需要注意避免长时间运行。我们分析的三种方法相对于上面的规则列表的性能并比较已通过所有这些测试的基准输出（悉尼城铁网）。
图2：开源产品线的出版商OReilly。交换站代表的同时属于双产品线的书籍。
接下来我们关注基于混合整数规划的方法，因为它是唯一保证octilinearity的方法，它在我们看来，是一个地铁地图布局清晰的本质，见第四部分。这也是第一种致力于使用全局优化从而避免陷入局部极小的绘制地铁地图的方法。它与其他两个基于局部优化的方法形成了对比。然而，由于没有求解一般的混合整数规划的快速算法（MIPS）是已知的，我们绘制一些对于解决较大实力重要的启发式数据减速和提速的方法。我们也勾勒如何扩展基本MIP来结合图形与非重叠站标签的放置。这种结合学科被称为克劳和穆策尔图标。克劳、穆策尔和比努奇等人曾使用MIP配方制作图标。然而，他们的方法追随了塔马西亚的拓扑形状的度量方法，它是一种常见的绘制正交图的方法。该方法包括三个步骤：平面化、正交化，压实。第一步修复了嵌入，第二步是形状（对每个弯曲和角度被确定的边缘的序列），第三个步骤是顶点和弯曲的坐标。塔马西亚提到他的正交图形绘制方法进行了六角（即60◦-）图纸，但这第三步绘制更小角度不成功（如octilinear图纸案例中的45◦）。作为使用重量级MIP机械的理由，我们给关于一个限制版的地铁布局问题的NP硬度的劳伦伯格完美证明，即决定是否一个给定的图形可以用直octilinear边画。这个证明提到了男孩用来建立Meccano或Marklin模型的构建工具的机械结构，见第5节。Octilinear画图的难度和正交图绘制形成了鲜明的对比，其中塔马西亚表面拓扑形状的度量方法是有效的解。
我们总结了一些关注手工地铁图和机械制地铁图剩余差异的想法，并在第六节给出了一个开放问题。
在谈到我们的关注好的地铁图的规则列表之前，我们向感兴趣的读者提到一篇写的很好的关于绘制好的地铁网络的大众（德国）报纸文章。它包含了一些有趣的历史记录。
2规则
在这一节中，我们列出并激发出好的地铁地图应该遵守的规则。每一个规则或多或少涉及了至少2个关于宏、斯托特、罗杰斯、劳伦伯格或沃尔夫的文件，这些算法我们将在下一节中讨论。读者被邀请研究欧文顿的书来弥补自己的思维已选出哪组规则是正确的，其书中包含了来自世界各地的大量地铁地图。这是一个有趣的制图问题，是否现已存在的地铁图规则是最用户友好的选择。例如，在地铁地图中很难估算距离或旅行时间。在地铁图上，对同一个距离的不同车站口，在外围部分实际上可能有几公里远，但在城市中心只有几百米。为评估怎样拓展现有的地铁图，实际上是提供给乘客快速作出正确的决定，应该作出用户研究。
在列举规则之前，我们快速地大致梳理一下邸巴蒂斯塔 等人的符号。给定一个图G =（V，E），如果delta;地图对G的每个顶点v到不同的点delta;（V）的平面，且每边{ u，v }到一个简单的（约旦）连接delta;（U）和delta;（V）的曲线，我们说delta;是图G。如果对任何一对边，其相应的曲线有大多数普遍端点，图为平面。如果其有一个平面图，那么回想的时候图就是平面的。一个平面图将平面分割成称为面的连通区域。 无界限面作为外表面也被提及。嵌入是一个有用的平面图的抽象：它修复了每个顶点的边缘和外部面选择的圆形的顺序。现在，我们可以说，如果图是平面的，并给出了一个（平面）嵌入，则其是平面。
我们假设我们有一个简单的平面图G，这是我们参考用的地铁图 。我们还假设给定一个位置pi;（V）isin;R2对G的每个顶点v。这些地点通常将是一个地理地图上的地铁站的位置。（注意：由于我们不认为地铁图有直线的边缘，这些位置不定义嵌入。）
（R1）保持输入嵌入。这支撑乘客的内心（网络）地图。
（R2）限制所有线段为水平，垂直和两个45◦对角线四个octilinear取向。每一个定位都是双向的。这个限制使地图更清晰。
（R3）确保相邻或不相邻的站保持一定的最小距离。这增加了地图的可读性。
（R4）保证沿着特定地铁线的弯道个数是小的，尤其是在几条线相交的交换站。如果弯曲无法避免，则钝角优先于锐角，即优先顺序是135◦，90◦，和45◦。这条规则可以帮助乘客分辨地铁线。
（R5）保持地铁车站之间的相对位置。例如，一个在现实中在其他站北方的站点在地图上不应该的那个站下面出现。这支撑（地理）乘客的思维地图。
（R6）保持网络总边缘长度是短的。这间接使地图的密集区域可以得到较大的可用空间的份额。结合规则（R3）这也使相邻站之间的距离尽可能均匀。规则（R6）支持布局清晰。
（R7）按线所属给每边上色。假定每行有一个独特的颜色。如果有一个边{u，v}属于k线，则k线相对于该边缘的副本（即所谓的多边缘）必须被绘制。它们对于{u，v}的规则应该竟可能与与事件{u，v}相关的其他边缘的规则一致。以帮助地图用户用人眼就可以辨别并跟随一条线，着色是有必要的。
（R8）标签站和其名字要确保标签不掩盖其他标签或网络部件。最好是所有的标签都放在两交换站之间的线的同一侧；为了节省空间，在一个水平线的站也可以交替标记在线的上面和下面。标签对于可读性好的图是必不可少的。
显然，每个地铁地图只能是妥协上述的一个标准。例如，一个有最小数目直线弯曲的图可以极大地扭曲的精神图，相反，保留精神地图可能需要大量的弯曲。
现在我们想尽可能正式地在这一点上陈述地铁图布局问题。 让L为覆盖G的一条线，即，G的一组的路径和周期，例如，G的每一个边缘属于至少一个L的元素。元素L isin; L被称为线和对应的底层传输网络的地铁线。
为了问题描述的简洁性，我们现在不坚持为（多）边着色（规则（R7））并放站标签（规则（R8））。计弯道数的时候，地铁线路仍发挥作用，参见规则（R4）。沿着G的一个边缘的多边缘（着色线）的排序本身是一个有趣的研究课题并且据发现最近还受到了一些关注。更多关于标签位置的放置，参见第4.6节。
（a）地理布局 （b）官方地图的相应剪裁
图3：悉尼城铁地铁网络
问题（地铁地图布局问题）：给定的平面图G =（V，E）的最大度为8，顶点坐标在R2，线G覆盖L，找如何画图G合适，即，尽可能遵循规则（R1）–（R6）用直线绘制。
注意最大顶点度为8的图的限制是使用octilinear边缘方向的限制所带来的一个直接结果。如何解除这个限制将在结论中讨论（见第6节）。
剩余内容已隐藏，支付完成后下载完整资料
资料编号：[29464]，资料为PDF文档或Word文档，PDF文档可免费转换为Word
以上是毕业论文外文翻译，课题毕业论文、任务书、文献综述、开题报告、程序设计、图纸设计等资料可联系客服协助查找。
