Дополнение 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.
У нас начальная область, у которой ширина в 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 от 02.03.2020: Пример обработки выложен в отдельной статье: Treemapping. Демонстрационная обработка
