Отрезки
Длина
Фрактальная размерность
Позиция

Подробнее о кривых, заполняющих пространство

Проводник по кривым, заполняющим пространство

У линии есть длина, но нет площади, а у квадрата площадь есть. И всё же линию можно изогнуть так, что она пройдёт через каждую часть квадрата. Начните с нескольких клеток и одной изогнутой линии, проходящей через них; разделите каждую клетку на меньшие и проведите линию изгибами через все эти клетки; повторите. Наблюдайте, как перо уровень за уровнем рисует кривую Гильберта, кривую Пеано и их родственниц, а затем поставьте перо в любое место кривой, чтобы увидеть, какая точка линии попадает в какую клетку квадрата. Кривая, заполняющая пространство, — это одна линия, которая посещает каждую клетку сетки; каждый уровень делит каждую клетку на меньшие и проводит линию изгибами через все эти клетки. Нажмите «Пуск», чтобы увидеть, как перо рисует каждый уровень от начала до конца, или «Шаг», чтобы нарисовать следующий уровень. Выберите кривую Гильберта, Мура или Пеано, Z-порядок, flowsnake Госпера или стреловидную кривую Серпинского. Щёлкните или потяните по рисунку, по цветной линии под ним или по ползунку «Перо», чтобы передвинуть перо вдоль кривой: плитка «Позиция» показывает номер шага и клетку, в которой он находится. Цвета идут вдоль линии, поэтому клетки близких цветов — это близкие шаги.

Как это работает

  1. Нажмите «Пуск», чтобы увидеть, как перо рисует каждый уровень от начала до конца, или «Шаг», чтобы нарисовать следующий уровень; потяните ползунок «Уровень», чтобы перейти к любому уровню.
  2. Выберите кривую Гильберта, Мура или Пеано, Z-порядок, кривую Госпера или стреловидную кривую Серпинского.
  3. Щёлкните или потяните по рисунку, по цветной линии под ним или по ползунку «Перо», чтобы передвинуть перо вдоль кривой.
  4. В плитках читайте число отрезков, длину, фрактальную размерность и позицию пера.

Линия, которая посещает каждую клетку

Кривая Гильберта уровня n идёт по сетке из 2ⁿ на 2ⁿ клеток, посещает каждую клетку один раз и всегда шагает в соседнюю клетку. Уровень 1 — это один изгиб через 4 клетки. Каждый следующий уровень заменяет каждую клетку 4 меньшими, а каждый шаг — маленькой копией изгиба, повёрнутой так, чтобы концы соединились. Линия через 4ⁿ клеток состоит из 4ⁿ − 1 шагов, а её длина в 2ⁿ − 2⁻ⁿ раз больше стороны квадрата: с каждым уровнем она почти точно удваивается, а рисунок остаётся того же размера. Кривая Пеано делает то же самое с 9 клетками на каждую клетку и S-образными изгибами, а кривая Мура соединяет четыре кривые Гильберта в замкнутую петлю.

От числовой прямой к квадрату

Цветная линия под рисунком — это числовая прямая от 0 до 1, а кривая — та же линия, уложенная в квадрат. Передвиньте перо, и плитка «Позиция» покажет, на каком оно шаге и какая это клетка. На кривой Гильберта шаги с близкими номерами всегда лежат в близких клетках, и это видно по цветам: каждый цвет держится вместе, одним пятном. Поэтому кривую Гильберта используют, чтобы хранить карты, изображения и другие двумерные данные в одномерной памяти. Z-порядок вычислить проще, потому что координаты клетки — это просто биты номера шага, розданные по очереди, но он делает скачки: почти половина его шагов ведёт не в соседнюю клетку.

Кривые, которые заполняют другие фигуры

Кривая Госпера, или flowsnake, заменяет каждый отрезок семью на сетке из треугольников и заполняет фигуру с фрактальным берегом — остров Госпера. Её размерность равна 2, как и у кривых, заполняющих квадрат: log 7 / log √7. Стреловидная кривая Серпинского заменяет каждый отрезок тремя, каждый вдвое короче. Она никогда не заполняет площадь: она сходится к треугольнику Серпинского, а её размерность равна log 3 / log 2 ≈ 1,585 — между линией и поверхностью.

Часто задаваемые вопросы

Как линия может заполнить квадрат?

Ни один отдельный уровень этого не делает: каждый уровень — обычная линия, у которой есть длина, но нет площади. Но уровни стабилизируются. Точка, лежащая на заданной доле пути вдоль линии, от уровня к уровню смещается всё меньше, и предел всех уровней — непрерывная кривая, проходящая через каждую точку квадрата. Джузеппе Пеано доказал в 1890 году, что такая кривая существует, к удивлению математиков своего времени.

Посещает ли кривая каждую точку ровно один раз?

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

Чем кривая Гильберта отличается от Z-порядка?

И та и другой выстраивают клетки сетки в один длинный ряд. Кривая Гильберта всегда шагает в соседнюю клетку, поэтому клетки, близкие в ряду, близки и в сетке. Z-порядок вычисляется быстрее, чередованием битов двух координат, но почти половина его шагов — скачки, некоторые из них через весь квадрат. Плитка «Длина» считает скачки.

Для чего используют кривые, заполняющие пространство?

Чтобы расположить двумерные данные в одномерном порядке, который держит соседей рядом. Базы данных и картографические сервисы индексируют места вдоль кривой Гильберта или в Z-порядке, графические программы обходят пиксели вдоль кривой Гильберта, чтобы распределить ошибки округления, а карты адресного пространства интернета используют её, чтобы родственные адреса оказывались бок о бок.

Почему стреловидная кривая Серпинского не заполняет квадрат?

Потому что она превращает каждый отрезок всего в три части вдвое меньшей длины; чтобы заполнить площадь, понадобилось бы четыре. Кривая сходится к треугольнику Серпинского — фигуре без площади с размерностью log 3 / log 2 ≈ 1,585.

Готовы попробовать?

Откройте PictorX в своем браузере — установка не требуется, для запуска не требуется кредитная карта.

Перейти в редактор