Pull to refresh

Comments 67

Хороший и простой метод, несколько раз видел в иллюстрациях, но руки не доходили разобраться как это все реализовано. Спасибо.
Спасибо за статью. Как раз думал, как сделать красивую визуализацию.
Почему бы не реализовать это в 3D? У плоских графов есть известная проблема планарности — если у графа есть подграф K33 или K35, то его дуги будут неизбежно пересекаться на плоскости. Эта непланарность ухудшает наглядность картинки. Графы в трёхмерном пространстве, напротив, не имеют такой проблемы: в 3D надо постараться, чтобы дуги пересекались. Спроецировать кривую Безье на экран — элементарная задача. Осталось написать написать простую рисовалку и картинки как в этой статье станут трёхмерными.
Я не уверен, но вроде как 3D, спроецированный на экран, станет 2D, и ребра все равно будут пересекаться. Или вы имеете в виду, что можно будет этот граф повертеть?
Кстати, кривые Безье и B-сплайны — разные вещи.
Да, я имею ввиду, что можно будет повертеть. Различия между кривыми Безье и B-сплайнами, имхо, несущественны: и то и то кусочно полиномиальные кривые с дополнительными условиями гладкости в местах стыков. Одни условия дают сплайны, другие — кривые Безье.
Ну, в принципе, отличная идея. Может быть даже и возьмусь на досуге за такой проект. Только не вижу смысла ничего проецировать, по-моему лучше реализовать это все на OpenGL.
они не существенны с точки зрения наблюдателя, но с математической, на мой взгляд значительная. Безье это аппроксимизация 1го порядка, а Би-сплайны второго. Что на самом деле дает значительные отличия при визуализации. Безье проходит через начальную и конечную точку изгибаясь от опорной (не помню как точно называется). В то время как Би-сплайн не проходит через начальную и конечную точку, она как бы не дотягивается до них. Для того чтобы Би-сплайны проходили через конечную и начальную необходимо добавить пару фиктивных точек с координатами идентичными реальным начальным и конечным.

Извините за зануда-режим, но для меня эта разница является существенной.
Никогда не понимал, зачем же это вообще нужно-то? На стену повесить в рамочку?
Проанализировать связи в системе.
Просмотрите изображения еще раз. Вы уверены, что они как-то приспособлены для анализа?

Трудно представить себе такую реплику:
— Вот тут посмотрите, у вас связи вокруг класса идут в форме ласточки, перепишите класс, чтобы в этом месте образовался зайчик.
Зато легко представить себе такую:
— Почему здесь имеется связь напрямую к подсистеме БД из клиентского приложения? Необходимо убрать эту связку.
Очень легко отслеживать нарушение уровняй абстракции на таких диаграмах.
На каких диаграммах? image
Неудачно подобранные примеры нисколько не нивелируют полезность метода в общем.
Мы про топик с вами говорим, или что?
В топике говорится про алгоритм. По сути примеров применения в топике 2 (последние картинки описывают отдельных технический аспект алгоритма). Первая картинка достаточно показательна — по ней можно предоположить что у системы (возможно) достаточно посредственная архитектура, исходя из анализа связности и связанности пакетов. Хотя для того, чтобы сказать что-то предметное кроме графика нужно иметь представление и о самой системе изнутри.
Второй пример просто не совсем показателен, т.к. в нем уже заданы декртовы координаты вершин графа, но вот если бы они небыли так красиво заданы — то просто так граф было бы не разобрать.
Ну а коли в топике говорится про алгоритм, а не про включенные в него картинки — я привел более наглядный пример.
Давайте сойдемся на том, что такие графы сделаны для того, чтобы отдел программистов отдохнул, ползая по простыне графа и красиво расставляя узлы.
Абсолютно не понял к чему камент.
Такие графы сделаны для упрощения анализа системы, чтобы как раз людям не пришлось вручную приводить граф к удобоваримому виду (ну или чтобы значительно упростить им эту задачу). Без подобных утилит мы получим графы подобные тому, что я привел парой каментов выше — абсолютно нечитаемые.
Вы его привели, как пример полезного графа, а теперь он нечитаем. Давайте не будем дальше продолжать эту дискуссию.
В ответ на Ваш комментарий с неудачным графом-кандидатом на обработку я привел граф, на котором данный алгоритм полезен. А раз этот граф претендует на обработку подобными алгоритмами — значит он изначально нечитаем — все вполне очевидно, следите за комментариями, на которые получаете ответ, во избежание путаницы.
Теоретически, если на всех уровнях соблюдается инкапсуляция, подобных «нежелательных связей» возникнуть не может. Но в реальных приложениях да, согласен.

Визуализацию можно сделать динамической и выводить на монитор РМа. Чуть где «проросло» лишнее — сирены, мигалки, алярм! Зондер-команда выдвигается в отдел разработки
Все сводится к тому, что если команда настолько профессиональна, что способна создавать качественные продукты без помощи визуализации графов системы — то она не нуждается в средствах визуализации.
Для анализа полезней будет распечатать схему зависимостей модулей в виде таблички…
Не поймите меня неправильно, графы для анализа системы могут быть полезны во многих задачах.
Но представленные в посте — только для красоты, функциональная нагрузка практически нулевая.
Такая же польза, как от генерации фракталов.
А вот насчет фракталов вы ой как сильно ошибаетесь )))
UFO just landed and posted this here
Дизассемблированный код != архитектура программной системы. Во втором случае, если у архитектора руки не кривые, картинки вполне могут быть красивыми и полезными.
Очень красиво, прямо как windows seven mobile.
Нужно для того, чтобы дать визуальное представление и возможность грубо оценить те или иные аспекты визуализируемых данных.
Оцените какой-нибудь из представленных посте графиков и я с вами сразу же соглашусь.
Вас интересует зачем нужны графы?
Нет, в этом случае я бы так и спросил. Меня интересует полезность алгоритма, представленного в топике.
В одном из постов на хабре я видел такую картинку:
image
Метод немного похож на то, что описано мною. Согласитесь, было бы намного уродливее, если бы все ребра были прямыми?
да ладно Вам, прикольно же :)
Для проектирования правильной обвязки поводов за системником, у меня сейчас первый вариант, завтра будет второй.
ох, неблагодарное это дело. сколько красоту ни наводил — через пару недель снова все разбираешь и в клубок
UFO just landed and posted this here
Несмотря на просьбу автора не изобретать велосипед, все же спрошу: где можно прочитать о алгоритме вывода B-сплайнов?
Собственно, главный вопрос — почему расчет значений, кроме основного цикла, имеет еще два случая — для 3 начальных точек и 2 конечных, и откуда взяты формулы для них (с формулами в цикле ясно, в вики они описаны в «Uniform cubic B-splines» в самом конце страницы http://en.wikipedia.org/wiki/B-spline)
Не для 2 конечных, а для 3 конечных: в начале для построения кривой используются точки P0, P1, P2 и в конце PN-1, PN-2, PN-3.

Почему эти случаи рассматриваются отдельно? Потому что на краях условия сшивки другие. Ведь точек с индексами P-1 и PN нету, следовательно нужно придумывать что-то другое. Я взял следующие условия:
— Первая производная совпадает с направление вектора P1 — P0 (коэффициенты a1 и b1)
— Вторая производная равна нулю (чтобы кривизна была нулевой, т.е. a2 = b2 = 0)
— Остальные коэффициенты a0, b0, a3, b3 определяется из условия равенства на краях.
Простите, PN-1 не заметил. Теперь стало яснее, но вот еще такой момент: комментарием ниже вы говорите, что выводили формулы сами, однако какими-то материалами вы ведь все равно пользовались для этого, что, думаю, логично? Возможно, расскажете о том, как пришли к описаным вами выше условиям на краях?
Материалами не пользовался. Я просто обобщил свои знания по сплайнам на двумерное пространттво. Условия на краях вывел из общих соображений:
1. Кривая должна выходить из точки P0
2. Кривая должна касаться отрезка, соединяющей P1-P0
3. Кривая должна иметь нулевую кривизну: это стандартное условие для любых сплайнов (необязательно двумерных).

Аналогично для другого края.
Да, увы, русскоязычный интернет весьма беден сведениями о сплайнах («Кривая должна иметь нулевую кривизну: это стандартное условие для любых сплайнов»). Что поделать, буду искать на этот счет материалы на английском.
Я, ради спортивного интереса, выводил все формулы сам, поэтому книжку наподобие «B-сплайны для чайников» вряд ли смогу посоветовать. Скорее всего, такое есть в каких-нибудь книжках по выч.методам.
Удобно. Для наглядности можно ещё ползунок сделать, который будет значение β изменять с одновременным динамическим изменением картинки.
Собственно, так и было сделано. Вот только когда графы большие, все начинает жутко тормозить, поэтому этот ползунок был впоследствии ликвидирован.
Писал не я. Если уговорю, то может и выложим. Но сначала там нужно говнокод исправить, так что в любом случае это будет нескоро.
Спасибо за хорошую и объемную статью c примером на внятном языке.
UFO just landed and posted this here
А что такое связи между процессами?
pstree — это ведь просто дерево, нет? А в статье речь идет о графах.
Подскажите какие инструменты для визуализации в NET вы используете в своей работе?
Я? Никакие. Это не я картинки рисовал.
Возможно, я что-то упустил, но каким образом выбираются опорные точки для прорисовки сплайнов? То есть, с конечными точками всё понятно, а вот с промежуточными не всё ясно. Используется какая-то сетка?
Опорные точки считаются по формуле Ci = (Pi-1 + 4 Pi + Pi+1) / 6
Крайние точки считаются отдельно и равны соответствующим крайним контрольным точкам.

Это выглядит вот так:
image
(Коэффициенты 1/6, 4/6 и 1/6 вытекают из равенста первых и вторых производных при сшивке, можете проверить)
Нет-нет, с самим построением сплайна всё понятно. Тут интересней другое — как выбираются точки P1 и P2, в частности?
Точки P1, P2 и т.д. — это вершины дерева, через которые проходит путь между соединяемыми вершинами.
А построение дерева — это, видимо, отдельная задача, имеющая множество вариантов решения и не связанная непосредственно с данным алгоритмом визуализации. Спасибо за пояснения и саму статью.
>> А построение дерева — это, видимо, отдельная задача, имеющая множество вариантов решения

Да, вы совершенно правы. Вы строите дерево любым удобным для вас способом, а потом накладываете на него ребра описанным методом.
Интересная статья, спасибо. Еще бы с Graph# это соединить.
Если Вы дополнительно к этому алгоритму прикрутите интерактивность, например, возможность выделить все линии пучка другим цветом ивозможность оставить только часть графа, то подобный софт будет очень и очень востребован :-) Респект!
Sign up to leave a comment.

Articles