Диссертация (1090638), страница 16
Текст из файла (страница 16)
Отображение удаляет вершины графа имеющиеменьше двух связей (рис. 4.9). При этом если узел графа был связан с удалёнными узлами его "электрозаряд отталкивания" увеличивается на сумму зарядовудалённых узлов, связанных с ним (заряд сохраняется).1111111111111112R11144610RR182521Рис.
4.9. Схема действия отображения Последовательно применяя отображение , получим последовательностьграфов { }. → 1 → … → Последовательность обрывается, когда – один узел. Расположим графузел в центре системы координат. Построение отображения −1 будем производить по индукции. Пусть нам удалось получить удовлетворительное изображение графа , тогда переходим к графу −1 и координаты узлов, содержащиеся в , переносим в −1 (Рис. 4.10). Узлы графа −1 которые имеют одну94связь и, следовательно, не содержатся в равномерно распределяются вокругсвязанных с ними узлов (например, по окружности в плоском случае).1110-1R46-1R111111 11Рис.
4.10. Схема действия отображения −1После действия −1 применяется силовой алгоритм с динамической подстройкой . Сочетание этих алгоритмов позволяет существенно повысить скорость построения графов с помощи метода физических аналогий.4.2.2. Применение методов "фокус+контекст"Методы "фокус+контекст" предназначены для взаимодействия с изображениями большого объема и позволяют совместить в одном изображении глобальный вид всей структуры и детали некоторого фрагмента, находящегося вфокусе.Рассмотрим подход, использующий свойства гиперболической геометрии. Основным достоинством этой техники является взаимодействие с большими иерархиями данных. С математической точки зрения граф размещаетсяна гиперболической плоскости, а затем эта плоскость отображается на круговую область дисплея.
На гиперболической плоскости действуют законы неевклидовой геометрии, в которой параллельные линии расходятся в разныестороны, а длина окружности растет экспоненциально по отношению к радиусу. Это даёт два асимптотических свойства:для небольшого радиуса пространство выглядит плоским;95для больших значений радиуса и длина окружности и её площадь растутэкспоненциально в зависимости от радиуса.Это свойство делает гиперболическое пространство идеальным для размещения в нём иерархических структур. Опишем два способа отображения гиперболического пространства на единичный диск евклидового пространства.
В обоих случаях одна окрестность гиперболического пространства находится в фокусе в центре диска, в то время как остальная часть гиперболического пространства постепенно исчезает в перспективе по мере приближения кгранице диска.Рассмотрим первую каноническую модель – проективное отображениеили модель Клейна, которая отображает линии гиперболического пространствав прямые линии на плоскости, но искажает углы (рис.
4.11).Рис. 4.11. Схема отображения в гиперболическое пространство [98, 99]Если точка имеет координаты (1 , 2 , … , ) в первоначальном пространстве представления и гиперболическое пространство задано уравнением:96 2 + 1 2 + 2 2 + ⋯ + 2 = +1 2(4.8)Так же пусть задан диск :1 2 + 2 2 + ⋯ + 2 + (+1 − С)2 < С2 ,(4.9)Граница диска образованна пересечением плоскости +1 = С и конусом асимптот к гиперболоиду .Уравнения вложения → будут иметь вид:1′ = 1 , 2′ = 2 , … , ′ = ,′+1= √ ( 2 + 1 2 + 2 2 + ⋯ + 2 ),(4.10)′при этом отображается на "верхнюю" (+1> 0) часть гиперболоида.Уравнения отображение "верхней" части гиперболического пространства в круг имеют вид:′′+1= ,1′′ =С′1′+1, 2′′ =С′2′+1, …, ′′ =С′′+1(4.11)Соответственно уравнения композиции → → , будут иметь вид:′′ =С,0< <+1( 2 +1 2 +22 +⋯+ 2 )(4.12)97Рис.
4.12. Граф, вложенный в двухмерное гиперболическоепространство модели Ф.Клейна [98, 99]Рис. 4.13. Граф, вложенный в трёхмерное гиперболическое пространствомодели Ф.Клейна [98, 99]98От модели Клейна перейдем к другой модели, которая в некоторых случаях позволит наиболее наглядно отобразить информационное взаимодействие– это конформная модель Пуанкаре, которая сохраняет углы, но превращаетлинии гиперболического пространства в дуги на диске .Новая модель получается следующим образом. Рассмотрим сферу , экватором которой служит граница диска . Пусть – точка модели Клейна, ′–точка южной полусферы, проецирующаяся в точку , ′′ – точка пересечения с прямой ′ , где – северный полюс (рис. 4.14).
Сопоставив каждой точке точку ′′, получим преобразование диска . Полученную таким образом модель геометрии Лобачевского называют моделью Пуанкаре на диске [84, 98,99].Рис. 4.14.Рис. 4.15.Выясним, как устроены прямые в модели Пуанкаре. Хорде соответствует сечение южной полусферы , плоскостью, перпендикулярной диску .Это сечение представляет собой полуокружность, перпендикулярную границедиска (рис. 4.15). При проекции из полюса на плоскость образованную точками, и эта полуокружность переходит в дугу окружности, перпендикулярнуюгранице диска.
Таким образом, для модели Пуанкаре в диске прямыми являют-99ся дуги окружностей, перпендикулярные границе диска , что позволяет припостроении дуг графа использовать геометрические примитивы графическихбиблиотек (например, OpenGL) [98, 99].Опишем преобразование, отвечающее за переход от модели Клейна к модели Пуанкаре : → в формулах:1′ = 1 , 2′ = 2 , … , ′ = ,′+1= − √( 2 − 1 2 − 2 2 − ⋯ − 2 ),(4.13)это проекция на южную полусферу. – радиус . Находя точку A′′ пересечения прямой ′ c диском , будем иметь:′′ =С22(С+√( −1 −22 −⋯− 2 )),0 < < + 1(4.14)Теперь можно получить уравнения преобразования координат из первоначального пространства представления → в диск в модели Пуанкаре(рис.
4.16):′ =С22(+√( +1 +2 2+⋯+ 2)),0< < +1Рис. 4.16. Граф, вложенный в трёхмерное гиперболическое пространствомодели А.Пуанкаре [98, 99](4.15)100Вышеописанная техника не зависит от алгоритма размещения и являетсяотдельным шагом обработки при построении изображения графа. Эта независимость имеет положительные и отрицательные стороны. Положительной стороной такого подхода является возможность организации модульного построения программного обеспечения, в котором искажение, это отдельный шаг обработки, выполняемый между модулем размещения и модулем отображения.
Притаком подходе построение искажения может происходить существенно быстрее, чем работает алгоритм размещения, что важно для интерактивности. Отрицательной же стороной может являться невыполнение критериев, предъявляемых к конечному изображению для конкретной задачи.Среди существующих перспективных силовых алгоритмов визуализациитакже интерес представляют [97]:алгоритм Фрюхтерман-Рейнгольда;алгоритм Камада-Кавая.В первом алгоритме добавляется требование равномерного распределения вершин и модифицированы формулы для вычисления сил, действующих навершины.
( , ) =2⃗⃗⃗⃗⃗⃗⃗⃗⃗⃗|| − || ( , ) =|| − ||2(4.16) ⃗⃗⃗⃗⃗⃗⃗⃗⃗⃗(4.17)В алгоритме Камада-Кавая предлагается считать, что идеальная длинапружины равна кратчайшему расстоянию между вершинами в графе, а потенциальная энергия E такой системы определяется по формуле:12 = ∑−1=1 ∑=+1 (| − | − )2(4.18)Синтез методов визуализации позволит пользователю выбрать изображение, которое наиболее удовлетворяет критериям представления для конкретнойзадачи и облегчит восприятие и анализ представляемой информации.101Реализация разработанного метода даёт приемлемое время построенияравное 4-м секундам для графов содержащих около 300 узлов (обычно 40-60секунд). Это достаточно для графического представления развивающейся кризисной ситуации на экране ПЭВМ разрешением 1920х1080 пикселей на ПЭВМSony Vaio SVS1511X9R/B процессор Intel Core i7-3612QM с тактовой частотой2100 MHz; объем оперативной памяти 4 ГБ [98, 99].4.3. Программная реализация системы визуально-аналитическогосопровождения процессов обработки структурированных данныхс применением активного моделирования в условиях интенсивногоразвития событий в кризисных ситуациях.
Практические примерыНакопление, анализ и визуализации текстовых данных по тематикам, связанным с проявлениями таких негативных факторов, как террористическая активность, природные и техногенные катастрофы и стихийные бедствия, действия крупной организованной преступности, массовые волнения и т.п. легли воснову разработанной функциональной схемы системы мониторинга и анализатекущих событий (рис. 4.17).ИсточникиинформацииРегиональные,федеральные изарубежные СМИМодульпоискаСпециализированные интернетфорумыВремянныеряды, тренды,ВремянныерядыграфикиМодульобработкитекстовойинформацииСбор инакоплениеданныхМодульвизуализацииМодульмониторингаДневникипользователейИнформационноаналитическиеисточникиБазаданныхИнформационно-аналитическийанализГрафыСводныетаблицы,отчетыРис.
4.17. Функциональная схема системы мониторинга и анализа текущих событий [19]102Данная модель легла в основу прогнозирования развития локальных конфликтов в программном комплексе «Визуально-аналитическое сопровождениепроцессов обработки структурированных данных» [19, 100].Ниже приведены экраны работы СППР "Визуально-аналитическое сопровождение процессов обработки структурированных данных".На рис. 4.18 изображены графики функций определяемых формулой(3.15) для сравнения текущей наблюдаемой кризисной ситуации с модельютренда «Ирак». В соответствии с критериями один и два наблюдаем, что текущая кризисная ситуация соответствует локальному конфликту в «Ираке».
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
