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;
ОтображениеПлитки.Текст = Плитка.Вес;
ОтображениеПлитки.Расшифровка = Плитка.ИД;
КонецПроцедуры
#КонецОбласти
Проба пера — карта-схема публикаций Инфостарта по категориям: 
Конечно, это только прототип. На данный момент вижу такие проблемы, которые планирую решить и осветить в следующей статье:
- Автоматическое раскрашивание областей.
- Выделение областей-родителей.
- Что-то сделать с заголовками, которые не помещаются в область.
Специальные предложения
См. также
Динамический список. Апгрейд справочника "Номенклатура" типовой конфигурации с помощью расширения
26.01.2020 3044 aximo 10
Подборка программ для взаимодействия с ЕГАИС Промо
ЕГАИС (Единая государственная автоматизированная информационная система) - автоматизированная система, предназначенная для государственного контроля за объёмом производства и оборота этилового спирта, алкогольной и спиртосодержащей продукции. Инфостарт рекомендует подборку проверенных решений для взаимодействия с системой.
Управление ИТ-проектами. Модуль 2: продвинутый онлайн-курс по классическим методам управления проектами. Вебинары проходят с 12 марта по 11 июня 2020 года. Промо
Продвинутый онлайн-курс по классическому управлению ИТ-проектами позволит слушателям освоить инструменты из PMBoK® и 1С:Технологии корпоративного внедрения и научиться их применять для проектов любого масштаба. Курс включает в себя 12 вебинаров и 12 видеолекции, разбор кейсов и рекомендации экспертов по проектам слушателей. Ведущая курса - Мария Темчина.
от 13000 рублей
1C:Предприятие для программистов: Расчетные задачи (зарплата). Онлайн-интенсив с 01 по 17 июня 2020 г. Промо
Данный онлайн-курс предусматривает изучение механизмов платформы “1С:Предприятие”, которые предназначены для автоматизации периодических расчетов, а именно - для расчета зарплаты. Курс предназначен для тех, кто уже имеет определенные навыки конфигурирования и программирования в системе “1С:Предприятие”, а также для опытных пользователей прикладного решения “1С:Зарплата и управление персоналом” и прочих прикладных решений, в которых реализован функционал расчета зарплаты.
4900 рублей
1C:Предприятие для программистов: Запросы и отчеты. Второй поток. Онлайн-интенсив с 17 марта по 16 апреля 2020 г. Промо
Данный онлайн-курс предусматривает углубленное изучение языка запросов и возможностей системы компоновки данных, которые понадобятся при разработке отчетов, работающих на платформе “1С:Предприятие” в рамках различных прикладных решений. Курс предназначен для тех, кто уже имеет определенные навыки конфигурирования и программирования в системе “1С:Предприятие”, а также для опытных пользователей различных прикладных решений, которые используют в своей работе отчеты разного назначения.
6500 рублей
Готовые переносы данных из различных конфигураций 1C Промо
Рекомендуем готовые решения для переноса данных из различных конфигураций 1C. C техподдержкой от разработчиков и гарантией от Инфостарт.
Программы для исполнения 54-ФЗ Промо
С 01.02.2017 контрольно-кассовая техника должна отправлять электронные версии чеков оператору фискальных данных - правила установлены в 54-ФЗ ст.2 п.2. Инфостарт предлагает подборку программ, связанных с применением 54-ФЗ, ККТ и электронных чеков.
Новый раздел на Инфостарте - Electronic Software Distribution Промо
Инфостарт напоминает: на нашем сайте можно купить не только ПО, связанное с 1С. В нашем арсенале – ESD-лицензии на ПО от ведущих вендоров: Microsoft, Kaspersky, ESET, Dr.Web, Аскон и другие.
- Низкие цены, без скрытых платежей и наценок
- Оперативная отгрузка
- Возможность оплаты с личного счета (кешбек, обмен стартмани на рубли и т.п.)
- Покупки идут в накопления для получения скидочных карт лояльности Silver (5%) и Gold (10%)
Подходы, методы и инструменты UX/UI для разработки эффективных интерфейсов на 1С
07.08.2019 7056 IvanAT1981 14
Подборка решений для взаимодействия со ФГИС «Меркурий» Промо
С 1 июля 2019 года все компании, участвующие в обороте товаров животного происхождения, должны перейти на электронную ветеринарную сертификацию (ЭВС) через ФГИС «Меркурий». Инфостарт предлагает подборку программ, связанных с этим изменением.
БСП: Дополнительные отчеты и обработки - одна обработка, несколько форм
29.07.2019 6518 dsdred 9
Программы для исполнения 488-ФЗ: Маркировка товаров Промо
1 января 2019 года вступил в силу ФЗ от 25.12.2018 № 488-ФЗ о единой информационной системе маркировки товаров с использованием контрольных (идентификационных) знаков, который позволяет проследить движение товара от производителя до конечного потребителя. Инфостарт предлагает подборку программ, связанных с применением 488-ФЗ и маркировкой товаров.
CorelDRAW Graphics Suite 2019 Промо
CorelDRAW – пакет профессиональных инструментов для редактирования фотографий, разработки дизайна, создания макетов страниц и векторных иллюстраций
INFOSTART MEETUP Kazan. 13 марта 2020 г. Промо
Инфостарт продолжает путешествие по России. Следующая остановка - Казань. Тема мероприятия - управление и технологии автоматизации учета на платформе "1С: Предприятие". Ждем всех: докладчиков и участников! Стоимость участия - 5 500 рублей. Цена действительна до 30.01.2020
5 500
Базовый курс по обмену данными в системе 1С:Предприятие. Онлайн-интенсив с 12 по 28 мая 2020 г. Промо
Данный онлайн-курс предусматривает изучение механизмов платформы “1С:Предприятие”, обеспечивающих обмен данными между различными прикладными 1С-решениями и взаимодействие с другими информационными системами. Курс предназначен для тех, кто уже имеет определенные навыки конфигурирования и программирования в системе “1С:Предприятие”.
5500 рублей
