java - 检测多条弯曲线是否相交

Question

我正在制作泳道图，但无法想出一个好的算法来自动布置连接图中节点的线。我本质上想要的是这个。

但是，我现在没有任何防止线重叠或相交的保护措施，有时会变得非常困惑。

有谁知道一种方法来检测一条线是否会与任何已经绘制的线相交？我想到的一个想法是将路径存储在数组或表格中，并在每次计划绘制新线时检查整个表格，但这似乎效率不高。

我通过使用 GWT 在 javascript 和 java 中执行此操作，所以也许有一种简单的方法可以使用这些语言提供的工具之一来解决这个问题？

Answer 1

如果您真正的问题是最小化线的交叉点，有几种算法可以尝试在图表中实现这一点。检查this link例如，auto routing for electric design automation 中使用的算法也更多。也用在这种图表中，比如 Lee algorithm , 或 A* Algorithm .

我不知道你使用的工具是否有足够的灵 active 来实现这种算法，通常你需要根据特定类型的图表实现你自己的启发式算法，但我希望这个链接足以给你好主意。

最小化图中的线交叉点是一个困难的 NP-Hard 问题，检查 this link (about the crossing number)获取更多信息。

祝你好运。