7

这是一个很长的镜头,但我想我可以在开始肮脏的工作之前尝试一下。

我有一个项目来构建一个应用程序,该应用程序将为定义的输入站(顶点)和线路(边缘),即一些公共交通的真实地图,将给定的地图模式化为地铁地图。我已经对该问题进行了一些研究,这是一个相当于 3-SAT 问题的 NP 完全问题。关于如何生成这样的地图,我也有一些理论想法,但还不够详细。

我正在寻找的是该问题的任何其他现有解决方案,某种伪代码,(几乎)任何其他编程语言中的一些真实代码等,任何可以减少我花在算法本身上的时间的东西,这将使我有更多的时间来处理应用程序的其他方面。

如果有人看到任何可以帮助我的东西,我会非常感激。

4

4 回答 4

6

如果你在谷歌上搜索“地铁地图布局问题”和“地铁地图线交叉”,你会发现很多参考资料,因为在过去 10 年里,它一直在积极研究。

这个问题似乎一点也不小,将“艺术”特征转化为数学约束似乎是最困难的任务之一。

无论如何,这里有三本我觉得很有趣的出版物(在许多其他出版物中):

使用多标准优化的地铁地图布局

地铁地图上的线交叉最小化

地铁地图布局问题

于 2010-10-15T14:50:33.417 回答
3

与您的主题相似的研究:http: //graphics.stanford.edu/papers/routemaps/

于 2010-10-15T15:54:32.420 回答
1

这只是一些关于挥手的建议——加少许盐。

我对“地铁”地图的概念是,线路倾向于八个主要方向之一,并且车站有规律地间隔。

我假设您正在尝试将一组真实坐标转换为“地铁”坐标。

我将从您的主要路线(例如,城市环路)开始,然后按重要性顺序逐步添加其他路线。

对于每条路线,您都想找到最接近的近似值,该近似值使用在八个基本方向上行驶的直线数量最少。您可以从实际坐标的边界框开始,将其拆分为网格,然后找到从网格正方形到网格正方形的“地铁”路线,然后连续优化该路线以减少弯道数量而不扭曲地图太多,并且尽可能不引入与其他路线的交叉点。

完成此操作后,缩放每条线路,使连续站点在“地铁”视图上的距离相同。

我的猜测是您仍然希望支持手动调整结果。

祝你好运!

于 2010-10-15T03:11:56.410 回答
1

感觉是计划问题。看起来你的硬约束是:

  • 每个站都必须在一个点上。一个点在网格上,点之间的距离为 X(我会在 2cm 上将此设为静态)

  • 同一地点不应有 2 个车站

  • 应该有足够的空间来绘制车站标签。请注意,可以为标签分配与分配站点的点不同的方向。

  • 应该有足够的空间来画地铁线。

看起来你的软约束是:

  • 对于每个站点,最小化到分配给站点的实际地理位置距离。

然后在上面扔一些像 Drools Planner 这样的东西,这里有一个护士排班的硬约束和软约束的例子

于 2010-12-20T11:08:48.130 回答