L. Fregimus Vacerro (fregimus) wrote,
L. Fregimus Vacerro
fregimus

Category:

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

На рисунках — кривые Гильберта порядка с 4 по 7. Каждая кривая — как будто нитка, аккуратно уложенная в единичном квадрате, то есть квадрате со стороной, равной единице.

Как «устроены» эти кривые, и чем замечательны?

Сначала разберемся, как построить такую кривую. Возьмем квадрат со стороной ½, уберем одну из его сторон, и поместим его точно в середину единичного квадрата, вот так:

Получилась Гильбертова кривая порядка 1. Теперь уменьшим ее ровно вдвое, и сделаем с нее 4 копии. Две передвинем, а две другие тоже передвинем и еще повернем на четверть оборота в противоположные стороны. Соединим концы линий тремя одинаковыми отрезками, длиной равной стороне нового, уменьшенного квадрата. На рисунке каждая копия окрашена своим цветом, а соединительные отрезки черные.

У нас получилась кривая порядка 2. Теперь повторим нашу процедуру, но уже с получившейся ломаной линией: уменьшим вдвое, сделаем четыре копии, две из которых повернуты, и вновь соединим отрезками, которые тоже укоротим вдвое:

Повторять этот алгоритм можно до бесконечности. Вот следующие четыре шага, с кривыми порядка от 4 до 7 включительно:

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

Разумеется, повторить алгоритм бесконечное число раз нельзя; говоря о бесконечностях, следует оперировать пределами, ε-окрестностями и прочими понятиями матанализа.

Доказательство[3] существования предельной кривой основывается на таком рассуждении (приведу здесь только основную наглядную идею). Расположим кривую порядка 2 (красная линия, средней толщины) поверх кривой порядка 1 (синяя, самая толстая линия). Видно, что первая как бы «обвивает» последнюю. Еще более это отношение заметно между кривыми порядка 2 и 3 (тонкая зеленая линия).

Возьмем кусочек бесконечно растяжимой резинки и нанесем на нее шкалу от 0 до 1. Разные участки резинки могут быть растянуты по-разному. Натянем ее по форме кривой первого порядка так, что концы будут соответствовать 0 и 1, а середины каждой из трех сторон — 1/4, 2/4 и 3/4 соответственно. Теперь возьмем еще одну такую же резинку, и растянем ее вдоль кривой второго порядка. Концы кривой опять прикрепим в точках 0 и 1, а к серединам каждого из 15 отрезков, составляющих кривую, прикрепим точки начиная с 1/16 и заканчивая 15/16. Легко видеть, что расстояние между соответствующими одному и тому же числу точках на двух резинках не превышает диагонали квадрата со стороной, равной длине каждого из отрезков кривой второго порядка.

Поскольку с каждой итерацией сторона будет уменьшаться вдвое, то установленное нами «отклонение» одной резинки от другой с увеличением номера итерации будет стремиться к нулю вместе с длиной отрезков, из которых кривая составлена. Обратите внимание, что каждая из резинок — это функция: если число на резинке оказалось в какой-то точке квадрата, то функция как раз и отображает это значение на точку в квадрате.

По теореме Коши, поскольку разница между любыми двумя функциями стремится к нулю (транзитивность тут доказывается разложением в геометрический ряд, см. [3]), то и предельная функция существует и непрерывна. Интуитивно это понятно из рисунка: с каждой итерацией расстояние между кривыми порядка n+1 и n, первой «обвивающей» последнюю, делается все меньше и меньше.

Далее следует доказать, что кривая проходит через любую точку квадрата. Рассуждение здесь такое. Кривая порядка 1 проходит на расстоянии не далее 1/4 от любой точки внутри квадрата. Поэтому любая из четырех ее уменьшенных копий в кривой второго порядка оказывается не далее 1/8 от любой точки каждой из четырех четвертей квадрата, а, значит, любая точка всего квадрата удалена от кривой не более, чем на 1/8. Кривая третьего порядка лежит не далее, чем в 1/16 от любой точки в квадрате, и так далее. Таким образом, в предельном случае кривая будет проходить в ε-окрестности любой точки внутри квадрата. Тогда для некоей последовательности аргументов функции, последовательность соответствующих значений непременно сойдется в данную точку; иными словами, кривая проходит через все точки квадрата. Строго можно доказать, что кривая не только проходит через все точки квадрата, но и «не влезает» в квадрат — через почти все некоторые точки она проходит более одного раза! (Это следует, например, из неизоморфности отрезка [0;1] единичному квадрату: на отрезке удаление почти любой точки рассекает его на два несвязных подмножества, а в квадрате такой точки нет) [Возможно, это ошибка. Ссылка в обсуждение — прочитайте!].

Интересен вопрос, можно ли говорить о фрактальности этой кривой. С одной стороны, кривая, безусловно, самоподобна, за исключением соединительных отрезков, в силу построения. С другой стороны, под Мандельбротово определение фрактала она не попадает[4]: поскольку кривая заполняет весь квадрат, то ее Хаусдорфова размерность совпадает с топологической, и равна 2. Так что ответ зависит от решения о том, что следует считать фракталом. В некотором смысле, кривая Гильберта находится на границе между фрактальными и не фрактальными объектами.

Алгоритмически Гильбертова кривая удобно строится с помощью переписывающей символьной системы Линденмайера (L-System)[5], конечный результат преобразования в которой интерпретируется как «черепашья» графика[6]. Если интересно, то об этом можно будет поговорить отдельно. А здесь пока приведу только код для Mathematica 6.0, с помощью которого были построены все иллюстрации:

LIterate[omega_, rules_, n_] := 
  Nest[StringReplace[#, rules]&, omega, n];

QuadPart[list_] :=
  With[{m = Length[list]/4},
   Flatten[
     Partition[#, m, m-1, {1,2}, {}]& /@ 
      Partition[list, m+1, m, {1,m}, {}], 1] /; IntegerQ[m] && m > 1];

HilbertCurve[r_, s_] :=
  Module[{
      omega = "L",
      rules = {"L" -> "+RF-LFL-FR+", "R" -> "-LF+RFR+FL-"},
      colority = 0.8,
      ttl, pts},
     
    ttl[{p_, d_}, "F"] := {p + d, d};
    ttl[{p_, d_}, "+"] := {p,   I*d};
    ttl[{p_, d_}, "-"] := {p,  -I*d};
    ttl[pd_, _] := pd;
   
    pts = 2^(s-r) * {Re[#], Im[#]}& /@ First /@ Split[
       First /@ FoldList[ttl, {0,1}, Characters @ LIterate["L", rules, r]]];
      
    Graphics[Style[{
       Thickness[1.5^(-r-8)],
       If[r > 1,
        MapThread[
         {#1, Line @ #2} &, {
          Riffle[Hue[#, 1, colority]& /@ (0.25 * Range[0, 3]), Black],
          QuadPart[pts]}],
        Line[pts]]}, Antialiasing -> False], {
      ImageSize -> 2^s * {1,1},
      ImagePadding -> None,
      PlotRangePadding -> 2^(s-r-1) * {1,1} }]
  ];

Table[HilbertCurve[i, 8], {i, 1, 7}]

Полезная литература

1. M. Gardner, Penrose Tiles to Trapdoor Ciphers, W. H. Freeman and Co. : NY, 1989.

2. E. W. Weisstein. Plane-Filling Function in MathWorld—A Wolfram Web Resource.

3. A. Bogomolny, Plane Filling Curves in Interactive Mathematics Miscellany and Puzzles.

4. B. Mandelbrot. The Fractal Geometry of Nature, W. H. Freeman and Co. : NY, 1982. Русское изд.: Б. Мандельброт. Фрактальная геометрия природы. Институт компьютерных исследований : M., 2002.

5. L-system in Wikipedia.

6. Web Turtle by Bill Kendrick.

Tags: chaos, computer, math, scipop
Subscribe
  • Post a new comment

    Error

    Anonymous comments are disabled in this journal

    default userpic
  • 25 comments