Кривая Мортона

В математическом анализе и информатике кривая Мортона, Z-последовательность, Z-порядок, кривая Лебега, порядок Мортона или код Мортона — это функция, которая отображает многомерные данные в одномерные, сохраняя локальность точек данных. Функция была введена в 1966 году Гаем Макдональдом Мортоном. Z-значение точки в многомерном пространстве легко вычисляется чередованием двоичных цифр его координатных значений. Когда данные запоминаются в этом порядке, могут быть использованы любые одномерные структуры, такие как двоичные деревья поиска, B-деревья, списки с пропусками или хеш-таблицы (с отбрасыванием младших битов). Созданный таким образом порядок можно эквивалентно описать как порядок, который можно получить обходом в глубину дерева квадрантов.