Избегайте пересечения линий

Question

У меня есть график, где должны отображаться встречи, связанные с датой их возникновения (см. Ниже). Проблема в этом вопросе заключается в расположении значка в нужном месте, чтобы линии соединения не пересекались.

Итак, что я пока имею:

Чтобы легко манипулировать, я реализовал зоны, временная шкала разделена на зоны, и я помещаю все значки, которые происходят в этой зоне. Вот проблема линий, которые пересекаются.

Идеальным решением было бы следующее: случайным образом распределить значки, чтобы линии не пересекались:

Я думал о создании "Pattern of Grid", определяющего места, где значок может быть размещен, и затем есть логика, какую из них соединить с какой точкой (например, максимум 12-15 точек в зонах, все они могут быть на также и в тот же день) Я реализовал свой метод JSFiddle перед реализацией в проекте, но он не гарантирует желаемый результат и также не оптимизирован.

//See the demo on JSFiddle

Поэтому, пожалуйста, может быть, у вас есть идеи, как достичь желаемого результата (см. Выше).

Answer 1

Если вам просто нужно, чтобы линии не пересекались, вы можете поместить значки в любое место, сделать начальное назначение, а затем, если это возможно, поменять пару значков так, чтобы общая длина этих линий уменьшилась. Доказательство правильности довольно просто. Предположим, у нас есть пара скрещивающих заданий

A   B
 \ /
  X
 / \
Y   Z

где X это точка пересечения. При условии, что AXY или же BXZ невырожденный треугольник, то из неравенства треугольника следует, что

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

Сходимость гарантирована, потому что общая длина всегда уменьшается.

Вы также можете захотеть, чтобы линии не были близко друг к другу, и в этом случае я бы посоветовал вам исследовать алгоритмы принудительного размещения.

Answer 2

Чтобы линии не пересекались, соедините точки на временной шкале со значками встреч следующим образом:

• Поместите значки в предварительном положении (например, в виде сетки) вверху
• Проходите точки шкалы слева направо
• Рассчитать направление от точки до каждого неподключенного значка
• Соедините точку со значком в крайнем левом направлении

Направление от временной шкалы к значку можно рассчитать в JavaScript с помощью Math.atan2(dy,dx) функция, где dy -_значок y -_точка y, а dx -_значок x -_точка x. Результат больше π/2 для линий, идущих влево, π/2 для вертикальных линий и меньше π/2; для линий, идущих направо.

После того, как это будет сделано, вы можете переместить некоторые значки вдоль их соединительной линии, чтобы создать более визуально приятный дистрибутив. Это можно сделать без риска создания пересеченных линий.

Если вы хотите переместить значок по горизонтали, проверьте направление соседних линий, чтобы убедиться, что вы не подходите слишком близко к другим линиям.

ОБНОВИТЬ:

Я думаю, что может быть полезно работать слева направо и затем справа налево, чтобы получить более симметричное распределение; в противном случае точки в правом верхнем углу соединяются с иконками в нижнем ряду, что не идеально.

Вам нужно будет поэкспериментировать с перетаскиванием значков вдоль их соединительной линии. Начиная с нижнего ряда и продвигаясь вверх, вы можете решить, насколько низко перетаскивать значки, исходя из того, насколько далеко точка шкалы времени находится от ее соседей, сходятся ли соседние линии, насколько близко вертикальная соединительная линия, перетащите Сначала значки в центре или по бокам... Вам нужно проверить, какие варианты дают наилучший результат.