Гиперболическая укладка
Гиперболическая укладка (hyperbolic layout) графов (главным образом, деревьев) разрабатывалась под влиянием вопросов визуализации графов большого размера и интерактивности и предполагает выполнение следующих двух действий. Сначала выполняется алгоритм размещения графа в гиперболической плоскости (или пространстве), а затем показываются результаты в знакомой евклидовой плоскости (или пространстве) с использованием одной из моделей гиперболической геометрии. Этот способ изображения деревьев аналогично использованию рыбьего глаза при традиционном размещении деревьев дает эффект искажения, позволяющий рассматривать потенциально большие деревья.
Гиперболическая геометрия основывается на системе аксиом, почти аналогичной традиционной евклидовой системе, которая отличается от неё лишь одной так называемой 5-й аксиомой. Тогда как указанная аксиома евклидовой геометрии гласит о том, что если линия не проходит через точку, то существует в точности одна линия, проходящая через эту точку, которая является параллельной исходной линии (т. е. которая не пересекается с заданной линией и находится с ней в одной и той же плоскости), в гиперболической геометрии предполагается существование более чем одной такой параллельной линии. Это альтернативное множество аксиом приводит нас к вполне согласованной форме геометрии, хотя и другой: в ней традиционные геометрические равенства не имеют места, например, сумма внутренних углов треугольника уже не обязательно равна 180°, и т. д.
Существует два канонических способа отображения гиперболической плоскости на внутренность круга евклидовой плоскости. В обоих случаях одна окрестность гиперболической плоскости находится в фокусе в центре круга, в то время как остальная часть гиперболической плоскости постепенно исчезает в перспективе по мере приближения к границе круга. Первая каноническая модель это конформная модель Пуанкаре (Poincaré model), которая сохраняет углы, но превращает линии гиперболического пространства в дуги единичного круга. Вторая каноническая модель это проективное отображение или модель Клейна (Klein model), которая отображает линии гиперболического пространства в прямые линии на плоскости, но зато искажает углы.
Гиперболические варианты существу, некоторые из классических алгоритмов размещения можно переформулировать в гиперболической постановке, получая иногда совершенно другие результаты виды, которые могут быть реализованы как в 2D, так и в 3D, представляют собой искаженный вид деревьев. Этот способ изображения похож на эффект от использования линз рыбьего глаза при традиционном размещении деревьев. Такое искаженное изображение позволяет осуществлять визуализацию потенциально больших деревьев, делая их пригодными для приложений из реальной жизни.
Литература
- Касьянов В.Н., Касьянова Е.В. Визуализация информации на основе графовых моделей. – Новосибирск: НГУ, 2014. – 149 с.
