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