Нужен алгоритм отрисовки графа, причем так, чтобы вершины располагались оптимальным образом, т.е. чтобы ребра пересекались минимальное число раз.
Т.е. дали на вход матрицу схемы московского метрополитена, на выходе получили что-то отдаленно ее напоминающее, а не исчерканный экран. :)
Скажите,плз, в каком направлении двигаться?
Соображения в общих чертах20.02.07 15:29 Автор: Heller <Heller> Статус: Elderman
Пусть координаты двух разных вершин, соединенных разными графами равны соответствено (x1;y1), (x2;y2), (x3;y3), (x4;y4). Соединены первые две точки и последние две. Можно сформулировать логическое условие их пересечения. Тут либо комбинация множества <>, либо ищешь точку пересечения двух прямых, проведенных через точки и смотришь, чтобы ее координаты попадали внутрь прямоугольника, построенного по этим точкам.
Короче должно получиться при пересечении 1, а при отсутствии оного 0.
Проверяешь пересечения для каждой пары ребер, получаешь количество пересечений, то есть критерий, который будет являться функцией кучи переменных - координат вершин. Далее применяешь любой алгоритм многомерной оптимизации и находишь оптимальное расположение точек на плоскости.
Отлично, но если узлов будет хотя бы сотня, боюсь я зависну надолго...21.02.07 19:52 Автор: Yurii <Юрий> Статус: Elderman
Гыг. Планарная проекция графа - вообще то NP-сложная задача.21.02.07 20:32 Автор: amirul <Serge> Статус: The Elderman Отредактировано 21.02.07 20:37 Количество правок: 1
подробно о проекте
Анализ криптографических сетевых...
новое сообщение
закрытая нитка
новое сообщение
в закрытой нитке
старое сообщение
