Алгоритм визуализации сети с наложениями

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

Пример на рис.1 показан пример с тремя сетями (желтая, зеленая и бордовая). Видно, что линии сходятся в одну. Необходим результат как на рисунке 2.

Кстати, тут не совсем оптимально разнесены, надо желтую с зеленной поменять местами.
Я разобрался как разводить наложенные прямые, а вот выбрать порядок, так чтоб кол-во пересечений было наименьшее кол-во, пока не знаю. Есть идея, искать участки (пути) состоящие из "накладных" линий, и начиная с участков с наибольшим кол-вом таких наложений высчитывать оптимальный вариант расположения этих линий, но тут есть нюанс. Например сходятся два участка, в одном линии состоят из 3-х линий, а в другом из 2-х. В одном получается, что оптимальнее располагать например желтую - синюю - бордовую, а в другом бордовую-желтую. Таким образом на стыке необходимо, как-то перекрещивать линии.
Возможно я изобретаю велосипед (скорее всего), но серфинг, толку мало дал, я нашел как рисовать параллельные прямые под разными углами, соединять их и т.д. Кстати, линии могут быть ортогональны и наклоны, кривых нет.
Т.е. я могу нарисовать с разложенными линиями, а вот как при этом разложении учесть условия оптимальности (суммарное минимальное кол-во пересечений)?
Может кто сталкивался с похожими задачами, ткинете носом пожайлуста. Крутиться в голове теория графов, но каков именно алгоритм?

0

6 вариантов всего... пусть программа попробует их все и сравнит количество пересечений

0

Это тестовый пример. Стартовых может быть до двадцати, а конечных в разы больше.

0

Пример более сложной сети.

0

Сообщение от bossyara Это тестовый пример. Стартовых может быть до двадцати, а конечных в разы больше.

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

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

Если кратко:
Шаг - минимальные изменения, например, поменять местами две соседние линии на каком-то отрезке. Вероятно, Вы используете подобные "шаги" в своём алгоритме "развода прямых".
Целевая функция - количество пересечений.

1. Разводите линии случайным образом.
2. Перебираете все возможные "шаги".
2а. Если нашёлся шаг, улучшающий целевую функцию, выполняете его. Переходите к пункту 2 для нового состояния.
2б. Если улучшающих шагов нет, то запоминаете решение. Переходите к пункту 1.

Количество перезапусков определите сами.

0