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

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

Определение

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

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

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

Примеры

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

• 

  Дерево, заполняющее квадратное пространство (итерация 1)

• 

  Дерево, заполняющее квадратное пространство (итерация 2)

• 

  Дерево, заполняющее квадратное пространство (итерация 3)

• 

  Дерево, заполняющее квадратное пространство (итерация 4)

• 

  Дерево, заполняющее квадратное пространство (итерация 5)

• 

  Дерево, заполняющее квадратное пространство (итерация 6)

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

• 

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

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

• 

  Дерево, заполняющее пространство треугольником (итерация 1)

• 

  Дерево, заполняющее пространство треугольником (итерация 2)

• 

  Дерево, заполняющее пространство треугольником (итерация 3)

• 

  Дерево, заполняющее пространство треугольником (итерация 4)

• 

  Дерево, заполняющее пространство треугольником (итерация 5)

• 

  Дерево, заполняющее пространство треугольником (итерация 6)

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

• 

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

Смотрите также

• H дерево
• Кривая заполнения пространства
• Быстрое изучение случайного дерева (RRTs)
• Разделение двоичного пространства

Рекомендации

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