地铁线路图的设计与实现 | 您所在的位置:网站首页 › 如何搜地铁路线图视频 › 地铁线路图的设计与实现 |
在北京、上海这样的一线城市,地铁绝对是上班族的首选交通工具,尽管有时挤得要命,但你真的找不出比地铁更准点的交通工具了。平时出门,我也总是习惯于在百度地图或丁丁地图里先查询一下地铁乘车路线,这些程序用起来非常方便。最近几天终于有点空余时间了,我就在想,我是否也可以写一个这样的程序?作为一名专业码农,我决定立刻动手。
首先,我给地铁线路图程序MetroGraphApp设定了几个关键目标: 1、 操作界面模仿百度地图,可以直接在线路图上设置起点和终点。 2、 路径查找算法不能太慢,绝大多数情况下,必须小于1秒。 3、 线路图数据必须是可配置的,适用于各个城市的地铁。
在介绍实现方法之前,先看一下最终的效果图: 图 1
图 2
【技术准备】 MetroGraphApp是一个.NET WinForm程序,开发工具是VS2010,开发语言是C#,绘图功能基于GDI+。线路图数据保存在一个XML文件中。查找路线时采用的是数据结构中的最短路径法。
【总体设计】 地铁线路构成了数据结构中的图(Graph),站点是节点(Node),站点之间的通行路径就是链接(Link),也就是边(Edge)。由于所有通行路径都是双向的,所以,这是一个无向图。在图中任选两点,两点之间的连续路径(Path)就是我们要查找的乘车路线。
图 3 在实际的地铁线路中,每条Link都属于一条线路(Line),例如:1号线、2号线,等等。两个站点之间可能有两条Link,它们分别属于不同的Line,这就是“双线并轨”。例如,在上海地铁线路中,“宝山路”到“宜山路”这段路径,“3号线”和“4号线”是在同一条轨道上运行的。如果是双线并轨,绘图的时候要并行绘制在一起。考虑到实用性和复杂性,我们在这里忽略多线并轨的情况。
整体类设计如下图所示:
图 4 MetroGraphView类是一个自定义的UserControl,用于绘制MetroGraph所表示的地铁线路图。默认情况下是没有任何数据的,所需的线路数据是通过LoadFromFile来装载的,该方法可以从指定的XML文件中读取数据。 在MetroGraphView控件上,用户可以通过鼠标点击的方式,选择起点和终点,然后控件会自动调用FindPath方法,获取两点之间的乘车路线(MetroPath),并将其绘制出来。
【源码实现】 MetroGraph、MetroNode、MetroLink、MetroLine、MetroPath类的实现都非常简单,这里不做过多解释,感兴趣的同学可以在文章末尾处下载源代码。
接下来,我们将重点介绍两个关键功能的实现: 1、 如何绘制线路图? 2、 如何查找乘车路线?
【如何绘制线路图】 地铁线路图的绘制可以分解为两个部分:节点绘制和链接绘制。 /// /// 绘制地铁线路图。 /// /// 绘图图面。 /// 地铁线路图。 private void PaintGraph(Graphics g, MetroGraph graph) { //绘制地铁路径 foreach (var link in graph.Links.Where(c => c.Flag >= 0)) PaintLink(g, link);
//绘制地铁站点 foreach (var node in graph.Nodes) PaintNode(g, node); }
细心的读者会发现,绘制Link的时候,有一个c.Flag>=0的筛选条件,这个Flag是干什么的呢?我来解释一下。 由于地铁的行车路径都是双向的,所以,我们在构造MetroGraph的时候,两个Node之间的Link一定是成对出现的,这两条Link的方向是相反的。但是在绘图的时候,我们只需要绘制其中的一条即可。这里就有一个逻辑问题,当绘制一条Link的时候,如何判断其反向Link已经绘制过了?我用了一个最简单的办法,直接在Link上放一个标志Flag,如果Flag=0,则绘制,如果Flag=-1,则不绘制。这个Flag是在构造XML数据的时候直接填进去的。 此外,Flag还有另外一个重要用途。文章前面提到过“双线并轨”的问题,例如图3中的A、B两个节点,他们之间存在Line3和Line4并轨的现象。对于并轨的两条Link,我们需要将其画成两条平行线,这两条线可能是水平线、垂直线,也可能是斜线。线之间没有空隙。如下图所示:
图 5 如何绘制这样两条平行线呢?办法很简单,只要将线段分别向两边移动一定距离即可(Flag的值可以控制移动方向)。假如Link的宽度是5px,那么移动的距离应该是 2.5px,由于DrawLine时用的Pen默认是居中对齐的,这样就可以画出没有间隙的两条平行线。代码如下:
/// /// 绘制地铁站点间的线路。 /// /// 绘图图面。 /// 地铁站点间的线路。 private void PaintLink(Graphics g, MetroLink link) { Point pt1 = new Point(link.From.X, link.From.Y); Point pt2 = new Point(link.To.X, link.To.Y);
using (Pen pen = new Pen(link.Line.Color, 5)) { pen.LineJoin = LineJoin.Round; if (link.Flag == 0) {//单线 g.DrawLine(pen, pt1, pt2); } else if (link.Flag > 0) {//双线并轨(如果是同向,则Flag分别为1和2,否则都为1) float scale = (pen.Width / 2) / Distance(pt1, pt2);
float angle = (float)(Math.PI / 2); if (link.Flag == 2) angle *= -1;
//平移线段 var pt3 = Rotate(pt2, pt1, angle, scale); var pt4 = Rotate(pt1, pt2, -angle, scale);
g.DrawLine(pen, pt3, pt4); } } }
节点的绘制就要简单多了。节点由圆圈和标签构成,圆圈在上,标签在下。标签的位置,是个值得改进的问题,因为标签可能会把Link线条给盖住。在本程序中,我认为影响不是很大,所以,我把标签统一放在圆圈的下方。 此外,对于可以换乘不同Line的站点,我们需要把圆圈画得大一些,这样更醒目。代码如下:
/// /// 绘制地铁站点。 /// /// 绘图图面。 /// 地铁站点。 private void PaintNode(Graphics g, MetroNode node) { //绘制站点圆圈 Color color = node.Links.Count > 2 ? Color.Black : node.Links[0].Line.Color; var rect = GetNodeRect(node); g.FillEllipse(Brushes.White, rect); using (Pen pen = new Pen(color)) { g.DrawEllipse(pen, rect); }
//绘制站点名称 var sz = g.MeasureString(node.Name, this.Font).ToSize(); Point pt = new Point(node.X - sz.Width / 2, node.Y + (rect.Height >> 1) + 4); g.DrawString(node.Name, Font, Brushes.Black, pt); }
【如何查找乘车路线】 这是图论中典型的路径搜索问题。当我处理这个问题的时候,我首先想到并实现的是最短路径法。最短路径法具有很强的现实意义,它表明路线比较节省时间。判断时间长短的办法由两个:一是通过累加Link上的权重(Weight)来判断,二是通过Link数量来判断。本文程序采用的是后者,因为根据实际经验,各个站点之间的运行时间是差不多的,以上海地铁为例,平均时间是大概3分钟一站。当然,我们没有考虑换乘的时间。代码如下:
/// /// 查找指定两个节点之间的最短路径。 /// /// 开始节点。 /// 结束节点。 /// 目标线路(为null表示不限制线路)。 /// 乘车路线列表。 private List FindShortestPaths(MetroNode startNode, MetroNode endNode, MetroLine line) { List pathtList = new List(); if (startNode == endNode) return pathtList;
//路径队列,用于遍历路径 Queue pathQueue = new Queue(); pathQueue.Enqueue(new MetroPath());
while (pathQueue.Count > 0) { var path = pathQueue.Dequeue();
//如果已经超过最短路径,则直接返回 if (pathtList.Count > 0 && path.Links.Count > pathtList[0].Links.Count) continue;
//路径的最后一个节点 MetroNode prevNode = path.Links.Count > 0 ? path.Links[path.Links.Count - 1].From : null; MetroNode lastNode = path.Links.Count > 0 ? path.Links[path.Links.Count - 1].To : startNode;
//继续寻找后续节点 foreach (var link in lastNode.Links.Where(c => c.To != prevNode && (line == null || c.Line == line))) { if (link.To == endNode) { MetroPath newPath = path.Append(link); if (pathtList.Count == 0 || newPath.Links.Count == pathtList[0].Links.Count) {//找到一条路径 pathtList.Add(newPath); } else if (newPath.Links.Count MetroPath path = new MetroPath(); if (startNode == null || endNode == null) return path; if (startNode == endNode) return path;
//如果起点和终点拥有共同线路,则查找直达路线 path = FindDirectPath(startNode, endNode); if (path.Links.Count > 0) return path;
//如果起点和终点拥有一个共同的换乘站点,则查找一次换乘路线 path = FindOneTransferPath(startNode, endNode); if (path.Links.Count > 0) return path;
//查找路径最短的乘车路线 var pathList = FindShortestPaths(startNode, endNode, null);
//查找换乘次数最少的一条路线 int minTransfers = int.MaxValue; foreach (var item in pathList) { var curTransfers = item.Transfers; if (curTransfers MetroPath path = new MetroPath();
var startLines = startNode.Links.Select(c => c.Line).Distinct().ToList(); var endLines = endNode.Links.Select(c => c.Line).Distinct().ToList();
var lines = startLines.Where(c => endLines.Contains(c)).ToList(); if (lines.Count == 0) return path;
//查找直达路线 List pathList = new List(); foreach (var line in lines) { pathList.AddRange(FindShortestPaths(startNode, endNode, line)); }
//挑选最短路线 return GetShortestPath(pathList); }
/// /// 查找一次中转的路线。 /// /// 开始节点。 /// 结束节点。 /// 乘车路线。 private MetroPath FindOneTransferPath(MetroNode startNode, MetroNode endNode) { List pathList = new List();
foreach (var startLine in startNode.Links.Select(c => c.Line).Distinct()) { foreach (var endLine in endNode.Links.Select(c => c.Line).Where(c=> c != startLine).Distinct()) { //两条线路的中转站 foreach (var transferNode in this.Graph.GetTransferNodes(startLine, endLine)) { //起点到中转站的直达路线 var startDirectPathList = FindShortestPaths(startNode, transferNode, startLine);
//中转站到终点的直达路线 var endDirectPathList = FindShortestPaths(transferNode, endNode, endLine);
//合并两条直达路线 foreach (var startDirectPath in startDirectPathList) { foreach (var endDirectPath in endDirectPathList) { var directPath = startDirectPath.Merge(endDirectPath); pathList.Add(directPath); } } } } }
//挑选最短路线 return GetShortestPath(pathList); }
【总结】 MetroGraphApp程序主要是应用了图论和GDI+的知识。最大的难点在于,如何更快地找出符合用户需要的乘车路线。 传统的深度遍历方法不能很好地解决我们的问题,我们需要在遍历之前,对前方的路径进行一次侦测,然后把那些不需要的路径全部“剪除”掉,这样就可以显著提高性能。 当然本文的算法并不能保证任意两点之间的路径,都能够在1秒之内找出,有些复杂的路径搜索还是会长达几十秒,只是这样的概率非常低。如果读者感兴趣,可以进一步研究改进。
最后补充一点,虽然这篇文章已经过去几年了,还是有人不断问我一些问题,这里集中回答一下: 1、xml路径数据是怎么产生的? 回答:我之前写过一个简单的矢量图设计软件,可以直接在界面上标记出节点和线条,然后生成xml文件,可惜现在这个程序现在找不到了。如果有网友确实想要,我可以重新写一个,不过需要付费的,哈哈^_^ 2、路径算法怎么实现的? 回答:其实文章已经写得比较清楚,如果文章看不懂,完整的算法就别看了,因为更看不懂的,这个不适合你,回去把数据结构基础知识好好补一下。另外,再次强调,这篇文章介绍的算法,纯粹是探讨技术的,如果有人想用于商业用途,还是省省吧,不是授权限制的问题,而是因为商业用途的地铁线路图程序,根本就不是简单的路径搜索,而是把任意两点之间的几条最优路径提前算好(有些特殊路径甚至需要人工挑选),然后缓存起来,用户每次查找的时候,根据起点和终点拼成一个KEY,然后根据key直接从缓存中读取,这样的时间复杂度就是O(1),没有比这更快的了。
代码见:MetroGraphApp.rar(百度网盘) |
CopyRight 2018-2019 实验室设备网 版权所有 |