Область техники, к которой относится изобретение
Настоящая технология относится к области хранения пространственных объектов.
Уровень техники
В современных компьютерных технологиях пространственное расположение объектов обычно включает в себя разделение пространства (сцены) на меньшие части. Разбиение может происходить различными методами. Одним из методов является разбиение пространства на квадранты. В компьютерной графике разбиение пространства (на квадранты, октанты и так далее) обычно осуществляется во время обработки данных графическим конвейером с целью уменьшить будущие расчеты и минимизировать количество объектов, направляемых на обработку графическому конвейеру. В больших деталях это раскрыто в патентной заявке США № 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 передачи данных. Таким образом, представленные здесь примеры не ограничивают объем настоящей технологии.
Через сеть 110 передачи данных сервер 102 соединен с электронным устройством 112. Электронное устройство 112 обычно связано с пользователем 111. Пользователем 111 может являться лицо, получающие данные об объектах, имеющих пространственные координаты. В качестве неограничивающего примера пользователя 111, из множества возможных примеров, можно назвать потенциального покупателя объекта недвижимости, который осуществляет поиск по пространственной базе данных, контент которых пополняется собственниками недвижимости или риэлторами. В качестве другого неограничивающего примера можно привести автомобилиста - владельца GPS-навигатора, который делает запрос о наличии, местоположении и часах работы автозаправочных станций, расположенных поблизости от него.
Следует отметить, что тот факт, что электронное устройство 112 связано с пользователем 111, не подразумевает какого-либо конкретного режима работы, равно как и необходимости входа в систему, быть зарегистрированным или чего-либо подобного.
Варианты осуществления электронного устройства 112 конкретно не ограничены, но в качестве примера электронного устройства 112 могут использоваться персональные компьютеры (настольные компьютеры, ноутбуки, нетбуки и т.п.), устройства беспроводной связи (мобильные телефоны, смартфоны, планшеты и т.п.), а также сетевое оборудование (маршрутизаторы, коммутаторы или шлюзы). На Фиг. 1 электронное устройство 112 реализовано в виде персонального компьютера Dell Precision Т1700 МТ СА033РТ170011RUWS с процессором Intel® Xeon™, частота процессора: 3300 МГц, с видеокартой nVIDIA Quadro K1080, с установленной и действующей операционной системой Windows 7 Pro 64-bit.
Электронное устройство 112 включает в себя носитель информации 114. В принципе, данный носитель информации 114 может быть носителем абсолютно любого типа и характера, включая ОЗУ, ПЗУ, диски (компакт диски, DVD-диски, дискеты, жесткие диски и т.д.), USB флеш-накопители, твердотельные накопители, накопители на магнитной ленте и т.д, а также их комбинации. В электронном устройстве 112, изображенном на Фиг. 1, носитель информации 114 реализован как жесткий диск с 500 Gb памяти. Носитель информации 114 может сохранять файлы пользователя и программные инструкции. В частности, носитель информации может хранить программное обеспечение для использования в качестве браузера 116.
В общем случае, целью браузера 116 является предоставление возможности пользователю 111 подключаться к серверу 102, делать запросы на предоставление информации, получать информацию с сервера 102 и отображать полученную информацию на дисплее 118. В электронном устройстве 112 браузер 116 реализован как Яндекс™ браузер. Однако, как будет понятно специалистам в данной сфере, реализация браузера 116 никак конкретно не ограничена. В качестве неограничивающих примеров, такими браузерами могут быть Google Chrome™, Internet Explorer™, различные мобильные поисковые приложения и так далее. Важно иметь в виду, что любое другое коммерчески доступное или собственное приложение может быть использовано для реализации вариантов осуществления настоящей технологии, не ограничивающих ее объем.
Электронное устройство 112 соединено с сетью 110 передачи данных через линию связи (не пронумерована).
Электронное устройство 112 включает в себя также дисплей 118, являющийся монитором Dell™ Е2214Н 2214-7803 с диагональю 21,5″, с разрешением 1920×1080, позволяющий представлять видеоинформацию пользователю 111. Таким образом, пользователь 111 имеет возможность видеть на дисплее 118 в интерфейса браузера 116 электронного устройства 112 визуальное отображение информации, полученной с сервера 102. Например, пользователь 111 может видеть на дисплее 118 все объекты недвижимости, выставленные на продажу в пределах определенного населенного пункта или его части, либо все земельные участки в пределах кадастрового квартала.
На Фиг. 2 показано схематическое изображение структуры и компонентов дерева квадрантов 108.
Дерево квадрантов 108 является иерархической структурой данных. Дерево квадрантов 108 включает в себя множество элементов 202 дерева квадрантов 108, а именно: узлов 216 дерева квадрантов 108 и листьев 214 дерева квадрантов 108 разного уровня.
В примере, изображенном на Фиг. 2, дерево квадрантов 108 включает в себя элементы 202 дерева квадрантов 108 пяти уровней, а именно: (а) четыре элемента 202 первого уровня 204, являющиеся в данном случае одним узлом 216 дерева квадрантов 108 и тремя листьями 214 дерева квадрантов 108, (б) четыре элемента 202 второго уровня 206, являющихся в данном случае тремя узлами 216 дерева квадрантов 108 и одним листом 214 дерева квадрантов 108, (в) двенадцать элементов 202 третьего уровня 208, являющихся в данном случае одним узлом 216 дерева квадрантов 108 и одиннадцатью листьями 214 дерева квадрантов 108, (г) четыре элемента 202 четвертого уровня 210, являющихся в данном случае одним узлом 216 дерева квадрантов 108 и тремя листами 214 дерева квадрантов 108, (д) четыре элемента 202 пятого уровня 212, являющихся в данном случае четырьмя листьями 214 дерева квадрантов 108.
Для наглядности, узлы 216 дерева квадрантов 108 обозначены на Фиг.2 как закрашенные квадраты, а листья 214 дерева квадрантов 108 обозначены как незакрашенные квадраты.
В данном примере, первый уровень 204 является самым высоким уровнем, а элементы 202 первого уровня 204 являются «корневыми элементами».
Пятый уровень 212, изображенный на Фиг. 2, является самым низким уровнем в данном примере. В других примерах самый низкий уровень может быть иным (например, шестым, седьмым, и так далее).
Уровень «материнского» элемента выше уровня «дочернего» элемента.
Дерево квадрантов 108 создается и поддерживается преимущественно для построения и поддерживания пространственных баз данных. Оно используется для рекурсивного разделения пространства на четыре региона.
Неограничивающим примером использования дерева квадрантов 108 может служить сервис карт, где каждый объект может быть расположен в определенном месте на двумерной карте и быть отмечен как точечный, площадной либо иной объект. Двумерная карта может быть рекурсивно разбита на четыре квадранта. Эти четыре квадранта, будучи элементами 202 первого уровня, могут быть рекурсивно разбиты на четыре элемента 202 второго уровня 206. Каждый из четырех элементов 202 второго уровня 206 может включать в себя объекты, расположенные в соответствующем одном из четырех квадрантов карты. Некоторые элементы 202 второго уровня 206, полученные в результате разбиения одного элемента 202 первого уровня 204, могут быть разбиты, в свою очередь, на следующие четыре элемента 202 третьего уровня 208, и так далее. В результате элементы (квадранты), разбитые на четыре элемента (квадранта) следующего уровня, являются узлами 216 дерева квадрантов 108, а неразбитые элементы (квадранты) являются листами 214 дерева квадрантов 108.
Другим неограничивающим примером использования дерева квадрантов 108 может служить база данных двумерных объектов, используемых в компьютерных играх.
Другим неограничивающим примером использования дерева квадрантов 108 может служить база данных объектов недвижимости, которая может использоваться риэлторами и/или иными лицами.
Дерево квадрантов 108 может иметь следующие свойства: (а) дерево квадрантов 108 разбивает пространство на квадранты; (б) каждый квадрант имеет максимальную вместимость, и когда максимальная вместимость достигнута, квадрант разделяется; (в) направление дерева квадрантов 108 следует пространственному разбиению.
На Фиг. 3 показано схематическое изображение четырех элементов 202 первого уровня 204 дерева квадрантов 108, изображенного на Фиг. 2.
Как было указано выше, в данном примере первый уровень 204 дерева квадрантов 108 включает в себя четыре корневых элемента 202 дерева квадрантов, три из которых, в данном примере, являются листьями 214 дерева квадрантов 108, и один элемент 202 является узлом 216 дерева квадрантов.
Как видно на Фиг. 3, тремя листьями 214 дерева квадрантов 108 являются листья, представленные квадратами с вершинами в точках AEIH (лист 302), EBFI (лист 304), IFCG (лист 306). Единственным узлом 216 первого уровня 204 является узел, представленный квадратом с вершинами в точках IGDH (узел 308).
Из четырех элементов 202 дерева квадрантов 108 первого уровня 204 два элемента - лист 304 и узел 308 - содержат в себе объекты.
Так, лист 304 содержит в себе объект 310, объект 312 и объект 314. Узел 308 содержит в себе объект 316.
Как было указано выше, под объектами могут пониматься графические объекты, например плоскостные, точечные и линейные объекты. Кроме того, объектами могут являться индикаторы графических объектов, то есть теги графических объектов. Тег графического объекта является носителем ссылки на запись в базе данных, где содержатся характеристики графического объекта.
В данном варианте осуществления настоящей технологии, объект 310, объект 312, объект 314 и объект 316 являются индикаторами различных графических объектов. Объект 310, объект 312, объект 314 и объект 316 хранятся в элементах 202 верхнего уровня 204 дерева квадрантов 108.
Узел 308 является узлом дерева квадрантов и, соответственно, у него имеются четыре дочерних элемента 202 дерева квадрантов. Этими четырьмя дочерними элементами 202 являются три узла 216 дерева квадрантов 108 второго уровня 206, и один лист 214 дерева квадрантов 108 второго уровня 206, как это показано на Фиг. 2.
Каждый из элементов 202 дерева квадрантов 108 дополнительно может включать в себя указатель на маркер (не изображен) в односвязном списке, относящийся к этому элементу дерева квадрантов для согласования структуры дерева квадрантов со структурой односвязного дерева. Таким образом, указатель на маркер может показывать начало той части односвязного списка, в которой хранятся объекты из соответствующего элемента дерева квадрантов.
На Фиг. 4 показано схематическое изображение четырех элементов 202 второго уровня 206 дерева квадрантов 108, изображенного на Фиг. 2.
Как было указано выше, в данном случае второй уровень 206 дерева квадрантов 108 включает в себя четыре элемента 202 дерева квадрантов, три из которых являются узлами 216 дерева квадрантов 108 и один элемент 202 является узлом 214 дерева квадрантов.
Изображенные на Фиг. 4 элементы 202 дерева квадрантов 108, представленные в виде квадратов с вершинами в точках MIJN, NJGK и LNKD, являются узлами 216 дерева квадрантов 108 (в данном случае они отмечены соответственно как узел 320, узел 322 и узел 324).
Изображенный на Фиг. 4 элемент 202 дерева квадрантов 108, представленный в виде квадрата с вершинами в точках HMNL, является листом 214 дерева квадрантов 108 (в данном случае он отмечен как лист 318).
Узел 320 содержит в себе один объект - объект 326.
Узел 322 содержит в себе два объекта - объект 330 и объект 328.
Узел 324 содержит в себе один объект - объект 332.
На Фиг. 4 также изображены пунктирными линиями объекты 310, 312, 314 и 316, которые расположены в элементах 202 первого уровня 204, а не второго уровня 204 дерева квадрантов 108. Таким образом, объект 316 не находится ни в одном из узлов 214 второго уровня 206: ни в узле 320, ни в узле 322. Объект 316 находится в узле 308 первого уровня 204, изображенном на Фиг. 3.
Как было указано выше, под объектами могут пониматься графические объекты, например плоскостные, точечные и линейные объекты. Кроме того, объектами могут являться индикаторы графических объектов, то есть теги графических объектов.
В данном варианте осуществления настоящей технологии, объект 326, объект 328, объект 330 и объект 332 являются тегами различных графических объектов. Эти теги хранятся в элементах 202 второго уровня 206 дерева квадрантов 108.
Узлы 318, 320, 322 являются узлами дерева квадрантов и, соответственно, у каждого из них имеются по четыре дочерних элемента 202 дерева квадрантов третьего уровня 208, как это показано на Фиг. 2. Здесь мы не будем описывать ни эти элементы 202 третьего уровня 208, ни иные элементы 202 более низких уровней, поскольку специалистам в данной области техники достаточно описания элементов первых двух уровней и описания расположения в них объектов. Описание элементов 202 третьего уровня 208 и более низких уровней было бы аналогичным вышеприведенному описанию. По этой же причине мы также не будем описывать объекты, расположенные в объектах 202 третьего уровня 208 и более низких уровней.
На Фиг. 5 показано схематическое изображение односвязного списка 500 с размещенными в нем маркерами первого уровня. Фиг. 5 будет описана ниже, при описании Фиг. 10, являющейся блок-схемой способа 1000, выполняемого на сервере 102.
На Фиг. 6 показано схематическое изображение односвязного списка 500 с размещенными в нем маркерами первого уровня 522, 524, 526 и 528, а также с размещенными объектами из элементов первого уровня дерева квадрантов. Фиг. 6 будет описана ниже, при описании Фиг. 10, являющейся блок-схемой способа 1000, выполняемого на сервере 102.
На Фиг. 7 показано схематическое изображение односвязного списка 500 с размещенными в нем маркерами первого и второго уровней, а также с размещенными в нем объектами из элементов первого уровня дерева квадрантов. Фиг. 7 будет описана ниже, при описании Фиг. 10, являющейся блок-схемой способа 1000, выполняемого на сервере 102.
На Фиг. 9 показано схематическое изображение односвязного списка 500 с размещенными в нем маркерами первого и второго уровней, а также с размещенными в нем объектами из элементов первого и второго уровней дерева квадрантов. Фиг. 9 будет описана ниже, при описании Фиг. 10, являющейся блок-схемой способа 1000, выполняемого на сервере 102.
На Фиг. 10 показана блок-схема способа 1000, выполняемого на сервере 102, изображенном на Фиг. 1, выполняемого в соответствии с вариантами осуществления настоящей технологии, не ограничивающими ее объем.
В вариантах осуществления настоящей технологии способ 1000 может выполняться на сервере 102, изображенном на Фиг. 1. Для этого сервер 102 включает в себя носитель информации 104, хранящий машиночитаемые инструкции, при выполнении которых сервер 102 выполняет этапы способа 1000. Однако, как это будет понятно специалистам в данной области техники, метод 1000 может быть осуществлен на других серверах.
Этап 1002 - размещение в односвязном списке первого, второго, третьего и четвертого маркеров первого уровня, относящихся соответственно к первому, второму, третьему и четвертому элементам первого уровня дерева квадрантов.
Способ 1000 начинается на этапе 1002, на котором сервер 102, изображенный на Фиг. 1, осуществляет размещение в односвязном списке 500, схематически изображенном на Фиг. 5, первого маркера первого уровня 522, второго маркера первого уровня 524, третьего маркера первого уровня 526 и четвертого маркера первого уровня 528.
Односвязный список 500, схематически изображенный на Фиг. 5, представляет собой динамическую структуру данных, состоящую из узлов списка, каждый из которых содержит как собственно данные, так и одну ссылку на следующий узел списка. В настоящем описании, такими узлами списка являются маркеры и объекты, причем объектом может быть, помимо прочего, тег графического объекта.
Маркеры представляют собой индикаторы начала той части односвязного списка 500, в которой располагаются объекты, расположенные в соответствующем элементе дерева квадрантов 108. Поскольку каждый уровень дерева квадрантов 108 имеет четыре квадранта, то и количество маркеров, соответствующих этим четырем квадрантам, равно четырем. Поскольку элементы дерева квадрантов 108 могут относиться к различным уровням, то и маркеры также могут относиться к различным уровням. Таким образом, общее количество маркеров может соответствовать количеству элементов дерева квадрантов 108. Например, обращаясь к Фиг. 2, мы можем видеть следующее количество элементов дерева квадрантов: 4 элемента первого уровня, 4 элемента второго уровня, 12 элементов третьего уровня, 4 элемента четвертого уровня, 4 элемента пятого уровня. Соответственно, в односвязном списке могут быть расположены следующие маркеры: 4 маркера первого уровня, 4 маркера второго уровня, 12 маркеров третьего уровня, 4 маркера четвертого уровня, 4 маркера пятого уровня.
На Фиг. 5 показаны первый маркер первого уровня 522, второй маркер первого уровня 524, третий маркер первого уровня 526, четвертый маркер первого уровня 528.
Первый маркер первого уровня 522 является индикатором начала той части 502 односвязного списка, в которой располагаются объекты, расположенные в листе 302 первого уровня 204 дерева квадрантов 108.
Второй маркер первого уровня 524 является индикатором начала той части 504 односвязного списка, в которой располагаются объекты, расположенные в листе 304 первого уровня 204 дерева квадрантов 108.
Третий маркер первого уровня 526 является индикатором начала той части 506 односвязного списка, в которой располагаются объекты, расположенные в листе 306 первого уровня 204 дерева квадрантов 108.
Четвертый маркер первого уровня 528 является индикатором начала той части 508 односвязного списка, в которой располагаются объекты, расположенные в узле 308 первого уровня 204 дерева квадрантов 108.
Как будет понятно специалистам в данной области техники, маркеры первого уровня 522, 524, 526 и 528, равно как и другие маркеры в односвязном списке 500, являются узлами односвязного списка. Это означает, что маркеры являются не только индикаторами начала определенных частей односвязного списка, но и содержат в себе ссылку на следующий узел односвязного списка. При этом следующим узлом односвязного списка может быть как другой маркер, так и объект.
Далее, способ 1000 переходит к этапу 1004.
Этап 1004 - размещение в односвязном списке объектов, хранящихся в любом из: первом, втором, третьем и четвертом элементе первого уровня дерева квадрантов, соответственно после первого, второго, третьего и четвертого маркера первого уровня.
На этапе 1004, сервер 102 осуществляет размещение в односвязном списке 500 объектов, хранящихся в элементах первого уровня дерева квадрантов 108.
Размещение в односвязном списке 500 объектов, хранящихся в элементах первого уровня 204 дерева квадрантов 108, осуществляется после соответствующих маркеров первого уровня, то есть так, как это показано на Фиг. 6.
На Фиг. 6 показано схематическое изображение односвязного списка 500 с размещенными в нем маркерами первого уровня 522, 524, 526 и 528, а также с размещенными объектами из элементов первого уровня 204 дерева квадрантов 108, а именно: с размещенными объектами 310, 312, 314 и 316.
Как было показано на Фиг. 3, два из четырех элементов первого уровня 204 дерева квадрантов 108 не содержат в себе объектов (лист 302 и лист 306), а два других элемента первого уровня 204 дерева квадрантов 108 содержат в себе объекты (лист 304 и узел 308).
Так, лист 304 содержит в себе объекты 310, 312 и 314. Узел 308 содержит в себе один объект - объект 316. Соответственно, эти объекты размещаются также в односвязном списке 500 после соответствующих маркеров.
Объекты 310, 312 и 314, размещенные во втором элементе первого уровня 204 дерева квадрантов 108, расположены после второго маркера первого уровня 524, то есть в части 504 односвязного списка 500.
Объект 316, размещенный в четвертом элементе первого уровня дерева квадрантов, расположен после четвертого маркера первого уровня 528, то есть в части 508 односвязного списка 500.
Как будет понятно специалистам в данной области техники, объекты, помещенные в односвязный список 500, помещаются туда в качестве узлов односвязного списка. Это означает, что объекты являются не только носителями определенной информации, присущей собственно объекту, но и содержат в себе ссылку на следующий узел односвязного списка. При этом следующим узлом односвязного списка может быть как другой маркер, так и объект. В некоторых вариантах осуществления настоящей технологии, узлом может быть также маркер массива, как это будет объяснено ниже при описании Фиг. 12. В том виде, как это изображено на Фиг. 6, первый маркер первого уровня 522 содержит ссылку на второй маркер первого уровня 524. Второй маркер первого уровня 524, в свою очередь, содержит ссылку на объект 314. Объект 314 содержит ссылку на объект 312. Объект 312 содержит ссылку на объект 310. Объект 310 содержит ссылку на третий маркер первого уровня 526. Третий маркер первого уровня 526 содержит ссылку на четвертый маркер первого уровня 528. Четвертый маркер первого уровня 528 содержит ссылку на объект 316. Объект 316 является последним узлом в односвязном списке 500 и поэтому не имеет ссылки.
В некоторых вариантах осуществления настоящей технологии, способ предусматривает получение новых объектов. Например, новые объекты могут быть получены при размещении на продажу новых объектов недвижимости, когда дерево квадрантов 108 используется для хранения информации об объектах недвижимости. Полученные новые объекты размещаются в соответствующий элемент дерева квадрантов и одновременно в соответствующую часть односвязного списка. При этом такой вновь полученный объект может размещаться в односвязном списке 500 после маркера, относящегося к соответствующему элементу дерева квадрантов. Так, например, если во втором элементе первого уровня (узле 304) первоначально находилось только два объекта - объект 310 и объект 312, то при добавлении нового объекта - объекта 314, объект 314 может быть добавлен в самое начало соответствующей части (части 504) односвязного списка 500, то есть после соответствующего маркера 524.
Затем, способ переходит к этапу 1006.
Этап 1006 - размещение в односвязном списке первого, второго, третьего и четвертого маркеров второго уровня, относящихся соответственно к первому, второму, третьему и четвертому элементам второго уровня дерева квадрантов
На этапе 1006 осуществляется размещение в односвязном списке 500 первого, второго, третьего и четвертого маркеров второго уровня, относящихся соответственно к первому, второму, третьему и четвертому элементам второго уровня дерева квадрантов. Другими словами, речь идет о размещении и об определении позиции одного набора из четырех маркеров второго уровня в односвязном списке.
Размещение в односвязном списке 500 первого, второго, третьего и четвертого маркеров второго уровня, относящихся соответственно к первому, второму, третьему и четвертому элементам второго уровня дерева квадрантов, осуществляется по одному из трех сценариев: а) между двумя маркерами одного и того же (первого) уровня; б) между последним маркером первого уровня и первым маркером третьего уровня; в) после последнего маркера первого уровня (последнего маркера первого уровня на момент, непосредственно предшествующий размещению маркеров второго уровня). Этот сценарий определяется тем, является ли четвертый квадрант второго уровня листом дерева квадрантов или узлом дерева квадрантов, то есть имеются либо не имеются маркеры третьего уровня. Кроме того, этот сценарий может дополнительно определяться тем, что речь идет о размещении маркеров второго уровня после самого последнего элемента первого уровня и что последний элемент второго уровня является листом дерева квадрантов, то есть не имеет дочерних элементов и, как следствие, не будет иметься маркеров третьего уровня.
Так, в некоторых вариантах осуществления настоящей технологии, когда материнский квадрант первого уровня дерева квадрантов является четвертым (последним) элементом первого уровня дерева квадрантов и когда четвертый (последний) элемент второго элемента дерева квадрантов является листом дерева квадрантов (то есть не имеет дочерних элементов), размещение в односвязном списке 500 первого, второго, третьего и четвертого маркеров второго уровня осуществляется после четвертого маркера первого уровня, то есть после самого последнего маркера в односвязном списке 500 (по состоянию до размещения четырех маркеров второго уровня.
Пример такого размещения показан на Фиг. 7. На Фиг. 7 показан односвязный список 500 в том виде, как если бы первые три элемента первого уровня дерева квадрантов были бы листами дерева квадрантов и четвертый элемент первого уровня дерева квадрантов был бы узлом дерева квадрантов (то есть как это изображено на Фиг. 2), и как если бы все четыре элемента второго уровня дерева квадрантов были бы листами дерева квадрантов. То есть Фиг. 7 изображает дерево квадрантов 500 так, как если бы четвертый элемент второго уровня дерева квадрантов (элемент дерева квадрантов с вершинами в точках LNKD, как это показано на Фиг. 4) не имел бы дочерних элементов.
Фиг. 7 изображает односвязный список 500 с расположенными в нем первым маркером первого уровня 522, вторым маркером первого уровня 524, третьим маркером первого уровня 526 и четвертым маркером первого уровня 528.
Дополнительно, на Фиг. 7, после четвертого маркера первого уровня 528 изображены четыре маркера второго уровня: первый маркер второго уровня 702, второй маркер второго уровня 704, третий маркер второго уровня 706, четвертый маркер второго уровня 708.
Как можно видеть из Фиг.7, четыре маркера второго уровня (702, 704, 706 и 708) расположены после последнего маркера первого уровня (528).
Первый маркер второго уровня 702 является индикатором начала той части 510 односвязного списка 500, в которой располагаются объекты, расположенные в листе 318 второго уровня 206 дерева квадрантов 108.
Второй маркер второго уровня 704 является индикатором начала той части 512 односвязного списка, в которой располагаются объекты, расположенные в листе 320 второго уровня 206 дерева квадрантов 108.
Третий маркер второго уровня 706 является индикатором начала той части 514 односвязного списка, в которой располагаются объекты, расположенные в узле 322 второго уровня 206 дерева квадрантов 108.
Четвертый маркер второго уровня 708 является индикатором начала той части 516 односвязного списка, в которой располагаются объекты, расположенные в узле 324 второго уровня 206 дерева квадрантов 108.
В некоторых вариантах осуществления настоящей технологии, когда четвертый (последний) элемент второго элемента дерева квадрантов является узлом дерева квадрантов (то есть имеет дочерние элементы третьего уровня), размещение в односвязном списке 500 первого, второго, третьего и четвертого маркеров второго уровня осуществляется между соответствующим маркером первого уровня, являющимся маркером материнского элемента первого уровня, и первым маркером третьего уровня.
Пример такого размещения показан на Фиг. 8. Материнским элементом первого уровня на Фиг.8 является четвертый элемент первого уровня.
На Фиг. 8 показан односвязный список 500 в том виде, как если бы первые три элемента первого уровня дерева квадрантов 108 были бы листами дерева квадрантов 108 и четвертый элемент первого уровня дерева квадрантов был бы узлом дерева квадрантов 108, и как если бы первый элемент второго уровня дерева квадрантов 108 был бы листом дерева квадрантов 108 и второй, третий и четвертый элементы второго уровня 204 дерева квадрантов 108 были бы узлом дерева квадрантов (то есть как это изображено на Фиг. 2).
Итак, на Фиг. 8 показан односвязный список 500 с расположенными в нем первым маркером первого уровня 522, вторым маркером первого уровня 524, третьим маркером первого уровня 526, четвертым маркером первого уровня 528.
Дополнительно, на Фиг. 8, после маркера 528 первого уровня изображены четыре маркера второго уровня: первый маркер второго уровня 702, второй маркер второго уровня 704, третий маркер второго уровня 706, четвертый маркер второго уровня 708.
Первый маркер второго уровня 702 является индикатором начала той части 510 односвязного списка, в которой располагаются объекты, расположенные в листе 318 второго уровня 206 дерева квадрантов 108.
Второй маркер второго уровня 704 является индикатором начала той части 512 односвязного списка, в которой располагаются объекты, расположенные в листе 320 второго уровня 206 дерева квадрантов 108.
Третий маркер второго уровня 706 является индикатором начала той части 514 односвязного списка, в которой располагаются объекты, расположенные в узле 322 второго уровня 206 дерева квадрантов 108.
Четвертый маркер второго уровня 708 является индикатором начала той части 516 односвязного списка, в которой располагаются объекты, расположенные в узле 324 второго уровня 206 дерева квадрантов 108.
Такое расположение маркеров отражает структуру первого и второго уровней дерева квадрантов 108, изображенного на Фиг. 2. Как показано на Фиг. 2, из четырех элементов первого уровня 204 дерева квадрантов 108, только один элемент является узлом дерева квадрантов (узел 308).
Узел, по определению, является элементом дерева квадрантов, имеющим четыре дочерних элемента. Таким образом, мы можем видеть на Фиг. 7, что после каждого из первых трех маркеров первого уровня 522, 524 и 526 не имеется маркеров второго уровня 206 дерева квадрантов 108, однако такие четыре маркера второго уровня имеются после четвертого маркера первого уровня 528. Наличие маркеров второго уровня 702, 704, 706 и 708 второго уровня 206 дерева квадрантов 108 объясняется тем, что четвертый маркер первого уровня 528 первого уровня 204 дерева квадрантов 108 относится к узлу 308, имеющему четыре дочерних элемента: один лист 318 и три узла 320, 322 и 324.
Кроме того, три элемента второго уровня 206 дерева квадрантов 108 имеют дочерние элементы третьего уровня 208 дерева квадрантов 108, а именно дочерние элементы дерева квадрантов 108 имеют узлы 320, 322 и 324. Соответственно, за тремя маркерами второго уровня 704, 706 и 708 расположены три комплекта маркеров третьего уровня. Маркеры третьего уровня, расположенные после маркеров второго уровня 704 и 706, не пронумерованы. Маркеры третьего уровня, расположенные за маркером второго уровня 708, пронумерованы как первый маркер третьего уровня 802, второй маркер третьего уровня 804, третий маркер третьего уровня 806 и четвертый маркер третьего уровня 808.
Соответственно, из Фиг. 8 видно, что когда четвертый (последний) элемент второго элемента дерева квадрантов является узлом дерева квадрантов (то есть имеет дочерние элементы третьего уровня), размещение в односвязном списке 500 первого, второго, третьего и четвертого маркеров второго уровня осуществляется между соответствующим маркером первого уровня, являющимся маркером материнского элемента первого уровня, и первым маркером третьего уровня. В данном случае, четыре маркера второго уровня (702, 704, 706 и 708) расположены между четвертым маркером первого уровня 528 и первым маркером третьего уровня 802.
В некоторых вариантах осуществления настоящей технологии, когда четвертый (последний) элемент второго элемента дерева квадрантов является листом дерева квадрантов (то есть не имеет дочерних элементов третьего уровня) и когда материнский квадрант первого уровня дерева квадрантов не является четвертым (последним) элементом первого уровня дерева квадрантов, размещение в односвязном списке 500 первого, второго, третьего и четвертого маркеров второго уровня осуществляется между соответствующим маркером первого уровня, являющимся маркером материнского элемента первого уровня, и непосредственно следующим за ним другим маркером того же уровня.
Такое расположение обусловлено тем фактом, что маркер материнского элемента первого уровня дерева квадрантов, предшествующий набору маркеров второго уровня, не является последним маркером первого уровня, и тем, что за последним маркером второго уровня не будут расположены маркеры третьего уровня, так как четвертый элемент дерева второго уровня дерева квадрантов является листом дерева квадрантов.
Затем способ переходит к этапу 1008.
Этап 1008 - размещение, в односвязном списке, объектов, хранящихся в любом из: первом, втором, третьем и четвертом элементе второго уровня дерева квадрантов, соответственно после первого, второго, третьего и четвертого маркера второго уровня
На этапе 1008 сервер 102 осуществляет размещение в односвязном списке 500 объектов, хранящихся в элементах второго уровня дерева квадрантов 108.
Размещение в односвязном списке 500 объектов, хранящихся в элементах второго уровня дерева квадрантов 108, осуществляется после соответствующих маркеров второго уровня, то есть так, как это показано на Фиг. 9.
На Фиг. 9, вслед за Фиг. 6 и Фиг. 7, показан в развитии процесс размещения объектов в односвязном списке 500.
Как было показано на Фиг. 4, один из четырех элементов второго уровня 206 дерева квадрантов 108 не содержит в себе объектов (лист 318), а три других элемента второго уровня 206 дерева квадрантов 108 содержат в себе объекты (узлы 320, 322 и 324).
Так, узел 320 содержит в себе один объект 326.
Узел 322 содержит в себе два объекта - объект 328 и объект 330. Узел 324 содержит в себе один объект - объект 332.
Все эти объекты - 326, 328, 330 и 332 - также размещены в односвязном списке 500.
Соответственно, после первого маркера второго уровня 702, то есть в части 510 односвязного списка 500, нет объектов, так как лист 318 не содержит объектов.
После второго маркера второго уровня 704, то есть в части 512 односвязного списка 500, расположен объект 326, то есть единственный объект, расположенный в узле 320.
После третьего маркера второго уровня 706, то есть в части 514 односвязного списка 500, расположены объекты 328 и 330, то есть все объекты, расположенные в узле 322.
После четвертого маркера второго уровня 708, то есть в части 516 односвязного списка 500, расположен объект 332, то есть объект, расположенный в узле 324.
Объекты 310, 312 и 314, размещенные во втором элементе первого уровня 204 дерева квадрантов 108, расположены после второго маркера первого уровня 524, то есть в части 504 односвязного списка 108.
Как можно увидеть на Фиг.9, объект 316 по-прежнему размещен в части 508 односвязного списка 500, то есть в той его части, которая содержит объекты, расположенные в узле 308, являющемся узлом первого уровня дерева квадрантов 108.
Как будет понятно специалистам в данной области техники, объекты, помещенные в односвязный список 500, помещаются туда в качестве узлов односвязного списка. Это означает, что объекты являются не только носителями определенной информации, присущей собственно объекту, но и содержат в себе ссылку на следующий узел односвязного списка. При этом следующим узлом односвязного списка 500 может быть как другой маркер, так и объект. В том виде, как это изображено на Фиг. 9, цепочка ссылок выглядит следующим образом: первый маркер первого уровня 522 → второй маркер первого уровня 524 → объект 314 → объект 312 → объект 310 → третий маркер первого уровня 526 → четвертый маркер первого уровня 528 → объект 316 → первый маркер второго уровня 702 → второй маркер второго уровня 704 → объект 324 → третий маркер второго уровня 706 → объект 330 → объект 328 → четвертый маркер второго уровня 708 → объект 332 → первый маркер третьего уровня 802 → второй маркер третьего уровня 804 → третий маркер третьего уровня 806 → четвертый маркер третьего уровня 808.
В некоторых вариантах осуществления настоящей технологии, способ предусматривает получение новых объектов. Полученные новые объекты размещаются в соответствующий элемент дерева квадрантов 108 и одновременно в соответствующую часть односвязного списка 500. При этом такой вновь полученный объект может размещаться в односвязном списке 500 после маркера, относящегося к соответствующему элементу дерева квадрантов. Так, например, если в третьем элементе второго уровня (узле 322) первоначально находился только один объект - объект 328, то при добавлении нового объекта - объекта 330, объект 330 добавляется в самое начало соответствующей части (части 514) односвязного списка 500, то есть после соответствующего маркера 706.
В данном варианте осуществления настоящей технологии, все объекты, размещаемые в односвязном списке 500 (объекты 310, 312, 314, 316, 326, 328, 330 и 332), являются тегами графических объектов. Это значит, что определенной информацией, присущей собственно объекту, является ссылка на запись в базе данных 106, где хранится подробная информация о графическом объекте.
В некоторых вариантах осуществления настоящей технологии, множество объектов в определенном элементе второго уровня 206 дерева квадрантов 108 может быть постоянным. В этом случае, сервер 102 может преобразовать ту часть односвязного списка 500, в которой размещено это множество объектов, в массив, причем размерность указанного массива равна количеству объектов в указанном множестве объектов. Соответственно, в односвязном списке 500 вместо соответствующего маркера второго уровня будет помещен соответствующий маркер массива.
Как будет понятно специалистам в данной области техники, объекты, помещенные в односвязный список 500, помещаются туда в качестве узлов односвязного списка. Это означает, что объекты являются не только носителями определенной информации, присущей собственно объекту, но и содержат в себе ссылку на следующий узел односвязного списка. Соответственно, маркер массива содержит 1) ссылку на массив в базе данных 106, и 2) ссылку на следующий узел односвязного списка 500.
Обратимся к примеру, проиллюстрированному на Фиг. 12. Узел 322, представленный на Фиг. 4, содержит в себе постоянный неизменяемый набор объектов 328 и 330. Таким образом, сервер 102 может преобразовать часть 514 односвязного списка 500, представленного на Фиг. 9, в массив 1204, схематически изображенный на Фиг. 12. Массив 1204 содержит в себе объекты 328 и 330, и массив 1204 хранится в базе данных 106 отдельно от односвязного списка 500. В односвязном списке 500 при этом маркер 706 третьего элемента второго уровня дерева квадрантов (см. Фиг. 9) заменяется на соответствующий маркер массива 1202 (см. Фиг. 12). Маркер 1202 является одновременно носителем определенной информации, присущей собственно объекту (ссылка на массив 1204), и содержит в себе ссылку на следующий узел односвязного списка 500, являющийся в данном примере маркером 708.
Затем способ 1000 завершается.
На Фиг. 11 показана блок-схема способа 1100, выполняемого на сервере 102, изображенном на Фиг. 1, выполняемого в соответствии с вариантами осуществления настоящей технологии, не ограничивающими ее объем.
В вариантах осуществления настоящей технологии способ 1100 может выполняться на сервере 102, изображенном на Фиг. 1. Для этого сервер 102 включает в себя носитель информации 104, хранящий машиночитаемые инструкции, при выполнении которых сервер 102 выполняет этапы способа 1100. Однако, как это будет понятно специалистам в данной области техники, метод 1100 может быть осуществлен на других серверах.
Этап 1102 - получение запроса пользователя 111 на предоставление пользователю 111 списка объектов.
На этапе 1102, сервер 102 по сети 110 передачи данных получает с электронного устройства 112 запрос пользователя 111 на предоставление ему списка объектов.
Представим, что база данных 106, хранящаяся на сервере 102, может быть базой данных объектов недвижимости, расположенных в Канаде, предлагаемых к продаже. Пользователь 111 заинтересован в покупке объектов недвижимости в районе аэропорта Пьер-Эллиот Трюдо рядом с Монреалем. Пользователь 111 на электронном устройстве 112 запускает браузер 116 и вводит в адресной строке браузера 116 URL сайта, с которого можно осуществлять запросы к базе данных 106, расположенной на сервере 102. На сайте пользователь 111 может видеть всю карту Канады и меню, позволяющее выбрать интересующий регион. Таким образом, пользователь 111 может ограничить свой поиск путем выбора соответствующего фрагмента пространства. В данном случае, соответствующий фрагмент пространства может быть выбран двумя способами. Первый способ заключается в последовательном выборе в меню интересующего фрагмента пространства. Так, например, если пользователь 111 заинтересован в нахождении объектов недвижимости в районе аэропорта Пьер-Эллиот Трюдо рядом с Монреалем, он может сначала выбрать провинцию (Квебек), затем агломерацию (остров Монреаль), затем муниципалитет (Дорваль). Второй способ заключается в приближении карты (zoom in) с одновременным центрированием в районе поиска и затем выделении фрагмента пространства мышью в районе аэропорта Пьер-Эллиот Трюдо. Как будет понятно специалистам в данной сфере, выбор интересующего участка пространства может быть осуществлен также любым иным способом.
Затем способ 1100 переходит к этапу 1104.
Этап 1104 - извлечение списка объектов из базы данных 106
В ответ на получение запроса пользователя 111 сервер 102 может определить в базе данных 106 самый мелкий квадрант из всех квадрантов, которые территориально охватывают весь фрагмент пространства, выбранный пользователем 111. Допустим, в качестве примера, что таковым квадрантом является узел 308 дерева квадрантов 108, изображенный на Фиг. 2. Узел 308 дерева квадрантов 108 имеет четыре дочерних элемента, в которых также могут содержаться объекты, относящиеся к частям территории, покрываемой узлом 308.
Далее, сервер 102 определяет, что узел 308 содержит в себе указатель на маркер в односвязном списке 108, относящийся к этому элементу дерева квадрантов, а именно - указатель на маркер 528 (см. Фиг. 9).
Способ 1100 может предусматривать предоставление пользователю 111 списка объектов, расположенных в указанном элементе дерева квадрантов и во всех указанных четырех дочерних элементах второго уровня дерева квадрантов, путем предоставления пользователю объектов, расположенных в односвязном списке 500 в определенном промежутке, причем указанный промежуток определяется как один из: (1) промежуток, начиная с маркера первого уровня, относящегося к данному элементу дерева квадрантов, и до следующего маркера первого уровня, когда данный элемент дерева квадрантов является одним из: первым, вторым и третьим элементом первого уровня дерева квадрантов; или (2) промежуток, начиная с четвертого маркера первого уровня, относящегося к данному элементу дерева квадрантов, и заканчивая последним объектом в односвязном списке, включая этот последний объект, когда данный элемент дерева квадрантов является четвертым элементом первого уровня дерева квадрантов. Другими словами, выбор объектов для предоставления пользователю 111 осуществляется из элемента первого уровня дерева квадрантов, охватывающего весь выбранный фрагмент пространства, и во всех дочерних элементах этого элемента первого уровня дерева квадрантов.
В вышеприведенном примере, узел 308 является четвертым (последним) элементом первого уровня дерева квадрантов 108. Таким образом, сервер 102 будет выбирать объекты из промежутка начиная с четвертого маркера первого уровня 528 и заканчивая последним объектом в односвязном списке, включая этот последний объект. То есть будут выбраны объекты 316, 326, 330, 328, 332 из односвязного списка 500 (см. Фиг.9). Сравнивая с Фиг.4, можно увидеть, что объекты 316, 326, 330, 328 и 332 - это все объекты, расположенные в пределах квадрата с вершинами HIGD, то есть все объекты, содержащиеся в узлах 308 (первый уровень), 318, 320, 322 и 324 (второй уровень). Таким образом, можно убедиться в том, что сервер 102 выберет из односвязного списка 500 те же самые объекты, которые он бы выбрал из дерева квадрантов. Выбор объектов из односвязного списка является менее ресурсозатратным, чем выбор объектов из дерева квадрантов. Таким образом, варианты осуществления настоящей технологии позволяют осуществлять экономию ресурсов сервера 102.
Поскольку объекты 316, 326, 330, 328, 332 из односвязного списка 500 являются тегами графических объектов, то сервер 102 дополнительно получит из базы данных 106 подробную информацию об объектах недвижимости, которые обозначены в односвязном списке 500 тегами графических объектов. К такой дополнительной информации могут относиться фотографии, подробное текстовое описание, вид права на объект недвижимости, площадь, годовой размер налогов, цена продажи, и так далее.
В альтернативных вариантах осуществления настоящей технологии, множество объектов в определенном элементе второго уровня может быть постоянным. В этом случае, сервер 102 может преобразовать ту часть односвязного списка, в которой размещено это множество объектов, в массив, причем размерность указанного массива равна количеству объектов в указанном множестве объектов. Соответственно, в односвязном списке 500 вместо соответствующего маркера второго уровня будет помещен соответствующий маркер соответствующего массива.
Как будет понятно специалистам в данной области техники, объекты, помещенные в односвязный список 500, помещаются туда в качестве узлов односвязного списка. Это означает, что объекты являются не только носителями определенной информации, присущей собственно объекту, но и содержат в себе ссылку на следующий узел односвязного списка. Соответственно, маркер массива содержит 1) ссылку на массив в базе данных 106, и 2) ссылку на следующий узел односвязного списка.
В примере, представленном на Фиг. 12, узел 322, представленный на Фиг. 4, содержит в себе постоянный неизменяемый набор объектов 328 и 330. Таким образом, сервер 102 может преобразовать часть 514 односвязного списка 500, представленного на Фиг. 9, в массив 1204, схематически изображенный на Фиг. 12. Массив 1204 содержит в себе объекты 328 и 330 и хранится в базе данных 106 отдельно от односвязного списка 500. В односвязном списке 500 при этом маркер 706 третьего элемента второго уровня дерева квадрантов (см. Фиг. 9) заменяется на соответствующий маркер массива 1202 (см. Фиг. 12). Маркер 1202 является одновременно носителем определенной информации, присущей собственно объекту (ссылка на массив 1204), и содержит в себе ссылку на следующий узел односвязного списка, являющийся в данном примере маркером 708.
В случае, когда часть односвязного списка преобразована сервером 102 в массив, извлечение объектов из базы данных 106 может осуществляться следующим способом.
Сервер 102 получает и предоставляет пользователю список объектов, расположенных в соответствующем элементе первого уровня 204 дерева квадрантов 108 и во всех дочерних элементах второго уровня дерева квадрантов, путем предоставления пользователю объектов, расположенных в: (i) односвязном списке 500 в определенном промежутке, причем указанный промежуток определяется как один из: (а) промежуток, начиная с маркера первого уровня, относящегося к соответствующему элементу первого уровня дерева квадрантов, и до следующего маркера первого уровня, когда n-элемент дерева квадрантов является одним из: первым, вторым и третьим элементом первого уровня дерева квадрантов; (б) промежуток, начиная с маркера первого уровня, относящегося к четвертому элементу дерева квадрантов, и заканчивая последним объектом в односвязном списке, включая этот последний объект, когда соответствующий элемент дерева квадрантов является четвертым элементом первого уровня дерева квадрантов; и (ii) во всех массивах, созданных в результате преобразования по меньшей мере одного из дочерних элементов соответствующего элемента первого уровня дерева квадрантов, содержащего постоянное множество объектов. Другими словами, выбор объектов для предоставления пользователю 111 осуществляется из элемента первого уровня дерева квадрантов, охватывающего весь выбранный фрагмент пространства, и во всех дочерних элементах этого элемента первого уровня дерева квадрантов.
Поясним на примере с использованием Фиг. 12.
В вышеприведенном примере, пользователь 111 был намерен найти объекты недвижимости, выставленные на продажу в районе аэропорта Пьер-Эллиот Трюдо поблизости от Монреаля. Допустим, что выбранный фрагмент пространства соответствует узлу 308 дерева квадрантов 108. Узел 308 является четвертым (последним) элементом первого уровня дерева квадрантов 108. Таким образом, сервер 102 будет выбирать объекты из промежутка начиная с четвертого маркера первого уровня 528 и заканчивая последним объектом в односвязном списке, включая этот последний объект, а также из массива 1204, созданного в результате преобразования сервером 102 части 514 односвязного списка, в которой располагались объекты, расположенные в узле 322 второго уровня 206 дерева квадрантов 108. То есть будут выбраны объекты 316, 326, 332 из односвязного списка 500 и объекты 328 и 330 из массива 1204 (см. Фиг. 12). Итого, будут выбраны объекты 316, 326, 330, 328, 332. Сравнивая с Фиг. 4, можно увидеть, что объекты 316, 326, 330, 328 и 332 - это все объекты, расположенные в пределах квадрата с вершинами HIGD, то есть все объекты, содержащиеся в узлах 308 (первый уровень), 318, 320, 322 и 324 (второй уровень).
Поскольку объекты 316, 326, 330, 328, 332 являются тегами графических объектов, то сервер 102 дополнительно получит из базы данных 106 подробную информацию об объектах недвижимости, которые обозначены в односвязном списке 500 либо в массиве 1204 тегами графических объектов. К такой дополнительной информации могут относиться фотографии, подробное текстовое описание, вид права на объект недвижимости, площадь, годовой размер налогов, цена продажи и так далее.
Затем способ 1100 переходит к этапу 1106.
Этап 1106 - предоставление списка объектов пользователю 111.
На этапе 1106, сервер 102 передает по сети 110 передачи данных список объектов с относящейся к ним информацией пользователю 111 на его электронное устройство 112 для отображения на дисплее 118. Передача осуществляется по сети 110 передачи данных на электронное устройство 112 пользователя 111 для отображении на дисплее 118.
Затем способ 1100 завершается.
В некоторых вариантах осуществления настоящей технологии, первым уровнем 204 дерева квадрантов 108 является любой уровень дерева квадрантов 108, начиная с корневого уровня дерева квадрантов включительно, и вторым уровнем дерева квадрантов является более низкий уровень дерева квадрантов, который непосредственно следует за первым уровнем дерева квадрантов. Все или некоторые варианты воплощения настоящей технологии, описанные выше, могут быть применены к любым уровням дерева квадрантов 108. Так, например, если за первым уровнем дерева квадрантов принять четырнадцатый уровень дерева квадрантов, считая от корневого уровня дерева квадрантов, то вторым уровнем дерева квадрантов будет пятнадцатый уровень дерева квадрантов, считая от корневого уровня, третьим уровнем дерева квадрантов будет шестнадцатый уровень дерева квадрантов, считая от корневого уровня, и так далее. Таким образом, описанная выше технология не ограничивается случаями, когда первым уровнем дерева квадрантов 108 является корневой уровень дерева квадрантов 108, а вторым и третьим уровнями дерева квадрантов 108 являются соответственно второй и третий уровни дерева квадрантов, считая от корневого уровня дерева квадрантов 108.
В рамках настоящего описания следует понимать, что везде, где указано получение данных от любого электронного устройства и/или от любого почтового сервера, и/или от любого другого сервера, может использоваться получение электронного или иного сигнала от соответствующего электронного устройства (сервера, почтового сервера), а отображение на экране устройства может быть реализовано как подача сигнала экрану, в котором содержится определенная информация, которая в дальнейшем может быть интерпретирована определенными образами и по меньшей мере частично отображена на экране электронного устройства. Подача и получение сигнала не везде указаны в рамках настоящего описания для упрощения изложения и облегчения понимания настоящего решения. Сигналы могут передаваться оптическими методами (по волоконно-оптической связи, например), электронными методами (по проводной или беспроводной связи), механическими методами (передача давления, температуры и/или других физических параметров посредством которых возможна передача сигнала).
Изобретение относится к области хранения пространственных объектов. Техническим результатом является снижение нагрузки на сервер при выборе объектов благодаря использованию односвязного списка. В способе оптимизации обработки запроса организуют в односвязный список множество объектов, содержащихся в дереве квадрантов, путем размещения в односвязном списке первого, второго, третьего и четвертого маркеров первого уровня, относящихся к первому, второму, третьему и четвертому элементам первого уровня дерева квадрантов, и размещения в односвязном списке объектов, хранящихся в любом из: первом, втором, третьем и четвертом элементе первого уровня дерева квадрантов, после первого, второго, третьего и четвертого маркера первого уровня. Передают запрос пользователя на предоставление пользователю списка объектов, содержащихся в базе данных. В ответ на запрос пользователя извлекают из базы данных и предоставляют пользователю список объектов, расположенных в односвязном списке. 2 н. и 19 з.п. ф-лы, 12 ил.
1. Реализуемый на компьютере способ оптимизации обработки запроса, включающий: организацию в односвязный список множества объектов, содержащихся в дереве квадрантов, включающем в себя элементы дерева квадрантов, каждый из которых является одним из: узел дерева квадрантов и лист дерева квадрантов, упомянутая организация множества объектов включает:
- размещение в односвязном списке первого, второго, третьего и четвертого маркеров первого уровня, относящихся соответственно к первому, второму, третьему и четвертому элементам первого уровня дерева квадрантов;
- размещение в односвязном списке объектов, хранящихся в любом из: первом, втором, третьем и четвертом элементе первого уровня дерева квадрантов, соответственно после первого, второго, третьего и четвертого маркера первого уровня;
передачу запроса пользователя на предоставление пользователю списка объектов, содержащихся в базе данных;
в ответ на запрос пользователя извлечение из базы данных и предоставление пользователю списка объектов, расположенных в односвязном списке.
2. Способ по п. 1, в котором n-элемент дерева квадрантов, являющийся одним из: первый элемент первого уровня дерева квадрантов, второй элемент первого уровня дерева квадрантов, третий элемент первого уровня дерева квадрантов и четвертый элемент первого уровня дерева квадрантов, включает в себя четыре элемента второго уровня дерева квадрантов, в способе дополнительно выполняют:
- размещение в односвязном списке первого, второго, третьего и четвертого маркеров второго уровня, относящихся соответственно к первому, второму, третьему и четвертому элементам второго уровня дерева квадрантов, после одного из:
- маркера первого уровня, относящегося к n-элементу дерева квадрантов, и до непосредственно следующего за ним первого маркера третьего уровня, когда четвертый элемент второго уровня дерева квадрантов является узлом дерева квадрантов;
- маркера первого уровня, относящегося к n-элементу дерева квадрантов, и до непосредственно следующего за ним другого маркера того же уровня, когда n-элемент первого уровня дерева квадрантов является одним из: первым, вторым и третьим элементом первого уровня дерева квадрантов, и когда четвертый элемент второго уровня дерева квадрантов является листом дерева квадрантов;
- четвертого маркера первого уровня, когда n-элемент первого уровня дерева квадрантов является четвертым элементом первого уровня дерева квадрантов и когда четвертый элемент второго уровня дерева квадрантов является листом дерева квадрантов;
- размещение, в односвязном списке, объектов, хранящихся в любом из: первом, втором, третьем и четвертом элементе второго уровня дерева квадрантов, соответственно после первого, второго, третьего и четвертого маркера второго уровня.
3. Способ по любому из пп. 1-2, в котором дополнительно выполняют:
- получение нового объекта,
- размещение указанного нового объекта в o-элементе дерева квадрантов,
- размещение указанного нового объекта в односвязном списке после маркера, относящегося к o-элементу дерева квадрантов.
4. Способ по любому из пп. 1-2, в котором объектом является тег графического объекта.
5. Способ по любому из пп. 1-2, в котором элемент дерева квадрантов дополнительно включает в себя указатель на маркер в односвязном списке, относящийся к этому элементу дерева квадрантов.
6. Способ по любому из пп. 1-2, в котором n-элемент дерева квадрантов, являющийся материнским элементом, имеет четыре элемента второго уровня дерева квадрантов, являющихся дочерними элементами, способ, в котором дополнительно получают запрос пользователя на предоставление пользователю списка объектов, расположенных в указанном n-элементе дерева квадрантов и во всех указанных четырех дочерних элементах второго уровня дерева квадрантов.
7. Способ по п. 6, в котором дополнительно определяют n-элемент дерева квадрантов как соответствующий соответствующему фрагменту пространства, выбранному пользователем, причем упомянутое определение осуществляют путем выбора сервером самого мелкого элемента дерева квадрантов из всех элементов дерева квадрантов, территориально охватывающих выбранный пользователем фрагмент пространства полностью.
8. Способ по п. 7, в котором дополнительно предоставляют пользователю список объектов, расположенных в указанном n-элементе дерева квадрантов и во всех указанных четырех дочерних элементах второго уровня дерева квадрантов, путем предоставления пользователю объектов, расположенных в односвязном списке в определенном промежутке, причем указанный промежуток определяется как один из:
- промежуток, начиная с маркера первого уровня, относящегося к n-элементу дерева квадрантов, и до следующего маркера первого уровня, когда n-элемент дерева квадрантов является одним из: первым, вторым и третьим элементом первого уровня дерева квадрантов;
- промежуток, начиная с четвертого маркера первого уровня, относящегося к n-элементу дерева квадрантов, и заканчивая последним объектом в односвязном списке, включая этот последний объект, когда n-элемент дерева квадрантов является четвертым элементом первого уровня дерева квадрантов.
9. Способ по любому из пп. 1-2, в котором множество объектов в любом из элементов второго уровня дерева квадрантов является постоянным, в способе дополнительно выполняют преобразование той части односвязного списка, в которой размещено это множество объектов, в массив, причем размерность указанного массива равна количеству объектов в указанном множестве объектов и причем указанный определенный элемент дерева квадрантов второго уровня включает в себя множество индексов, каждый из которых соответствует определенному объекту из указанного множества объектов.
10. Способ по п. 7, в котором множество объектов в любом из элементов второго уровня дерева квадрантов является постоянным, в способе дополнительно выполняют преобразование той части односвязного списка, в которой размещено это множество объектов, в массив, причем размерность указанного массива равна количеству объектов в указанном множестве объектов и причем указанный определенный элемент дерева квадрантов второго уровня включает в себя множество индексов, каждый из которых соответствует определенному объекту из указанного множества объектов.
11. Способ по п. 10, в котором по меньшей мере в одном из дочерних элементов n-элемента дерева квадрантов множество объектов является постоянным и в котором дополнительно предоставляют пользователю список объектов, расположенных в указанном n-элементе первого уровня дерева квадрантов и во всех указанных четырех дочерних элементах второго уровня дерева квадрантов, путем предоставления пользователю объектов, расположенных в:
- односвязном списке в определенном промежутке, причем указанный промежуток определяется как один из: промежуток, начиная с маркера первого уровня, относящегося к n-элементу дерева квадрантов, и до следующего маркера первого уровня, когда n-элемент дерева квадрантов является одним из: первым, вторым и третьим элементом первого уровня дерева квадрантов; промежуток, начиная с маркера первого уровня, относящегося к n-элементу дерева квадрантов, и заканчивая последним объектом в односвязном списке, включая этот последний объект, когда n-элемент дерева квадрантов является четвертым элементом первого уровня дерева квадрантов; и
- во всех массивах, созданных в результате преобразования по меньшей мере одного из дочерних элементов n-элемента дерева квадрантов, содержащего постоянное множество объектов.
12. Способ по любому из пп. 1-2, в котором первым уровнем дерева квадрантов является любой уровень дерева квадрантов, начиная с корневого уровня дерева квадрантов включительно, и вторым уровнем дерева квадрантов является более низкий уровень дерева квадрантов, который непосредственно следует за первым уровнем дерева квадрантов.
13. Способ по любому из пп. 10-11, в котором первым уровнем дерева квадрантов является любой уровень дерева квадрантов, начиная с корневого уровня дерева квадрантов включительно, и вторым уровнем дерева квадрантов является более низкий уровень дерева квадрантов, который непосредственно следует за первым уровнем дерева квадрантов.
14. Компьютер для оптимизации обработки запроса, включающий в себя процессор, выполненный с возможностью:
организации в односвязный список множества объектов, содержащихся в дереве квадрантов, включающем в себя элементы дерева квадрантов, каждый из которых является одним из: узел дерева квадрантов и лист дерева квадрантов, упомянутая организация множества объектов включает:
- размещения в односвязном списке первого, второго, третьего и четвертого маркеров первого уровня, относящихся соответственно к первому, второму, третьему и четвертому элементам первого уровня дерева квадрантов;
- размещения в односвязном списке объектов, хранящихся в любом из: первом, втором, третьем и четвертом элементе первого уровня дерева квадрантов, соответственно после первого, второго, третьего и четвертого маркера первого уровня;
получения запроса пользователя на предоставление пользователю списка объектов, содержащихся в базе данных;
в ответ на запрос пользователя извлечение сервером из базы данных и предоставление пользователю списка объектов, расположенных в односвязном списке.
15. Компьютер по п. 14, в котором процессор дополнительно выполнен с возможностью:
- размещения в односвязном списке первого, второго, третьего и четвертого маркеров второго уровня, относящихся соответственно к первому, второму, третьему и четвертому элементам второго уровня дерева квадрантов, после одного из:
- маркера первого уровня, относящегося к n-элементу дерева квадрантов, и до непосредственно следующего за ним первого маркера третьего уровня, когда четвертый элемент второго уровня дерева квадрантов является узлом дерева квадрантов;
- маркера первого уровня, относящегося к n-элементу дерева квадрантов, и до непосредственно следующего за ним другого маркера того же уровня, когда n-элемент первого уровня дерева квадрантов является одним из: первым, вторым и третьим элементом первого уровня дерева квадрантов, и когда четвертый элемент второго уровня дерева квадрантов является листом дерева квадрантов;
- четвертого маркера первого уровня, когда n-элемент первого уровня дерева квадрантов является четвертым элементом первого уровня дерева квадрантов и когда четвертый элемент второго уровня дерева квадрантов является листом дерева квадрантов;
- размещения, в односвязном списке, объектов, хранящихся в любом из: первом, втором, третьем и четвертом элементе второго уровня дерева квадрантов, соответственно после первого, второго, третьего и четвертого маркера второго уровня.
16. Компьютер по любому из пп. 14-15, в котором процессор дополнительно выполнен с возможностью:
- получения нового объекта,
- размещения указанного нового объекта в o-элементе дерева квадрантов,
- размещения указанного нового объекта в односвязном списке после маркера, относящегося к o-элементу дерева квадрантов.
17. Компьютер по любому из пп. 14-15, в котором процессор дополнительно выполнен с возможностью получения запроса пользователя на предоставление пользователю списка объектов, расположенных в указанном n-элементе дерева квадрантов и во всех указанных четырех дочерних элементах второго уровня дерева квадрантов.
18. Компьютер по п. 17, в котором процессор дополнительно выполнен с возможностью определения n-элемента дерева квадрантов как соответствующего соответствующему фрагменту пространства, выбранному пользователем.
19. Компьютер по любому из пп. 14-15, в котором процессор дополнительно выполнен с возможностью преобразования той части односвязного списка, в которой размещено множество объектов, в массив, причем размерность указанного массива равна количеству объектов в указанном множестве объектов.
20. Компьютер по п. 18, в котором процессор дополнительно выполнен с возможностью преобразования той части односвязного списка, в которой размещено множество объектов, в массив, причем размерность указанного массива равна количеству объектов в указанном множестве объектов.
21. Компьютер по п. 20, в котором процессор дополнительно выполнен с возможностью предоставления пользователю списка объектов, расположенных в указанном n-элементе первого уровня дерева квадрантов и во всех указанных четырех дочерних элементах второго уровня дерева квадрантов.
| Способ защиты переносных электрических установок от опасностей, связанных с заземлением одной из фаз | 1924 |
|
SU2014A1 |
| US 5319743 A, 07.06.1994 | |||
| Способ и приспособление для нагревания хлебопекарных камер | 1923 |
|
SU2003A1 |
| Изложница с суживающимся книзу сечением и с вертикально перемещающимся днищем | 1924 |
|
SU2012A1 |
| СПОСОБ КОДИРОВАНИЯ И ДЕКОДИРОВАНИЯ ДАННЫХ ТРЕХМЕРНЫХ ОБЪЕКТОВ И УСТРОЙСТВО ДЛЯ ЕГО ОСУЩЕСТВЛЕНИЯ | 2003 |
|
RU2267161C2 |
| СПОСОБ ПОДГОТОВКИ ОТОБРАЖЕНИЯ ДАННЫХ В СЕРВЕРАХ (ВАРИАНТЫ) И МАШИНОЧИТАЕМЫЙ НОСИТЕЛЬ | 2010 |
|
RU2445705C2 |
