避免线的交点 [英] Avoid intersections of lines

问题描述

我有时间表，应该在哪里出现连接到它的起源日期的约会（见下文）。在这个问题上的问题是将图标放置在正确的位置，以便连接线不会交叉。

所以我到目前为止：

为了方便操作，我已经实现了区域，时间轴被分成区域并将所有起源图标放在此区域中。这是跨越的行的问题。

理想解决方案就是这一个，随机传播线条不会交叉的图标：

我曾想过制作网格图案，定义图标可放置的位置，而不是具有哪个连接的逻辑（例如最多12-15个点，它们都可能在同一天）我已经在 JSFiddle 在项目中实现之前，但它不保证我想要的结果，也不是优化的。

  //请参阅在JSFiddle上演示
  

所以，请你也许有一些想法如何达到我想要的结果（见上文） 。 解决方案

如果您只需要不要跨越的行，就可以将图标放在任何位置，进行初始分配并那么，只要可以交换一对图标以使这些线的总长度减少，就可以做到这一点。正确性的证明非常简单。假设我们有一对交叉分配

  AB 
 \ / 
 X 
 / \ 
 YZ 
  

其中 X 是交点。假设 AXY 或 BXZ 是一个非退化三角形，那么从三角不等式得出

  d（A，Y）+ d（B，Z） （B，X）+ d（X，Z）
 = d（A，X）+ d（X，Z）+ d（B， X）+ d（X，Y）
 = d（A，Z）+ d（B，Y），
  

，所以我们会重新分配。

  AB 
 | | 
 | | 
 | | 
 YZ 
  

保证收敛性，因为总长度始终在减少。

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

I have timeline where should appear the appointments that are connected to it's origin date(see below). Problem in this issue is positioning the icon at the right place so that the connection lines don't cross.

So what I have so far:

In order to manipulate easily I have implemented the zones, the timeline is divided into zones and I place all the icons that has origin in this zone. Here is a problem of the lines that crosses.

The ideal solution would be this one, randomly spread the icons that lines does not cross:

I've thought of making "Pattern of Grid", defining the places where the icon could be placed and than have logic which one to connect to which dot.(max 12-15 dots in zones for example,they all could be on the same date as well) I've implemented my though on JSFiddle before implementing in the project but it does not guaranty the result I want and is not optimised as well.

//See the demo on JSFiddle

So please, maybe you have some ideas how to reach my desired result(see above).

解决方案

If you just need the lines not to cross, you can put the icons wherever you want, make an initial assignment and then, as long as it's possible to swap a pair of icons so that the total length of those lines decreases, do that. The proof of correctness is pretty simple. Suppose we have a pair of crossing assignments

A   B
 \ /
  X
 / \
Y   Z

where X is the intersection point. Assuming that AXY or BXZ is a nondegenerate triangle, then it follows from the triangle inequality that

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),

so we will reassign like so.

A   B
|   |
|   |
|   |
Y   Z

Convergence is guaranteed because the total length is always decreasing.

You may also want the lines not to be close together, in which case I would suggest that you investigate force-directed layout algorithms.

这篇关于避免线的交点的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！