用于示态的算法（地铁）地图

Question

这是一个远景，但我想我可能会在开始肮脏的工作之前尝试。

我有一个项目来构建一个应用程序，该应用程序将用于定义的输入站（顶点）和行（边缘），即某些公共交通的真实地图，将给定的地图示意到地铁地铁地图。我已经对这个问题进行了一些研究，这是一个与3-SAT问题相同的NP完整问题。我也有一些关于如何生成这样的地图的理论想法，但它们还不够详细。

我正在寻找的是此问题的其他现有解决方案，某种伪代码，几乎（几乎）其他编程语言等中的一些真实代码，作为回报，我有更多时间在应用程序的其他方面工作。

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

Answer 1

如果您在Google上搜索“地铁图布局问题”和“ Metro Map Line Crossing”，您会发现很多参考文献，因为它在过去10年中进行了非常积极的研究。

这个问题似乎根本不是微不足道的，将“艺术”特征转化为数学约束似乎是最困难的任务之一。

无论如何，这是我发现的三个出版物（在许多其他许多出版物中）：

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

地铁图上的线交叉最小化

地铁图布局问题

恩！

Answer 2

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

Answer 3

这只是用手势的一些建议 - 与少许盐一起服用。

我对“地铁”地图的概念是一条线倾向于定期间隔的八个主要方向和站点之一。

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

我将从您的主要路线（例如，城市循环）开始，然后按重要性顺序添加其他路线。

对于每条路线，您想找到最接近的近似值，该近似是在八个主要方向上传播的最少的直线。您可以从实际坐标的边界框开始，将其分成网格，然后找到从网格正方形到网格正方形的“地铁”路线，然后连续完善该路线以减少弯曲的数量而不扭曲地图，从而将其分开，然后将其分开。太多了，如果可能的话，没有与其他路线进行过境。

完成此操作后，将每条线扩展，以使连续的电台在“地铁”视图上相同。

我的猜测是，您仍然需要支持对结果的手动调整。

祝你好运！

Answer 4

感觉像计划问题。看起来您的硬约束是：

• 每个站都必须在某个点上。一个点在网格上，点之间的距离为x（我会在2厘米上做这个静态）

• 同一地点不应有2个站

• 应该有足够的空间来绘制车站标签。请注意，可以从分配站的点分配标签的不同说明。

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

看起来您的软限制是：

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

然后将类似流口水的计划者扔在上面， 这是护士名册的硬性和软限制的示例.