Кривые Гильберта с визуализацией Python

В этой статье я немного расскажу вам об особом типе фракталов, известном как кривая Гильберта.

Дэвид Гилберт

Давид Гильберт был немецким математиком, сыгравшим большую роль в формировании современной математики в конце 1800-х и начале 1900-х годов. Гильберт внес значительный вклад в широкий спектр математических областей, включая теорию чисел, геометрию и основы математики. Некоторые из его самых известных работ включают его аксиоматизацию геометрии и его разработку основной теоремы Гильберта. Он также работал над доказательством Великой теоремы Ферма и был одной из ведущих фигур в развитии математической логики 20-го века. После его смерти в 1943 году его работы продолжают изучаться и применяться в различных областях математики и информатики.

Кривые Гильберта

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

Представление кривых Гильберта в виде системы Линденмайера

Системы Линденмайера, также известные как L-системы, представляют собой тип формальной грамматики, используемой для моделирования роста растений, органических структур и других геометрий. Они были разработаны венгерским биологом и математиком Аристидом Линденмайером в конце 1960-х годов.

L-системы — это, по сути, набор правил, описывающих, как строка символов развивается с течением времени. Эти правила можно использовать для создания широкого спектра фрактальных паттернов, включая ветвящиеся деревья. Рассмотрим строку «AB» с правилом замены A ➞ B,B ➞ AA,имаксимальный уровень рекурсии 2. Наша строка «AB» эволюционирует в «BAA. >» на первом уровне рекурсии и «AABB» на втором уровне рекурсии. Постепенно струна усложняется, и из итераций локальных структур рождается надстройка.

Кривые Гильберта могут быть выражены в виде L-системы со следующими условиями.

Alphabet : A, B

Constants : F, +, −
  F: Draw in the forward direction
  +: Turn left 90 degrees
  -: Turn right 90 degrees

Axiom : A
Production rules:
A → +BF−AFA−FB+
B → −AF+BFB+FA−

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

Визуализация кривых Гильберта

Теперь, когда мы понимаем, что такое кривые Гильберта в математическом контексте, давайте повеселимся и напишем код для визуализации этих непрерывных фракталов. Я собираюсь использовать Python с пакетом Hilbert Curve для начала.

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

def draw2DHilbert(ax, bitsNumber):
    #Setting the dimension we are drawing/plotting in
    dimension = 2
    #Setting the maximum Hilbert Integer
    maxHilbertInteger = 2**(bitsNumber*dimension)

    #Create list of Hilbert Integers and locations
    hilbertIntegers = np.arange(maxHilbertInteger)
    locations = decode(hilbertIntegers, dimension, bitsNumber)

    #Matplotlib drawing locations and setting labels
    ax.plot(locations[:,0], locations[:,1], '.-')
    ax.set_title('%d Bits / Dimension' % (bitsNumber))
    ax.set_xlabel('Dim 1')
    ax.set_ylabel('Dim 2')
    ax.set_aspect('equal')

#Create figure with certain size
fig = plt.figure(figsize=(6.5,6.5))

#Iterate over bits and plot onto separate subplots
for iterator, bitsNumber in enumerate([1, 2, 3, 4]):
    ax = fig.add_subplot(2,2,iterator+1)

    #Call our function to draw the Hilbert Curve
    draw2DHilbert(ax, bitsNumber)

#Set the figure layout
fig.tight_layout()

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

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

def draw3DHilbert(ax, bitsNumber):
    #Setting the dimension we are drawing/plotting in
    dimension = 3
    #Setting the maximum Hilbert Integer
    maxHilbertInteger = 2**(bitsNumber*dimension)

    #Create list of Hilbert Integers and locations
    hilbertIntegers = np.arange(maxHilbertInteger)
    locations = decode(hilbertIntegers, dimension, bitsNumber)

    #Matplotlib setting colormap, drawing locations, and setting labels
    cmap = plt.cm.get_cmap('cool')
    for step in range(maxHilbertInteger-1):
        ax.plot(
            [locations[step,0], locations[step+1,0]],
            [locations[step,1], locations[step+1,1]], 
            [locations[step,2], locations[step+1,2]], 
            '.-',color=cmap(step/maxHilbertInteger)
        )
    ax.set_title('%d Bits / Dimension' % (bitsNumber))
    ax.set_xlabel('Dim 1')
    ax.set_ylabel('Dim 2')
    ax.set_zlabel('Dim 3')
    ax.set_aspect('equal')

#Create figure with certain size
fig = plt.figure(figsize=(8,8))

#Iterate over bits and plot onto separate subplots
for iterator, bitsNumber in enumerate([1, 2, 3, 4]):
    ax = fig.add_subplot(2,2,iterator+1,projection='3d')

    #Call our function to draw the Hilbert Curve
    draw3DHilbert(ax, bitsNumber)

#Set the figure layout
fig.tight_layout()

И теперь у нас есть красивый пример кривой Гильберта в трех измерениях!

Весь код этой статьи можно найти на моем Github.

Если вы нашли эту статью на Medium интересной, подпишитесь на меня! Я пишу о математике, информатике и обо всем, что между ними!