Treemapping — способ визуализации данных древовидной структуры. Карта-схема дерева

02.03.20

Разработка - Математика и алгоритмы

Предлагается ознакомиться с редким способом графического представления иерархических данных. Приводится алгоритм формирования и пример реализации.

Дополнение 1 от 02.03.2020: Пример обработки выложен в отдельной статье: Treemapping. Демонстрационная обработка

В моей практике приходилось пользоваться одной бесплатной и свободной программой, которая называется WinDirStat. Назначение ее — анализ использованного пространства дисковой памяти. Сам анализ выглядит таким вот образом:

 

Очень выручала в случаях, когда SSD небольшой, свободное место заканчивается и нужно определить, как максимально быстро и с минимальными потерями решить проблему. Позже я узнал, что данный способ представления называется Treemap (не надо путать с классом TreeMap из Java), а процесс формирования — Treemapping.

Данный способ мало известен в русскоязычном интернете, даже перевода термина пока нет. Предложу свой вариант — «Карта-схема дерева».

 
В англоязычном ситуация гораздо лучше. Примеры из Википедии:

Treemapping реализован во многих библиотеках визуализации данных (например — Google Charts). Но, к сожалению, не в 1С. Возникло желание восполнить этот пробел и разобраться с алгоритмом формирования.

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

Области, чаще всего, прямоугольные, но не обязательно. Например, существуют алгоритмы составления карты-схемы дерева в виде диаграммы Вороного. Необходимое требование — формы областей должны быть простыми и похожими друг на друга. По возможности, различаться только размерами. Тогда будет наглядно восприниматься примерное соотношение размеров, соответствующее значению показателя.

Примеры подходящих данных:

  • папки и файлы на диске, показатель — размер;
  • иерархический справочник товаров, показатель — выручка от продаж, складские остатки, себестоимость продаж;
  • иерархический справочник контрагентов, показатели — выручка от продаж, авансы, задолженность;
  • ABC-XYZ анализ по товарам или контрагентам, в качестве групп уже могут выступать не группы иерархии, а классы ABC/XYZ.

Так же данные могут содержать еще один дополнительный показатель, уже необязательно аддитивный — его значение преобразуется в цвет области.

 
Как вариант, аддитивный показатель — выручка по номенклатуре и группам, дополнительный — процент прибыльности продаж:

Алгоритмов формирования таких карт-схем довольно много, самые простые, естественно, для прямоугольных областей. Самый простой из прямоугольных называется Slice-and-dice (можно перевести «В нарезку», если я не ошибаюсь).

 
Просто нарезаем каждую область вдоль наибольшей стороны (высоты или ширины), в пропорции значения показателя.

Как видим, результат удачным получается не всегда, т.к. области могут быть не слишком похожими друг на друга и различным образом ориентированными, не всегда на глаз виден порядок различия. Но есть и плюс — сохраняется заданный порядок узлов дерева.

Другой способ и алгоритм — Squarified treemap («Квадратная карта-схема»). Как понятно из названия, суть способа в том, чтобы сделать все области «как можно более квадратными», т.е. чтобы соотношение высоты к ширине было как можно ближе к единице или, другими словами, отношение большей стороны к меньшей минимально. Результат гораздо более нагляден, но требуется чтобы узлы дерева на каждом уровне были отсортированы по значению показателя, т.е. исходный порядок может нарушиться. Если порядок не важен — то способ довольно неплох. Его и рассмотрим более подробно.

Смысл алгоритма легче понять по аналогии. Пусть у нас есть прямоугольная область и нам нужно ее замостить прямоугольными плитками. Введем критерий качества плитки — отношение ее большей стороны к меньшей, чем это отношение меньше, тем плитка лучше. Качество замощения будем оценивать по наихудшей плитке. Один вариант замощения будем считать лучше другого, если самая плохая плитка в нем лучше самой плохой в другом.

Разработаем алгоритм для узлов на первом уровне дерева и всей области диаграммы. Потом рекурсивно применим этот же алгоритм для непосредственных потомков каждого первоуровневого узла и областей выделенных для них. Потом — для их потомков, и так далее, до конечных узлов.

  1. На каждом шаге итерации замощения у нас есть еще не замощенная прямоугольная область и ряд значений, в соответствие которому нужно подобрать плитки. Берем первое значение, рассчитываем область к текущему замощению и соотношение сторон плитки. Если ряда значений нет, замощение закончено.
  2. Добавляем следующее значение, рассчитываем новый вариант размещения. Если добавлять нечего, то замощение закончено.
  3. Если новый вариант хуже, то его отбрасываем, предыдущий оставляем как окончательный и переходим к шагу 1, иначе отбрасываем предыдущий вариант и переходим к шагу 2.
 
Посмотрим, как это происходит на примере.

У нас начальная область, у которой ширина в 1.5 раза больше высоты. Размещаемые пункты дерева имеют веса: 6, 6, 4, 3, 2, 2, 1. Сумма весов равна 24.

Шаг 1. Размещаем первую плитку вдоль наименьшей стороны (для минимизации отношения сторон). Высоту плитки считаем 1, ширина равна 1.5*(6/24). Соотношение сторон получается 8/3.

Шаг 2. Добавляем второй элемент, новое соотношение равно 3/2, оно меньше предыдущего, значит — этот вариант лучше.

Шаг 3. Добавляем третий элемент, соотношение больше предыдущего, вариант отбрасываем, вариант с предыдущего шага считаем окончательным.

Шаг 4. Добавляем одну плитку с весом 4, соотношение сторон равно 9/4

Шаг 5. Добавляем второй элемент, новое соотношение равно 49/27, оно меньше предыдущего, значит — этот вариант лучше.

Шаг 6. Добавляем следующий элемент, соотношение больше предыдущего, вариант отбрасываем, вариант с предыдущего шага считаем окончательным.

Шаг 7. Добавляем одну плитку с весом 2, соотношение сторон равно 25/18

Шаг 8. Добавляем второй элемент, новое соотношение равно 144/50, оно больше предыдущего, вариант отбрасываем, вариант с предыдущего шага считаем окончательным.

Шаг 9. Добавляем одну плитку с весом 2, соотношение сторон равно 25/18

Шаг 10. Остается единственное возможное место для последней плитки

 
Вот такой программный код у меня получился:
 #Область ЗамоститьОбласть

Процедура ЗамоститьОбласть(ОбщаяОбластьЗамощения, РазмещаемыеУзлы, ОбщийВес)
	
	РазмещаемыеУзлыНачало = 0;
	
	ВесКРазмещению = ОбщийВес;
	НезамощеннаяОбласть = ОбщаяОбластьЗамощения;
	РазмещаемыйВес = РазмещаемыеУзлы[РазмещаемыеУзлыНачало].Вес;
	
	РасчетРазмещения = РассчитатьРазмещение(НезамощеннаяОбласть, РазмещаемыеУзлы, РазмещаемыеУзлыНачало, РазмещаемыеУзлыНачало, РазмещаемыйВес, ВесКРазмещению);
			
	РазмещаемыеУзлыКонец = 1;
	
	Пока РазмещаемыеУзлыКонец < РазмещаемыеУзлы.Количество() Цикл
		
		РасчетРазмещенияПредыдущий = РасчетРазмещения;
		РазмещаемыйВесПредыдущий = РазмещаемыйВес;
		
		РазмещаемыйВес = РазмещаемыйВес + РазмещаемыеУзлы[РазмещаемыеУзлыКонец].Вес;
		РасчетРазмещения = РассчитатьРазмещение(НезамощеннаяОбласть, РазмещаемыеУзлы, РазмещаемыеУзлыНачало, РазмещаемыеУзлыКонец, РазмещаемыйВес, ВесКРазмещению);
		
		Если РасчетРазмещения.СоотношениеСторон > РасчетРазмещенияПредыдущий.СоотношениеСторон Тогда
			
			ОтобразитьЗамощение(РасчетРазмещенияПредыдущий);
			
			РазмещаемыеУзлыНачало = РазмещаемыеУзлыКонец;
			
			ВесКРазмещению = ВесКРазмещению - РазмещаемыйВесПредыдущий;
			НезамощеннаяОбласть = ИсключитьОбласть(НезамощеннаяОбласть, РасчетРазмещенияПредыдущий.ЗамощаемаяЧасть);
			РазмещаемыйВес = РазмещаемыеУзлы[РазмещаемыеУзлыНачало].Вес;
			
			РасчетРазмещения = РассчитатьРазмещение(НезамощеннаяОбласть, РазмещаемыеУзлы, РазмещаемыеУзлыНачало, РазмещаемыеУзлыНачало, РазмещаемыйВес, ВесКРазмещению);
		КонецЕсли;
		
		РазмещаемыеУзлыКонец = РазмещаемыеУзлыКонец + 1;
		
	КонецЦикла;
	
	Если РазмещаемыеУзлыНачало < РазмещаемыеУзлы.Количество() Тогда
		ОтобразитьЗамощение(РасчетРазмещения);
	КонецЕсли;
	
КонецПроцедуры

#Область РассчитатьРазмещение

Функция РассчитатьРазмещение(ОбластьЗамощения, РазмещаемыеУзлы, РазмещаемыеПунктыНачало, РазмещаемыеПунктыКонец, Знач РазмещаемыйВес, ОбщийВес)
	
	РезультатРасчета = Новый Структура;
	
	ЗамощаемаяЧасть = РассчитатьОбластьЗамощения(ОбластьЗамощения, РазмещаемыйВес / ОбщийВес);
	
	СоотношениеСторон = 0;
	
	ОставшаясяЗамощаемаяЧасть = ЗамощаемаяЧасть;
	
	Плитки = Новый Массив;
	
	Для НомерПункта = РазмещаемыеПунктыНачало По РазмещаемыеПунктыКонец - 1 Цикл
		
		ПунктДерева = РазмещаемыеУзлы[НомерПункта];
	
		Плитка = РассчитатьОбластьЗамощения(ОставшаясяЗамощаемаяЧасть, ПунктДерева.Вес / РазмещаемыйВес);
		ОставшаясяЗамощаемаяЧасть = ИсключитьОбласть(ОставшаясяЗамощаемаяЧасть, Плитка);
		РазмещаемыйВес = РазмещаемыйВес - ПунктДерева.Вес;
		
		ДобавитьПлитку(Плитка, Плитки, СоотношениеСторон, ПунктДерева);
		
	КонецЦикла;
	
	ДобавитьПлитку(ОставшаясяЗамощаемаяЧасть, Плитки, СоотношениеСторон, РазмещаемыеУзлы[РазмещаемыеПунктыКонец]);
	
	РезультатРасчета.Вставить("СоотношениеСторон", СоотношениеСторон); 
	РезультатРасчета.Вставить("ЗамощаемаяЧасть", ЗамощаемаяЧасть); 
	РезультатРасчета.Вставить("Плитки", Плитки); 
	
	Возврат РезультатРасчета;
КонецФункции

Процедура ДобавитьПлитку(Плитка, Плитки, СоотношениеСторон, ПунктДерева)
	
	СоотношениеСторонПлитки = СоотношениеСторонПлитки(Плитка);
	
	Если СоотношениеСторонПлитки > СоотношениеСторон Тогда
		СоотношениеСторон = СоотношениеСторонПлитки;
	КонецЕсли;
		
	Плитка.Вставить("Вес", ПунктДерева.Вес);
	Плитка.Вставить("ИД", ПунктДерева.ПолучитьИдентификатор());
	Плитка.Вставить("ДочерниеСтроки", ПунктДерева.ПолучитьЭлементы());
		
	Плитки.Добавить(Плитка);

КонецПроцедуры

Функция РассчитатьОбластьЗамощения(ОбластьЗамощения, ДоляОбласти)
	
	Если ОбластьЗамощения.Ширина >= ОбластьЗамощения.Высота Тогда
		ЗамощаемаяЧасть = ПрямоугольнаяОбласть(ОбластьЗамощения.Лево, ОбластьЗамощения.Верх, Окр(ОбластьЗамощения.Ширина * ДоляОбласти,3), 
		ОбластьЗамощения.Высота);
	Иначе
		ЗамощаемаяЧасть = ПрямоугольнаяОбласть(ОбластьЗамощения.Лево, ОбластьЗамощения.Верх, ОбластьЗамощения.Ширина, 
		Окр(ОбластьЗамощения.Высота * ДоляОбласти,3));
	КонецЕсли;
	
	Возврат ЗамощаемаяЧасть;
	
КонецФункции

#КонецОбласти

#КонецОбласти


#Область ВспомогательныеПроцедурыФункции

Функция ПрямоугольнаяОбласть(Лево, Верх, Ширина, Высота)
	
	Возврат Новый Структура("Лево, Верх, Ширина, Высота", Лево, Верх, Ширина, Высота);

КонецФункции

Функция СоотношениеСторонПлитки(Плитка)
	
	Если Плитка.Ширина >= Плитка.Высота Тогда
		Возврат Плитка.Ширина / Плитка.Высота;
	Иначе
		Возврат Плитка.Высота / Плитка.Ширина;
	КонецЕсли;

КонецФункции

Функция ИсключитьОбласть(НачальнаяОбласть, ИсключаемаяОбласть)
	
	Если НачальнаяОбласть.Ширина = ИсключаемаяОбласть.Ширина Тогда
		Возврат ПрямоугольнаяОбласть(НачальнаяОбласть.Лево, 
		НачальнаяОбласть.Верх + ИсключаемаяОбласть.Высота, 
		НачальнаяОбласть.Ширина, 
		НачальнаяОбласть.Высота - ИсключаемаяОбласть.Высота);
	Иначе	
		Возврат ПрямоугольнаяОбласть(НачальнаяОбласть.Лево + ИсключаемаяОбласть.Ширина, 
		НачальнаяОбласть.Верх, 
		НачальнаяОбласть.Ширина - ИсключаемаяОбласть.Ширина, 
		НачальнаяОбласть.Высота);
	КонецЕсли;
КонецФункции

Функция ОтобразитьЗамощение(Расчет)
			
	ЗамощаемаяОбласть = Расчет.ЗамощаемаяЧасть;
	
	Для каждого Плитка Из Расчет.Плитки Цикл
		
		Если Плитка.ДочерниеСтроки.Количество() = 0 Тогда
			
			РисоватьПлитку(Плитка);
			
		Иначе
			
			ЗамоститьОбласть(Плитка, Плитка.ДочерниеСтроки, Плитка.Вес);
			
		КонецЕсли;
		
	КонецЦикла;
КонецФункции

Процедура РисоватьПлитку(Плитка)
			
	ОтображениеПлитки = КартаСхемаДерева.Рисунки.Добавить(ТипРисункаТабличногоДокумента.Текст);
	ОтображениеПлитки.Ширина = Плитка.Ширина-0.8;
	ОтображениеПлитки.Высота = Плитка.Высота-0.8;
	ОтображениеПлитки.Лево = Плитка.Лево+0.4;
	ОтображениеПлитки.Верх = Плитка.Верх+0.4;
	ОтображениеПлитки.Текст = Плитка.Вес;
	ОтображениеПлитки.Расшифровка = Плитка.ИД;

КонецПроцедуры

#КонецОбласти

Проба пера — карта-схема публикаций Инфостарта по категориям:

Конечно, это только прототип. На данный момент вижу такие проблемы, которые планирую решить и осветить в следующей статье:

  1. Автоматическое раскрашивание областей.
  2. Выделение областей-родителей.
  3. Что-то сделать с заголовками, которые не помещаются в область.

Дополнение 1 от 02.03.2020: Пример обработки выложен в отдельной статье: Treemapping. Демонстрационная обработка

визуализация диаграмма древовидные иерархические анализ выручка прибыльность

См. также

Богатый редактор картинок, хранимых в базе, с возможностью РИСОВАНИЯ. Редактор внешних файлов картинок. Объект, расширяющий возможности работы с картинками из встроенного языка (Три в одном) + Обработка «Стандартизация картинок»

Работа с интерфейсом Рабочее место Платформа 1С v8.3 Управляемые формы Конфигурации 1cv8 Платные (руб)

Обработка предназначена для редактирования картинок в режиме «Предприятие», с возможностью РИСОВАТЬ на них. Поддерживается работа как в обычных формах (толстый клиент) так и на управляемых формах (тонкий клиент). Обработка позволяет редактировать как картинки, хранимые в базе, так и графические файлы с диска на файловой системе. Помимо базовых функций (изменение размеров, преобразование формата, обрезание картинки, повороты и т.п.) – редактор имеет богатый набор инструментов для рисования. Доступна функция вставки изображения из буфера обмена. Также обработка может быть использована из встроенного языка как объект для редактирования картинок. Объект может быть использован: на стороне клиента, на стороне сервера, из внешнего соединения. Данная обработка будет особенно полезна тем, кто вносит картинки в базу (изображения номенклатуры, фотографии физических лиц и т.п.). Функционал реализуется с использованием JavaScript и бесплатного ПО ImageMagick (без использования внешних компонент).

6000 руб.

16.01.2015    61699    43    59    

80

[Расширения] Динамическое управление видимостью и доступностью элементов форм (УФ) (8.3.6+)

Работа с интерфейсом Платформа 1С v8.3 Управляемые формы Конфигурации 1cv8 Платные (руб)

Механизм «Динамическое управление доступом к элементам форм объектов 1С8» предназначен для обеспечения возможности оперативного управления видимостью и доступностью элементов форм документов и справочников продуктов фирмы «1С» «1С:Предприятие 8». Решение универсальное, встраивается в любую конфигурацию с минимальными доработками, что позволяет без проблем обновлять типовые решения.

5000 руб.

14.01.2016    54316    16    21    

42

Управление дашбордами

Работа с интерфейсом Платформа 1С v8.3 Конфигурации 1cv8 Платные (руб)

Обработка предназначена для создания и управления дашбордами.

2400 руб.

29.06.2020    16623    21    4    

35

Модель состояния для MVC

Работа с интерфейсом Платформа 1С v8.3 Конфигурации 1cv8 Абонемент ($m)

"MVC плохо применима в 1С" - познакомьтесь с моделью состояния и, возможно, ваше мнение поменяется! Представленное решение является эволюционным развитием идеи реализации MVC для 1С. В новой версии добавлены DSL для описания модели состояния, а также параметризация свойств параметров и элементов формы.

1 стартмани

05.07.2022    3577    kalyaka    2    

27

Табло очереди заказов на экран телевизора

WEB-интеграция Работа с интерфейсом Платформа 1С v8.3 1С:Розница 2 Платные (руб)

Связка из веб-приложения и расширения для 1С: Розница 2.3.

3600 руб.

29.04.2022    12010    1    5    

10

Условное оформление элементов форм в пользовательском режиме 1С (управление видимостью и доступностью элементов форм)

Работа с интерфейсом Платформа 1С v8.3 Платные (руб)

Подсистема условного оформления элементов форм (далее подсистема) предназначена для настройки оформления элементов форм (видимость, доступность, цвет фона, цвет текста и прочее) в пользовательском режиме 1С. Также подсистему возможно использовать для ограничения доступа к реквизитам формы для определенных пользователей (или групп пользователей).

6000 руб.

18.01.2022    8773    1    2    

6

Программный интерфейс для доработки форм

Работа с интерфейсом Платформа 1С v8.3 Конфигурации 1cv8 Бесплатно (free)

Реализовал простой способ программного создания новых элементов, команд и реквизитов на форме.

25.11.2021    9407    AtamanovYS    19    

138
Комментарии
В избранное Подписаться на ответы Сортировка: Древо развёрнутое
Свернуть все
1. Steelvan 302 18.02.20 15:21 Сейчас в теме
Древосхема
Древосхематизация

или

Древокарта
Древокартография

---

Надо сокращать, "Карта-схема дерева" очень длинно и этим отринут пользоваться.
randomus; +1 Ответить
6. randomus 273 19.02.20 08:42 Сейчас в теме
(1) Неплохо. Но пока склонен придерживаться своего варианта )
2. Steelvan 302 18.02.20 18:52 Сейчас в теме
Древораскладка
Древораскладывание
3. Yashazz 4707 18.02.20 19:55 Сейчас в теме
У меня руки не дошли такое смастерить. Спасибо огромное, пригодится много где.
Но название и правда кривовато, это ведь даже не совсем дерево, скорее именно плитка.
Я бы назвал "мощёнка". Потому что мощно)
arqnet2011; randomus; Bassgood; +3 Ответить
8. randomus 273 19.02.20 08:55 Сейчас в теме
(3)Тоже неплохо ) Но все же - дерево. Хотя и не всегда. В узлах - мощёнка, в целом - дерево )

Мощено древо )))
4. CheBurator 3119 19.02.20 02:51 Сейчас в теме
5. DrAku1a 1678 19.02.20 05:04 Сейчас в теме
"Иерархическая диаграмма" - ИМХО, смотрится проще и нагляднее. В качестве анализа каталогов и файлов - реализована в программе "Scanner"
tormozit; EMelihoff; acanta; randomus; +4 Ответить
7. randomus 273 19.02.20 08:45 Сейчас в теме
(5) На вкус и цвет. На мой взгляд, Treemap нагляднее. И аккуратнее как-то )
Но спасибо за информацию.
DrAku1a; CyberCerber; +2 Ответить
15. check2 353 20.02.20 00:13 Сейчас в теме
(5) Шикарная программа, сам ею пользуюсь, только нужно учитывать, что механизмов для её реализации в 1С нет от слова совсем.
16. DrAku1a 1678 20.02.20 04:04 Сейчас в теме
(15)Реализовывал с использованием поля HTML и Raphael.js. Надеюсь в будущем увидеть подобное в составе базовых механизмов платформы 1С:Предприятие.
trinhvanthuong; tormozit; arakelyan; KUAvanesov; leonidkorolev; check2; acanta; +7 Ответить
17. check2 353 20.02.20 07:29 Сейчас в теме
(16) Красиво. Было бы неплохо статью об этом написать, но ведь Вы же понимаете, что для этого должна ещё стоять и java. А я имел ввиду, что само 1С:Предприятие из коробки таких средств не имеет.
20. DrAku1a 1678 26.10.20 04:57 Сейчас в теме
19. tormozit 7133 22.10.20 12:02 Сейчас в теме
(16) Классно. Тоже очень хочу такую диаграмму в штатном механизме платформы. Но и твою реализацию бы посмотрел.
9. terrorion 92 19.02.20 09:00 Сейчас в теме
Вещь. А можно какую-нибудь демку выложить?
10. randomus 273 19.02.20 09:21 Сейчас в теме
(9) Работаю над этим. В принципе, весь основной код опубликован в статье. Можно свободно копипастить, пробовать, модифицировать.
11. Sintson 411 19.02.20 09:22 Сейчас в теме
Ооочень круто!
Автор, ты молоток! Утащил в свои закрома.
12. CyberCerber 851 19.02.20 10:27 Сейчас в теме
Уже лет 15 пользуюсь программой Spacemonger: https://www.snapfiles.com/screenfiles/spacemonger.gif
Функционал аналогичен WinDirStat, очень удобно при оценке места и чистке диска.
Но никогда не думал, что эту визуализацию можно применить для построения отчетов, отличная идея!
randomus; +1 Ответить
13. Yashazz 4707 19.02.20 12:11 Сейчас в теме
Насчёт заголовков, которые не помещаются - шрифт можно уменьшать.
14. AlX0id 19.02.20 13:19 Сейчас в теме
В принципе, многие анализаторы диска подобную функциональность реализуют в той или иной форме.. Так что напрасно про редкую применяемость )
А так плюс, чо )
18. iCortezik 8 02.03.20 08:37 Сейчас в теме
Что-то сделать с заголовками, которые не помещаются в область.


Тут только наведением смотреть запись
Оставьте свое сообщение