避免线的交叉

Question

我有时间线应该出现与其起源日期相关的约会(见下文).此问题的问题是将图标放在正确的位置,以便连接线不会交叉.

那么到目前为止我所拥有的:

为了便于操作,我实现了区域,时间线分为区域,我将所有图标放在此区域中.这是穿过的线的问题.

在理想的解决方案将是这一个,随机散播线不交叉的图标:

我曾想过制作"网格图案",定义图标可以放置的位置,而不是逻辑哪一个连接到哪个点.(例如,区域中最多12-15个点,它们都可以在同样的日期)我在项目实施之前已经实现了我的JSFiddle,但它并不保证我想要的结果,也没有进行优化.

//See the demo on JSFiddle

所以请,也许你有一些想法如何达到我想要的结果(见上文).

Answer 1

如果您只需要线条不交叉，则可以将图标放在您想要的任何位置，进行初始分配，然后，只要可以交换一对图标以使这些线条的总长度减少，就可以这样做。正确性的证明非常简单。假设我们有一对交叉作业

A   B
 \ /
  X
 / \
Y   Z

X交点在哪里。假设AXYorBXZ是非退化三角形，则根据三角形不等式得出

d(A, Y) + d(B, Z) < d(A, X) + d(X, Y) + d(B, X) + d(X, Z)
                  = d(A, X) + d(X, Z) + d(B, X) + d(X, Y)
                  = d(A, Z) + d(B, Y),

所以我们将像这样重新分配。

A   B
|   |
|   |
|   |
Y   Z

收敛是有保证的，因为总长度总是递减的。

您可能还希望线条不要靠近在一起，在这种情况下，我建议您研究力导向布局算法。