|
ru.algorithms
- RU.ALGORITHMS ----------------------------------------------------------------
From : Ivan Cachinsky 2:469/142.19 18 Jul 2002 11:26:29
To : Nickita A Startcev
Subject : "Красивая" визуализация графа.
--------------------------------------------------------------------------------
18 Июл 02 09:40, Roman Dawydkin -> Nickita A Startcev:
NS>> Какие есть идеи по красивой визуализации графа?
NS>> Для каждой пары вершин известно "псевдорасстояние" между ними,
NS>> хочется чтоб "близкие" вершины отображались рядом, а далекие - далеко.
RD> В поставке Java SDK от Sun есть demo-апплет GraphLayout, там именно
RD> это и происходит. Задаются вершины и желаемые расстояния между ними. Всё
Прикольно... я года три назад делал примерно похожее, хотя о сановском аплете не
знал:)
Идея у меня была такая.
Все вершины представляются механическими точками с массой 1 и электрическим
зарядом +1. Все ребра - пружины некоторой жесткости (она вычисляется), длина
пружин задается юзером как степень желабельной близости вершин. Соответсвенно,
ребра притягивают (или отталкивают) вершины, которые они соединяют, сами по себе
вершины отталкиваются. Ребра также имеют заряд +1 на 1 длины (независимо от
"растяженности", т.е. заряд пружины есть f(её длины) ;) - но так лучше) и вес 1
(всего). Однако, заряд пружины не действует на вершины, которые она связывает, и
наоборот. Самое хитрое: всё это изначально помещается на поверхность сферы,
радиус которой вычисляется от количества вершин и ребер. При этом вершины
свободно плавают по поверхности сферы, а пружины-ребра проходят напрямую сквозь
сферу. Все силы также действуют по прямой через внутренность сферы. Hачальная
расстановка вершин на сфере - от балды. Каждый момент времени вычисляются все
силы (ньютоновские и кулоновские, кроме гравитационных;), перемещения и
скорости. Система довольно быстро приходит в некоторое динамическое равновесие.
С этого момента включается некоторое малое трение - нужно удалить из системы
излишки кинетической энергии. Система плавно замрет очень близко от положения
равновесия. Этот момент отслеживается так: суммарная оценка кинетической энергии
(сумма модулей скорости вершин) стремится к 0. Дальше: крутим камеру обзора
вокруг сферы, минимизируя количество видимых из камеры пересечений ребер и
вершин. Дальше, найдя это положение, пересчитываем все координаты (поворачиваем
к "нам") и плавно так сжимаем её в элипсоид вдоль z (вглюбь экрана),
"расплющивая" её в блин. Поскольку мы всё это делаем плавно, то система
аккуратно "разъедется", и большинство пересечений исчезнут (если повезет). Я при
этом еще и плавно увеличивал радиус сферы по осям x и y - чтобы разместить две
поверхности в одной. В конце концов задняя и передняя стенки сферы сольются в
радостном экстазе и ты получишь искомое плоское изображение;)
Грабли и фичи.
1. Ситуация а. Имеем граф из 4 вершин и со всеми 6 ребрами. Возможны два
расположения - вершины образуют выпуклый четырехугольник, 1 пересечение ребер,
либо имеем треугольник и 1 вершина внутри - пересечений нет. Этот алгоритм
находит правильное расположение почти сразу.
2. Ситуация б. Всего две вершины, связанные ребром, при этом изначально
поставленные так, что расстояние между вершинами больше или меньше длины
пружины, т.е. в системе есть потенциальная энергия Гука. Вот тут во всей красе
себя покажет твой метод интегрирования. Поскольку трения нет, то физически они
должны колебаться вокруг положения равновесия до конца веков с _одинаковым_
периодом и амплитудой. Если алгоритм интергирования хотя бы чуть-чуть врет в
одну сторону, то система либо остановиться, либо её порвет как тузик грелку! Я
до этого допер не сразу ... %( Метод прямоугольников, как и метод трапеций,
применим плохо :(. Частично лечится небольшим изначальным коэффициентом трения
(положительным или отрицательным;).
3. Работа алгоритма очень сильно зависит от коэффициентов, точнее их корректного
подбора. Тут придется взять карандаш и всё аккуратно просчитать.
Кстати, в ситуации б) равновесное расстояние не будет равно длине пружины, так
как вершины сами по себе отталкиваются.
4. Перед кодированием необходимо запастись очень толковым учебником
(справочником) по аналитической геометрии. Так, расстояние между двумя
скрещивающимися прямыми через коэффициенты их уравнений навскидку посчитать
сложно, а в 4 из 5 учебников есть только формула с жуткими символами, не имеющая
никакого отношения к реальности;), так как искомая формула записывается в три
строчки жутких дробей;). Я кстати пользовался нашим бауманским учебником, но его
смели с прилавков почти сразу еще года три назад:(.
5. Производительность... Стоимость тольково реализованного алгоритма для n
вершин, m ребер и T шагов по времени - O(nmt), достаточно с большим
коэффициентом при О... При этом m может достигать n(n-1)/2... Hо можно очень
даже оптимизировать...
6. Мою статью по этой байде я переслать не могу - шибко здоровая, а сети пока
нема%(, но можешь поискать её на www.bmstu.ru. Её обещали опубликовать в
материалах конференции СHТК2000, но я как-то не проверял. Где-то был исходник на
MSVC6, но глюкавый и недописанный - так как готовился к конференции и сколько
успел, столько успел;) Его в принципе могу переслать.%)
ЗЫ. Кстати, есть еще широко известный класс алгоритмов, применяемых при
трассировке разводки печатных плат. Там несколько другая специфика, но суть та
же. Там применяются ломаные с осепаралельными сегментами, при этом как правило
больше 1 слоя. Толковое описалово можно найти в нашей кафедральной книжке.
Hавскидку примерно так: Е.С.Пугачев, "Алгоритмы, применяемые при конструировании
ЭВМ", изд-во МГТУ им. Баумана, 2001. Две недели назад я её видел в Москве на
олимпийском, так что возможно найдешь. Кстати, Пугачев, насколько я помню,
работал(-ет) на CADENCE Systems, занимается (-лся) именно спектрой, правда для
сановских спарков... Если не в курсе - CADENCE SPECCTRA самый крутой авторутер
(трассировщик) в мире;)
Ладно, будут вопросы - спрашивай;)
Ivan
--- IDA Pro 4.04
* Origin: ic'station 18 Июл 02,11:26 (2:469/142.19)
Вернуться к списку тем, сортированных по: возрастание даты уменьшение даты тема автор
|
"Красивая" визуализация графа. 