Хабр Курсы для всех
РЕКЛАМА
Практикум, Хекслет, SkyPro, авторские курсы — собрали всех и попросили скидки. Осталось выбрать!
Хабр доступен 24/7 благодаря поддержке друзей
Комментарии 67
Хороший и простой метод, несколько раз видел в иллюстрациях, но руки не доходили разобраться как это все реализовано. Спасибо.
Спасибо за статью. Как раз думал, как сделать красивую визуализацию.
Красота!
Почему бы не реализовать это в 3D? У плоских графов есть известная проблема планарности — если у графа есть подграф K33 или K35, то его дуги будут неизбежно пересекаться на плоскости. Эта непланарность ухудшает наглядность картинки. Графы в трёхмерном пространстве, напротив, не имеют такой проблемы: в 3D надо постараться, чтобы дуги пересекались. Спроецировать кривую Безье на экран — элементарная задача. Осталось написать написать простую рисовалку и картинки как в этой статье станут трёхмерными.
Я не уверен, но вроде как 3D, спроецированный на экран, станет 2D, и ребра все равно будут пересекаться. Или вы имеете в виду, что можно будет этот граф повертеть?
Кстати, кривые Безье и B-сплайны — разные вещи.
Кстати, кривые Безье и B-сплайны — разные вещи.
Да, я имею ввиду, что можно будет повертеть. Различия между кривыми Безье и B-сплайнами, имхо, несущественны: и то и то кусочно полиномиальные кривые с дополнительными условиями гладкости в местах стыков. Одни условия дают сплайны, другие — кривые Безье.
Ну, в принципе, отличная идея. Может быть даже и возьмусь на досуге за такой проект. Только не вижу смысла ничего проецировать, по-моему лучше реализовать это все на OpenGL.
они не существенны с точки зрения наблюдателя, но с математической, на мой взгляд значительная. Безье это аппроксимизация 1го порядка, а Би-сплайны второго. Что на самом деле дает значительные отличия при визуализации. Безье проходит через начальную и конечную точку изгибаясь от опорной (не помню как точно называется). В то время как Би-сплайн не проходит через начальную и конечную точку, она как бы не дотягивается до них. Для того чтобы Би-сплайны проходили через конечную и начальную необходимо добавить пару фиктивных точек с координатами идентичными реальным начальным и конечным.
Извините за зануда-режим, но для меня эта разница является существенной.
Извините за зануда-режим, но для меня эта разница является существенной.
Никогда не понимал, зачем же это вообще нужно-то? На стену повесить в рамочку?
Проанализировать связи в системе.
Просмотрите изображения еще раз. Вы уверены, что они как-то приспособлены для анализа?
Трудно представить себе такую реплику:
— Вот тут посмотрите, у вас связи вокруг класса идут в форме ласточки, перепишите класс, чтобы в этом месте образовался зайчик.
Трудно представить себе такую реплику:
— Вот тут посмотрите, у вас связи вокруг класса идут в форме ласточки, перепишите класс, чтобы в этом месте образовался зайчик.
Зато легко представить себе такую:
— Почему здесь имеется связь напрямую к подсистеме БД из клиентского приложения? Необходимо убрать эту связку.
Очень легко отслеживать нарушение уровняй абстракции на таких диаграмах.
— Почему здесь имеется связь напрямую к подсистеме БД из клиентского приложения? Необходимо убрать эту связку.
Очень легко отслеживать нарушение уровняй абстракции на таких диаграмах.
На каких диаграммах? 
Неудачно подобранные примеры нисколько не нивелируют полезность метода в общем.
Мы про топик с вами говорим, или что?
В топике говорится про алгоритм. По сути примеров применения в топике 2 (последние картинки описывают отдельных технический аспект алгоритма). Первая картинка достаточно показательна — по ней можно предоположить что у системы (возможно) достаточно посредственная архитектура, исходя из анализа связности и связанности пакетов. Хотя для того, чтобы сказать что-то предметное кроме графика нужно иметь представление и о самой системе изнутри.
Второй пример просто не совсем показателен, т.к. в нем уже заданы декртовы координаты вершин графа, но вот если бы они небыли так красиво заданы — то просто так граф было бы не разобрать.
Ну а коли в топике говорится про алгоритм, а не про включенные в него картинки — я привел более наглядный пример.
Второй пример просто не совсем показателен, т.к. в нем уже заданы декртовы координаты вершин графа, но вот если бы они небыли так красиво заданы — то просто так граф было бы не разобрать.
Ну а коли в топике говорится про алгоритм, а не про включенные в него картинки — я привел более наглядный пример.
Давайте сойдемся на том, что такие графы сделаны для того, чтобы отдел программистов отдохнул, ползая по простыне графа и красиво расставляя узлы.
Абсолютно не понял к чему камент.
Такие графы сделаны для упрощения анализа системы, чтобы как раз людям не пришлось вручную приводить граф к удобоваримому виду (ну или чтобы значительно упростить им эту задачу). Без подобных утилит мы получим графы подобные тому, что я привел парой каментов выше — абсолютно нечитаемые.
Такие графы сделаны для упрощения анализа системы, чтобы как раз людям не пришлось вручную приводить граф к удобоваримому виду (ну или чтобы значительно упростить им эту задачу). Без подобных утилит мы получим графы подобные тому, что я привел парой каментов выше — абсолютно нечитаемые.
Вы его привели, как пример полезного графа, а теперь он нечитаем. Давайте не будем дальше продолжать эту дискуссию.
В ответ на Ваш комментарий с неудачным графом-кандидатом на обработку я привел граф, на котором данный алгоритм полезен. А раз этот граф претендует на обработку подобными алгоритмами — значит он изначально нечитаем — все вполне очевидно, следите за комментариями, на которые получаете ответ, во избежание путаницы.
Теоретически, если на всех уровнях соблюдается инкапсуляция, подобных «нежелательных связей» возникнуть не может. Но в реальных приложениях да, согласен.
Визуализацию можно сделать динамической и выводить на монитор РМа. Чуть где «проросло» лишнее — сирены, мигалки, алярм! Зондер-команда выдвигается в отдел разработки
Визуализацию можно сделать динамической и выводить на монитор РМа. Чуть где «проросло» лишнее — сирены, мигалки, алярм! Зондер-команда выдвигается в отдел разработки
Для анализа полезней будет распечатать схему зависимостей модулей в виде таблички…
Вы пробовали?
А вот пример задачи. Пощёлкайте.
Нужно для того, чтобы дать визуальное представление и возможность грубо оценить те или иные аспекты визуализируемых данных.
Вас интересует зачем нужны графы?
да ладно Вам, прикольно же :)
Для проектирования правильной обвязки поводов за системником, у меня сейчас первый вариант, завтра будет второй.
Несмотря на просьбу автора не изобретать велосипед, все же спрошу: где можно прочитать о алгоритме вывода 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 определяется из условия равенства на краях.
Почему эти случаи рассматриваются отдельно? Потому что на краях условия сшивки другие. Ведь точек с индексами P-1 и PN нету, следовательно нужно придумывать что-то другое. Я взял следующие условия:
— Первая производная совпадает с направление вектора P1 — P0 (коэффициенты a1 и b1)
— Вторая производная равна нулю (чтобы кривизна была нулевой, т.е. a2 = b2 = 0)
— Остальные коэффициенты a0, b0, a3, b3 определяется из условия равенства на краях.
Простите, PN-1 не заметил. Теперь стало яснее, но вот еще такой момент: комментарием ниже вы говорите, что выводили формулы сами, однако какими-то материалами вы ведь все равно пользовались для этого, что, думаю, логично? Возможно, расскажете о том, как пришли к описаным вами выше условиям на краях?
Материалами не пользовался. Я просто обобщил свои знания по сплайнам на двумерное пространттво. Условия на краях вывел из общих соображений:
1. Кривая должна выходить из точки P0
2. Кривая должна касаться отрезка, соединяющей P1-P0
3. Кривая должна иметь нулевую кривизну: это стандартное условие для любых сплайнов (необязательно двумерных).
Аналогично для другого края.
1. Кривая должна выходить из точки P0
2. Кривая должна касаться отрезка, соединяющей P1-P0
3. Кривая должна иметь нулевую кривизну: это стандартное условие для любых сплайнов (необязательно двумерных).
Аналогично для другого края.
Я, ради спортивного интереса, выводил все формулы сам, поэтому книжку наподобие «B-сплайны для чайников» вряд ли смогу посоветовать. Скорее всего, такое есть в каких-нибудь книжках по выч.методам.
Удобно. Для наглядности можно ещё ползунок сделать, который будет значение β изменять с одновременным динамическим изменением картинки.
Спасибо за хорошую и объемную статью c примером на внятном языке.
Подскажите какие инструменты для визуализации в NET вы используете в своей работе?
Возможно, я что-то упустил, но каким образом выбираются опорные точки для прорисовки сплайнов? То есть, с конечными точками всё понятно, а вот с промежуточными не всё ясно. Используется какая-то сетка?
Опорные точки считаются по формуле Ci = (Pi-1 + 4 Pi + Pi+1) / 6
Крайние точки считаются отдельно и равны соответствующим крайним контрольным точкам.
Это выглядит вот так:
Крайние точки считаются отдельно и равны соответствующим крайним контрольным точкам.
Это выглядит вот так:
(Коэффициенты 1/6, 4/6 и 1/6 вытекают из равенста первых и вторых производных при сшивке, можете проверить)
Нет-нет, с самим построением сплайна всё понятно. Тут интересней другое — как выбираются точки P1 и P2, в частности?
Интересная статья, спасибо. Еще бы с Graph# это соединить.
Если Вы дополнительно к этому алгоритму прикрутите интерактивность, например, возможность выделить все линии пучка другим цветом ивозможность оставить только часть графа, то подобный софт будет очень и очень востребован :-) Респект!
Зарегистрируйтесь на Хабре, чтобы оставить комментарий
Визуализация графов. Метод связывания ребер