кривая Пеано

Кривая, заполняющая пространство

Две итерации кривой Пеано

В геометрии кривая Пеано является первым примером заполняющей пространство кривой , открытой Джузеппе Пеано в 1890 году. ^[1] Кривая Пеано является сюръективной , непрерывной функцией из единичного интервала на единичный квадрат , однако она не является инъективной . Пеано был мотивирован более ранним результатом Георга Кантора о том, что эти два множества имеют одинаковую мощность . Из-за этого примера некоторые авторы используют фразу «кривая Пеано» для более общего обозначения любой заполняющей пространство кривой. ^[2]

Строительство

Кривая Пеано может быть построена последовательностью шагов, где шаг th строит набор квадратов и последовательность центров квадратов из набора и последовательности, построенных на предыдущем шаге. В качестве базового случая состоит из одного единичного квадрата и является одноэлементной последовательностью, состоящей из его центральной точки. $я$ $S_{i}$ $P_{i}$ $S_{0}$ $P_{0}$

На шаге каждый квадрат разбивается на девять меньших равных квадратов, а его центральная точка заменяется смежной подпоследовательностью центров этих девяти меньших квадратов. Эта подпоследовательность формируется путем группировки девяти меньших квадратов в три столбца, упорядочивания центров смежно внутри каждого столбца, а затем упорядочивания столбцов от одной стороны квадрата к другой таким образом, чтобы расстояние между каждой последовательной парой точек в подпоследовательности равнялось длине стороны малых квадратов. Возможны четыре таких упорядочения: $я$ $с$ $S_{i-1}$ $с$

Три левых центра снизу вверх, три средних центра сверху вниз и три правых центра снизу вверх
Правые три центра снизу вверх, средние три центра сверху вниз и левые три центра снизу вверх
Три левых центра сверху вниз, три средних центра снизу вверх и три правых центра сверху вниз
Три правых центра сверху вниз, три средних центра снизу вверх и три левых центра сверху вниз.

Среди этих четырех упорядочений, один для выбирается таким образом, что расстояние между первой точкой упорядочения и его предшественником в также равно длине стороны малых квадратов. Если была первой точкой в своем упорядочении, то первый из этих четырех упорядочений выбирается для девяти центров, которые заменяют . ^[3] $с$ $P_{i}$ $с$ $с$

Сама кривая Пеано является пределом кривых, проходящих через последовательности квадратных центров, уходящие в бесконечность. $я$

L-системная конструкция

Кривая Пеано, показанная во введении, может быть построена с использованием системы Линденмайера . Эту L-систему можно описать следующим образом:

Переменные :	XYF
Константы :	+ −
Начинать :	Х
Правила :	( X → XFYFX+F+YFXFY−F−XFYFX ), ( Y → YFXFY−F−XFYFX+F+YFXFY )

где " F " означает "тянуть вперед", "+" означает "повернуть по часовой стрелке на 90°", а "−" означает "повернуть против часовой стрелки на 90°". Изображение во введении показывает изображения первых трех итераций правил.

Кривая, показанная в разделе «Построение», может быть построена следующим образом:

Переменные :	Ф
Константы :	+ −
Начинать :	Ф
Правила :	( Ф → Ф+Ф−Ф−ФФ−Ф−Ф−ФФ )

где " F " означает "тянуть вперед", "+" означает "повернуть по часовой стрелке на 90°", а "−" означает "повернуть против часовой стрелки на 90°". Изображение выше показывает первые две итерации правила.

Варианты

В определении кривой Пеано можно выполнить некоторые или все шаги, сделав центры каждой строки из трех квадратов смежными, а не центры каждого столбца квадратов. Эти выборы приводят к множеству различных вариантов кривой Пеано. ^[3]

«Многоосновный» вариант этой кривой с различным числом подразделений в разных направлениях может использоваться для заполнения прямоугольников произвольной формы. ^[4]

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

Ссылки

^ Пеано, Г. (1890), «Sur une courbe, qui remplit toute une aire plane», Mathematische Annalen , 36 (1): 157–160 , doi : 10.1007/BF01199438.
^ Гугенхаймер, Генрих Вальтер (1963), Дифференциальная геометрия, Courier Dover Publications, стр. 3, ISBN 9780486157207.
^ ab Bader, Michael (2013), "2.4 Peano curve", Space-Filling Curves, Texts in Computational Science and Engineering, т. 9, Springer, стр. 25–27 , doi :10.1007/978-3-642-31046-1_2, ISBN 9783642310461.
^ Коул, А. Дж. (сентябрь 1991 г.), «Полутоновая обработка без дизеринга или улучшения краев», The Visual Computer , 7 (5): 235–238 , doi :10.1007/BF01905689

[1] Пеано, Г. (1890), «Sur une courbe, qui remplit toute une aire plane», Mathematische Annalen , 36 (1): 157–160 , doi : 10.1007/BF01199438.

[2] Гугенхаймер, Генрих Вальтер (1963), Дифференциальная геометрия, Courier Dover Publications, стр. 3, ISBN 9780486157207.

[bader-3] Bader, Michael (2013), "2.4 Peano curve", Space-Filling Curves, Texts in Computational Science and Engineering, т. 9, Springer, стр. 25–27 , doi :10.1007/978-3-642-31046-1_2, ISBN 9783642310461.

[4] Коул, А. Дж. (сентябрь 1991 г.), «Полутоновая обработка без дизеринга или улучшения краев», The Visual Computer , 7 (5): 235–238 , doi :10.1007/BF01905689