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

Question

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

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

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

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

Answer 1

如果您的真正问题是最小化线交叉点，那么有几种算法试图在图表中实现这一点。例如，检查此链接，还有更多算法用于电气设计自动化的自动布线，这些算法也用于此类图表，如Lee 算法或A* 算法。

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

最小化图中的线交叉点是一个困难的 NP-Hard 问题，请查看此链接（关于交叉点数）以获取更多信息。

祝你好运。