Галерея деревьев

Введение

Деревья как структуры данных используются для сортировок, поиска, организации очередей, во многих классических алгоритмах, но их можно строить и просто так, для красоты.

У этого дерева сначала меняется коэффициент ветвления, а затем отношение длины потомка к длине предка

При организации объектов в древовидную структуру как правило поддерживается сходство всего дерева и его части. Иначе говоря, ветка похожа на ствол, у неё могут быть свои ветки со своей иерархией.

Именно за счёт того, что простые элементы в рекурсивной манере собираются в один объект, его визуальная сложность (неформ.) может быть большой.

Это тоже дерево, просто с большим количеством самоналожений

Ниже в статье приведён подробный разбор кода для построения и визуализации таких деревьев, технические детали реализации и ссылка на демо, которое можно запустить прямо в браузере.

Формализация задачи

Определим дерево как объект, который строится по правилам, изложенным далее, начиная с единственного отрезка - ствола. У каждой ветки (включая ствол), кроме терминальных (оконечных, самых "тонких" веток) одинаковое число потомков. Длина потомка равна длине родителя, умноженной на некоторую константу, потомки равномерно распределены в некотором диапазоне углов. Еще одной константой определяется максимальная глубина рекурсии, то есть количество уровней потомков (дети, внуки, ...) у ствола.

Менее красочная, но при этом менее загромождённая и более понятная картинка, приведённая ниже, содержит все перечисленные компоненты: ветвление, уменьшение длины потомков, окончание рекурсии на некоторой глубине, равномерное распределение потомков внутри диапазона углов.

Для более живой и привлекательной отрисовки введём прибавление небольшой центрированной случайной величины к углу, под которым рисуется каждая ветка. Дрожание на видео в начале статьи вызвано именно этим. И на картинке выше можно увидеть, что ствол немного наклонён относительно вертикали.

Структура кода

Генерация и рисование деревьев построены на классе Branch, который представляет из себя совокупность перечисленных выше параметров ветки и списка веток-потомков.

За классом следует объявление ползунков (трекбаров?.. на базовой кафедре с трепетом относились к импортозамещению в терминологии) для регулировки параметров, с которыми будет генерироваться дерево:

cv2.createTrackbar('length', 'trackbars', 170, 300, nothing)

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

За созданием трекбаров следует вечный цикл (который, впрочем, прерывается нажатием кнопки q), в котором происходит создание дерева и его отрисовка.

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

tree = Branch (length_ = cv2.getTrackbarPos('length', 'trackbars'), ...

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

tree.draw (canvas, 500, 550, 2, tick)

Для создания эффекта затухания с уходом вправо (который можно интерпретировать как тень, третье измерение и возможно ещё что-то) изображение домножается на 0.95 и сдвигается вправо на 4 пикселя - значения, подобранные на глаз.

shadow = canvas.astype ("float") * 0.95

new_canvas = canvas_.copy ()

new_canvas [:, shift :, :] = shadow [:, : -shift, :]

canvas = new_canvas

Наконец, происходит вывод изображения на экран и запись очередного кадра в видео (которая была удалена из кода, потому что она использует рукописную библиотеку, которую нельзя просто так взять и поставить. Но если хочется записать видео, можно найти туториал по cv2.VideoWriter). Именно с помощью этой функции были сгенерированы все примеры для этой статьи - можно просто смотреть, какие деревья получаются при разных параметрах, а потом выбирать лучшие моменты из записанной полностью истории. За счёт сжатия и того, что кадры по сравнению с естественными изображениями слабо детализированы, видео получаются небольшого объёма.

cv2.imshow ("render", canvas)

out.write (canvas)

Дерево с коэффициентом ветвления, равным единице

class Branch

Визуализация

Функция draw(img, x, y, depth, tick) принимает на вход изображение, в которое будет происходить рисование, абсолютные координаты корня текущего поддерева, глубину, на которой рисуется лист в виде окружности, и номер прохода главного цикла, который служит дискретным аналогом времени.

Найдём координаты конца текущей ветки:

x1 = int (x + self.length * math.cos (self.angle))

y1 = int (y + self.length * math.sin (self.angle))

Нарисуем линию толщиной в одну шестьдесят пятую от длины, но не меньше одного пикселя:

cv2.line (img, (x, y), (x1, y1), self.color, max (1, int(self.length / 65)))

Если глубина достигла нуля, нарисуем лист:

if (depth == 0):

cv2.circle (img, (int (x1), int (y1)), 3, ((10 + tick * 7) % 255 + 10, 40, 10), -1)

Рекурсивно вызовем отрисовку для всех детей:

for child in self.children:

child.draw (img, x1, y1, depth - 1, tick)

Создание объекта

Конструктор принимает все параметры, о которых шла речь выше, и ещё некоторые, а именно угол (дерево может вращать целиком) и цвет.

def __init__(self, length_, angle_, color_, angle_range_,

length_decrement_factor_, max_depth_, branching_factor_):

self.length = length_

self.angle = angle_ + float (np.random.randint (300) - 150) / 10000

self.color = color_

Если ветка является терминальной, то есть не имеет потомков, для разнообразия нарисуем её другим цветом.

if (max_depth_ < 1):

self.color = (color_[0] + 10, color_[0] + 30, color_[0] + 20)

self.children = []

Разберём отдельно случай с единственным потомком на ветку, чтобы ненароком не поделить на ноль.

if (max_depth_ > 0):

if (branching_factor_ > 1):

angle_step = angle_range_ / (branching_factor_ - 1)

else:

angle_step = angle_range_ / 2

Добавим в список детей текущей ветки количество веток, равное branching_factor с параметрами, зависящими от её праметров.

for i in range (branching_factor_):

Длина потомка равна длине предка, умноженной на числовой коэффициент.

self.add_child (length_ = int (self.length * length_decrement_factor_),

Угол потомка равен углу предка, к которому прибавлен угловой шаг, умноженный на номер потомка.

angle_ = - angle_range_ / 2 +

self.angle + i * angle_step,

Цвет, диапазон углов, коэффициент, с которым изменяется длина, и количество потомков остаются неизменными.

color_ = self.color,

angle_range_ = angle_range_,

length_decrement_factor_ = length_decrement_factor_,

Ограничение на глубину уменьшается на 1 для выхода из рекурсии.

max_depth_ = max_depth_ - 1,

branching_factor_ = branching_factor_)

Если потомок становится больше предка, древесная структура может перестать прослеживаться за счёт выхода далеко за пределы экрана.

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

Итоги, конкурс деревьев

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

Полный код проекта лежит в этом репозитории. Быстро работающая версия rendering_local.ipynb требует для работы интерпретатор питона и установленную библиотеку OpenCV.

Семинар с очень, очень подробным рассказом про то, как это работает, выложен здесь.

Если получилось построить красивое дерево, можно его заскринить или сохранить видос и отправить в чат. Потом устроим голосование и выложим самые-самые в наш инстаграм :)