Avoid intersections of lines

Question

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

Answer 1

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.

Answer 2

To make sure the lines don't cross, connect the points on the timeline to the appointment icons as follows:

• Put the icons in a preliminary position (like a grid) at the top
• Go through the timeline points from left to right
• Calculate the direction from the point to each unconnected icon
• Connect the point to the icon in the left-most direction

The direction from the timeline point to the icon can be calculated in JavaScript using the Math.atan2(dy,dx) function, where dy is y_icon - y_point and dx is x_icon - x_point. The result is greater than π/2 for lines going to the left, π/2 for vertical lines, and less than π/2; for lines going to the right.

After this is done, you can move some of the icons down along their connecting line to create a more visually pleasing distribution. This can be done without the risk of creating crossed lines.

If you want to move an icon horizontally, check the direction of its neighbouring lines, to make sure you don't get too close to other lines.

UPDATE:

I think it may be beneficial to work from left to the middle and then from right to the middle, to get a more symmetrical distribution; otherwise points on the far right get connected to icons on the bottom row, which is not ideal.

You'll need to experiment with dragging the icons down along their connecting line. Starting with the bottom row and working your way up, you could decide how low to drag the icons based on how far the timeline point is from its neighbours, whether the neighbouring lines are convergent, how close to vertical the connecting line is, drag the icons in the center or on the sides first... You'll have to check to see which options give the best looking result.