这是一个很长的镜头，但我想我可以在开始肮脏的工作之前尝试一下。
我有一个项目来构建一个应用程序，该应用程序将为定义的输入站（顶点）和线路（边缘），即一些公共交通的真实地图，将给定的地图模式化为地铁地图。我已经对该问题进行了一些研究，这是一个相当于 3-SAT 问题的 NP 完全问题。关于如何生成这样的地图，我也有一些理论想法，但还不够详细。
我正在寻找的是该问题的任何其他现有解决方案，某种伪代码，（几乎）任何其他编程语言中的一些真实代码等，任何可以减少我花在算法本身上的时间的东西，这将使我有更多的时间来处理应用程序的其他方面。
如果有人看到任何可以帮助我的东西，我会非常感激。
如果你在谷歌上搜索“地铁地图布局问题”和“地铁地图线交叉”，你会发现很多参考资料，因为在过去 10 年里，它一直在积极研究。
这个问题似乎一点也不小，将“艺术”特征转化为数学约束似乎是最困难的任务之一。
无论如何，这里有三本我觉得很有趣的出版物（在许多其他出版物中）：
！
与您的主题相似的研究：http: //graphics.stanford.edu/papers/routemaps/
这只是一些关于挥手的建议——加少许盐。
我对“地铁”地图的概念是，线路倾向于八个主要方向之一，并且车站有规律地间隔。
我假设您正在尝试将一组真实坐标转换为“地铁”坐标。
我将从您的主要路线（例如，城市环路）开始，然后按重要性顺序逐步添加其他路线。
对于每条路线，您都想找到最接近的近似值，该近似值使用在八个基本方向上行驶的直线数量最少。您可以从实际坐标的边界框开始，将其拆分为网格，然后找到从网格正方形到网格正方形的“地铁”路线，然后连续优化该路线以减少弯道数量而不扭曲地图太多，并且尽可能不引入与其他路线的交叉点。
完成此操作后，缩放每条线路，使连续站点在“地铁”视图上的距离相同。
我的猜测是您仍然希望支持手动调整结果。
祝你好运！
感觉是计划问题。看起来你的硬约束是：
每个站都必须在一个点上。一个点在网格上，点之间的距离为 X（我会在 2cm 上将此设为静态）
同一地点不应有 2 个车站
应该有足够的空间来绘制车站标签。请注意，可以为标签分配与分配站点的点不同的方向。
应该有足够的空间来画地铁线。
看起来你的软约束是：
然后在上面扔一些像 Drools Planner 这样的东西，这里有一个护士排班的硬约束和软约束的例子。