Трещина в голове

+ в цитатник

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

Комментировать

« Пред. запись — К дневнику — След. запись »

Страницы: [1] [Новые]

psv обратиться по имени Среда, 18 Апреля 2007 г. 17:12 (ссылка)

Ха=) Ну так мы этим же почти баяном занимались, когда крыши писали=) Сначала определяешь наверняка является ли граф планарным. Это делается по количеству узлов и рёбер. Потом можно даже двумя путями идти. Например можно отбросить все вершины с одним ребром. А потом начинаем воевать с покрывающими деревьями. Либо по-другому. Взять любой граф, двойственный данному и узлы этого графа будут как раз фрагментами плоскости. их мне ажется размещать будет легче.

Ответить С цитатой В цитатник

teal обратиться по имени Среда, 18 Апреля 2007 г. 17:25 (ссылка)

Да, с планарным-то просто довольно-таки. Хотя, дуги графически нужно располагать в соответствии с инженерными традициями: не просто так под любым углом, а используя точки перегиба, разрывы и т.д. Есть классный алгоритм Сугиямы, он как раз бы тут подходил, если б не циклы. Тут еще нужно учитывать, что все вершины графа взвешены. Задача -- рисование энергосети. Так что придется помедитировать =)

Ответить С цитатой В цитатник

psv обратиться по имени Среда, 18 Апреля 2007 г. 17:44 (ссылка)

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

Ответить С цитатой В цитатник

teal обратиться по имени Среда, 18 Апреля 2007 г. 17:54 (ссылка)

Ну прямо прописные истины говоришь. =) Этого не хватает. Даже "пружинный" алгоритм не справляется за приемлимое время. Каждое ребро представляется в виде пружинки, которая растягивается и стягивается, ну а вершины -- это типа атомов что-то, постоянно отталкиваются. Работает довольно быстро и результат дает неплохой, но для это задачи тоже не приемлимо. У нас есть решение, просто нужно найти время его запрограммировать.

Ответить С цитатой В цитатник

LiveInternetLiveInternet

-Подписка по e-mail

-Поиск по дневнику

-Интересы

-Постоянные читатели

-Статистика

Трещина в голове