2014 dxdy logo

Научный форум dxdy

Математика, Физика, Computer Science, Machine Learning, LaTeX, Механика и Техника, Химия,
Биология и Медицина, Экономика и Финансовая Математика, Гуманитарные науки




Начать новую тему Ответить на тему
 
 Алгоритм визуализации сети с наложениями.
Сообщение01.03.2016, 18:46 


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

 Профиль  
                  
Показать сообщения за:  Поле сортировки  
Начать новую тему Ответить на тему  [ 1 сообщение ] 

Модераторы: Модераторы Математики, Супермодераторы



Кто сейчас на конференции

Сейчас этот форум просматривают: нет зарегистрированных пользователей


Вы не можете начинать темы
Вы не можете отвечать на сообщения
Вы не можете редактировать свои сообщения
Вы не можете удалять свои сообщения
Вы не можете добавлять вложения

Найти:
Powered by phpBB © 2000, 2002, 2005, 2007 phpBB Group