Дерево, заполняющее пространство

редактировать

Деревья, заполняющие пространство, представляют собой геометрические конструкции, аналогичные кривым заполнения пространства, но имеют ветвящуюся древовидную структуру и укоренены. Дерево, заполняющее пространство, определяется инкрементным процессом, результатом которого является дерево, для которого каждая точка в пространстве имеет путь конечной длины, который сходится к нему. В отличие от кривых заполнения пространства, отдельные пути в дереве короткие, что позволяет быстро добраться до любой части пространства из корня. Простейшие примеры деревьев, заполняющих пространство, имеют регулярную, самоподобную фрактальную структуру, но могут быть обобщены на нерегулярные и даже рандомизированные / Монте-Карло вариантов (см. Быстро исследуемое случайное дерево ). Деревья, заполняющие пространство, имеют интересные параллели в природе, в том числе сосудистые сети и фрактал рост растений, а также много интересных связей с L-системами в информатике.

Содержание

1 Определение
2 Примеры
3 См. Также
4 Ссылки

Определение

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

Термин «дерево, заполняющее пространство» в этом смысле был создан в техническом отчете 2009 года, который определяет «заполнение пространства» и «дерево» иначе, чем их традиционные определения в математике. Как объясняется в статье кривая заполнения пространства, в 1890 году Пеано нашел первую кривую заполнения пространства, и по определению Джордана 1887 года, которое сейчас является стандартным, кривая представляет собой единую кривую. функция, а не последовательность функций. Кривая является «заполняющей пространство», потому что это «кривая, диапазон которой содержит весь двумерный единичный квадрат» (как объяснено в первом предложении кривой заполнения пространства ).

Напротив, дерево заполнения пробелов, как определено в техническом отчете, не является единым деревом. Это всего лишь последовательность деревьев. В документе говорится: «Дерево, заполняющее пространство, на самом деле определяется как бесконечная последовательность деревьев». Он определяет $T square {\ displaystyle T _ {\ text {square}}}$ ${\ displaystyle T _ {\ text {square}}}$ как «последовательность деревьев», затем заявляет « $T square {\ displaystyle T _ {\ text {square }}}$ ${\ displaystyle T _ {\ text {square}}}$ - это дерево, заполняющее пробелы ". Это не заполнение пространства в стандартном смысле включения всего двумерного единичного квадрата. Вместо этого в документе это определяется как наличие деревьев в последовательности, произвольно приближающихся к каждой точке. В нем говорится: «Древовидная последовательность T называется« заполнением пространства »в пространстве X, если для каждого x ∈ X существует путь в дереве, который начинается в корне и сходится к x.». Стандартный термин для этой концепции состоит в том, что она включает в себя набор точек, которые плотны всюду в единичном квадрате.

Примеры

Простейшим примером дерева, заполняющего пространство, является дерево, которое заполняет квадрат плоской области. На изображениях показана конструкция плоской области $[0, 1] 2 ⊂ R 2 {\ displaystyle [0,1] ^ {2} \ subset \ mathbb {R} ^ {2}}$ ${\ displaystyle [0,1] ^ { 2} \ subset \ mathbb {R} ^ {2}}$ . На каждой итерации к существующим деревьям добавляются дополнительные ветви.

Квадратное дерево заполнения пространства (Итерация 1)
Квадратное дерево заполнения пространства (Итерация 2)
Квадратное дерево заполнения пространства (Итерация 3)
Квадратное дерево заполнения пространства (Итерация 4)
Квадратное дерево, заполняющее пространство (итерация 5)
Квадратное дерево, заполняющее пространство (итерация 6)

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

Схема подразделения для первых трех итераций дерева заполнения пространства треугольника

Первые шесть итераций дерева заполнения пространства треугольника проиллюстрированы ниже:

Дерево заполнения пространства треугольника (итерация 1)
Дерево заполнения пространства треугольников (итерация 2)
Дерево заполнения пространства треугольников (итерация 3)
Дерево заполнения пространства треугольников (итерация 4)
Дерево заполнения пространства треугольников (итерация 5)
Пространство треугольника -заполняющее дерево (итерация 6)

Заполняющие пространство деревья также могут быть построены в более высоких измерениях. Простейшими примерами являются кубы в $R 3 {\ displaystyle \ mathbb {R} ^ {3}}$ $\ mathbb {R} ^ {3}$ и гиперкубы в $R n. {\ Displaystyle \ mathbb {R} ^ {n}}$ $\ mathbb {R} ^ {n}$ . Подобная последовательность итераций, используемая для дерева заполнения пространства квадрат, может использоваться для гиперкубов. Третья итерация такого дерева заполнения пространства в $R 3 {\ displaystyle \ mathbb {R} ^ {3}}$ $\ mathbb {R} ^ {3}$ проиллюстрирована ниже:

Дерево заполнения пространства куба (итерация 3)

См. Также

Ссылки

^Саган, Х. и Дж. Холбрук: "Кривые, заполняющие пространство", Springer-Verlag, New York, 1994
^Каффнер, Дж. Дж. И С. М. Лавалль: Деревья, заполняющие пространство, Институт робототехники, Университет Карнеги-Меллона, CMU-RI-TR-09-47, 2009.
^Kuffner, JJ; LaValle, S.M.; «Деревья, заполняющие пространство: новый взгляд на поэтапный поиск для планирования движения», Интеллектуальные роботы и системы (IROS), Международная конференция IEEE / RSJ 2011 г., том, №, стр.2199-2206, 25-30 сентября. 2011
^Куффнер, Дж. Дж. И С. М. ЛаВалль: Деревья, заполняющие пространство, Институт робототехники, Университет Карнеги-Меллона, CMU-RI-TR-09-47, 2009 г.