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

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

Иллюстрации

Показать все

Реферат

Область техники, к которой относится изобретение

Настоящая технология относится к области хранения пространственных объектов.

Уровень техники

В современных компьютерных технологиях пространственное расположение объектов обычно включает в себя разделение пространства (сцены) на меньшие части. Разбиение может происходить различными методами. Одним из методов является разбиение пространства на квадранты. В компьютерной графике разбиение пространства (на квадранты, октанты и так далее) обычно осуществляется во время обработки данных графическим конвейером с целью уменьшить будущие расчеты и минимизировать количество объектов, направляемых на обработку графическому конвейеру. В больших деталях это раскрыто в патентной заявке США № US 20030227455, опубл. 11.12.2003.

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

Поиск объекта в дереве квадрантов является относительно легким и относительно не затратным с точки зрения потребления вычислительных мощностей.

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

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

Раскрытие изобретения

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

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

размещение в односвязном списке объектов, хранящихся в любом из: первом, втором, третьем и четвертом элементе первого уровня дерева квадрантов, соответственно после первого, второго, третьего и четвертого маркера первого уровня.

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

Возможен вариант осуществления способа, в котором дополнительно выполняют:

получение нового объекта, размещение указанного нового объекта в o-элементе дерева квадрантов, размещение указанного нового объекта в односвязном списке после маркера, относящегося к o-элементу дерева квадрантов.

Возможен вариант осуществления способа, в котором объектом является тег графического объекта.

Возможен вариант осуществления способа, в котором элемент дерева квадрантов дополнительно включает в себя указатель на маркер в односвязном списке, относящийся к этому элементу дерева квадрантов.

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

Возможен вариант осуществления способа, в котором запрос пользователя осуществляется путем выбора пользователем соответствующего фрагмента пространства.

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

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

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

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

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

Еще одним объектом настоящей технологии является компьютер. Компьютер включает в себя процессор. Процессор выполнен с возможностью: размещения в односвязном списке первого, второго, третьего и четвертого маркеров первого уровня, относящихся соответственно к первому, второму, третьему и четвертому элементам первого уровня дерева квадрантов; размещения в односвязном списке объектов, хранящихся в любом из: первом, втором, третьем и четвертом элементе первого уровня дерева квадрантов, соответственно после первого, второго, третьего и четвертого маркера первого уровня.

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

Возможен вариант осуществления компьютера, в котором процессор дополнительно выполнен с возможностью: получения нового объекта, размещения указанного нового объекта в o-элементе дерева квадрантов, размещения указанного нового объекта в односвязном списке после маркера, относящегося к o-элементу дерева квадрантов.

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

Возможен вариант осуществления компьютера, в котором процессор дополнительно выполнен с возможностью определения n-элемента дерева квадрантов как соответствующего соответствующему фрагменту пространства, выбранному пользователем,

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

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

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

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

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

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

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

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

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

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

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

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

В настоящем описании выражение «носитель информации, предназначенный для использования компьютером» (также кратко именуемый «носитель информации») охватывает носители любого характера и типа, в том числе оперативные запоминающие устройства, постоянные запоминающие устройства, диски (компакт-диски, DVD-диски, гибкие диски, жесткие диски и т.д.), USB-ключи, твердотельные накопители, ленточные накопители и т.д.

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

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

В настоящем описании термин «массив» («ряд») охватывает набор однотипных компонентов (элементов), расположенных в памяти непосредственно друг за другом, доступ к которым осуществляется по индексу (индексам). В отличие от односвязного списка, массив является структурой с произвольным доступом.

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

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

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

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

Краткое описание чертежей

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

На Фиг. 1 показано схематическое изображение варианта воплощения компьютерных систем, реализующих настоящую технологию.

На Фиг. 2 показано схематическое изображение структуры и компонентов дерева квадрантов.

На Фиг. 3 показано схематическое изображение четырех элементов 202 первого уровня 204 дерева квадрантов 108, показанного на Фиг. 2, с размещенными в них объектами.

На Фиг. 4 показано схематическое изображение четырех элементов 202 второго уровня 206 дерева квадрантов 108, изображенного на Фиг. 2.

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

На Фиг. 6 показано схематическое изображение воплощения односвязного списка 500 с размещенными в нем маркерами первого уровня и объектами из элементов первого уровня дерева квадрантов, реализованного в соответствии с вариантами осуществления настоящей технологии, не ограничивающими ее объем.

На Фиг. 7 показано схематическое изображение воплощения односвязного списка 500 с размещенными в нем маркерами первого и второго уровней, а также с размещенными в нем объектами из элементов первого уровня дерева квадрантов, реализованного в соответствии с вариантами осуществления настоящей технологии, не ограничивающими ее объем.

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

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

На Фиг. 10 показана блок-схема способа 1000, выполняемого на сервере 102, изображенном на Фиг. 1, выполняемого в соответствии с вариантами осуществления настоящей технологии, не ограничивающими ее объем.

На Фиг. 11 показана блок-схема способа 1100, выполняемого на сервере 102, изображенном на Фиг. 1, выполняемого в соответствии с вариантами осуществления настоящей технологии, не ограничивающими ее объем.

На Фиг. 12 показано схематическое изображение воплощения односвязного списка 500 с размещенными в нем маркерами первого, второго и третьего уровней, с размещенными в нем объектами из элементов первого и второго уровней дерева квадрантов, и с маркером 1202 массива, реализованного в соответствии с вариантами осуществления настоящей технологии, не ограничивающими ее объем.

Осуществление изобретения

На Фиг. 1 показана принципиальная схема различных компьютерных систем 100, находящихся в связи друг с другом с помощью сети 110 передачи данных. Важно иметь в виду, что различные компьютерные системы 100 представлены как иллюстративный вариант осуществления настоящей технологии. Таким образом, нижеследующее их описание должно рассматриваться исключительно как описание иллюстративных примеров настоящей технологии. Это описание не предназначено для определения объема или установления границ настоящей технологии. Некоторые полезные примеры модификаций компьютерных систем 100 также могут быть охвачены нижеследующим описанием. Целью этого является также исключительно помощь в понимании, а не определение объема и границ настоящей технологии. Эти модификации не представляют собой исчерпывающий список, и специалистам в данной области техники будет понятно, что возможны и другие модификации. Кроме того, это не должно интерпретироваться так, что там, где это еще не было сделано, т.е. там, где не были изложены примеры модификаций, никакие модификации невозможны, и/или что то, что описано, является единственным способом осуществления этого элемента данной технологии. Как будет понятно специалисту в данной области техники, это, скорее всего, не так. Кроме того, следует иметь в виду, что компьютерные системы 100 представляют собой в некоторых конкретных проявлениях достаточно простой вариант осуществления настоящей технологии, и в подобных случаях представлен здесь с целью облегчения понимания. Как будет понятно специалисту в данной области техники, многие варианты осуществления настоящей технологии будут обладать гораздо большей сложностью.

Система 100 включает в себя сервер 102. Сервер 102 может представлять собой обычный компьютерный сервер. В примере варианта осуществления настоящей технологии, сервер 102 может представлять собой сервер Dell™ PowerEdge™, на котором используется операционная система Microsoft™ Windows Server™. Излишне говорить, что сервер 102 может представлять собой любое другое подходящее аппаратное и/или прикладное программное, и/или системное программное обеспечение или их комбинацию. В представленном варианте осуществления настоящей технологии, не ограничивающем ее объем, сервер 102 является одиночным сервером. В других вариантах осуществления настоящей технологии, не ограничивающих ее объем, функциональность сервера 102 может быть разделена, и может выполняться с помощью нескольких серверов.

В некоторых вариантах осуществления настоящей технологии, сервер 102 находится под контролем и/или управлением поставщика сервиса карт, такого, например, как провайдер сервиса карт Yandex™. Таким образом, сервер 102 может быть выполнен с возможностью выполнять один или несколько поисков в ответ на поисковый запрос по сервису карт, введенный пользователем 111 в браузер 116 электронного устройства 112, соединенного с сервером 102 по сети 110 передачи данных. Сервер 102 также выполнен с возможностью передавать электронному устройству 112 результат поиска, который будет отображаться пользователю 111 электронного устройства 112 на дисплее 118 через интерфейс браузера 116. Эти функции хорошо известны в данной области техники и поэтому не будут здесь описаны.

Сервер 102 включает в себя носитель информации 104, который может использоваться сервером. В принципе, данный носитель информации 104 может быть носителем абсолютно любого типа и характера, включая ОЗУ, ПЗУ, диски (компакт диски, DVD-диски, дискеты, жесткие диски и т.д.), USB флеш-накопители, твердотельные накопители, накопители на магнитной ленте и т.д., а также их комбинации.

Варианты осуществления сервера 102 хорошо известны в данной области техники. Таким образом, достаточно отметить, что каждый сервер 102 содержит, среди прочего, интерфейс сетевой связи (например, модем, сетевую карту и тому подобное) (не изображен) для двусторонней связи по сети 110 передачи данных; и процессор (не изображен), соединенный с интерфейсом сетевой связи, который выполнен с возможностью выполнять различные процедуры, включая те, что описаны ниже. С этой целью процессор может сохранять или иметь доступ к машиночитаемым инструкциям, выполнение которых инициирует процессор выполнять различные описанные здесь процедуры.

Носитель информации 104 сервера 102 предназначен для хранения данных, в том числе машиночитаемых инструкций и баз данных.

В частности, носитель информации 104 сервера 102 осуществляет хранение базы данных 106, в которой хранится дерево квадрантов 108, являющееся иерархической структурой данных. Дерево квадрантов 108 включает в себя множество элементов n-дерева (узлов n-дерева и листьев n-дерева) разного уровня. Дерево квадрантов 108 создается и поддерживается преимущественно для построения и поддерживания пространственных баз данных. Дерево квадрантов 108 используется для рекурсивного разделения пространства на четыре региона. Каждый элемент дерева квадрантов 108, представляющий регион, имеет максимальную вместимость; когда максимальная вместимость элемента дерева квадрантов 108 достигнута, регион и элемент дерева квадрантов разделяется. Дерево квадрантов 108 следует пространственному разбиению дерева квадрантов 108.

Носитель информации 104 сервера 102 также осуществляет хранение машиночитаемых инструкций, обеспечивающих управление базами данных, их обновление, пополнение, модификации. В частности, машиночитаемые инструкции, сохраненные на носителе информации 104, позволяют серверу 102 получать (обновлять) данные об объектах с электронного устройства 112 по сети 110 передачи данных, размещать указанные объекты в дереве квадрантов 108, менять положение и/или характеристики указанных объектов в дереве квадрантов 108, удалять указанные объекты из дерева квадрантов 108, получать с электронного устройства 112 по сети 110 передачи данных запросы пользователя 111 на предоставление списка объектов, содержащихся в определенном участке пространства, получать из базы данных 106 данные об объектах, хранящихся в элементах дерева квадрантов 108, соответствующих участку пространства, которым интересуется пользователь 111, и передавать этот список на электронное устройство 112 пользователя 111 по сети 110 передачи данных.

Сервер 102 соединен с сетью 110 передачи данных через линию связи (не пронумерована). В некоторых вариантах осуществления настоящей технологии, не ограничивающих ее объем, сеть 110 передачи данных связи может представлять собой Интернет. В других вариантах осуществления настоящей технологии, сеть 110 передачи данных может быть реализована иначе - в виде глобальной сети передачи данных, локальной сети передачи данных, частной сети передачи данных и т.п.

Реализация линии связи не ограничена и будет зависеть от того, какие устройства присоединены к сети 110 передачи данных. В качестве примера, но не ограничения, подключение сервера 102 к сети 110 передачи связи может быть осуществлено по проводной связи (соединение на основе сети Ethernet). В то же время, другие устройства могут быть подключены иными способами. Так, в случаях, в которых подключенное устройство представляет собой беспроводное устройство связи (например, электронное устройство 112, реализованное как смартфон), подключение представляет собой беспроводную сеть связи (например, среди прочего, линия связи сети 3G, линия связи сети 4G, беспроводной интернет Wireless Fidelity или коротко WiFi®, Bluetooth® и т.п.). В тех примерах, где устройство настольный компьютер (как, например, электронное устройство 112), линия связи может быть как беспроводной так и проводной (соединение на основе сети Ethernet).

Важно иметь в виду, что различные воплощения сервера 102, электронного устройства 112, линий связи для подсоединения к сети 110 передачи данных даны исключительно в иллюстрационных целях. Таким образом, специалисты в данной области техники смогут понять подробности других конкретных вариантов осуществления сервера 102, электронного устройства 112, линий связи для подсоединения к сети 110 передачи данных. Таким образом, представленные здесь примеры не ограничивают объем настоящей технологии.