ОБЛАСТЬ ТЕХНИКИ, К КОТОРОЙ ОТНОСИТСЯ ИЗОБРЕТЕНИЕ
[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] В контексте описания термин «объект» обозначает пространственный объект, имеющий координаты. Пространственный объект может быть точечным объектом, линейным объектом, плоскостным объектом, трехмерным объектом, многомерным объектом. Информация об объекте, помимо координат, может включать в себя информацию о форме и размерах объекта. Информация об объекте может включать в себя иные данные, помимо вышеперечисленных, например цвет объекта. Различные данные об объекте могут храниться в одной базе данных либо в нескольких базах данных, совместно или порознь. Например, информация о координатах объекта и его размерах может храниться совместно и быть ассоциированной с маркером объекта, в то время как вся иная информация может храниться отдельно.
[83] В контексте описания термин «информация» включает в себя информацию любого характера или типа, которая может быть записана в базе данных. Таким образом, информация охватывает, среди прочего, аудиовизуальную информацию (изображения, фильмы, звукозаписи, презентации и т. д. ), данные (данные местоположения, числовые данные и т.д.), текстовую информацию (высказывания, комментарии, вопросы, сообщения и т. д.), документы, электронные таблицы и т. д.
[84] В контексте описания термин «компонент» охватывает программное обеспечение (соответствующее конкретному оборудованию), которое является одновременно необходимым и достаточным для выполнения конкретной указанной функции (функций).
[85] В настоящем описании выражение «носитель информации, предназначенный для использования компьютером» охватывает носители любого характера и типа, в том числе оперативные запоминающие устройства, постоянные запоминающие устройства, диски (компакт-диски, DVD-диски, гибкие диски, жесткие диски и т. д. ), USB-ключи, твердотельные накопители, ленточные накопители и т. д.
[86] В настоящем описании слова «первый», «второй», «третий» и т. д. используются только в качестве описательных элементов для целей разделения существительных, отличающихся друг от друга, а не с целью определения какого-либо конкретного соотношения между указанными существительными. Таким образом, например, следует понимать, что термины «первый сервер» и «третий сервер» не означают введения конкретной последовательности, типа, хронологии, иерархии или ранжирования (например) конкретного сервера или нескольких серверов, а их использование (само по себе) не означает, что в какой-либо конкретной ситуации должен обязательно существовать какой-либо «второй сервер». Кроме того, как указано в данном описании относительно других примеров осуществления технологии, ссылка на «первый» элемент и «второй» элемент не означает, что два элемента не могут представлять собой в реальном мире фактически один и тот же элемент. Таким образом, например, в некоторых случаях «первый» сервер и «второй» сервер могут представлять собой один компонент программного обеспечения и (или) оборудования, а в других ситуациях могут быть реализованы на различном программном обеспечении и (или) оборудовании.
[87] Каждый из вариантов осуществления имеет по меньшей мере одну из вышеупомянутых целей и/или один из вышеупомянутых аспектов, но не обязательно все их. Следует иметь в виду, что некоторые аспекты, которые стали результатом попытки достичь вышеупомянутой цели, могут достигать другие цели, специально не упомянутые здесь.
[88] Дополнительные и/или альтернативные особенности, цели, аспекты и преимущества станут очевидны из нижеследующего описания, сопровождающих чертежей и прилагаемой формулы изобретения.
КРАТКОЕ ОПИСАНИЕ ЧЕРТЕЖЕЙ
[89] Для лучшего понимания настоящего решения, а также других его аспектов и особенностей, предлагается обратиться к нижеследующему описанию, которым следует пользоваться совместно с прилагаемыми чертежами, на которых:
[90] Фиг. 1 является схематическим изображением варианта воплощения сетевых компьютерных систем, реализующих настоящее решение
[91] Фиг. 2 является схематическим изображением, показывающим структуру и компоненты бинарного дерева.
[92] Фиг. 3 является схематическим изображением, показывающим структуру и компоненты дерева квадрантов.
[93] Фиг. 4 является схематическим изображением объекта в дереве квадрантов.
[94] Фиг. 5 является блок-диаграммой способа 400, выполняемого на сервере 102, изображенном на Фиг. 1, и выполненного в соответствии с вариантами осуществления, не ограничивающими объем правовой охраны.
[95] Фиг. 6 является альтернативным схематическим изображением объекта в дереве квадрантов.
[96] Фиг. 7 является блок-диаграммой способа 600, являющегося продолжением способа 400, и выполненного в соответствии с вариантами осуществления, не ограничивающими объем правовой охраны.
ОСУЩЕСТВЛЕНИЕ ИЗОБРЕТЕНИЯ
[97] На Фиг. 1 изображена принципиальная схема различных сетевых компьютерных систем 100, находящихся в связи друг с другом с помощью сети 110 передачи данных. Важно иметь в виду, что различные сетевые компьютерные системы 100 представлены как иллюстративный вариант осуществления. Это описание не предназначено для определения объема или установления границ настоящего решения. Некоторые полезные примеры модификаций компьютерных систем 100 также могут быть охвачены нижеследующим описанием. Целью этого является также исключительно помощь в понимании, а не определение объема и границ настоящего решения. Эти модификации не представляют собой исчерпывающий список, и специалистам в данной области техники будет понятно, что возможны и другие модификации. Кроме того, это не должно интерпретироваться так, что там, где это еще не было сделано, т. е. там, где не были изложены примеры модификаций, никакие модификации невозможны, и/или что то, что описано, является единственным способом осуществления этого элемента. Как будет понятно специалисту в данной области техники, это, скорее всего, не так. Кроме того, следует иметь в виду, что компьютерные системы 100 представляют собой в некоторых конкретных проявлениях достаточно простой вариант осуществления настоящего решения, и в подобных случаях представлен здесь с целью облегчения понимания. Как будет понятно специалисту в данной области техники, многие варианты осуществления будут обладать гораздо большей сложностью.
[98] Система 100 включает в себя сервер 102. Сервер 102 может представлять собой обычный компьютерный сервер. В примере варианта осуществления сервер 102 может представлять собой сервер Dell™ PowerEdge™, на котором используется операционная система Microsoft™ Windows Server™. Излишне говорить, что сервер 102 может представлять собой любое другое подходящее аппаратное и/или прикладное программное, и/или системное программное обеспечение или их комбинацию. В представленном варианте осуществления сервер 102 является одиночным сервером. В других вариантах осуществления функциональность сервера 102 может быть разделена, и может выполняться с помощью нескольких серверов.
[99] В некоторых вариантах осуществления сервер 102 находится под контролем и/или управлением поставщика сервиса карт, такого, например, как провайдер сервиса карт Yandex™. Таким образом, сервер 102 может быть выполнен с возможностью выполнять один или несколько поисков в ответ на поисковый запрос по сервису карт, введенный пользователем 120 в браузер 126 клиентского устройства 122, соединенного с сервером 102 по сети 110 передачи данных. Сервер 102 также выполнен с возможностью передавать клиентскому устройству 122 результат поиска, который будет отображаться пользователю 120 клиентского устройства 122 на дисплее 128 через интерфейс браузера 126. Эти функции хорошо известны в данной области техники и, поэтому, не будут здесь описаны.
[100] Сервер 102 включает в себя носитель информации 104, который может использоваться сервером. В принципе, данный носитель информации может быть носителем абсолютно любого типа и характера, включая ОЗУ, ПЗУ, диски (компакт диски, DVD-диски, дискеты, жесткие диски и т. д. ), USB флеш-накопители, твердотельные накопители, накопители на магнитной ленте и т. д, а также их комбинации.
[101] Варианты осуществления сервера 102 хорошо известны в данной области техники. Таким образом, достаточно отметить, что каждый сервер 102 содержит, среди прочего, интерфейс сетевой связи (например, модем, сетевую карту и тому подобное) для двусторонней связи по сети 110 передачи данных; и процессор, соединенный с интерфейсом сетевой связи, который выполнен с возможностью выполнять различные процедуры, включая те, что описаны ниже. С этой целью процессор может сохранять или иметь доступ к машиночитаемым инструкциям (кодам), выполнение которых инициирует процессор выполнять различные описанные здесь процедуры.
[102] Носитель информации 104 сервера 102 предназначен для хранения данных, в том числе машиночитаемых инструкций (кодов) и баз данных.
[103] В частности, носитель информации 104 сервера 102 осуществляет хранение базы данных 106, одним из основных элементов которой является n-дерево 108, являющееся иерархической структурой данных, n-дерево 108 включает в себя множество элементов n-дерева (узлов n-дерева и листьев n-дерева) разного уровня, n-дерево создается и поддерживается преимущественно для построения и поддерживания пространственных баз данных, где пространство может быть двумерным, трехмерным, четырехмерным, пятимерным и т. д. n-дерево используется для рекурсивного разделения пространства на предопределенное число регионов. В зависимости от типа n-дерева, оно может хранить информацию о точечных, линейных, площадных объектах, объемных, многомерных объектах, n-дерево может иметь различные воплощения. Например, оно может быть воплощено как бинарное дерево 199, изображенное на Фиг. 2, или как дерево квадрантов 198, изображенное на Фиг. 3, или как дерево октантов (рисунок отсутствует), и т. д. При этом любое из этих воплощений может иметь следующие общие свойства: (а) n-дерево разбивает пространство на регионы (адаптирующиеся ячейки); (б) каждый регион (адаптирующаяся ячейка) имеет максимальную вместимость; когда максимальная вместимость достигнута, ячейка разделяется; (в) n-дерево следует пространственному разбиению n-дерева. Подробнее n-дерево будет описано ниже на примере двух его воплощений: на примере бинарного дерева 199, и дерева квадрантов 198.
[104] Носитель информации 104 сервера 102 также осуществляет хранение машиночитаемых инструкций (кодов), обеспечивающих управление базами данных, их обновление, пополнение, модификации. В частности, машиночитаемые инструкции, сохраненные на носителе информации 104, позволяют серверу получать (обновлять) данные об объектах с электронного устройства 112 по сети 110 передачи данных, размещать указанные объекты в n-дереве 108, менять положение и/или характеристики указанных объектов в n-дереве 108, удалять указанные объекты из n-дерева 108.
[105] Сервер 102 соединен с сетью 110 передачи данных через линию связи (не пронумерована). В некоторых вариантах осуществления сеть 110 передачи данных связи может представлять собой Интернет. В других вариантах осуществления, сеть 110 передачи данных может быть реализована иначе - в виде глобальной сети передачи данных, локальной сети передачи данных, частной сети передачи данных и т. п. [106] Реализация линии связи не ограничена, и будет зависеть от того, какие устройства присоединены к сети 110 передачи данных. В качестве примера, но не ограничения, подключение сервера 102 к сети 110 передачи связи может быть осуществлено по проводной связи (соединение на основе сети Ethernet). В то же время, другие устройства могут быть подключены иными способами. Так, в случаях, в которых подключенное устройство представляет собой беспроводное устройство связи (например, клиентское устройство 122, реализованное как смартфон), подключение представляет собой беспроводную сеть связи (например, среди прочего, линия связи сети 3G, линия связи сети 4G, беспроводной интернет Wireless Fidelity или коротко WiFi®, Bluetooth® и т. п. ). В тех примерах, где устройство настольный компьютер (как, например, электронное устройство 112), линия связи может быть как беспроводной (беспроводной интернет Wireless Fidelity или коротко WiFi®, Bluetooth® и т. п) так и проводной (соединение на основе сети Ethernet).
[107] Важно иметь в виду, что различные воплощения сервера 102, электронного устройства 112, клиентского устройства 122, подсоединений к сети 110 передачи данных даны исключительно в иллюстрационных целях. Таким образом, специалисты в данной области техники смогут понять подробности других конкретных вариантов осуществления воплощения сервера 102, электронного устройства 112, клиентского устройства 122, линий связи для подсоединения к сети 110 передачи данных. [108] Через сеть 110 передачи данных, сервер 102 соединен с электронным устройством 112. Электронное устройство 112 обычно связано с публикатором 111. Электронное устройство может иметь дисплей 118. Публикатором 111 является лицо, размещающие данные об объектах, имеющих пространственные координаты, для дальнейшего предоставления доступа к ним пользователю 120. В качестве нескольких неограничивающих примеров публикаторов 111, из множества возможных примеров, можно назвать: (а) собственник автозаправочной станции, размещающий координаты и часы работы автозаправочной станции на сервисе двумерных карт (реализованном на сервере 102 с использование дерева квадрантов), например на двумерных Яндекс. Картах; (б) разработчик графики компьютерных игр, загружающий трехмерную графику в трехмерное виртуальное пространство, проиндексированное в n-дереве 108, являющееся деревом октантов, и сохраненное на носителе информации 104 на сервере 102.
[109] Следует отметить, что тот факт, что электронное устройство 112 связано с публикатором 111, не подразумевает какого-либо конкретного режима работы, равно как и необходимости входа в систему, быть зарегистрированным, или чего-либо подобного.
[110] Варианты электронного устройства 112 конкретно не ограничены, но в качестве примера электронного устройства 112 могут использоваться персональные компьютеры (настольные компьютеры, ноутбуки, нетбуки и т. п. ), устройства беспроводной связи (мобильные телефоны, смартфоны, планшеты и т. п. ), а также сетевое оборудование (маршрутизаторы, коммутаторы или шлюзы). На Фиг. 1 электронное устройство 112 реализовано в виде персонального компьютера Dell Precision ΤΙ 700 МТ CA033PT170011RUWS с процессором Intel® Хеоп™ , частота процессора: 3300 МГц, с видеокартой nVIDIA Quadro K2000, с установленной и действующей операционной системой Windows 7 Pro 64-bit.
[Ill] Электронное устройство 112 включает в себя носитель информации 114, который может использоваться компьютером. В принципе, данный носитель информации может быть носителем абсолютно любого типа и характера, включая ОЗУ, ПЗУ, диски (компакт диски, DVD-диски, дискеты, жесткие диски и т. д. ), USB флеш-накопители, твердотельные накопители, накопители на магнитной ленте и т.д, а также их комбинации. В электронном устройстве 112, изображенном на Фиг. 1, носитель информации реализован как жесткий диск с 500 Gb памяти. Носитель информации 114 может сохранять файлы пользователя и программные инструкции (коды). В частности, носитель информации может хранить программное обеспечение для использования в качестве приложения 116 для загрузки файлов. В общем случае, целью приложения 116 для загрузки файлов является предоставление возможности публикатору 111 загружать файлы через сеть 110 передачи данных на сервер 102.
[112] Реализация приложения 116 для загрузки файлов никак конкретно не ограничена. В качестве неограничивающих примеров, такими приложениями могут быть приложения, позволяющие передачу данных по протоколам HTTP или FTP. В электронном устройстве 112, изображенном на Фиг. 1, программа 116 для загрузки файлов реализована как предустановленный FTP-клиент BlazeFTP с поддержкой мультисессии и кэширования. FTP (File Transfer Protocol) - это протокол, предназначенный для передачи файлов в сетях ПО передачи данных. FTP позволяет подключаться к серверам FTP, например к серверу 102, просматривать содержимое каталогов и загружать файлы с сервера или на сервер. FTP-клиент это приложение для упрощения доступа к FTP серверу. В зависимости от назначения может, предоставлять пользователю простой доступ к удаленному FTP-серверу в режиме текстовой консоли либо отображать файлы на удаленном сервере как если бы они являлись частью файловой системы компьютера публикатора 111.
[113] В других вариантах осуществления, не ограничивающих объем правовой охраны, приложение 116 для загрузки файлов может представлять собой веб браузер, например Яндекс браузер. Важно иметь в виду, что любое другое коммерчески доступное или собственное приложение может быть использовано для реализации вариантов осуществления настоящего решения.
[114] Электронное устройство 112 соединено с сетью 110 передачи данных через линию связи (не пронумерована).
[115] Через сеть ПО передачи данных, сервер 102 соединен также с клиентским устройством 122. Клиентское устройство 122 обычно связано с пользователем 120 сервиса. Пользователем сервиса 120 является лицо, заинтересованное в использовании объектов (в том числе виртуальных), имеющих пространственные координаты, размещенных на сервере 102 публикатором 111с помощью электронного устройства 112 путем загрузки таких объектов с помощью приложения 116 для загрузки файлов по сети 110 передачи данных. В качестве нескольких неограничивающих примеров пользователей 120 сервиса, из множества возможных примеров, можно назвать: (а) водитель автомобиля, осуществляющий с помощью клиентского устройства 122 поиск ближайшей автозаправочной станции на сервисе двумерных карт, например на двумерных Яндекс. Картах (реализованном на сервере 102 с использование дерева квадрантов); (б) геймер, играющий онлайн в компьютерную игру, содержащую объекты, выполненные с использованием технологии построения трехмерной графики, где объекты трехмерной графики хранятся в n-дереве 108, являющимся деревом октантов и сохраненным на носителе информации 104 на сервере 102.
[116] Следует отметить, что тот факт, что клиентское устройство 122 связано с пользователем 120 сервиса, не подразумевает какого-либо конкретного режима работы, равно как и необходимости входа в систему, быть зарегистрированным, или чего-либо подобного.
[117] Варианты клиентского устройства 122 конкретно не ограничены, но в качестве примера клиентского устройства 122 могут использоваться персональные компьютеры (настольные компьютеры, ноутбуки, нетбуки и т. п. ), устройства беспроводной связи (мобильные телефоны, смартфоны, планшеты и т. п. ), а также сетевое оборудование (маршрутизаторы, коммутаторы или шлюзы). На Фиг. 1 клиентское устройство 122 реализовано в виде смартфона Apple iPhone 5S с установленной на нем и действующей операционной системой iOS 7, с Bluetooth, Wi-Fi, 3G, LTE, системами позиционирования GPS и ГЛОНАСС.
[118] Клиентское устройство 122 включает в себя также носитель информации 124. В принципе, данный носитель информации может быть носителем абсолютно любого типа и характера, включая ОЗУ, ПЗУ, диски (компакт диски, DVD-диски, дискеты, жесткие диски и т. д. ), USB флеш-накопители, твердотельные накопители, накопители на магнитной ленте и т. д, а также их комбинации. В клиентском устройстве 122, изображенном на Фиг. 1, носитель информации 124 реализован как флеш накопитель объемом 16 Гб.
[119] Носитель информации 124 может сохранять файлы пользователя и программные инструкции (коды). В частности, носитель информации 124 может хранить программное обеспечение, реализующее функции браузера 126. В общем случае, целью браузера 126 является предоставление возможности пользователю 120 сервиса загружать на клиентское устройство 122 файлы через сеть 110 передачи данных с сервера 102, и показывать загруженные изображения (видео) на дисплее 128. Реализация браузера 126 никак конкретно не ограничена. В качестве неограничивающих примеров, такими браузерами могут быть Яндекс браузер, Google Chrome, Internet Explorer, различные мобильные поисковые приложения, и так далее. В клиентском устройстве 122 браузер 126 реализован как мобильный браузер Яндекс. Важно иметь в виду, что любое другое коммерчески доступное или собственное приложение может быть использовано для реализации вариантов осуществления настоящего решения.
[120] Клиентское устройство 122 включает в себя также дисплей 128, являющийся сенсорным экраном 4", с разрешением 640x1136, позволяющий представлять видеоинформацию пользователю 120 сервиса, а также который может использоваться как устройство ввода информации. Таким образом, пользователь 120 сервиса имеет возможность видеть на дисплее 128 в интерфейса браузера 126 клиентского устройства 122 различные объекты, например местоположение ближайшей автозаправочной станции на сервисе двумерных карт (реализованном на сервере 102 с использование дерева квадрантов 198), например на двумерных Яндекс. Картах.
[121] Фиг. 2 является схематическим изображением, показывающим структуру и компоненты бинарного дерева 199.
[122] Бинарное дерево 199 является разновидностью n-дерева 108. Бинарное дерево 199 является иерархической структурой данных. Бинарное дерево 199 включает в себя множество элементов 202 бинарного дерева 199, а именно: узлов 204 бинарного дерева 199 и листьев 206 бинарного дерева 199 разного уровня. В примере, изображенном на Фиг. 2, бинарное дерево 199 включает в себя элементы 202 бинарного дерева четырех уровней, а именно: (а) один элемент 202 первого уровня 299, являющийся в данном случае узлом 204 бинарного дерева 199, (б) два элемента 202 второго уровня 298, являющихся в данном случае узлами 204 бинарного дерева 199, (в) четыре элемента 202 третьего уровня 297, являющихся в данном случае тремя узлами 204 бинарного дерева 199 и одним листом 206 бинарного дерева 199, (г) шесть элементов 202 четвертого уровня 296, являющихся в данном случае шестью листьями 206 бинарного дерева 199.
[123] Первый уровень 299 является самым высоким уровнем, а элемент 202 первого уровня 299 является «корневым элементом».
[124] Четвертый уровень 296, изображенный на Фиг. 2, является самым низким уровнем в данном примере. В других примерах самый низкий уровень может быть иным (например, пятым, шестым, седьмым и так далее).
[125] Уровень «материнского» элемента выше уровня «дочернего» элемента. Например, уровень материнского элемента 204 первого уровня 299 выше уровня дочерних элементов 204 второго уровня 298; уровень обоих материнских элементов 204 второго уровня 298 выше уровня соответствующих им двух пар дочерних элементов 204/204 и 206/204 третьего уровня 297; и так далее.
[126] Бинарное дерево 199 создается и поддерживается преимущественно для построения и поддерживания пространственных баз данных. Оно используется для рекурсивного разделения пространства на два региона.
[127] Неограничивающим примером использования бинарного дерева может служить база данных IP-адресов, где каждый IP-адрес может быть отмечен как точка на прямой, причем все IP-адреса могут быть расположены на данной прямой в определенной последовательности, например по возрастанию номера. Соответственно, отметив некую точку на прямой, включающей IP-адреса, эта прямая может быть рекурсивно разбита на две других прямых, включающие IP-адреса, расположенные до и после данной точки. Некоторые полученные в результате разбиения прямой две новые прямые могут быть разбиты, в свою очередь, на следующие две прямые (два луча, отрезка), и так далее. В результате прямые, разбитые на две прямые следующего уровня, являются узлами 204 бинарного дерева 199, а неразбитые прямые являются листами 206 бинарного дерева 199.
[128] Другим неограничивающим примером использования бинарного дерева 199 может служить база данных расстояний между населенными пунктами, где расстояния между населенными пунктами расположены на прямой и имеют определенные линейные координаты. Таким образом, база данных, построенная с помощью бинарного дерева 199,
может отображать данные о расстояниях между объектами, расположенными в двухмерном пространстве.
[129] Еще одним неограничивающим примером использования бинарного дерева 199 может служить база данных расстояний между астрономическими объектами, где расстояния между астрономическими объектами расположены на прямой и имеют определенные линейные координаты. Таким образом, база данных, построенная с помощью бинарного дерева 199, может отображать данные о расстояниях между объектами, расположенными в трехмерном пространстве.
[130] Еще одним неограничивающим примером использования бинарного дерева 199 может служить база данных диапазонов частот для радиовещания, выделенных различным пользователям государственными регуляторами на определенной территории. Таким образом, база данных, построенная с помощью бинарного дерева 199, может использоваться не только для точечных объектов (например, IP-адресов) или условно точечных объектов (например, астрономических объектов), но и для иных объектов, например для линейных объектов, каковым могут считаться диапазоны частот.
[131] Бинарное дерево 199 может иметь следующие свойства: (а) бинарное дерево 199 разбивает пространство на прямые (отрезки); (б) каждая прямая (отрезок) имеет максимальную вместимость; когда максимальная вместимость достигнута, отрезок разделяется; (в) бинарное дерево 199 следует пространственному разбиению бинарного дерева 199, то есть рекурсивному разбиению на два региона.
[132] Фиг. 3 является схематическим изображением, показывающим структуру и компоненты дерева квадрантов 198.
[133] Дерево квадрантов 198 является разновидностью n-дерева 108. Дерево квадрантов 198 является иерархической структурой данных. Дерево квадрантов 198 включает в себя множество элементов 202 дерева квадрантов 198, а именно: узлов 204 дерева квадрантов 198 и листьев 206 дерева квадрантов 198 разного уровня. В примере, изображенном на Фиг. 3, дерево квадрантов 198 включает в себя элементы 202 дерева квадрантов 198 пяти уровней, а именно: (а) один элемент 202 первого уровня 299, являющийся в данном случае узлом 204 дерева квадрантов 198, (б) четыре элемента 202 второго уровня 298, являющихся в данном случае тремя узлами 204 дерева квадрантов 198 и одним листом 206 дерева квадрантов 198, (в) двенадцать элементов 202 третьего уровня 297, являющихся в данном случае четырьмя узлами 204 дерева квадрантов 198 и восемью листами 206 дерева квадрантов 198, (г) шестнадцать элементов 202 четвертого уровня 296, являющихся в данном случае тремя узлами 204 дерева квадрантов 198 и тринадцатью листами 206 дерева квадрантов 198, (д) двенадцать элементов 202 пятого уровня 295, являющихся в данном случае двенадцатью листьями 206 дерева квадрантов 198. Для наглядности, узлы 204 дерева квадрантов 198 обозначены на Фиг. 3 как не закрашенные квадраты, а листья 206 дерева квадрантов 198 обозначены как закрашенные квадраты.
[134] Первый уровень 299 является самым высоким уровнем, а элемент 202 первого уровня 299 является «корневым элементом».
[135] Пятый уровень 295, изображенный на Фиг. 3, является самым низким уровнем в данном примере. В других примерах самый низкий уровень может быть иным (например, шестым, седьмым, и так далее).
[136] Уровень «материнского» элемента выше уровня «дочернего» элемента.
[137] Дерево квадрантов 198 создается и поддерживается преимущественно для построения и поддерживания пространственных баз данных. Оно используется для рекурсивного разделения пространства на четыре региона.
[138] Неограничивающим примером использования дерева квадрантов 198 может служить сервис карт, где каждый объект может быть расположен в определенном месте на двумерной карте и быть отмечен как точечный, площадной либо иной объект. Двумерная карта, будучи элементом 299 первого уровня, может быть рекурсивно разбита на четыре элемента 298 второго уровня. Каждый из четырех элементов 298 второго уровня может включать в себя объекты, расположенные в соответствующем одном из четырех квадрантов карты. Некоторые элементы 298, полученные в результате разбиения элемента 299 первого уровня, могут две быть разбиты, в свою очередь, на следующие четыре элемента 202, и так далее. В результате элементы (квадранты), разбитые на четыре элемента (квадранта) следующего уровня, являются узлами 204 дерева квадрантов 198, а неразбитые элементы (квадранты) являются листами 206 дерева квадрантов 198.
[139] Другим неограничивающим примером использования бинарного дерева может служить база данных двумерных объектов, используемых в компьютерных играх.
[140] Дерево квадрантов 198 может иметь следующие свойства: (а) дерево квадрантов 198 разбивает пространство на квадранты; (б) каждый квадрант имеет максимальную вместимость; когда максимальная вместимость достигнута, квадрант разделяется; (в) дерево квадрантов 198 следует пространственному разбиению дерева квадрантов 198, то есть рекурсивному разбиению на четыре региона.
[141] Фиг. 4 является схематическим изображением объекта в дереве квадрантов 198. Для наглядности, и в качестве неограничивающего примера, предположим, что дерево квадрантов 198 представляет собой дерево квадрантов для обслуживания сервиса географических карт.
[142] На Фиг. 4 изображены четыре листа 206 дерева квадрантов 198, образованные путем рекурсивного разделения узла 204 дерева квадрантов 198. Все четыре листа 206 дерева квадрантов 198, образованные путем рекурсивного разделения узла 204 дерева квадрантов 198, имеют границы 302 элементов n-дерева (в данном случае - границы листов 206 дерева квадрантов 198).
[143] На Фиг. 4 также изображен пространственный объект 304. Для наглядности, и в качестве неограничивающего примера, предположим, что данный объект представляет собой населенный пункт на карте, а граница 308 данного объекта 304 представляют собой границы населенного пункта. Данный объект сохранен в элементе 202 дерева квадрантов 198 как тег, содержащий в себе координаты, размер и границы населенного пункта. Тег соединен с внешней базой данных, где сохранено наименование населенного пункта.
[144] Данный объект 304, как видно на Фиг. 4, расположен одновременно на территории, отображаемой в двух квадрантах, а именно: в квадранте с углами ABCD, и в квадранте с углами CGHD. Таким образом, граница 308 объекта 304 пересекает границу DC квадрантов ABCD и CGHD.
[145] В соответствии с некоторыми воплощениями настоящего решения, объект 304 может быть логически размещен только в одном элементе 202 дерева квадрантов 198. Примем за данное, что элементы дерева квадрантов более высокого уровня, чем изображенный на Фиг. 4 узел дерева квадрантов, по определенным причинам не подходят для размещения в них объекта 304 (например, они полностью заполнены и не могут вмещать новые объекты). В этом случае возникает необходимость определить в данном уровне наиболее подходящий элемент дерева квадрантов для размещения в нем объекта 304. В одном из вариантов определение наиболее подходящего элемента дерева квадрантов 198 для размещения объекта 304 осуществляется путем определения центра 306 объекта 304. Как мы видим на Фиг. 4, центр 306 объекта 304 территориально расположен в границах листа 206 с вершинами в точках ABCD. Исходя из этого, наиболее подходящим квадрантом для размещения объекта 304 будет квадрант, в пределах которого находится центр 306 объекта 304, то есть квадрант ABCD. Объект 304 будет размещен в квадранте ABCD, и не будет размещен в квадранте CGHD.
[146] В отличие от некоторых известных решений, предусматривающих деление объектов, пересекаемых границами элементов n-дерева (включая границы элементов дерева квадрантов), в настоящем решении не происходит деления объекта, а весь объект полностью помещается в один квадрант.
[147] В отличие от некоторых существующих решений, предусматривающих одновременное увеличение в разных направлениях элементов n-дерева (включая элементов дерева квадрантов) с целью обеспечить включение нераздробленного объекта, в настоящем решении не происходит увеличения в разных направлениях элементов n-дерева (включая элементов дерева квадрантов).
[148] Согласно вариантам осуществления для включения нераздробленного объекта в элемент n-дерева (в данном примере - в элемент дерева квадрантов), осуществляется условное увеличение размера наиболее подходящего элемента n-дерева (в данном примере - элемента дерева квадрантов) путем добавления к нему зоны присутствия объекта CEFD, при этом граница зоны присутствия объекта FE удалена от пересекаемой границы DC наиболее подходящего элемента ABCD на максимальную величину 310 выступания (выступа) объекта 304 за границу DC наиболее подходящего элемента ABCD.
[149] Говоря в общем, практическое значение прибавления зоны присутствия объекта 309 заключается в том, что зона присутствия объекта 309 является индикатором того, что поиск должен быть осуществлен не только в квадранте, соответствующем точке, выбранной пользователем 120, но и в прилегающем соседнем квадранте.
[150] Согласно настоящему описанию увеличение размера наиболее подходящего элемента n-дерева может являться условным, т. е. увеличение не осуществляется непосредственным увеличением элементом, а добавлением элементу определенного маркера, указывающего на то, что следует рассмотреть соседние элементы, элементы более высокого или низкого уровней. Соседние элементы могут содержать информацию об искомом объекте.
[151] В качестве наглядного неограничивающего примера, представим, что изображенный на Фиг. 4 материнский узел 204 представляет фрагмент географической карты. Материнский узел 204 является полностью заполненным и не может вместить объект 304. Материнский узел 204 рекурсивно разбит на четыре листа 206, каждый из листов 206 представляющих менее крупные и более детальные фрагменты географической карты. Карта изображена на дисплее 128 клиентского устройства 122 в пользовательском интерфейсе. Пользователь 120 сервиса осуществляет клик компьютерной мышью в точке 312. Несмотря на то, что точка 312 расположена в элементе DCGH и вне элемента ABCD, точка 312 расположена в зоне присутствия объекта 309, являющейся продолжением элемента ABCD. Таким образом, в ответ на запрос некоего объекта пользователем 120, сервер 102 предоставит пользователю 120 не только объекты, хранящиеся в элементе DCGH, но и объекты, хранящиеся в элементе ABCD.
[152] Точно такой же результат был бы получен, если бы пользователь 120 осуществил бы клик компьютерной мышью в точке 314, поскольку точка 314 хотя и находится вне пределов объекта 304, но она находится в пределах зоны присутствия объекта 309. Клик в пределах зоны 309 (зона DCEF) указывает на то, что поиск должен быть осуществлен не только в элементе DCGH, но и в элементе ABCD, к которому относится зона присутствия объекта DCEF.
[153] На Фиг. 5 представлен способ 400, который выполняется в соответствии с неограничивающими вариантами осуществления настоящего решения. В вариантах осуществления способ 400 может выполняться на сервере 102, изображенном на Фиг. 1. Для этого сервер 102 включает в себя носитель информации 104, хранящий машиночитаемые инструкции (коды), при выполнении которых сервер 102 выполняет этапы способа 400.
[154] Этап 402 - получение из памяти компьютера объекта 304, подходящего для размещения в дереве квадрантов 198.
[155] Способ 400 начинается на этапе 402, на котором сервер 102 получает из памяти компьютера объект 304 для размещения в дереве квадрантов 198. Компьютером может быть сервер 102 либо группа серверов, выполняющих функции сервера 102.
[156] В качестве неограничивающих примеров, объектом 303 для размещения в дереве квадрантов может быть точечный объект, площадной объект, и прочие объекты.
[157] Предварительно, объект 304 может быть загружен публикатором 111 с помощью приложения 116 для загрузки файлов, с использованием электронного устройства 112, по сети 110 передачи данных в память компьютера, где память компьютера может быть носителем информации 104 сервера 102.
[158] Затем способ 400 переходит к выполнению этапа 404.
[159] Этап 404 - определение наиболее подходящего элемента 202 дерева квадрантов 198 для размещения объекта 304.
[160] Далее, на этапе 404, сервер 102 определяет наиболее подходящий элемент 202 дерева квадрантов 198 для размещения объекта 304.
[161] Элемент 202 дерева квадрантов 198 представляет собой элемент иерархической структуры данных. Элементами 202 дерева квадрантов 198 являются узлы 204 дерева квадранта 198 и листья 206 дерева квадранта 198 разного уровня. Количество уровней может быть различным. Например, количество уровней дерева квадрантов 198, изображенного на Фиг. 3, равно пяти.
[162] Лист 206 дерева квадрантов 198 является элементом 202 дерева квадрантов 198, хранящим информацию об объектах, не имеющим «потомков». Ключ листа дерева квадрантов состоит из двух компонент (для координат x и у).
[163] Узел 204 дерева квадрантов 198 является элементом 202 дерева квадрантов 198, хранящим информацию об объектах, имеющим четыре потомка. Ключ узла состоит из двух компонент (для координат x и у). Потомками узла 204 дерева квадрантов 198 могут быть узлы 204 дерева квадрантов 198 следующего уровня, либо листья 206 дерева квадрантов 198 следующего уровня, либо узлы 204 дерева квадрантов 198 следующего уровня и листья 206 дерева квадрантов 198 следующего уровня.
[164] В соответствии с некоторыми вариантами, объект 304 может быть размещен только в одном элементе 202 дерева квадрантов 198. Обычно наиболее подходящим элементом 202 дерева квадрантов 198 для размещения объекта 304 является такой элемент 202, который является элементом самого низкого уровня, позволяющего размещение объекта 304 в нем без дробления. Так, если обратиться к Фиг. 4, наиболее подходящим элементом 202 для размещения объекта 304 мог бы быть узел 204 дерева квадрантов 198. [165] Однако в некоторых вариантах, максимальное допустимое количество объектов 304, расположенных в одном элементе 202 дерева квадрантов 199, может быть предопределено. В таком случае способ может дополнительно включать в себя определение количества объектов 304, в данный момент уже размещенных в элементе 202 дерева квадрантов 198. Таким образом, элемент 202, который является элементом самого низкого уровня, позволяющего размещение объекта 304 в нем без дробления, может оказаться неподходящим для размещения объекта в случае, когда максимальное допустимое количество объектов 304, расположенных в этом элементе 202 высокого уровня, уже достигнуто.
[166] В таком случае, способ может дополнительно включать создание четырех квадрантов следующего, более низкого уровня, как это изображено на Фиг. 4. Так, на Фиг. 4 изображено рекурсивное разбиение узла (квадранта) 204 на четыре листа (квадранта) 206.
[167] Далее, продолжается процедура определения наиболее подходящего элемента 202. При этом процедура определения наиболее подходящего элемента 202 в различных вариантах осуществления может происходить как (i) с перераспределением объектов 304 между элементами 202 разных уровней, так и (и) без такого перераспределения.
[168] Когда процедура определения наиболее подходящего элемента 202 происходит с перераспределением объектов 304 между элементами 202 разных уровней, такое перераспределение может происходить, в том числе, между материнским узлом 204 дерева квадрантов и четырьмя дочерними элементами 202 (в данном случае - четырьмя листьями 206) дерева квадрантов.
[169] В некоторых вариантах осуществления, перераспределение может осуществляться с учетом размеров объектов.
[170] В качестве наглядного неограничивающего примера представим, что в материнском узле 204 находился объект меньшего размера, чем вновь размещаемый объект 304, и при этом такой объект меньшего размера находится в пределах территории, ограниченной точками ABCD, показанной на Фиг. 4. Представим далее, что такой ранее размещенный объект меньшего размера способен разместиться в квадранте, ограниченном точками ABCD, без пересечения границ 302 соответствующего дочернего квадранта. Таким образом, перенесение такого объекта меньшего размера в дочерний квадрант ABCD освобождает место для вновь размещаемого объекта 304 в материнским квадранте 204. Такое перераспределение является выгодным с точки экономии ресурсов, поскольку позволяет с минимальными затратами ресурсов разместить оба объекта в наиболее подходящие элементы 202 дерева квадрантов 198, избегая манипуляций с элементами 202.
[171] В качестве отступления следует отметить, что перераспределение объектов может происходить не только при добавлении нового объекта 304, но и при перемещении в пространстве объектов, уже помещенных в элементы 202 дерева квадрантов, что может влечь за собой перемещение объекта из одного элемента 202 в другой элемент 202. Кроме того, перераспределение объектов может происходить в случае ликвидации объектов. Так, например, в случае ликвидации ряда близко расположенных объектов в двумерной компьютерной игре, число объектов может сократиться настолько, что это может повлечь упразднение четырех дочерних листов 206 дерева квадрантов 198, поскольку сумма объектов в одном материнском узле 204 и всех четырех дочерних листах 206, вместе взятых, не превышает максимально допустимого количества объектов 304 материнского узла 204. Таким образом, материнский узел 204 трансформируется в лист 206 (того же уровня, где на котором находился ранее, будучи узлом 204), а все объекты 304 перераспределяются из упраздненных дочерних узлов 206 в материнский квадрант (бывший узел 204, он же нынешний лист 206 того же уровня что и бывший узел 204).
[172] Продолжая описание этапа 404, в некоторых вариантах, перераспределения объектов между элементами 202 не происходит, либо перераспределение объектов между элементами не позволяет разместить все объекты (вновь размещаемый объект и по меньшей мере один перераспределяемой объект) таким образом, чтобы ни один из них не пересекал границ соответствующих элементов 202. В таком случае, наиболее подходящим для размещения элементом 202 может оказаться элемент 202, граница 302 которого все же будет пересечена границей 308 объекта 304. В таких случаях, определение наиболее подходящего элемента 202 дерева квадрантов 198 для размещения объекта 304 осуществляется путем определения центра 306 объекта 304. Центр 306 объекта 304 математически определяется как место, одинаково удаленное от краев (концов) объекта. Размещение объекта 304 в элемент 202 дерева квадрантов 198 по месту нахождения центра 306 объекта 304 фактически приводит к тому, что в качестве наиболее подходящего элемента 202 дерева квадрантов 198 для размещения объекта 304 выбирается такой элемент 202 дерева квадрантов 198, который будет иметь наименьший прирост площади после условного увеличения его размера путем добавления к нему зоны присутствия объекта 309. В других вариантах осуществления, в качестве наиболее подходящего элемента 202 дерева квадрантов 198 для размещения объекта 304 выбирается такой элемент 202 дерева квадрантов 198, который будет иметь прирост площади, после условного увеличения его размера путем добавления к нему зоны присутствия объекта 309, в пределах заранее установленного лимита.
[173] Как видно на Фиг. 4, центр 306 объекта 304 находится в пределах листа 206 дерева квадрантов 198 с вершинами в точках ABCD. Таким образом, наиболее подходящим элементом 202 дерева квадрантов 198 для размещения объекта 304 в данном воплощении является лист 206 дерева квадрантов 198 с вершинами в точках ABCD.
[174] Затем способ 400 переходит к выполнению этапа 406.
[175] Этап 406 - определение, выходят ли границы объекта 304 за границы наиболее подходящего элемента 202 дерева квадрантов 198.
[176] Поскольку квадранты следующего уровня созданы путем рекурсивного разбиения узла 204 дерева квадрантов 198 на четыре части, то может оказаться, что объект 304 не будет полностью помещаться в какой-то один вновь созданный элемент дерева квадрантов. Соответственно, на этапе 406, сервер 102 определяет, выходят ли границы объекта 304 за границы наиболее подходящего элемента 202 дерева квадрантов 198. Определение осуществляется путем сопоставления местоположения, формы и размера объекта 304 с границами элемента 202 дерева квадрантов 198, в пределах которого расположен центр 306 объекта 304.
[177] В случае, когда границы объекта 304 не выходят за границы наиболее подходящего элемента 202 дерева квадрантов 198, способ завершается.
[178] В качестве примера представим, что распределение объекта 304 осуществлялось без процедуры перераспределения объектов между элементами 2020 разных уровней, и что размер и местоположение объекта 304 таковы, что границы объекта 304 выходят за границы наиболее подходящего элемента 202 дерева квадрантов 198 (эта ситуация изображена на Фиг. 4).
[179] В случае, когда границы объекта 304 выходят за границы наиболее подходящего элемента 202 дерева квадрантов 198, способ переходит к этапу 408.
[180] Этап 408 - определение границы 302 наиболее подходящего элемента 202 дерева квадрантов 198, которая будет пересечена границей 308 объекта 304, когда объект 304 расположен в этом наиболее подходящем элементе 202 дерева квадрантов 198.
[181] На этапе 408, сервер 102 определяет, какая именно граница 302 наиболее подходящего элемента 202 дерева квадрантов 198 будет пересечена границей 308 объекта 304, когда объект 304 расположен в этом наиболее подходящем элементе 202 дерева квадрантов 198. Определение осуществляется путем сопоставления местоположения, формы и размера объекта 304 с границами элемента 202 дерева квадрантов 198, в пределах которого расположен центр 306 объекта 304.
[182] В примере, изображенном на Фиг. 4, сервер 102 определит, что после рекурсивного разбиения узла 204 на четыре листа 206, объект 304 находится преимущественно на территории листа 206 дерева квадрантов с вершинами в точках ABCD, но пересекает границу CD между листом 206 дерева квадрантов с вершинами в точках ABCD и листом 206 дерева квадрантов с вершинами в точках CGHD.
[183] Затем способ 400 переходит к выполнению этапа 410.
[184] Этап 410 - условное увеличение размера наиболее подходящего элемента 202 дерева квадрантов 198 путем добавления к нему зоны 309 присутствия объекта 304.
[185] На этапе 410, сервер 102 осуществляет условное увеличение размера наиболее подходящего элемента 202 дерева квадрантов 198 путем добавления к нему зоны 309 присутствия объекта 304. Условное увеличение размера наиболее подходящего элемента 202 дерева квадрантов 198 путем добавления к нему зоны 309 присутствия объекта 304 осуществляется таким образом, что при этом граница зоны присутствия объекта оказывается удалена от указанной границы 302 наиболее подходящего элемента 304 дерева квадрантов 198 на максимальную величину 310 выступания объекта 304 за пределы наиболее подходящего элемента 302 дерева квадрантов 198.
[186] Таким образом, зона 309 присутствия объекта 304 может быть определена как прямоугольник или квадрат, где пересекаемая граница наиболее подходящего элемента 202 дерева квадрантов 198 и граница зоны присутствия объекта являются противолежащими параллельными отрезками в прямоугольнике или квадрате, а боковыми сторонами зоны 309 присутствия объекта 304 являются параллельные отрезки, соединяющие соответствующие крайние точки пересекаемой границы наиболее подходящего элемента 202 дерева квадрантов 198 и границы зоны присутствия объекта.
[187] Так, в примере, изображенном на Фиг. 4, зона 309 присутствия объекта 304 является прямоугольником с вершинами в точках CEFD. Пересекаемая граница определена как отрезок CD, граница зоны присутствия объекта определена как отрезок EF, параллельный отрезку CD, а боковыми сторонами зоны 309 присутствия объекта 304 являются параллельные отрезки СЕ и FD. Граница зоны присутствия объекта EF удалена от пересекаемой границы CD на максимальную величину 310 выступания (выступа) объекта 304 за пределы наиболее подходящего элемента 302 дерева квадрантов 198.
[188] В другом примере, изображенном на Фиг. 6, зона 309 присутствия объекта 304 является прямоугольником с вершинами в точках BIJC. Пересекаемая граница определена как отрезок ВС, граница зоны присутствия объекта определена как отрезок IJ, параллельный отрезку ВС, а боковыми сторонами зоны 309 присутствия объекта 304 являются параллельные отрезки BI и JC. Граница зоны присутствия объекта IJ удалена от пересекаемой границы ВС на максимальную величину 310 выступания объекта 304 за пределы наиболее подходящего элемента 302 дерева квадрантов 198.
[189] Как видно из сравнения Фиг. 4 и Фиг. 6, зона 309 присутствия объекта 304, условно увеличивающая размер элемента 202 дерева квадрантов (в данном случае квадранта с вершинами в точках ABCD), может как минимум частично перекрывать другой элемент 202 того же уровня (как изображено на Фиг. 4), либо зона 309 присутствия объекта 304, условно увеличивающая размер элемента 202 дерева квадрантов (в данном случае квадранта с вершинами в точках ABCD), может как минимум частично выходить за пределы предшествующего элемента 202 (в данном примере - за пределы узла 204, как это изображено на Фиг. 6).
[190] Затем способ 400 завершается.
[191] На Фиг. 7 представлен способ 600, который выполняется в соответствии с неограничивающими вариантами осуществления настоящего решения. В вариантах осуществления способ 600 может выполняться на сервере 102, изображенном на Фиг. 1. Для этого сервер 102 включает в себя носитель информации 104, хранящий машиночитаемые инструкции (коды), при выполнении которых сервер 102 выполняет этапы способа 600. Способ 600 является продолжением способа 400, представленного на блок-схеме в Фиг. 5.
[192] Этап 602 - получение запроса пользователя 120 о предоставлении объекта 304, ассоциированного с элементом 202 дерева квадрантов 198
[193] Способ 600 начинается на этапе 602, на котором сервер 102 получает запрос пользователя 120 о предоставлении объекта 304, ассоциированного с элементом 202 дерева квадрантов 198. Запрос пользователя 120 может осуществляться через пользовательский интерфейс компьютера, например, через пользовательский интерфейс браузера 126 клиентского устройства 122, соединенного с сервером 102 по сети ПО передачи данных.
[194] Запрос может быть осуществлен пользователем 120 путем выбора фрагмента пространства, изображенного на дисплее 128 клиентского устройства 122, во время сессии браузера 126. В качестве наглядного неограничивающего примера, на дисплее 128 может быть изображена двумерная географическая карта, предоставленная сервисом карт Яндекс. Карты. Для выбора фрагмента пространства, пользователь 120 может кликнуть мышью в районе объекта 304, изображенного на карте. Координаты выбранной точки на пользовательском интерфейсе передаются с клиентского устройства 122 по сети 110 передачи данных на сервер 102.
[195] Затем способ 600 переходит к выполнению этапа 604.
[196] Этап 604 - осуществление сервером 102 поиска объекта 304 в дереве квадрантов 198.
[197] На этапе 604 сервер 102 осуществляет поиск объекта 304. Напомним, что в указанном примере искомым объектом 304 является населенный пункт. Данный объект 304 хранится в наиболее подходящем элементе 202 дерева квадрантов 198.
[198] С целью поиска элемента 304, сервер 102 определяет, какому элементу 202 дерева квадрантов 198 соответствует точка, выбранная пользователем 120 в пользовательском интерфейсе компьютера, и выбирает объекты 304, расположенные в данном элементе 202 дерева квадрантов.
[199] Следует иметь в виду, что точке, выбранной пользователем 120, может соответствовать множество элементов 202 дерева квадрантов 198 разных уровней. Например, если нижним уровнем дерева квадрантов в данной точке является элемент четвертого уровня, то выбранной точке могут соответствовать четыре различных квадранта (то есть по одному квадранту первого, второго, третьего и четвертого уровней). Соответственно, сервер 102 выбирает все объекты 304, расположенные во всех указанных элементах 202 дерева квадрантов 198.
[200] С целью поиска элемента 304, сервер 102 также определяет, соответствует ли выбранной пользователем 120 точке в интерфейса компьютера какая-либо зона присутствия объекта 309. Если сервер определяет, что выбранной пользователем 120 точке соответствует зона присутствия объекта 309, то сервер 102 также дополнительно выбирает объекты 304 из того соседнего элемента 202 дерева квадрантов 199, который был увеличен зоной присутствия объекта 309. Другими словами, зона присутствия объекта 309 является индикатором того, что поиск должен быть осуществлен не только в квадрантах, соответствующих выбранной точке, но и в прилегающем соседнем квадранте.
[201] Следует отметить, что выбранной пользователем 120 точке могут соответствовать несколько зон присутствия объектов 309. В таком случае, сервер 102 также дополнительно выбирает объекты 304 из всех соответствующих соседних элементов 202 дерева квадрантов 199.
[202] Затем способ 600 переходит к выполнению этапа 606.
[203] Этап 606 - предоставление пользователю 120 объекта 304, ассоциированного с элементом 202 дерева квадрантов 198.
[204] На этапе 606 сервер 102 предоставляет пользователю 120 объект 304, найденный в дереве квадрантов, как это было показано выше. В случае, когда сервер 102 нашел множество объектов 304, предоставляются все эти объекты 304.
[205] В некоторых вариантах осуществления, пользователь может сокращать или увеличивать число предоставляемых ему объектов 304 путем «приближения» или «удаления» карты » (zoom in, zoom out), тем самым сообщая серверу 102, что пользователь 102 заинтересован в получении объектов 304, расположенных в элементах 202 определенного уровня и более низких уровней, отсекая тем самым крупные объекты, расположенные в элементах более высокого уровня. В качестве наглядного примера, в элементах 202 более высокого уровня может быть представлена страна, в элементах 202 более низкого уровня - населенные пункты, а в элементах 202 еще боле низкого уровня -строения.
[206] Предоставление объектов 304 может осуществляться сервером 102 по сети 110 передачи данных на клиентское устройство 122 для демонстрации в пользовательском интерфейсе во время сессии браузера 126.
Изобретение относится к технологиям пространственного расположения объектов с использованием гибкой иерархической структуры памяти. Техническим результатом является снижение вычислительных затрат на обработку данных за счет перераспределения объектов в элементах n-дерева. Предложен способ пространственного хранения объекта посредством гибкой иерархической структуры, содержащей множество элементов n-дерева. Способ включает в себя этап, на котором осуществляют получение из памяти компьютера объекта для размещения в одном из множества элементов n-дерева. Далее, определяют наиболее подходящий элемент n-дерева для размещения объекта, определяют выход границы объекта за границы наиболее подходящего элемента n-дерева. А также осуществляют определение при выходе границы объекта за границы наиболее подходящего элемента n-дерева границы наиболее подходящего элемента n-дерева, пересеченной частью объекта при расположении объекта в этом элементе n-дерева. 2 н. и 47 з.п. ф-лы, 7 ил.
1. Способ пространственного хранения объекта посредством гибкой иерархической структуры, содержащей множество элементов n-дерева, включающий:
получение из памяти компьютера объекта для размещения в одном из множества элементов n-дерева;
определение наиболее подходящего элемента n-дерева для размещения объекта;
определение выхода границы объекта за границы наиболее подходящего элемента n-дерева;
определение границы, пересеченной частью объекта при расположении объекта в наиболее подходящем элементе n-дерева и выходе объекта за границы указанного элемента n-дерева;
увеличение размера наиболее подходящего элемента n-дерева посредством добавления к нему зоны присутствия объекта, имеющей границу, удаленную от границы указанного элемента n-дерева на максимальную величину выступа объекта за его пределы.
2. Способ по п. 1, включающий получение запроса пользователя посредством выбора пользователем фрагмента пространства, предоставление пользователю объекта, ассоциированного с элементом n-дерева посредством пользовательского интерфейса компьютера.
3. Способ по п. 2, в котором указанный фрагмент пространства соответствует одному из:
элементу n-дерева, содержащему по меньшей мере один объект, находящийся в выбранном пользователем фрагменте пространства;
зоне присутствия объекта, увеличивающей размер соседнего элемента n-дерева.
4. Способ по п. 3, который включает при соответствии выбранного фрагмента пространства указанной зоне присутствия объекта осуществление поиска объекта в элементе n-дерева, содержащем по меньшей мере один объект, находящийся в выбранном пользователем фрагменте пространства, и в соседнем элементе n-дерева, увеличенном зоной присутствия объекта, соответствующей выбранному указанному фрагменту пространства.
5. Способ по п. 1, в котором множество элементов n-дерева включает в себя по меньшей мере одно из:
множество узлов n-дерева, каждый из которых имеет предопределенное число элементов n-дерева следующего уровня, и
множество листьев n-дерева.
6. Способ по п. 1, в котором определение наиболее подходящего элемента n-дерева для размещения объекта осуществляют посредством определения центра объекта.
7. Способ по п. 1, который включает определение количества объектов в элементе n-дерева.
8. Способ по п. 1, в котором предопределяют максимально допустимое количество объектов, расположенных в одном элементе n-дерева.
9. Способ по п. 8, который включает формирование предопределенного количества элементов n-дерева следующего уровня при числе объектов, соответствующих данному элементу n-дерева, превышающему максимально допустимое количество.
10. Способ по п. 9, который включает перераспределение объекта между элементами n-дерева разных уровней.
11. Способ по п. 10, в котором перераспределение объекта осуществляют между предшествующим элементом n-дерева и одним из множества сформированных элементов n-дерева следующего уровня.
12. Способ по п. 10, в котором перераспределение объектов между предшествующим элементом n-дерева и одним из множества сформированных элементов n-дерева следующего уровня осуществляют с учетом размера перераспределяемых объектов.
13. Способ по п. 10, в котором перераспределение объектов между предшествующим элементом n-дерева и одним из множества сформированных элементов n-дерева следующего уровня осуществляют с учетом потенциального пересечения перераспределяемых объектов границами элементов n-дерева следующего уровня.
14. Способ по п. 8, включающий упразднение предопределенного количества элементов n-дерева следующего уровня при сумме объектов во всех этих элементах n-дерева указанного следующего уровня и в предшествующем элементе n-дерева, меньшей или равной максимально допустимому количеству объектов предшествующего элемента n-дерева.
15. Способ по п. 14, включающий перемещение объектов из предопределенного количества упраздненных элементов n-дерева следующего уровня в предшествующий элемент n-дерева.
16. Способ по п. 1, в котором по меньшей мере одна зона присутствия объекта, увеличивающая размер элемента n-дерева, по меньшей мере частично перекрывает другой элемент n-дерева того же уровня.
17. Способ по п. 1, в котором по меньшей мере одна зона присутствия объекта, увеличивающая размер элемента n-дерева следующего уровня, выходит за пределы предшествующего элемента n-дерева.
18. Способ по п. 1, в котором каждый объект размещен только в одном элементе n-дерева.
19. Способ по п. 1, в котором n-дерево является деревом квадрантов и предопределенное число элементов дерева квадрантов следующего уровня равно четырем.
20. Способ по п. 19, в котором определение наиболее подходящего элемента дерева квадрантов для размещения объекта осуществляется посредством выбора элемента дерева квадрантов, имеющего наименьший прирост площади после увеличения размера наиболее подходящего элемента дерева квадрантов посредством добавления к нему зоны присутствия объекта.
21. Способ по п. 1, в котором n-дерево является деревом октантов и предопределенное число элементов дерева октантов следующего уровня равно восьми.
22. Способ по п. 21, в котором определение наиболее подходящего элемента дерева октантов для размещения объекта осуществляется посредством выбора элемента дерева октантов, имеющего наименьший прирост объема после увеличения размера наиболее подходящего элемента дерева октантов посредством добавления к нему зоны присутствия объекта.
23. Способ по п. 1, в котором n-дерево является бинарным деревом и предопределенное число элементов бинарного дерева следующего уровня равно двум.
24. Способ по п. 23, в котором определение наиболее подходящего элемента бинарного дерева для размещения объекта осуществляется посредством выбора элемента бинарного дерева, имеющего наименьший прирост длины после увеличения размера наиболее подходящего элемента бинарного дерева посредством добавления к нему зоны присутствия объекта.
25. Постоянный носитель информации, включающий базу данных, содержащую гибкую иерархическую структуру с группой элементов n-дерева, и машиночитаемые коды, выполненные с возможностью их осуществления компьютером способа по п. 1.
26. Носитель по п. 25, в котором машиночитаемые коды выполнены с возможностью получения запроса пользователя посредством выбора пользователем фрагмента пространства, предоставления пользователю объекта, ассоциированного с элементом n-дерева, посредством пользовательского интерфейса компьютера.
27. Носитель по п. 26, в котором указанный фрагмент пространства соответствует одному из:
элементу n-дерева, содержащему по меньшей мере один объект, находящийся в выбранном пользователем фрагменте пространства, и
зоне присутствия объекта, увеличивающей размер соседнего элемента n-дерева.
28. Носитель по п. 26, в котором машиночитаемые коды выполнены с возможностью при соответствии выбранного указанного фрагмента указанной зоне присутствия объекта осуществления поиска объекта в
элементе n-дерева, содержащем по меньшей мере один объект, находящийся в выбранном пользователем фрагменте пространства, и в
соседнем элементе n-дерева, увеличенном зоной присутствия объекта, соответствующей выбранному указанному фрагменту пространства.
29. Носитель по п. 26, в котором машиночитаемые коды и компьютер выполнены с возможностью получения запроса пользователя посредством пользовательского интерфейса компьютера.
30. Носитель по п. 25, в котором группа элементов n-дерева содержит по меньшей мере одно из:
множество узлов n-дерева, причем каждый из множества узлов n-дерева имеет предопределенное число элементов n-дерева следующего уровня (дочерних элементов), и
множество листьев n-дерева.
31. Носитель по п. 25, в котором машиночитаемые коды и компьютер выполнены с возможностью определения наиболее подходящего элемента n-дерева для размещения объекта посредством определения центра объекта.
32. Носитель п. 25, в котором машиночитаемые коды и компьютер выполнены с возможностью определения количества объектов в элементе n-дерева.
33. Носитель по п. 25, в котором максимальное допустимое количество объектов, расположенных в одном элементе n-дерева, предопределено.
34. Носитель по п. 33, в котором машиночитаемые коды и компьютер выполнены с возможностью создания предопределенного количества элементов n-дерева следующего уровня в случае при превышении максимально допустимого количества объектов, соответствующих данному элементу n-дерева любого уровня.
35. Носитель по п. 25, в котором машиночитаемые коды и компьютер выполнены с возможностью перераспределения объекта между элементами n-дерева разных уровней.
36. Носитель по п. 35, в котором машиночитаемые коды и компьютер выполнены с возможностью перераспределения объекта между предшествующим элементом n-дерева и одним из группы сформированных элементов n-дерева следующего уровня.
37. Носитель по п. 36, в котором машиночитаемые коды и компьютер выполнены с возможностью перераспределения объектов с учетом размера перераспределяемых объектов.
38. Носитель по п. 36, в котором машиночитаемые коды и компьютер выполнены с возможностью перераспределения объектов с учетом потенциального пересечения перераспределяемых объектов границами элементов n-дерева следующего уровня.
39. Носитель по п. 33, в котором машиночитаемые коды и компьютер выполнены с возможностью упразднения предопределенного числа элементов n-дерева следующего уровня при сумме объектов во всех этих элементах n-дерева указанного следующего уровня и в предшествующем элементе n-дерева, не превышающей максимальное допустимое количество объектов предшествующего элемента n-дерева.
40. Носитель по п. 25, в котором машиночитаемые коды и компьютер выполнены с возможностью перемещения объектов из предопределенного числа упраздненных элементов n-дерева следующего уровня в предшествующий элемент n-дерева.
41. Носитель по п. 25, в котором по меньшей мере одна зона присутствия объекта, увеличивающая размер элемента n-дерева, по меньшей мере частично перекрывает другой элемент n-дерева этого же уровня.
42. Носитель по п. 25, в котором по меньшей мере одна зона присутствия объекта, увеличивающая размер элемента n-дерева следующего уровня, выходит за пределы предшествующего элемента n-дерева.
43. Носитель по п. 25, в котором каждый объект размещен только в одном элементе n-дерева.
44. Носитель по п. 25, в котором n-дерево является деревом квадрантов и предопределенное число элементов дерева квадрантов следующего уровня равно четырем.
45. Носитель по п. 44, в котором машиночитаемые коды и компьютер выполнены с возможностью определения наиболее подходящего элемента дерева квадрантов для размещения объекта посредством выбора элемента дерева квадрантов, имеющего наименьший прирост площади после увеличения размера наиболее подходящего элемента дерева квадрантов.
46. Носитель по п. 25, в котором n-дерево является деревом октантов и предопределенное число элементов дерева октантов следующего уровня равно восьми.
47. Носитель по п. 46, в котором машиночитаемые коды и компьютер выполнены с возможностью определения наиболее подходящего элемента дерева октантов для размещения объекта посредством выбора элемента дерева октантов, имеющего наименьший прирост объема после увеличения размера наиболее подходящего элемента дерева октантов.
48. Носитель по п. 25, в котором n-дерево является бинарным деревом и предопределенное число элементов бинарного дерева следующего уровня равно двум.
49. Носитель по п. 25, в котором машиночитаемые коды и компьютер выполнены с возможностью определения наиболее подходящего элемента бинарного дерева для размещения объекта посредством выбора элемента бинарного дерева, имеющего наименьший прирост длины после увеличения размера наиболее подходящего элемента бинарного дерева.
| Способ и приспособление для нагревания хлебопекарных камер | 1923 |
|
SU2003A1 |
| US 5461712 A, 24.10.1995 | |||
| Способ защиты переносных электрических установок от опасностей, связанных с заземлением одной из фаз | 1924 |
|
SU2014A1 |
| US 8681168 B2, 25.03.2014 | |||
| Приспособление для суммирования отрезков прямых линий | 1923 |
|
SU2010A1 |
| СИСТЕМА ИДЕНТИФИКАЦИИ ИЗОБРАЖЕНИЙ | 2002 |
|
RU2302656C2 |
