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

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

Иллюстрации

Показать все

Реферат

ОБЛАСТЬ ТЕХНИКИ, К КОТОРОЙ ОТНОСИТСЯ ИЗОБРЕТЕНИЕ

[1] Настоящее решение относится к системе и способу обработки запроса пользователя на предоставление объекта, сохраненного с использованием гибкой иерархической структуры.

УРОВЕНЬ ТЕХНИКИ

[2] В современных компьютерных технологиях, пространственное расположение объектов обычно включает в себя разделение пространства (сцены) на меньшие части. Разбиение может происходить различными методами, причем метод может учитывать вид пространства. Например, плоскостные объекты зачастую разбиваются на квадранты, трехмерные объекты зачастую разбиваются на октанты. В двумерной и трехмерной компьютерной графике, разбиение пространства обычно осуществляется во время обработки данных графическим конвейером с целью уменьшить будущие расчеты и минимизировать количество объектов, направляемых на обработку графическому конвейеру. В больших деталях это раскрыто в патенте США US 20030227455 Al "Grid-based loose octree for spatial partitioning" ("Основанное на сетке гибкое октодерево для пространственной декомпозиции").

[3] Как только пространство разделено, и все объекты этого пространства определены в подходящие для них ячейки, результаты обычно сохраняются в определенной структуре данных для последующего использования компонентами обработки графических данных, такими как движком видеоигр или генератором анимации. Структура данных обычно создается после создания сцены, но до ее визуализации и до момента взаимодействия пользователя со сценой. Во время визуализации сцены может потребоваться найти объект на сцене, соответствующий выбранной точке. Получив соответствующую точку в одномерных координатах (например, по оси х), или в двумерных координатах (например, в координатах осей х, у) или в трехмерных координатах (например, в координатах осей х, у, z), или в многомерных координатах, структура данных позволяет осуществлять поиск в ней, чтобы найти информацию об объекте, содержащем выбранную точку.

[4] Существует по меньшей мере несколько существующих техник и соответствующих этим техникам структур данных для пространственного разделения. Они включают в себя регулярную координатную сетку, бинарное дерево, дерево квадрантов, дерево октантов, к-дерево. Каждая техника имеет свои особенности.

[5] Так, например, бинарное дерево имеет корневой узел, имеющий два дочерних узла (левый дочерний узел и правый дочерний узел). Каждый дочерний узел, в свою очередь, может иметь по два дочерних узла, и так далее. Каждый узел представляет отрезок пространства. Каждый отрезок подразделен на два дочерних отрезка. Каждый узел структуры данных имеет указатель, то есть родительский узел указывает на дочерние узлы. Более мелкое разбиение на отрезки каждого последующего уровня осуществляется для зон со значительным количеством размещенных там объектов. Бинарное дерево может быть подразделено единообразно либо не единообразно, в зависимости от использованного алгоритма пространственного разбиения. Бинарное дерево иерархически разбивает пространство на отрезки вплоть до определенной глубины (детализации).

[6] Дерево квадрантов имеет структуру, подобную бинарному дереву, однако узлы дерева квадрантов имеют большее число дочерних узлов (обычно четыре). Каждый узел дерева квадрантов представляет собой квадрант пространства. Каждый квадрант может быть подразделен на дочерние квадранты (обычно четыре). Каждый родительский квадрант может иметь указатели на дочерние квадранты. Более мелкое разбиение на квадранты каждого последующего уровня осуществляется для зон со значительным количеством размещенных там объектов. Дерево квадрантов может быть подразделено единообразно либо не единообразно, в зависимости от использованного алгоритма пространственного разбиения. Дерево квадрантов иерархически разбивает пространство на квадранты вплоть до определенной глубины (детализации).

[7] Дерево октантов имеет структуру, подобную бинарному дереву, а также подобную дереву квадрантов, однако узлы дерева октантов имеют большее число дочерних узлов (обычно восемь). Каждый узел дерева октантов представляет собой октант пространства, каждый октант может быть подразделен на дочерние октанты (обычно восемь). Каждый родительский октант может иметь указатели на дочерние октанты. Более мелкое разбиение на октанты каждого последующего уровня осуществляется для зон со значительным количеством размещенных там объектов. Дерево октантов может быть подразделено единообразно либо не единообразно, в зависимости от использованного алгоритма пространственного разбиения. Дерево октантов иерархически разбивает пространство на октанты вплоть до определенной глубины (детализации).

[8] Объекты, размещенные в ячейках (таких, например, как октанты, квадранты, отрезки) могут разбиваться, когда границы разбиения пересекают данные объекты. Обработка таких разделенных объектов требует затрат значительных ресурсов.

[9] Таким образом, в то время как существующие обычные компьютерные системы являются приемлемыми, улучшение таких систем, тем не менее, возможно.

СУЩНОСТЬ ИЗОБРЕТЕНИЯ

[10] Целью настоящего решения является устранение или смягчение по меньшей мере некоторых из неудобств, присутствующих на существующем уровне техники.

[11] В соответствии с вариантами осуществления настоящего решения, предусматривается способ определения пространственного хранения объекта. Способ осуществляется с использованием гибкой иерархической структуры. Гибкая иерархическая структура включает в себя множество (группу) элементов n-дерева. Способ исполняется на компьютере, определяющем пространственное хранение объекта. Способ включает в себя: получение из памяти компьютера объекта для размещения в одном из множества элементов n-дерева; определение наиболее подходящего элемента n-дерева для размещения объекта; выявление (проверку), выходят ли границы объекта за границы наиболее подходящего элемента n-дерева; в случае, если границы объекта выходят за границы наиболее подходящего элемента n-дерева, определение границы наиболее подходящего элемента n-дерева, которая будет пересечена частью объекта, когда объект расположен в этом наиболее подходящем элементе n-дерева; условное увеличение размера наиболее подходящего элемента n-дерева путем добавления к нему зоны присутствия объекта, при этом граница зоны присутствия объекта удалена от указанной границы наиболее подходящего элемента n-дерева на максимальную величину выступания объекта за пределы наиболее подходящего элемента n-дерева.

[12] В некоторых вариантах осуществления способ дополнительно включает в себя предоставление пользователю объекта, ассоциированного с элементом n-дерева, предоставление через пользовательский интерфейс компьютера, осуществляемое в ответ на запрос пользователя, где запрос пользователя осуществляется путем выбора пользователем соответствующего фрагмента пространства.

[13] В некоторых вариантах осуществления способ характеризуется тем, что указанный фрагмент пространства соответствует одному из: элементу n-дерева, размещающему по меньшей мере один объект, находящийся в выбранном пользователем фрагменте пространства; и зоне присутствия объекта, условно увеличивающей размер соседнего элемента n-дерева.

[14] В некоторых вариантах осуществления способ дополнительно включает в себя, в ответ на то, что выбранный указанный фрагмент пространства соответствует указанной зоне присутствия объекта, осуществление поиска объекта, причем поиск объекта осуществляется в: (i) элементе n-дерева, размещающем по меньшей мере один объект, находящийся в выбранном пользователем фрагменте пространства и в (ii) соседнем элементе n-дерева, условно увеличенном зоной присутствия объекта, соответствующей выбранному указанному фрагменту пространства.

[15] В некоторых вариантах осуществления способ дополнительно включает в себя получение, через пользовательский интерфейс компьютера, запрос пользователя.

[16] В некоторых вариантах осуществления способ характеризуется тем, что множество элементов n-дерева включает в себя как минимум одно из: множество узлов n-дерева, причем каждый из множества узлов n-дерева имеет предопределенное число элементов п-дерева следующего уровня (дочерних элементов), и множество листьев n-дерева.

[17] В некоторых вариантах осуществления способ характеризуется тем, что указанное определение наиболее подходящего элемента n-дерева для размещения объекта осуществляется путем определения центра объекта.

[18] В некоторых вариантах осуществления способ дополнительно включает в себя определение количества объектов в элементе n-дерева.

[19] В некоторых вариантах осуществления способ характеризуется тем, что максимальное допустимое количество объектов, расположенных в одном элементе n-дерева, предопределено.

[20] В некоторых вариантах осуществления технологии способ дополнительно включает в себя создание предопределенного числа (количества) элементов n-дерева следующего уровня в случае, когда число объектов, соответствующих данному элементу n-дерева любого уровня (предшествующий элемент n-дерева), превышает максимально допустимое количество.

[21] В некоторых вариантах осуществления способ дополнительно включает в себя

перераспределение объекта между элементами n-дерева разных уровней.

[22] В некоторых вариантах осуществления способ характеризуется тем, что перераспределение объекта осуществляется между предшествующим элементом n-дерева и одним из множества вновь созданных элементов n-дерева следующего уровня.

[23] Способ также может характеризоваться тем, что перераспределение объектов между предшествующим элементом n-дерева и вновь созданными элементами n-дерева следующего уровня осуществляется с учетом размера перераспределяемых объектов.

[24] Способ может характеризоваться тем, что перераспределение объектов между предшествующим элементом n-дерева и вновь созданными элементами n-дерева следующего уровня осуществляется с учетом потенциального пересечения перераспределяемых объектов границами элементов n-дерева следующего уровня.

[25] В некоторых вариантах осуществления способ дополнительно включает в себя упразднение предопределенного числа элементов n-дерева следующего уровня в случае, когда сумма объектов во всех этих элементах n-дерева указанного следующего уровня и в предшествующем элементе n-дерева не превышает максимально допустимое количество объектов предшествующего элемента n-дерева.

[26] В некоторых вариантах осуществления способ дополнительно включает в себя перемещение объектов из предопределенного числа (количества) упраздненных элементов n-дерева следующего уровня в предшествующий элемент n-дерева.

[27] В некоторых вариантах осуществления способ характеризуется тем, что по меньшей мере одна зона присутствия объекта, увеличивающая размер элемента n-дерева, как минимум частично перекрывает другой элемент n-дерева того же уровня.

[28] В некоторых вариантах осуществления способ характеризуется тем, что по меньшей мере одна зона присутствия объекта, увеличивающая размер элемента n-дерева следующего уровня, выходит за пределы предшествующего элемента n-дерева.

[29] В некоторых вариантах осуществления способ характеризуется тем, что каждый объект может быть размещен только в одном элементе n-дерева.

[30] В некоторых вариантах осуществления способ характеризуется тем, что n-дерево является деревом квадрантов, и предопределенное число элементов дерева квадрантов следующего уровня равно четырем.

[31] В некоторых вариантах осуществления способ характеризуется тем, что определение наиболее подходящего элемента дерева квадрантов для размещения объекта осуществляется путем выбора такого элемента дерева квадрантов, который будет иметь наименьший прирост площади после условного увеличения размера наиболее подходящего элемента дерева квадрантов путем добавления к нему зоны присутствия объекта.

[32] В некоторых вариантах осуществления способ характеризуется тем, что n-дерево является деревом октантов, и предопределенное число элементов дерева октантов следующего уровня равно восьми.

[33] В некоторых вариантах осуществления способ характеризуется тем, что определение наиболее подходящего элемента дерева октантов для размещения объекта осуществляется путем выбора такого элемента дерева октантов, который будет иметь наименьший прирост объема после условного увеличения размера наиболее подходящего элемента дерева октантов путем добавления к нему зоны присутствия объекта.

[34] В некоторых вариантах осуществления способ характеризуется тем, что n-дерево является бинарное деревом, и предопределенное число элементов бинарного дерева следующего уровня равно двум.

[35] В некоторых вариантах осуществления способ характеризуется тем, что определение наиболее подходящего элемента бинарного дерева для размещения объекта осуществляется путем выбора такого элемента бинарного дерева, который будет иметь наименьший прирост расстояния после условного увеличения размера наиболее подходящего элемента бинарного дерева путем добавления к нему зоны присутствия объекта.

[36] Другим объектом настоящего решения является постоянный носитель информации. Постоянный носитель информации хранит базу данных. База данных включает в себя гибкую иерархическую структуру. Гибкая иерархическая структура включает в себя множество элементов n-дерева. Постоянный носитель информации хранит машиночитаемые инструкции (коды), при выполнении которых компьютером осуществляется: получение из памяти компьютера объекта для размещения в одном из множества элементов n-дерева; определение наиболее подходящего элемента n-дерева для размещения объекта; выявление, выходят ли границы объекта за границы наиболее подходящего элемента n-дерева; в случае, если границы объекта выходят за границы наиболее подходящего элемента n-дерева, определение границы наиболее подходящего элемента n-дерева, которая будет пересечена частью объекта, когда объект расположен в этом наиболее подходящем элементе n-дерева; условное увеличение размера наиболее подходящего элемента n-дерева путем добавления к нему зоны присутствия объекта, при этом граница зоны присутствия объекта удалена от указанной границы наиболее подходящего элемента n-дерева на максимальную величину выступания объекта за пределы наиболее подходящего элемента n-дерева.

[37] В некоторых вариантах осуществления постоянный носитель информации хранит машиночитаемые инструкции (коды), при выполнении которых компьютером дополнительно осуществляется предоставление пользователю объекта, ассоциированного с элементом n-дерева, предоставление через пользовательский интерфейс компьютера, осуществляемое в ответ на запрос пользователя, где запрос пользователя осуществляется путем выбора пользователем соответствующего фрагмента пространства. [38] В некоторых вариантах осуществления постоянный носитель информации характеризуется тем, что указанный фрагмент пространства соответствует одному из: (i) элементу n-дерева, размещающему по меньшей мере один объект, находящийся в выбранном пользователем фрагменте пространства, и (и) зоне присутствия объекта, условно увеличивающей размер соседнего элемента n-дерева.

[39] В некоторых вариантах осуществления постоянный носитель информации хранит машиночитаемые инструкции (коды), при выполнении которых компьютером, в ответ на то, что выбранный указанный фрагмент пространства соответствует указанной зоне присутствия объекта, дополнительно осуществляется поиск объекта, причем поиск объекта осуществляется в: (i) элементе n-дерева, размещающем по меньшей мере один объект, находящийся в выбранном пользователем фрагменте пространства, и в (и) соседнем элементе n-дерева, условно увеличенном зоной присутствия объекта, соответствующей выбранному указанному фрагменту пространства.

[40] В некоторых вариантах осуществления постоянный носитель информации хранит машиночитаемые инструкции (коды), при выполнении которых компьютером дополнительно осуществляется получение, через пользовательский интерфейс компьютера, запрос пользователя.

[41] В некоторых вариантах осуществления постоянный носитель информации характеризуется тем, что множество элементов n-дерева включает в себя как минимум одно из: множество узлов n-дерева, причем каждый из множества узлов n-дерева имеет предопределенное число элементов n-дерева следующего уровня (дочерних элементов), и множество листьев n-дерева.

[42] В некоторых вариантах осуществления постоянный носитель информации характеризуется тем, что указанное определение наиболее подходящего элемента n-дерева для размещения объекта осуществляется путем определения центра объекта.

[43] В некоторых вариантах осуществления постоянный носитель информации хранит машиночитаемые инструкции (коды), при выполнении которых компьютером дополнительно осуществляется определение количества объектов в элементе n-дерева.

[44] В некоторых вариантах осуществления постоянный носитель информации характеризуется тем, что максимальное допустимое количество объектов, расположенных в одном элементе n-дерева, предопределено.

[45] В некоторых вариантах осуществления постоянный носитель информации хранит машиночитаемые инструкции (коды), при выполнении которых компьютером осуществляется создание предопределенного числа элементов n-дерева следующего уровня, когда число объектов, соответствующих данному элементу n-дерева любого уровня (предшествующий элемент), превышает максимально допустимое количество. [46] В некоторых вариантах осуществления постоянный носитель информации хранит машиночитаемые инструкции (коды), при выполнении которых компьютером осуществляется перераспределение объекта между элементами n-дерева разных уровней.

[47] В некоторых вариантах осуществления постоянный носитель информации характеризуется тем, что перераспределение объекта осуществляется между предшествующим элементом n-дерева и одним из множества вновь созданных элементов n-дерева следующего уровня.

[48] Постоянный носитель информации может характеризоваться тем, что перераспределение объектов между предшествующим элементом n-дерева и вновь созданными элементами n-дерева следующего уровня осуществляется с учетом размера перераспределяемых объектов.

[49] Постоянный носитель информации может характеризоваться тем, что перераспределение объектов между предшествующим элементом n-дерева и вновь созданными элементами n-дерева следующего уровня осуществляется с учетом потенциального пересечения перераспределяемых объектов границами элементов n-дерева следующего уровня.

[50] В некоторых вариантах осуществления постоянный носитель информации хранит машиночитаемые инструкции (коды), при выполнении которых компьютером дополнительно осуществляется упразднение предопределенного числа элементов n-дерева следующего уровня в случае, когда сумма объектов во всех этих элементах n-дерева указанного следующего уровня и в предшествующем элементе n-дерева не превышает максимально допустимое количество объектов предшествующего элемента n-дерева.

[51] В некоторых вариантах осуществления постоянный носитель информации хранит машиночитаемые инструкции (коды), при выполнении которых компьютером осуществляется перемещение объектов из предопределенного числа упраздненных элементов n-дерева следующего уровня в предшествующий элемент n-дерева.

[52] В некоторых вариантах осуществления постоянный носитель информации характеризуется тем, что по меньшей мере одна зона присутствия объекта, увеличивающая размер элемента n-дерева, как минимум частично перекрывает другой элемент n-дерева того же уровня.

[53] В некоторых вариантах осуществления постоянный носитель информации характеризуется тем, что по меньшей мере одна зона присутствия объекта, условно увеличивающая размер элемента n-дерева следующего уровня, выходит за пределы предшествующего элемента n-дерева.

[54] В некоторых вариантах постоянный носитель информации характеризуется тем, что каждый объект может быть размещен только в одном элементе n-дерева.

[55] В некоторых вариантах постоянный носитель информации характеризуется тем, что n-дерево является деревом квадрантов, и предопределенное число элементов дерева квадрантов следующего уровня равно четырем.

[56] В некоторых вариантах осуществления постоянный носитель информации характеризуется тем, что определение наиболее подходящего элемента дерева квадрантов для размещения объекта осуществляется путем выбора такого элемента дерева квадрантов, который будет иметь наименьший прирост площади после условного увеличения размера наиболее подходящего элемента дерева квадрантов путем добавления к нему зоны присутствия объекта.

[57] В некоторых вариантах осуществления постоянный носитель информации характеризуется тем, что n-дерево является деревом октантов, и предопределенное число элементов дерева октантов следующего уровня равно восьми.

[58] В некоторых вариантах постоянный носитель информации характеризуется тем, что определение наиболее подходящего элемента дерева октантов для размещения объекта осуществляется посредством выбора элемента дерева октантов, имеющего наименьший прирост объема после условного увеличения размера наиболее подходящего элемента дерева октантов путем добавления к нему зоны присутствия объекта.

[59] В некоторых вариантах осуществления постоянный носитель информации характеризуется тем, что n-дерево является бинарным деревом, и предопределенное число элементов бинарного дерева следующего уровня равно двум.

[60] В некоторых вариантах постоянный носитель информации характеризуется тем, что определение наиболее подходящего элемента бинарного дерева для размещения объекта осуществляется посредством выбора такого элемента бинарного дерева, который будет иметь наименьший прирост дины после условного увеличения размера наиболее подходящего элемента бинарного дерева путем добавления к нему зоны присутствия объекта.

[61] В контексте описания настоящего решения, «сервер» представляет собой программу, выполняемую на соответствующем оборудовании и способную осуществлять прием запросов (например, подаваемых клиентскими устройствами), передаваемых по сети, и выполнять эти запросы или обеспечивать их выполнение. Оборудование может представлять собой один компьютер или одну компьютерную систему, однако ни одно, ни другое не является обязательным . В данном контексте выражение «по меньшей мере один сервер» не означает, что каждая задача (например, предусмотренная принятыми инструкциями или запросами) или какая-либо конкретная задача будет принята, выполнена или ее выполнение будет обеспечено тем же самым сервером (то есть тем же самым программным обеспечением и/или оборудованием); предполагается, что прием и передача, выполнение или обеспечение выполнения любой задачи или запроса либо обработка результатов задачи или запроса может осуществлять любое число компонентов программного обеспечения или устройств и все эти компоненты программного обеспечения или оборудования могут быть представлены одним сервером или несколькими серверами, причем выражение «по меньшей мере один сервер» охватывает оба указанных варианта.

[62] В контексте описания настоящего решения, «электронное устройство» представляет собой любое компьютерное оборудование, обеспечивающее возможность выполнения программного обеспечения, предназначенного для решения требуемой задачи. В контексте настоящего описания, термин «электронное устройство» в основном ассоциируется с публикатором. Тем не менее, в некоторых случаях электронное устройство (то есть как устройство, ассоциированное в данном описании с публикатором) может также использоваться как клиентское устройство (то есть как устройство, ассоциированное в данном описании с публикатором). Таким образом, некоторые (не имеющие ограничительного характера) примеры электронных устройств включают в себя персональные компьютеры (настольные компьютеры, переносные компьютеры, нетбуки и т. д. ), смартфоны и планшеты, а также сетевое оборудование, такое как маршрутизаторы, коммутаторы и шлюзы. Следует отметить, что в данном контексте тот факт, что устройство функционирует в качестве электронного устройства, не исключает возможности его функционирования в качестве сервера для других электронных и клиентских устройств. Использование выражения «электронное устройство» не препятствует применению нескольких клиентских и/или электронных устройств в процессе приема и передачи, выполнения или обеспечения выполнения задачи либо запроса или обработки результатов задачи или запроса либо этапов способа, представленного в настоящем описании.

[63] В контексте описания «клиентское устройство» представляет собой любое компьютерное оборудование, обеспечивающее возможность выполнения программного обеспечения, предназначенного для решения требуемой задачи. В контексте настоящего описания термин «клиентское устройство» в основном ассоциируется с пользователем клиентского устройства. Тем не менее, в некоторых случаях клиентское устройство может также использоваться как электронное устройство (то есть как устройство, ассоциированное в данном описании с публикатором). Таким образом, некоторые (не имеющие ограничительного характера) примеры клиентских устройств включают в себя персональные компьютеры (настольные компьютеры, переносные компьютеры, нетбуки и т. д.), смартфоны и планшеты, а также сетевое оборудование, такое как маршрутизаторы, коммутаторы и шлюзы. Следует отметить, что в данном контексте тот факт, что устройство функционирует в качестве клиентского устройства, не исключает возможности его функционирования в качестве сервера для других клиентских устройств или электронных устройств. Использование выражения «клиентское устройство» не препятствует применению нескольких клиентских и/или электронных устройств в процессе приема и передачи, выполнения или обеспечения выполнения задачи либо запроса или обработки результатов задачи или запроса либо этапов способа, представленного в настоящем описании.

[64] В контексте описания настоящей технологии, «база данных» представляет собой любой структурированный набор данных, независимо от конкретной структуры, программы управления базой данных или оборудования, на котором осуществляется хранение данных, реализована память или иным способом обеспечивается возможность использования данных. База данных может быть реализована на том же оборудовании, что и процесс, осуществляющий хранение или использование информации, записанной в базе данных, или на отдельном оборудовании, таком как выделенный сервер или множество серверов.

[65] В контексте описания термин «n-дерево» обозначает иерархическую структуру данных, включающую в себя множество элементов n-дерева (узлов n-дерева и листьев n-дерева) разного уровня, n-дерево создается и поддерживается преимущественно для построения и поддерживания пространственных баз данных, где пространство может быть двумерным, трехмерным, четырехмерным, пятимерным и т. д. Оно используется для рекурсивного разделения пространства на предопределенное число регионов. В зависимости от типа n-дерева, оно может хранить информацию о точечных, линейных, площадных объектах, объемных, многомерных объектах, n-дерево может иметь различные воплощения, например бинарное дерево, дерево квадрантов, дерево октантов, и т.д. При этом любое из этих воплощений может иметь следующие общие свойства: (а) n-дерево разбивает пространство на регионы (адаптирующиеся ячейки); (б) каждый регион (адаптирующаяся ячейка) имеет максимальную вместимость; когда максимальная вместимость достигнута, ячейка разделяется; (в) n-дерево следует пространственному разбиению n-дерева.

[66] В контексте описания «элемент n-дерева» («ячейка», «адаптирующаяся ячейка», «adaptable cell») представляет собой элемент иерархической структуры данных. Элементами n-дерева являются узлы n-дерева и листья n-дерева разного уровня.

[67] В контексте описания термин «лист n-дерева» обозначает элемент n-дерева (адаптирующуюся ячейку), хранящий информацию об объектах, не имеющий «потомков». Ключ узла состоит из предопределенного числа компонент (по числу координат, используемых для описания пространства).

[68] В контексте описания термин «узел n-дерева» обозначает элемент n-дерева (адаптирующуюся ячейку), хранящий информацию об объектах, имеющий предопределенное число потомков, в зависимости от характеристик описываемого пространства. Ключ узла состоит из предопределенного числа компонент (по числу координат, используемых для описания пространства). Потомками узла n-дерева могут быть узлы n-дерева следующего уровня, либо листья n-дерева следующего уровня, либо узлы n-дерева следующего уровня и листья n-дерева следующего уровня.

[69] В контексте описания термин «объект» обозначает элемент, существующий в реальном или виртуальном пространстве. Объект может быть точечным, линейным, площадным, трехмерным, многомерным. В целях сохранения в различных иерархических структурах данных, объект может быть представлен тегом. Тег может иметь пространственные координаты. Тег дополнительно также может включать информацию о размере объекта. Тег может также включать информацию о форме объекта. Тег может включать в себя другую информацию. В некоторых воплощениях настоящей технологии, тег может быть связан с внешней базой данных, хранящей дополнительные данные об объекте (например, часы работы продуктового магазина, стоимость здания в компьютерной игре, и так далее).

[70] В контексте описания термин «дерево октантов» («восьмеричное дерево», «октодерево», «octree»), обозначает иерархическую структуру данных, включающую в себя множество (группу) элементов дерева октантов (узлов дерева октантов и листьев дерева октантов) разного уровня. Дерево октантов создается и поддерживается преимущественно для построения и поддерживания трехмерных баз данных. Оно используется для рекурсивного разделения пространства на восемь регионов (октантов). Октанты могут быть кубическими, а также иметь форму параллелепипеда. Дерево октантов может хранить информацию о точечных, линейных, площадных и объемных объектах. Дерево октантов может иметь различные воплощения. При этом любое из этих воплощений может иметь следующие общие свойства: (а) дерево октантов разбивает пространство на октанты; (б) каждый октант имеет максимальную вместимость; когда максимальная вместимость достигнута, ячейка разделяется; (в) дерево каталога следует пространственному разбиению дерева октантов.

[71] В контексте описания «элемент дерева октантов» представляет собой элемент иерархической структуры данных. Элементами дерева октантов являются узлы дерева октантов и листья дерева октантов разного уровня.

[72] В контексте описания термин «лист дерева октантов» обозначает элемент дерева октантов, хранящий информацию об объектах, не имеющих «потомков». Ключ листа дерева октантов состоит из трех компонент (для координат х, у и z).

[73] В контексте описания термин «узел дерева октантов» обозначает элемент дерева октантов, хранящий информацию об объектах, имеющих восемь потомков (по одному на каждый октант). Ключ узла состоит из двух компонент (для координат х, у и z). Потомками узла дерева октантов могут быть узлы дерева октантов следующего уровня, либо листья дерева октантов следующего уровня, либо узлы дерева октанток следующего уровня и листья дерева октантов следующего уровня.

[74] В контексте описания термин «дерево квадрантов» («4-дерево», «квадродерево», «quadtree»), обозначает иерархическую структуру данных, включающую в себя множество элементов дерева квадрантов (узлов дерева квадранта и листьев дерева квадранта) разного уровня. Дерево квадрантов создается и поддерживается преимущественно для построения и поддерживания пространственных баз данных. Оно используется для рекурсивного разделения пространства на четыре региона (квадранта). Квадранты могут быть квадратными и прямоугольными. Дерево квадрантов может хранить информацию о точечных, линейных и площадных объектах. Дерево квадрантов может иметь различные воплощения. При этом любое из этих воплощений может иметь следующие общие свойства: (а) дерево квадрантов разбивает пространство на квадранты (адаптирующиеся ячейки); (б) каждый квадрант имеет максимальную вместимость; когда максимальная вместимость достигнута, ячейка разделяется; (в) дерево каталога следует пространственному разбиению дерева квадрантов.

[75] В контексте описания «элемент дерева квадрантов» представляет собой элемент иерархической структуры данных. Элементами дерева квадрантов являются узлы дерева квадранта и листья дерева квадранта разного уровня.

[76] В контексте описания термин «лист дерева квадрантов» обозначает элемент дерева квадрантов, хранящий информацию об объектах, не имеющих «потомков». Ключ листа дерева квадрантов состоит из двух компонент (для координат x и у).

[77] В контексте описания термин «узел дерева квадрантов» обозначает элемент дерева квадрантов, хранящий информацию об объектах, имеющих четыре потомка (по одному на каждый квадрант). Ключ узла состоит из двух компонент (для координат x и у). Потомками узла дерева квадрантов могут быть узлы дерева квадрантов следующего уровня, либо листья дерева квадрантов следующего уровня, либо узлы дерева квадрантов следующего уровня и листья дерева квадрантов следующего уровня.

[78] В контексте описания термин «бинарное дерево» обозначает иерархическую структуру данных, включающую в себя множество элементов бинарного дерева (узлов бинарного дерева и листьев бинарного дерева) разного уровня. Бинарное дерево создается и поддерживается преимущественно для построения и поддерживания линейных баз данных. Оно используется для рекурсивного разделения линейного пространства на два региона (интервала). Бинарное дерево может хранить информацию о точечных и линейных объектах. Бинарное дерево может иметь различные воплощения. При этом любое из этих воплощений может иметь следующие общие свойства: (а) бинарное дерево разбивает линию на интервалы (адаптирующиеся ячейки); (б) каждый интервал (адаптирующаяся ячейка) имеет максимальную вместимость; когда максимальная вместимость достигнута, ячейка разделяется; (в) бинарное дерево каталога следует линейному разбиению бинарного дерева.

[79] В контексте описания «элемент бинарного дерева» представляет собой элемент иерархической структуры данных. Элементами бинарного дерева являются узлы бинарного дерева и листья бинарного дерева разного уровня.

[80] В контексте описания термин «лист бинарного дерева» обозначает элемент бинарного дерева, хранящий информацию об объектах, не имеющих «потомков». Ключ листа бинарного дерева состоит из одной компоненты (для координат оси х).

[81] В контексте описания термин «узел бинарного дерева» обозначает элемент бинарного дерева, хранящий информацию об объектах, имеющих два потомка (по одному на каждый интервал). Ключ узла состоит из одной компоненты (для координаты х). Потомками узла бинарного дерева могут быть узлы бинарного дерева следующего уровня, либо листья бинарного дерева следующего уровня, либо узлы бинарного дерева следующего уровня и листья бинарного дерева следующего уровня.

[82] В контексте описания термин «объект» обозначает пространственный объект, имеющий координаты. Пространственный объект может быть точечным объектом, линейным объектом, плоскостным объектом, трехмерным объектом, многомерным объектом. Информация об объекте, помимо координат, может включать в себя информацию о форме и размерах объекта. Информация об объекте может включать в себя иные данные, помимо вышеперечисленных, например цвет объекта. Различные данные об объекте могут храниться в одной базе данных либо в нескольких базах данных, совместно или порознь. Например, информация о координатах объекта и его размерах может храниться совместно и быть ассоциированной с