СПОСОБ И ЭЛЕКТРОННОЕ УСТРОЙСТВО ДЛЯ СОЗДАНИЯ ИНДЕКСА СЕГМЕНТОВ МНОГОУГОЛЬНИКОВ Российский патент 2020 года по МПК G06F16/51 G06F16/587 

ОБЛАСТЬ ТЕХНИКИ

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

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

[02] Задача о принадлежности точки многоугольнику широко используется во множестве сфер, включая системы географического позиционирования (GPS), компьютерные игры, компьютерное зрение, приложения по сопоставлению, системы автоматизированного проектирования и так далее. Некоторые решения этой задачи продиктованы требованиями определения относительного положения данного пользовательского устройства по отношению к географической области или региону.

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

[04] Следовательно, желательные улучшения способов решения задачи о принадлежности точки многоугольнику.

РАСКРЫТИЕ ТЕХНОЛОГИИ

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

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

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

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

[09] Первым объектом настоящей технологии является способ создания индекса сегментов по меньшей мере одного многоугольника, определяющего границы соответствующей географической области на карте. Способ выполняется электронным устройством. Электронное устройство обладает доступом к базе данных для размещения индекса. Способ включает в себя сегментирование электронным устройством, опорной зоны на опорном уровне на зоны первого уровня на первом уровне. Опорная зона покрывает по меньшей мере часть карты, которая включает в себя все сегменты по меньшей мере одного многоугольника. Опорная зона является родительской зоной для зон первого уровня. Способ включает в себя, в ответ на то, что по меньшей мере один сегмент, который по меньшей мере частично расположен в более чем одной зоне первого уровня, индексирование электронным устройством, по меньшей мере одного сегмента как связанного с опорной зоной. Индексирование включает в себя сохранение, электронным устройством, данных о по меньшей мере одном сегменте, связанном с опорной зоной, поскольку сегменты, которые расположены только на зоне первого уровня, индексируются связанными с зонами, отличными от опорной зоны. Способ включает в себя, до достижения конечных условий, итерационно: (i) сегментирование электронным устройством данной зоны на данном уровне на зоны последующих уровней, причем данная зона является родительской зоной для соответствующих зон последующих уровней; и (ii) в ответ то, что по меньшей мере один другой сегмент по меньшей мере частично расположен внутри более чем одной соответствующей зоны последующего уровня, индексирование электронным устройством по меньшей мере одного другого сегмента как связанного с данной зоной. Индексирование включает в себя: создание электронным устройством геомаркера для данной зоны, причем геомаркер указывает на (i) расположение данной зоны в соответствующей родительской зоне, причем соответствующая родительская зона данной зоны находится на предыдущем уровне по отношению к данному, и (ii) географическую связь между данной зоной и другими дочерними зонами по отношению к соответствующей родительской зоне. Индексирование также включает в себя сохранение электронным устройством данных по меньшей мере об одном другом сегменте, связанном с геомаркером данной зоны. Сегменты, которые находятся внутри только одной соответствующей зоны последующего уровня, индексируются как связанные с дочерними зонами соответствующей одной из только одной зоны последующего уровня.

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

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

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

[13] В некоторых вариантах осуществления способа, способ далее включает в себя получение электронным устройством, указания на местоположение целевой точки на карте. Способ далее включает в себя получение доступа электронным устройством, к индексу для определения: целевой зоны низшего уровня, соответствующей местоположению целевой точки на основе геомаркеров зоны в индексе; и других целевых зон, которые (i) по меньшей мере частично расположены вдоль заранее определенного направления на карте от целевой зоны низшего уровня и (ii) по меньшей мере частично выровнены с целевой зоной низшего уровня в заранее определенном направлении, на основе геомаркеров зон, хранящихся в индексе. Заранее определенное направление было определено на основе географической связи между дочерними зонами данной родительской зоны. Целевая зона низшего уровня и другие целевые зоны формируют набор целевых зон, связанных с целевой точкой и заранее определенном направлении на карте.

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

[15] В некоторых вариантах осуществления способа, способ далее включает в себя определение электронным устройством того, где находится целевая точка в рамках данной географической области. Граница данной географической области соответствует данному многоугольнику из по меньшей мере одного многоугольника. Определение включает в себя создание электронным устройством набора целевых сегментов путем группировки данных о сегментах, оба из которых (i) хранятся в индексе, связанном с набором целевых зон, и (ii) связаны с данным многоугольником. Способ далее включает в себя геометрическое определение электронным устройством, числа целевых сегментов в наборе целевых сегментов, которые пересекаются с лучом, который проецируется от местоположения целевой точки вдоль заранее определенного направления на карте. В ответ на геометрическое определение того, что четное число целевых сегментов пересекает луч, способ включает в себя определение электронным устройством того, что целевая точка находится снаружи данной географической области. В ответ на геометрическое определение того, что нечетное число целевых сегментов пересекает луч, способ включает в себя определение электронным устройством того, что целевая точка находится внутри данной географической области.

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

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

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

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

[20] Вторым объектом настоящей технологии является электронное устройство для создания индекса сегментов по меньшей мере одного многоугольника, определяющего границы соответствующей географической области на карте. Электронное устройство обладает доступом к базе данных для размещения индекса. Электронное устройство выполнено с возможностью осуществлять сегментирование опорной зоны на опорном уровне на зоны первого уровня на первом уровне. Опорная зона покрывает по меньшей мере часть карты, которая включает в себя все сегменты по меньшей мере одного многоугольника. Опорная зона является родительской зоной для зон первого уровня. Электронное устройство выполнено с возможностью осуществлять, в ответ на то, что по меньшей мере один сегмент по меньшей мере частично расположен в более чем одной зоне первого уровня, индексирование по меньшей мере одного сегмента как связанного с опорной зоной. Индексирование также включает в себя сохранение электронным устройством данных по меньшей мере об одном сегменте, связанном в опорной зоной. Сегменты, расположенные внутри только одной зоны первого уровня, индексируются как связанные с зонами, отличными от опорной зоны. Электронное устройство выполнено с возможностью осуществлять, до достижения конечных условий, итерационно: (i) сегментирование данной зоны на данном уровне на зоны последующих уровней, причем данная зона является родительской зоной для соответствующих зон последующих уровней; и (ii) в ответ то, что по меньшей мере один другой сегмент по меньшей мере частично расположен внутри более чем одной соответствующей зоны последующего уровня, индексирование по меньшей мере одного другого сегмента как связанного с данной зоной. Электронное устройство, которое выполнено с возможностью осуществлять индексирование, представляет собой электронное устройство, которое выполнено с возможностью осуществлять создание электронным устройством геомаркера для данной зоны, причем геомаркер указывает на (i) расположение данной зоны в соответствующей родительской зоне, причем соответствующая родительская зона данной зоны находится на предыдущем уровне по отношению к данному, и (ii) географическую связь между данной зоной и другими дочерними зонами по отношению к соответствующей родительской зоне. Электронное устройство, которое выполнено с возможностью осуществлять индексирование, представляет собой электронное устройство, которое выполнено с возможностью осуществлять данных по меньшей мере об одном другом сегменте, связанном с геомаркером данной зоны. Сегменты, которые находятся внутри только одной соответствующей зоны последующего уровня, индексируются как связанные с дочерними зонами соответствующей одной из только одной зоны последующего уровня.

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

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

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

[24] В некоторых вариантах осуществления электронного устройства, электронное устройство выполнено далее с возможностью осуществлять: получение доступа к индексу для определения: целевой зоны низшего уровня, соответствующей местоположению целевой точки на основе геомаркеров зоны в индексе; и других целевых зон, которые (i) по меньшей мере частично расположены вдоль заранее определенного направления на карте от целевой зоны низшего уровня и (ii) по меньшей мере частично выровнены с целевой зоной низшего уровня в заранее определенном направлении, на основе геомаркеров зон, хранящихся в индексе. Заранее определенное направление было определено на основе географической связи между дочерними зонами данной родительской зоны. Целевая зона низшего уровня и другие целевые зоны формируют набор целевых зон, связанных с целевой точкой и заранее определенном направлении на карте.

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

КРАТКОЕ ОПИСАНИЕ ЧЕРТЕЖЕЙ

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

[41] На Фиг. 1 представлена система, подходящая для реализации неограничивающих вариантов осуществления настоящей технологии.

[42] На Фиг. 2 представлено картографическое представление карты, представленное электронным устройством системы, показанной на Фиг. 1, в соответствии с вариантами осуществления настоящей технологии.

[43] На Фиг. 3 представлен многоугольник, представляющий собой границу географической области картографического представления, показанного на Фиг. 2, в соответствии с некоторыми вариантами осуществления настоящей технологии.

[44] На Фиг. 4 представлено визуальное представление, демонстрирующее процедуру индексирования для опорной зоны, определенной сервером, показанным на Фиг. 1, в соответствии с некоторыми вариантами осуществления настоящей технологии.

[45] На Фиг. 5 представлено визуальное представление, демонстрирующее процедуру индексирования для зоны первого уровня, определенной сервером, показанным на Фиг. 1, в соответствии с некоторыми вариантами осуществления настоящей технологии.

[46] На Фиг. 6 представлено визуальное представление, демонстрирующее процедуру индексирования для зоны второго уровня, определенной сервером, показанным на Фиг. 1, в соответствии с некоторыми вариантами осуществления настоящей технологии.

[47] На Фиг. 7 представлено схематическое представление древовидной структуры индекса, показанного на Фиг. 1, созданного в процессе создания индекса, в соответствии с некоторыми вариантами осуществления настоящей технологии.

[48] На Фиг. 8 представлено визуальное представление зон, которые связаны с соответствующими нодами древовидной структуры, показанной на Фиг. 7, в соответствии с вариантами осуществления настоящей технологии.

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

ОСУЩЕСТВЛЕНИЕ

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

[51] Система 100 включает в себя клиентское устройство 102. Клиентское устройство 102 обычно связано с пользователем 104 и, таким образом, иногда может упоминаться как клиентское устройство 102. Следует отметить, что тот факт, что клиентское устройство 102 связано с пользователем 104, не подразумевает какого-либо конкретного режима работы, равно как и необходимости входа в систему, регистрации, или чего-либо подобного.

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

[53] Клиентское устройство 102 включает в себя аппаратное обеспечение, программное обеспечение и/или встроенные программы (или сочетание перечисленного) для выполнения приложения 106, причем картографическое приложение 106 используется, среди прочего, для получения доступа или, иным образом, отображения карты.

[54] Картографическое приложение 106, среди прочего, может быть специализированным картографическим приложением, например, приложением Яндекс.Карты для мобильных устройств, веб-браузером или любым другим приложением, которое может предоставлять одно или несколько картографических изображений. Картографическое приложение 106 также может быть реализовано как приложение захвата/обработки изображения, приложение 3D-игры и так далее. Следовательно, в широком смысле, картографическое приложение 106 может быть данным приложением, выполненным с возможностью отрисовывать и отображать одно или несколько изображений, не выходя за рамки объема настоящей технологии.

[55] Клиентское устройство 102 соединено с сетью 108 передачи данных через линию 110 передачи данных. В некоторых вариантах осуществления настоящего технического решения, не ограничивающих ее объем, сеть 108 передачи данных может представлять собой Интернет. В других вариантах осуществления настоящей технологии сеть 108 передачи данных может быть реализована иначе - в виде глобальной сети передачи данных, локальной сети передачи данных, частной сети передачи данных и т.п.

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

[57] Общий вариант осуществления клиентского устройства 102 известен. Тем не менее, следует отметить, что клиентское устройство 102 включает в себя устройство 103 вывода. Устройство 103 вывода выполнено с возможностью представлять визуальную информацию пользователю 104. Визуальная информация может представлять собой текст, изображения, видео и так далее. Конкретнее, устройство 103 вывода выполнено с возможностью отображать вывод графического приложения 106. Устройство 103 вывода может быть реализовано как монитор, встроенный экран, сенсорный экран и так далее.

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

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

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

[61] Сервер 112 изображения соединен с сетью 108 передачи данных через линию 116 передачи данных. Реализация линии 116 передачи данных не ограничена и будет зависеть от того, какой сервер 112 изображения используется. Предполагается, что примеры вариантов осуществления линии 110 передачи данных, предоставленные выше, могут быть применены к линии 116 передачи данных.

[62] В общем случае, сервер 112 выполнен с возможностью: получать с помощью сети 112 передачи данных и линий 110, 116 передачи данных от клиентского устройства 102 запрос 160 для отображения данного картографического представления; (ii) получать графические данные (например, один или несколько фрагментов изображения), необходимые для создания запрашиваемого картографического представления, (iii) передавать ответ 162, содержащий извлеченные графическое данные клиентскому устройству 102 через сеть 108 передачи данных и линии 110, 116 передачи данных, (iv) получать от клиентского устройства 102 указание 164 на местоположение данной целевой точки (например, выбранной пользователем 104), (v) определять, находится ли целевая точка внутри данной географической области и (vi) опционально, в ответ на то, что целевая точка находится внутри данной географической области, передавать ответ 166, содержащий зависящие от региона данные клиентскому устройству 102, через сеть 108 передачи данных и линии 110, 116 передачи данных. То как именно сервер 112 выполнен с возможностью выполнять по меньшей мере некоторые из вышеупомянутых не исчерпывающих функций сервера 112, которые будут более подробно описаны ниже.

[63] Сервер 112 изображения обладает доступом к базе 114 данных изображений. В общем случае, база 114 данных выполнена с возможностью сохранять среди прочего (i) данные, необходимые для отрисовки одного или нескольких картографических изображений и (ii) индекс(ы) границ географических областей. В представленном варианте осуществления настоящей технологии, не ограничивающем ее объем, база 114 данных является одиночной базой данных. В других неограничивающих вариантах осуществления настоящей технологии, функциональность базы 114 данных может быть разделена, и может выполняться с помощью нескольких баз данных.

[64] То, как база 114 данных размещает графические данные для отрисовки одного или нескольких картографических изображений, никак конкретно не ограничено, но, например, база 114 данных может быть выполнена с возможностью сохранять графические данные для отображения других картографических представлений карты на других уровнях приближения. Следует иметь в виду, что природа картографических изображений (графических данных), сформированных другими картографическими представлениями, которые хранятся сервером 112, никак конкретно не ограничена. Например, для отрисовки конкретного картографического представления на конкретном уровне приближения, база 112 данных может хранить соответствующее множество картографических изображений для конкретного уровня приближения, также известных как "фрагменты карты", которые вместе формируют конкретное картографическое представление. Естественно, графические данные могут быть реализованы несколькими различными путями и могут зависеть от, среди прочего, различных вариантов осуществления настоящей технологии.

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

[66] В общем случае, индекс 150 представляет собой структуру данных, которая создана для улучшения скорости операций поиска и/или извлечения данных из базы 114 данных. Индекс 150 может использоваться сервером 112 для быстрого нахождения данных в базе 114 данных, связанных с одной или несколькими географическими областями, причем сервер 112 получает доступ к базе 114 данных для извлечения данных. Подразумевается, что в некоторых вариантах осуществления технологии, создание и/или поддержание индекса 150 может требовать дополнительного объема памяти в базе 114 данных, но может привести к увеличению скорости операций поиска и/или извлечения данных из базы 114 данных, по сравнению со скоростью операций поиска и/или извлечения данных из базы 114 данных, причем данные, связанные одной или несколькими областями, не хранятся в индексированном формате.

[67] Как будет описано более подробно далее, сервер 112 может быть выполнен с возможностью сохранять индекс 150 в базе 112 данных для будущего использования, например, для определения того, находится ли данная целевая точка (выбранная, например, пользователем 104) внутри или снаружи одной или нескольких соответствующих географических областей, связанных с индексом 150.

[68] В некоторых вариантах осуществления настоящей технологии, индекс 150 может создаваться и/или поддерживаться сервером 112 путем заполнения одной или нескольких записей в базе данных 114. В других вариантах осуществления технологии, индекс 150 может создавать и/или поддерживаться сервером 112 в форме древовидной структуры 700, как визуально показано на Фиг. 7. В общем случае, древовидная структура 700 включает в себя число нод на различных уровнях древовидной структуры 700, и при этом каждая нода древовидной структуры 700 связана, в общем случае, с некоторой информацией об одной или нескольких географических областях. Процесс создания индекса 150 сервером 112 будет более подробно описан далее.

[69] На Фиг. 2, представлено картографическое представление 200, которое является по меньшей мере частью карты на данном уровне масштабирования. Например, картографическое представление 200 может отображаться пользователю 104 с помощью устройства 103 вывода после передачи ответа 162 сервером 112 устройству 104 в ответ на запрос 160 от устройства 104. На картографическом представлении 200 в общем случае представлен парк 202, озеро 204, парковку 206 и дорогу 208. Как уже ранее упоминалось, картографическое представление 200 может быть сформировано из соответствующего множества картографических изображений, хранящихся в базе 114 данных, и которые могут извлекаться сервером 112 после получения запроса 160 от устройства 104.

[70] Следует отметить, что парк 202 является данной географической областью, представленной на картографическом представлении 200 карты, которая ограничена или определена границей 210, и эта граница общем случае соответствует периметру парка 202 на карте. Например, если пользователь 104 использует курсор или другие подходящие средства для "перемещения по" парку 202, граница 210 может, опционально, визуально отображаться картографическим приложением 106 отличительным образом для "подсвечивания" периметра парка 202 на карте.

[71] Следует иметь в виду, что, несмотря на то, что соответствующие границы для озера 204, парковки 206 и дороги 208 не показаны на Фиг. 2, они все связаны с соответствующими географическими областями, отображаемыми на картографическом представлении 200 карты, и могут ограничиваться или определяться соответствующими границами, которые в общем случае связаны с их соответствующими периметрами на карте.

[72] Например, следует иметь в виду, что, несмотря на то, что процесс создания индекса 150 будет описан далее в отношении данной географической области парка 202, сервер 112 может быть выполнен с возможностью создавать индекс 150 таким образом, чтобы индекс 150 был связан с географическими областями по меньшей мере некоторых из: озеро 204, парковка 206 и дорога 208 - в дополнении к парку 202 - аналогичным образом, не выходя за границы настоящей технологии.

[73] Следует отметить, что картографическое приложение 106 может быть выполнено с возможностью перекрывать картографическое представление 200 с помощью "слоя границ" для визуального отображения границы 210 на данном уровне приближения карты. Например, данные, представляющие собой границу 210 (и другие потенциальные границы других географических областей) могут предоставляться как часть данного слоя границ, который накладывается на карту. После того как данный слой границ был наложен на карту, картографическое приложение 106 может перекрывать картографическое представление 200 карты на данном уровне приближения данным слоем границ таким образом, чтобы визуальное отображение границы 210 в общем случае соответствовало периметру парка 202 на картографическом представлении 200.

[74] Со ссылкой как на Фиг. 2 и. 3, граница 210 парка 202 может представлять собой многоугольник 300, обладающий вершинами и сегментами. Другими словами, данные, представляющие собой границу 210, которая представлена как часть слоя границы, могут соответствовать данным, которые представляют собой многоугольник 300. Число вершин и сегментов многоугольника 300 может зависеть от формы границы 210.

[75] В некоторых вариантах осуществления настоящей технологии подразумевается, что сервер 112 может быть выполнен с возможностью создавать индекс 150 для сегментов многоугольника 300, соответствующего границе 210 парка 202. Как было упомянуто ранее, также подразумевается, что сервер 112 может быть выполнен с возможностью создавать индекс 150 для сегментов многоугольника 300 и для сегментов одного или нескольких дополнительных многоугольников, соответствующих границам одной или нескольких дополнительных соответствующих географических областей, предоставляемых как часть данного слоя границ, не выходя за пределы настоящей технологии.

[76] Многоугольник 300 обладает (i) множеством вершин, включающих в себя вершину А через Q, и (ii) множеством сегментов, соединяющих соответствующие пары вершин из множества вершин. Сервер 112 может быть выполнен с возможностью идентифицировать и сохранять в базе 114 данных геоданные, указывающие на географические местоположения множества вершин многоугольника 300 на карте.

[77] Например, геоданные могут включать в себя соответствующую широту и соответствующую долготу (а также в некоторых случаях соответствующую высоту), которые соответствуют географическому местоположению данной вершины на карте. Дополнительно, в некоторых вариантах осуществления настоящей технологии сервер, сервер 112 может быть выполнен с возможностью сохранять в базе 114 данных геоданные, связанные с каждым из множества сегментов многоугольника 300.

[78] Сервер 112 может также быть выполнен с возможностью сохранять информацию, указывающую на соответствие между географической областью парка 202 и геоданные множества сегментов многоугольника 300, формирующего границу 210. Например, в случаях, когда сервер 112 сохраняет геоданные, связанные с более чем одним многоугольником (например, формирующие более одной границы в соответствующих географических областях), сервер 112 может использовать эту информацию для определения того, какие вершины и какие сегменты, которые хранятся в базе 114 данных, связаны с какими из более чем одного многоугольника и, соответственно, с какой из более чем одной географических областей.

[79] Подразумевается, что в некоторых вариантах осуществления технологии, после того, как геоданные, связанные с многоугольником 300, становятся доступны и потенциально хранятся в базе 114 данных, сервер 112 может начать процесс создания индекса 150.

[80] Далее будет описано то, как именно сервер 112 создает индекс 150.

[81] Сервер 112 выполнен с возможностью определять опорную зону 302, которая охватывает все сегменты многоугольника 300. Другими словами, сервер 112 может выполнен с возможностью определять геоданные, связанные с данной зоной на карте, которая охватывает геоданные всех вершин многоугольника 300 (и других потенциальных многоугольников).

[82] Можно сказать, что опорная зона 302 охватывает по меньшей мере часть карты, которая охватывает все сегменты многоугольника 300 (и другие потенциальные многоугольники). В одном случае, опорная зона 302 может быть определена сервером 112 таким образом, чтобы покрывать по меньшей мере часть карты, которая включает в себя все сегменты одного или нескольких многоугольников. В другом случае, сервер 112 может определять, что опорная зона 302 представляет собой всю карту (т.е. опорная зона 302 охватывает всю карту).

[83] На Фиг. 3, опорная зона 302 представлена в форме квадрата (квадратной формы), тем не менее это не является обязательным в каждом варианте осуществления настоящей технологии. Например, сервер 112 может быть выполнен с возможностью определять данную опорную зону в форме треугольника, прямоугольника, пятиугольника, шестиугольника и круга и так далее. Форма данной опорной зоны может зависит, среди прочего, от формы многоугольника 300, формы других потенциальных многоугольников и/или различных вариантов осуществления настоящей технологии.

[84] После того как опорная зона 302 определена сервером 112, который выполнен с возможностью выполнять процедуру индексирования для опорной зоны 302. Процедура индексирования для опорной зоны 302 позволяет индексировать по меньшей мере некоторые сегменты многоугольника 300 (и других потенциальных многоугольников) в связи с опорной зоной 302 в индексе 150.

[85] В общем случае, процедура индексирования опорной зоны 302 может быть сведена к двум шагам:

- этап идентификации - за время которого идентифицируются сегменты, предназначенные для индексирования как связанные с опорной зоной 302; и

- этап индексирования - за время которого сегменты, идентифицированные на этапе идентификации, индексируются как связанные с опорной зоной 302 в индексе 150.

[86] То как именно сервер 112 выполнен с возможностью выполнять два этапа процедуры индексирования для опорной зоны 302 будет более подробно описано далее со ссылкой на Фиг. 4.

[87] Во время этапа идентификации, сервер 112 выполнен с возможностью сегментировать опорную зону 302. Сегментирование опорной зоны 302 приводит ко множеству зон 410, 420, 430 и 440 первого уровня, которые меньше по размеру, чем опорная зона 302, и которые расположены внутри опорной зоны 302 на карте.

[88] На Фиг. 4 в верхней ее части представлено визуальное представление 400 того, как сервер 112 может быть выполнен с возможностью сегментировать опорную зону 302. В нижней ее части представлено визуальное представление 401 опорного уровня 450 опорной зоны 302 (на котором опорная зона 302 не сегментирована), и первого уровня 460 (на котором опорная зона 302 сегментирована на зоны 410, 420, 430 и 440 первого уровня).

[89] Следует иметь в виду, что визуальные представления 400 и 401 представлены для визуальной иллюстрации того, как сервер 112 выполнен с возможностью выполнять процедуру индексирования для опорной зоны 302 - сервер 112 выполнен без возможности создавать или отрисовывать сам по себе визуальные представления 400 и 401.

[90] Сервер 112 выполнен с возможностью определять линии сегментирования 402 и 404 для сегментирования опорной зоны 302. Линии сегментирования 402 и 404 используются сервером 112 для сегментирования опорной зоны 302 на зоны 410, 420, 430 и 440 первого уровня на первом уровне 460, как упоминалось ранее.

[91] На Фиг. 4 зоны 410, 420, 430 и 440 первого уровня представлены как четыре квадратные зоны. Тем не менее, следует иметь в виду, что число и форма зон 410, 420, 430 и 440 первого уровня могут зависеть от, среди прочего, формы соответствующей опорной зоны 302, числа линий сегментирования, определенных сервером 112 и/или различных вариантов осуществления технологии.

[92] На Фиг. 4 зоны 410, 420, 430 и 440 первого уровня представлены как равные или, другими словами, занимающие равные области опорной зоны 302. Тем не менее, зоны 410, 420, 430 и 440 первого уровня могут занимать неравные области опорной зоны 302 в других вариантах осуществления, не выходя за границы настоящей технологии.

[93] Другими словами, можно сказать, что в неограничивающем варианте осуществления Фиг. 4. после определения линий сегментирования 402 и 404, они используются сервером 112 для, в некотором смысле, для "тесселяции" опорной зоны 302 множеством одинаковых непрерывных квадратных ячеек или квадрантов (зоны 410, 420, 430 и 440 первого уровня) таким образом, чтобы образовалась сетка для опорной зоны 302. В этом случае:

- зона 410 первого уровня соответствует северо-западной ячейке или квадранту сетки;

- зона 420 первого уровня соответствует северо-восточной ячейке или квадранту сетки;

- зона 430 первого уровня соответствует юго-западной ячейке или квадранту сетки; и

- зона 440 первого уровня соответствует юго-восточной ячейке или квадранту сетки.

[94] В контексте настоящей технологии, опорная зона 302 соответствует "родительской зоне" для зон 410, 420, 430 и 440 первого уровня. Аналогичным образом, зоны 410, 420, 430 и 440 первого уровня соответствуют соответствующим "дочерним зонам" опорной зоны 302. Следовательно, можно сказать, что, когда зона сегментирована: (i) данная зона на данном уровне сегментирована на данное множество зон на последующем уровне, (ii) данное множество зон включает в себя дочерние зоны для данной зоны, и (iii) данная зона является родительской зоной для данного множества зон.

[95] Во время этапа идентификации, после того как опорная зона 302 сегментирована, сервер 112 выполнен с возможностью идентифицировать сегменты многоугольника 300 (или другие потенциальные многоугольники), которые расположены по меньшей мере частично в более чем одной из зон 410, 420, 430 и 440 первого уровня (например, более чем один квадрант сетки опорной зоны 302). Другими словами, сервер 112 может быть выполнен с возможностью идентифицировать сегменты многоугольника 300, которые пересекают по меньшей мере одну из линий 402 и 404 сегментирования, которые используются для сегментирования опорной зоны 302.

[96] В данном примере, сервер 112 идентифицирует сегменты А-В, D-E, F-G и M-N как по меньшей мере частично расположенные в более чем одной из зон 410, 420, 430 и 440 первого уровня. Таким образом идентифицированные сегменты А-В, D-E, F-G и M-N индексируются сервером 112 как связанные с опорной зоной 302.

[97] Сервер 112, тем самым, выполняет этап индексирования процедуры индексирования опорной зоны 302. В общем случае, индексирование сегментов А-В, D-E, F-G и M-N как связанных с опорной зоной 302 может включать в себя: (i) создание геомаркера для опорной зоны 302, которая указывает на местоположение опорной зоны 302 на карте и (ii) сохранение геоданных, связанных с сегментами А-В, D-E, F-G и M-N (и/или вершинами, соединенными с этими сегментами), связанными с геомаркером ссылки 302 в базе данных 114.

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

[99] В некоторых вариантах осуществления настоящей технологии, где сервер 112 выполнен с возможностью создавать геомаркеры для опорной зоны 302, создание геомаркера для опорной зоны 302 может выполняться сервером 112 с помощью алгоритма геохеширования, применяемого сервером 112. В общем случае, алгоритм геохеширования может позволить закодировать местоположение опорной зоны 302 на карте на основе геоданных (например, указание на координаты), связанных с опорной зоной 302. Например, сервер 112 может применять алгоритм геохеширования для кодировки местоположения опорной зоны 302 как "XXX" на карте или с помощью любой подходящей геохешированной строки

[100] В некоторых вариантах осуществления настоящей технологии, во время этапа индексирования сервер 112 может быть выполнен с возможностью заполнять запись в базе 114 данных геоданными о сегментах А-В, D-E, F-G и M-N, связанных с геомаркером (или любым другим подходящим маркером) опорной зоны 302.

[101] В других вариантах осуществления настоящей технологии, во время этапа индексирования и со ссылкой на Фиг. 7, сервер 112 может быть выполнен с возможностью создавать для опорной зоны 302 "корневую ноду" на опорной уровне 450 древовидной структуры 700 и сохранять геоданные сегментов А-В, D-E, F-G и M-N, связанных с этой корневой нодой. Например, предполагая, что опорная зона 302 покрывает только часть карты, корневая нода может создаваться как связанная с геомаркером "XXX" опорной зоны 302, как показано на Фиг. 7.

[102] Процедура индексирования для опорной зоны 302, тем самым, завершается. Следует отметить, что в некоторых вариантах осуществления настоящей технологии, процедура индексирования для опорной зоны 302 завершается созданием корневой ноды древовидной структуры 700, где хранятся геоданные сегментов А-В, D-E, F-G и M-N.

[103] Сервер 112 также выполнен с возможностью создавать индекс 150. Например, сервер 112 может продолжать создавать индекс 150 путем выполнения процедур индексирования других данных зон (отличных от опорной зоны 302) и для индексирования других сегментов многоугольника 300 (отличных от сегментов А-В, D-E, F-G и M-N, поскольку они уже проиндексированы).

[104] Следующая аналогия суммирует процедуру индексирования для опорной зоны 302:

- сегменты многоугольника 300 (и других потенциальных многоугольников), которые пересекают линии 402 и/или 404 сегментирования, в данном случае, сегменты А-В, D-E, F-G и M-N, в некотором смысле "сохраняются" на опорном уровне 350 и, таким образом, индексируются как связанные с корневой нодой древовидной структуры 700, созданной для опорной зоны 302; и

- другие сегменты многоугольника 300 (и других потенциальных многоугольников), которые не пересекают линии 402 и/или 404 сегментирования, в данном случае сегменты В-С, C-D, E-F, G-H, H-I, I-J, J-K, K-L, L-M, N-O, О-Р, P-Q и Q-A, в некотором смысле "попадают" на последующий уровень, в данном случае первый уровень 460, чтобы быть проиндексированными как связанные с зонами, отличными от опорной зоны 302.

[105] Например, как показано на Фиг. 4:

- сегменты N-O, О-Р, P-Q и Q-A расположены полностью в зоне 410 первого уровня (например, в северо-западном квадранте опорной зоны 302) и, следовательно, "попадают" на первый уровень 460 и в зону 410 первого уровня;

- сегменты В-С и C-D расположены полностью в зоне 420 первого уровня (например, в северо-восточном квадранте опорной зоны 302) и, следовательно, "попадают" на первый уровень 460 и в зону 420 первого уровня;

- сегменты G-H, H-I, I-J, J-K, K-L и L-M расположены полностью в зоне 430 первого уровня (например, в юго-западном квадранте опорной зоны 302) и, следовательно, "попадают" на первый уровень 460 и в зону 430 первого уровня; и

- сегмент E-F расположен полностью в зоне 440 первого уровня (например, в северозападном квадранте опорной зоны 302) и, следовательно, "попадает" на первый уровень 460 и в зону 430 первого уровня.

[106] Тем не менее, как будет понятно из нижеследующего описания Фиг. 5, сегменты многоугольника 300, которые "попадают" на первый уровень 460, не обязательно будут индексироваться как связанные с зонами 410, 420, 430 и 440 первого уровня на первом уровне 460. Например, сервер 112 может быть выполнен с возможностью выполнять процедуры индексирования для по меньшей мере некоторых из зон 410, 420, 430 и 440 первого уровня, во время которой сервер 112 может определять:

- какие, если таковые имеются, из сегментов, которые "попадают" на первый уровень 460, "сохраняются" на первом уровне 460 для индексирования с соответствующими из зон 410, 420, 430 и 440 первого уровня; и

- какие, если таковые имеются, из сегментов, которые "попадают" на первый уровень 460, "попадают" далее на последующий уровень для индексирования и другими зонами, отличными от (i) опорной зоны 302 и (ii) зон 410, 420, 430 и 440 первого уровня.

[107] Опять же, как будет понятно из описания Фиг. 5 далее, подразумевается, что сервер 112 может быть выполнен с возможностью определять (i) какие из сегментов данного многоугольника "сохраняются" на данном уровне (предназначены для индексирования в данную зону на данном уровне), и (ii) какие сегменты данного многоугольника "попадают" далее на последующий уровень (iii) на основе, среди прочего, наличия пересечений между сегментами данного многоугольника и данными линиями пересечения на данном уровне.

[108] Со ссылкой на Фиг. 5 будет описано то, как именно сервер 112 выполнен с возможностью выполнять процедуру индексирования зоны 430 первого уровня. Следует иметь в виду, что сервер 112 может также выполнять процедуры индексирования для зон 410, 420 и 440 первого уровня аналогичным образом и, следовательно, это не будет подробно описано далее.

[109] Аналогично процедуре индексирования опорной зоны 302, процедура индексирования зоны 430 первого уровня может быть суммирована до двух этапов: (i) этапа идентификации и (ii) этапа индексирования. Два этапа процедуры индексирования зоны 430 первого уровня будут описаны далее.

[110] Во время этапа идентификации, сервер 112 выполнен с возможностью сегментировать зону 430 первого уровня. Сегментирование зоны 430 первого уровня приводит ко множеству зон 510, 520, 530 и 540 второго уровня, которые меньше по размеру, чем зона 430 первого уровня и которые расположены внутри зоны 430 первого уровня на карте. Естественно, зоны 510, 520, 530 и 540 второго уровня также расположены внутри опорной зоны 302.

[111] На Фиг. 5 в верхней ее части представлено визуальное представление 500 того, как сервер 112 может быть выполнен с возможностью сегментировать зону 430 первого уровня. В нижней ее части показано визуальное представление 501 опорного уровня 450 опорной зоны 302, первого уровня 460 зоны 410, 420, 430 и 440 первого уровня, и второй уровень 470.

[112] Следует отметить, что второй уровень 470 в визуальном представлении 510 показан только частично -в том смысле, что другие из зон 410, 420 и 440 первого уровня могут быть сегментированы на соответствующие зоны второго уровня 470, аналогично тому как зона 430 первого уровня сегментирована на зоны 510, 520, 530 и 540 второго уровня, не выходя за пределы настоящей технологии.

[113] Следует иметь в виду, что визуальные представления 500 и 501 представлена для визуальной иллюстрации того, как сервер 112 выполнен с возможностью выполнять процедуру индексирования зоны 430 первого уровня - сервер 112 выполнен без возможности создавать или отрисовывать сам по себе визуальные представления 500 и 501.

[114] Сервер 112 выполнен с возможностью определять линии сегментирования 502 и 504 для сегментирования зоны 430 первого уровня. Линии сегментирования 502 и 504 используются сервером 112 для сегментирования зоны 430 первого уровня на зоны 510, 520, 530 и 540 второго уровня на втором уровне 470, как упоминалось ранее.

[115] На Фиг. 5 зоны 510, 520, 530 и 540 второго уровня представлены как четыре квадратные зоны. Тем не менее, следует иметь в виду, что аналогично зонам 410, 420, 430 и 440 первого уровня, число и формы зон второго уровня могут зависеть от среди прочего, различных вариантов осуществления настоящей технологии.

[116] Другими словами, аналогично тому, как это было описано выше для линий 402 и 404 сегментирования, в неограничивающем варианте осуществления Фиг. 5. после определения линий сегментирования 502 и 504, они используются сервером 112 для, в некотором смысле, для "тесселяции" зоны 430 первого уровня множеством одинаковых непрерывных квадратных ячеек или квадрантов (зоны 510, 520, 530 и 540 второго уровня) таким образом, чтобы образовалась сетка для зоны 430 первого уровня.

[117] Следует отметить, что зона 430 первого уровня соответствует "родительской зоне" для зон 510, 520, 530 и 540 второго уровня. Аналогичным образом, зоны 510, 520, 530 и 540 второго уровня соответствуют соответствующим "дочерним зонам" зоны 430 первого уровня.

[118] Как было упомянуто ранее, сегменты M-N и F-G "сохраняются" на опорном уровне 450 (например, индексируются как связанные с опорной зоной 302) и, следовательно, не "попадают" на первый уровень 460 и в зону 430 первого уровня. Только сегменты G-H, Н-I, I-J, J-K, K-L и L-M, которые "попадают" на первый уровень 460 и в зону 430 первого уровня, показаны на визуальном представлении 500.

[119] Во время этапа идентификации, сервер 112 выполнен с возможностью идентифицировать сегменты многоугольника 300, которые расположены по меньшей мере частично в более чем одной из зон 510, 520, 530 и 540 второго уровня (например, более чем один квадрант сетки опорной зоны 430). Другими словами, аналогично тому, что было описано выше, сервер 112 может быть выполнено с возможностью идентифицировать сегменты многоугольника 300, которые перекрываются по меньшей мере с одной из линий 502 и 504 сегментирования.

[120] В данном примере, сервер 112 идентифицирует сегменты H-I и J-K как по меньшей мере частично расположенные в более чем одной из зон 510, 520, 530 и 540 второго уровня. Таким образом идентифицированные сегменты H-I и J-K индексируются сервером 112 как связанные с зоной 430 первого уровня.

[121] Сервер 112, тем самым, выполняет этап индексирования процедуры индексирования зоны 430 первого уровня. Аналогично тому, что было описано выше для этапа индексирования опорной зоны 302, индексирование сегментов H-I и J-K как связанных с зоной 430 первого уровня, может включать в себя (i) создание геомаркера для зоны 430 первого уровня и (ii) сохранение геоданных, связанных с сегментами Н-I и J-K (и/или вершинами, соединенными этим сегментами), как связанные с геомаркером зоны 430 первого уровня в базе 114 данных.

[122] Геомаркер для зоны 430 первого уровня (и геомаркеры для зон 410, 420 и 440 первого уровня) могут создаваться сервером 112 с помощью алгоритма хеширования. В общем случае, после создания, геомаркер зоны 430 первого уровня указывает на (i) местоположение зоны 430 первого уровня в ее родительской зоне (например, опорной зоне 302), и (ii) географическую связь между зоной 430 первого уровня и зонами 410, 420 и 440 первого уровня (другими дочерними зонами опорной зоны 302).

[123] То, как именно сервер 112 выполнен с возможностью создавать геомаркеры для зон 410, 420, 430 и 440 первого уровня, будет более подробно описано далее.

[124] В некоторых вариантах осуществления настоящей технологии, для создания данного геомаркера для данной одной из зон 410, 420, 430 и 440 первого уровня, сервер 112 может быть выполнен с возможностью осуществлять: (i) кодирование географической связи между данной одной из зон 410, 420, 430 и 440 первого уровня, и другими зонами 410, 420, 430 и 440 первого уровня, и (ii) если геомаркер был создан для родительской зоны (в данном случае, опорной зоны 302), создание данного геомаркера путем добавления к геомаркеру родительской зоны соответствующей закодированной географической связи между данной одной из зон 410, 420, 430 и 440 первого уровня и другими зонами 410, 420, 430 и 440 первого уровня.

[125] Предположим, как упоминалось ранее, что геомаркер "XXX" был создан для опорной зоны 302. Таким образом, сервер 112 может создавать геомаркеры для зон 410, 420, 430 и 440 первого уровня путем (i) кодирования географической связи между соответствующей одной из зон 410, 420, 430 и 440 первого уровня, и другими зонами 410, 420, 430 и 440 первого уровня, и (ii) добавления соответствующей закодированной географической связи к геомаркеру "XXX".

[126] Географическая связь между данной одной из зон 410, 420, 430 и 440 первого уровня и другими зонами 410, 420, 430 и 440 первого уровня может быть закодирована различными способами. В одном варианте осуществления настоящей технологии, сервер 112 может быть выполнен с возможностью применять Z-код для кодировки (например, код Мортона) как часть алгоритма хеширования. В общем случае, Z-код для кодировки позволяет проецировать многомерные данные на одно измерение, одновременно сохраняя локальность данных.

[127] Например, сервер 112 может применять Z-код для кодировки как часть алгоритма хеширования для создания:

- закодированной географической связи "00" для зоны 410 первого уровня, поскольку зона 410 первого уровня является верхним левым (северо-западным) квадрантом сетки опорной зоны 302;

- закодированной географической связи "01" для зоны 420 первого уровня, поскольку зона 420 первого уровня является верхним правым (северо-восточным) квадрантом сетки опорной зоны 302;

- закодированной географической связи "10" для зоны 430 первого уровня, поскольку зона 430 первого уровня является нижним левым (юго-западным) квадрантом сетки опорной зоны 302; и

- закодированной географической связи "11" для зоны 440 первого уровня, поскольку зона 440 первого уровня является нижним правым (юго-восточным) квадрантом сетки опорной зоны 302.

[128] Следует отметить, что геомаркер для каждой из зон 410, 420, 430 и 440 первого уровня указывает на географическую связь между соответствующей одной из зон 410, 420, 430 и 440 первого уровня и другими зонами 410, 420, 430 и 440 первого уровня в опорной зоне 302.

[129] Например, в данном случае, закодированная географическая связь для данной зоны первого уровня представляет собой две цифры, где (i) значение первой цифры, которое может быть "0" или "1", указывает на то, является ли данная зона первого уровня одной из верхних (северных) зон первого уровня в опорной зоне 302 или одной из нижних (южных) зон первого уровня в опорной зоне 302 соответственно, и (ii) значение второй цифры, которое может быть "0" или "1", указывает на то, является ли данная зона первого уровня одной из левых (западных) зон первого уровня в опорной зоне 302 или одной из правых (восточных) зон первого уровня в опорной зоне 302 соответственно.

[130] В данном случае, закодированная географическая связь "10" для зоны 430 первого уровня включает в себя две цифры, где (i) первая цифра, обладающая значением "1", указывает на то, что зона 430 первого уровня является одной из нижних (южных) зон первого уровня в опорной зоне 302, и (ii) вторая цифра, обладающая значением "0", указывает на то, что зона 430 первого уровня является одной из левых (западных) зон первого уровня в опорной зоне 302. Следовательно, комбинация двух цифр, обладающих значениями " 1" и "0" соответственно, указывает на то, что зона 430 первого уровня является нижней левой (юго-западной) зоной первого уровня среди зон 410, 420, 430 и 440 первого уровня в опорной зоне 302.

[131] Также, закодированная географическая связь "01" для зоны 420 первого уровня включает в себя две цифры, где (i) первая цифра, обладающая значением "0", указывает на то, что зона 420 первого уровня является одной из верхних (северных) зон первого уровня в опорной зоне 302, и (ii) вторая цифра, обладающая значением "1", указывает на то, что зона 420 первого уровня является одной из правых (восточных) зон первого уровня в опорной зоне 302. Следовательно, комбинация двух цифр, обладающих значениями "0" и " 1" соответственно, указывает на то, что зона 420 первого уровня является верхней правой (северо-восточной) зоной первого уровня среди зон 410, 420, 430 и 440 первого уровня в опорной зоне 302.

[132] Тем не менее, следует иметь в виду, что в других вариантах осуществления настоящей технологии, сервер 112 может быть выполнен с возможностью выполнять любой другой подходящий способ кодирования для кодировки географической связи между данной одной из зон 410, 420, 430 и 440 первого уровня и другими зонами 410, 420, 430 и 440 первого уровня, не выходя за пределы настоящей технологии.

[133] Как упоминалось ранее, предположим, что геомаркер "XXX" был создан для опорной зоны 302. Следовательно, сервер 112 может быть выполнен с возможностью добавлять соответствующую закодированную географическую связь к геомаркеру "XXX" опорной зоны 302 для создания соответствующих геомаркеров для зон 410, 420, 430 и 440 первого уровня таким образом, что:

- геомаркер "ХХХ00" соответствует зоне 410 первого уровня - что означает, что зона 410 первого уровня является северо-западной зоной в опорной зоне 302;

- геомаркер "ХХХ01" соответствует зоне 420 первого уровня - что означает, что зона 420 первого уровня является северо-восточной зоной в опорной зоне 302;

- геомаркер "XXX10" соответствует зоне 430 первого уровня - что означает, что зона 430 первого уровня является юго-западной зоной в опорной зоне 302; и

- геомаркер "XXX11" соответствует зоне 440 первого уровня - что означает, что зона 440 первого уровня является юго-восточной зоной в опорной зоне 302.

[134] Когда был создан геомаркер для зоны 430 первого уровня, сервер 112 может продолжать этап индексирования для зоны 430 первого уровня.

[135] С учетом того, что сегменты H-I и J-K идентифицированы для индексирования сервером 112 как связанные с зоной 430 первого уровня, со ссылкой на Фиг. 7, сервер 112 может быть выполнен с возможностью создавать, для зоны 430 первого уровня, "листовую ноду" на первом уровне 460 древовидной структуры 700 и сохранять геоданные сегментов H-I и J-K как связанных с этой листовой нодой.

[136] Процедура индексирования для зоны 430 первого уровня, тем самым, завершается. Следует отметить, что в некоторых вариантах осуществления настоящей технологии, процедура индексирования для зоны 430 первого уровня завершается созданием данной листовой ноды древовидной структуры 700 для зоны 430 первого уровня, где хранятся геоданные сегментов H-I и J-K.

[137] Следует отметить, что сервер 112 может быть выполнен с возможностью создавать дополнительные листовые ноды на первом уровне 460 для соответствующей одной из зон 410, 420 и 440 первого уровня во время процедур индексирования для соответствующих из зон 410, 420 и 440 первого уровня, аналогично тому, как сервер 112 создает листовую ноду на первом уровне 460 для зоны 430 первого уровня.

[138] Сервер 112 также может быть выполнен с возможностью создавать индекс 150. Например, сервер 112 может продолжать создавать индекс 150 путем выполнения процедур индексирования для других зон (отличных от опорной зоны 302 и зон 410, 420, 430 и 440 первого уровня) и для индексирования других сегментов многоугольника 300 (отличных от сегментов, которые уже были индексированы).

[139] Подразумевается, что в некоторых вариантах осуществления настоящей технологии сервер 112 может быть выполнен с возможностью определять, удовлетворяется ли конечное условие в процедуре индексирования зоны 430 первого уровня. В ответ на определение того, что конечное условие не выполняется, сервер 112 может продолжать создавать индекс 150. В ответ на определение того, что конечное условие выполняется, сервер 112 может индексировать сегменты многоугольника 300, которые еще не были индексированы, как связанные с соответствующими зонами нижнего уровня. То, на чем основано конечное условие, и как именно сервером 112 выполняется определение того, выполняется ли конечное условие, будет описано далее более подробно.

[140] Возвращаясь к Фиг. 5, следует отметить, что сегменты G-H, I-J, K-L и L-M, которые "попадают" в зону 430 первого уровня, и которые не пересекаются с какой-либо из линий 502 и 504 сегментирования, "попадают" дальше на второй уровень 470. Например:

- сегмент G-H расположен полностью в зоне 540 второго уровня и, следовательно, "попадает" на второй уровень 470 сегментации и в зону 540 второго уровня;

- сегмент I-J расположен полностью в зоне 530 второго уровня и, следовательно, "попадает" на второй уровень 470 сегментации и в зону 530 второго уровня; и

- сегменты K-L и L-M расположены полностью в зоне 510 второго уровня и, следовательно, "попадают" на второй уровень 470 сегментации и в зону 510 второго уровня.

[141] Со ссылкой на Фиг. 6 будет описано то, как именно сервер 112 выполнен с возможностью выполнять процедуру индексирования зоны 510 второго уровня. Следует иметь в виду, что сервер 112 может также выполнять процедуры индексирования для зон 530 и 540 второго уровня аналогичным образом и, следовательно, это не будет подробно описано далее.

[142] Следует отметить, что сервер 112 может не использовать процедуру индексирования для зоны 520 второго уровня, поскольку никакие из сегментов многоугольника 300, в данном примере, не "попадают" в зону 520 второго уровня. Поскольку в данном нет необходимости индексировать какие-либо сегменты как связанные с зоной 520 второго уровня, нет необходимости ни выполнять процедуру индексирования для зоны 520 второго уровня, ни создавать ноду в древовидной структуре 700 (см. Фиг. 7), связанной с зоной 520 второго уровня.

[143] Аналогично процедуре индексирования зоны 430 первого уровня, процедура индексирования зоны 510 второго уровня может быть суммирована до двух этапов: (i) этапа идентификации и (ii) этапа индексирования. Два этапа процедуры индексирования зоны 510 второго уровня будут описаны далее.

[144] Во время этапа идентификации, сервер 112 выполнен с возможностью сегментировать зону 510 второго уровня. Сегментирование зоны 510 второго уровня приводит ко множеству зон 610, 620, 630 и 640 третьего уровня, которые меньше по размеру, чем зона 510 второго уровня и которые расположены внутри зоны 510 второго уровня на карте. Естественно, зоны 610, 620, 630 и 640 третьего уровня также расположены внутри опорной зоны 302.

[145] На Фиг. 6 в верхней ее части представлено визуальное представление 600 того, как сервер 112 может быть выполнен с возможностью сегментировать зону 510 второго уровня. В нижней ее части показано визуальное представление 601 опорного уровня 450 опорной зоны 302, первого уровня 460 зоны 410, 420, 430 и 440 первого уровня, второго уровня 470 зон 510, 520, 530 и 540 второго уровня, и третий уровень 480.

[146] Следует отметить, что третий уровень 480 в визуальном представлении 601 показан только частично - в том смысле, что другие из зон 510, 520 и 530 и других зон второго уровня из зон 410, 420 и 440 первого уровня могут быть сегментированы на соответствующие зоны третьего уровня 480, аналогично тому как зона 510 второго уровня сегментирована на зоны 610, 620, 630 и 640 третьего уровня, не выходя за пределы настоящей технологии.

[147] Следует иметь в виду, что визуальные представления 600 и 601 представлена для визуальной иллюстрации того, как сервер 112 выполнен с возможностью выполнять процедуру индексирования зоны 510 второго уровня - сервер 112 выполнен без возможности создавать или отрисовывать сам по себе визуальные представления 600 и 601.

[148] Сервер 112 выполнен с возможностью определять линии сегментирования 602 и 604 для сегментирования зоны 510 второго уровня. Линии сегментирования 502 и 504 используются сервером 112 для сегментирования зоны 510 второго уровня на зоны 610,620, 630 и 640 третьего уровня на третьем уровне 480, как упоминалось ранее.

[149] Как упоминалось ранее, только сегменты K-L и L-M, которые "попадают" на второй уровень 470 и в зону 510 второго уровня, показаны на визуальном представлении 500. Во время этапа идентификации, аналогично тому, что было описано выше, сервер 112 может быть выполнено с возможностью идентифицировать сегменты многоугольника 300, которые перекрываются по меньшей мере с одной из линий 602 и 604 сегментирования.

[150] В данном примере, сервер 112 идентифицирует сегмент K-L как по меньшей мере частично расположенный в более чем одной из зон 610, 620, 630 и 640 третьего уровня. Таким образом идентифицированный сегмент K-L индексируется сервером 112 как связанный с зоной 510 второго уровня.

[151] Сервер 112, тем самым, выполняет этап индексирования процедуры индексирования зоны 510 второго уровня. Аналогично тому, что было описано выше для этапа индексирования зоны 430 первого уровня, индексирование сегмента K-L как связанного с зоной 430 первого уровня, может включать в себя (i) создание геомаркера для зоны 510 второго уровня и (ii) сохранение геоданных, связанных с сегментом K-L как связанных с геомаркером зоны 510 второго уровня в базе 114 данных.

[152] Геомаркер для зоны 510 второго уровня (и геомаркеры для зон 530 и 540 второго уровня) может создаваться сервером 112 с помощью алгоритма хеширования аналогично тому, как создаются геомаркеры для зон 410, 420, 430 и 440 первого уровня и, следовательно, этот процесс не будет описан далее.

[153] Тем не менее, следует отметить, что вместо добавления соответствующей закодированной географической связи между данной одной из зон 510, 520, 530 и 540 второго уровня и других из зон 510, 520, 530 и 540 второго уровня к геомаркеру опорной зоны 302 (как показано на примере на Фиг. 5), сервер 112 добавляет соответствующую закодированную географическую связь к геомаркеру зоны 430 первого уровня. В самом деле, следует учитывать, что сервер 112 выполнен с возможностью добавлять соответствующую закодированную географическую связь к геомаркеру соответствующей родительской зоны для создания геомаркера для соответствующей дочерней зоны. В случае зоны 430 первого уровня (пример на Фиг. 5), родительской зоной является опорная зона 302. В случае зоны 510 второго уровня (пример на Фиг. 6), родительской зоной является зона 430 первого уровня.

[154] Следовательно, сервер 112 может быть выполнен с возможностью добавлять соответствующую закодированную географическую связь к геомаркеру "XXX10" зоны 430 первого уровня для создания соответствующих геомаркеров для зон 510, 530 и 540 второго уровня таким образом, что:

- геомаркер "XXX1000" предназначен для зоны 510 второго уровня - что означает, что (i) зона 510 второго уровня является северо-западной зоной в зоне 430 первого уровня, и (ii) зона 510 второго уровня является северо-западной зоной в юго-западной зоне (зоне 430 первого уровня) опорной зоны 302;

- геомаркер "XXX1010" предназначен для зоны 530 второго уровня - что означает, что (i) зона 530 второго уровня является юго-западной зоной в зоне 430 первого уровня, и (ii) зона 530 второго уровня является юго-западной зоной в юго-западной зоне (зоне 430 первого уровня) опорной зоны 302; и

- геомаркер "XXX1011" предназначен для зоны 540 второго уровня - что означает, что (i) зона 530 второго уровня является юго-восточной зоной в зоне 430 первого уровня, и (ii) зона 530 второго уровня является юго-восточной зоной в юго-западной зоне (зоне 430 первого уровня) опорной зоны 302.

[155] Опять же, следует отметить, что в данном примере серверу 112 может не требоваться создавать геомаркер для зоны 520 второго уровня, как описано выше. Когда был создан геомаркер для зоны 510 второго уровня, сервер 112 может продолжать этап индексирования для зоны 510 второго уровня.

[156] С учетом того, что сегмент K-L идентифицирован для индексирования сервером 112 как связанный с зоной 510 второго уровня, со ссылкой на Фиг. 7, сервер 112 может быть выполнен с возможностью создавать, для зоны 510 второго уровня, "листовую ноду" на втором уровне 470 древовидной структуры 700 и сохранять геоданные сегмента K-L как связанные с этой листовой нодой.

[157] Процедура индексирования для зоны 510 второго уровня, тем самым, завершается. Следует отметить, что в некоторых вариантах осуществления настоящей технологии, процедура индексирования для зоны 510 второго уровня завершается созданием данной листовой ноды древовидной структуры 700 для зоны 510 второго уровня, где хранятся геоданные сегмента K-L.

[158] Следует отметить, что сервер 112 может быть выполнен с возможностью создавать дополнительные листовые ноды на втором уровне 470 для соответствующей одной из зон 530, 540 второго уровня и для других зон второго уровня из зон 410, 420 и 440 первого уровня, аналогично тому, как сервер 112 создает листовую ноду на втором уровне 470 для зоны 510 второго уровня..

[159] Сервер 112 также может быть выполнен с возможностью создавать индекс 150. Например, сервер 112 может продолжать создавать индекс 150 путем выполнения процедур индексирования для других зон (отличных от опорной зоны 302 и зон 410, 420, 430 и 440 первого уровня) и для индексирования других сегментов многоугольника 300 (отличных от сегментов, которые уже были индексированы).

[160] В некоторых вариантах осуществления настоящей технологии, сервер 112 может быть выполнен с возможностью создавать индекс 150 по меньшей мере до момента удовлетворения конечного условия. Подразумевается, что конечное условие может быть основано по меньшей мере на одном из: (i) число пикселей, включенных в по меньшей мере одну зону низшего уровня, и (ii) число сегментов, расположенных полностью в по меньшей мере одной зоне низшего уровня.

[161] Например, конечное условие может удовлетворяться в ответ на то, что сервер 112 определяет, что по меньшей мере одно из: (i) число пикселей, включенных в по меньшей мере одну зону низшего уровня, находится ниже заранее определенного минимума числа пикселей, которое будет включено по меньшей мере в одну зону низшего уровня, и (ii) число сегментов, расположенных полностью в по меньшей мере одной зоне низшего уровня, ниже заранее определенного минимального числа сегментов, предназначенных для расположения полностью в по меньшей мере одной зоне низшего уровня.

[162] Заранее определенное минимальное число пикселей, которые предназначены для включения по меньшей мере в одну зону низшего уровня и/или заранее определенное минимальное число сегментов, которые предназначены для расположения полностью по меньшей мере в одной зоне низшего уровня, могут быть определены оператором сервера 112. Например, оператор сервера 112 может определять заранее определенное минимальное число пикселей, предназначенных для включения по меньшей мере в одну зону низшего уровня и/или заранее определенное минимальное число сегментов, которые предназначены для расположения полностью по меньшей мере в одной зоне низшего уровня, для контроля за размером данной древовидной структуры, предназначенной для создания в качестве результата процесса создания индекса 150.

[163] Предположим, что для обоих нижеследующих примеров идентичный многоугольник обрабатывается на идентичной карте. В первом примере, если заранее определенное минимальное число пикселей, предназначенных для включения по меньшей мере в одну зону низшего уровня и/или заранее определенное минимальное число сегментов, которые предназначены для расположения полностью по меньшей мере в одной зоне низшего уровня, большое, следует иметь в виду, что конечное условие будет удовлетворено быстрее в процессе создания индекса 150 и, следовательно, соответствующая древовидная структура будет потенциально меньше (потенциально меньше нод на потенциально меньшем числе уровней). Во втором примере, если заранее определенное минимальное число пикселей, предназначенных для включения по меньшей мере в одну зону низшего уровня и/или заранее определенное минимальное число сегментов, которые предназначены для расположения полностью по меньшей мере в одной зоне низшего уровня, маленькое, следует иметь в виду, что конечное условие будет удовлетворено быстрее в процессе создания индекса 150 и, следовательно, соответствующая древовидная структура будет потенциально больше (потенциально больше нод на потенциально большем числе уровней).

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

[165] Как будет описано более подробно далее со ссылкой на Фиг. 8, во время фазы использования индекса 150, сервер 112 выполнен с возможностью получать доступ к по меньшей мере некоторым нодам древовидной структуры 700 для извлечения геоданных, связанных с по меньшей мере некоторыми нодами для их дальнейшей обработки. Следовательно, контролируя размер древовидной структуры 700, которая создается как результат процесса создания индекса 150 с помощью конечного условия, можно снизить общее число нод (на потенциально более чем одном уровне) древовидной структуры 700, к которой серверу 112 может потенциально понадобиться доступ для извлечения геоданных, что в свою очередь снижает количество времени, которое необходимо для операций поиска и/или извлечения данных из индекса 150.

[166] Следует также отметить, что выполнение конечного условия - другими словами, когда сервер 112 определяет, что по меньшей мере одно из (i) число пикселей, включенных в по меньшей мере одну зону низшего уровня, находится ниже заранее определенного минимума числа пикселей, которое будет включено по меньшей мере в одну зону низшего уровня, и (ii) число сегментов, расположенных полностью в по меньшей мере одной зоне низшего уровня, ниже заранее определенного минимального числа сегментов, предназначенных для расположения полностью в по меньшей мере одной зоне низшего уровня - не означает, что сегменты многоугольника 300 (и других потенциальных многоугольников), которые еще не были проиндексированы к моменту выполнения конечного условия, не будут проиндексированы. Наоборот, сегменты многоугольника 300, которые еще не были проиндексированы к моменту, когда было удовлетворено конечное условие, будут проиндексированы как связанные с соответствующими зонами низших уровней. В результате, ноды низших уровней данной древовидной структуры могут быть связаны с большим числом сегментов, если конечное условие выполняется раньше в процессе создания индекса 150, чем ноды низших уровней другой данной древовидной структуры, если конечное условие выполняется позже в процессе создания индекса 150.

[167] Дополнительно или альтернативно, конечное условие может выполняться после того как все сегменты многоугольника 300 и других потенциальных многоугольников, предназначенных для связи с индексом 150, проиндексированы сервером 112. Например, сервер 112 может быть выполнен с возможностью отслеживать, потенциально во время процедуры индексирования каждой данной зоны, число сегментов многоугольника 300 (и других потенциальных многоугольников), которые уже проиндексированы и/или которые еще не проиндексированы. Таким образом, конечное условие может выполняться, когда сервер 112 определяет, что (i) все сегменты, которые предназначены для индексирования в индекс 150, уже проиндексированы и/или (ii) все сегменты, которые предназначены для индексирования, будут проиндексированы после выполнения текущей процедуры индексирования.

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

[169] Тем не менее, эти "компромисс" между (i) меньшим количеством времени, необходимым для извлечения геоданных из данной древовидной структуры таким образом контролируемого размера, и (ii) потенциально большим объемом необходимого времени, в некоторых случаях, для дальнейшем обработки извлеченных геоданных из данной древовидной структуры таким образом контролируемого размера, может быть полезным в некоторых случаях для снижения общего объема времени, необходимого для (i) извлечения и (ii) обработки геоданных в целом.

[170] Сервер 112 может быть выполнен с возможностью проверять, выполнялось ли конечное условие раньше, во время и/или после процедуры индексации каждый данной зоны. Например, как упоминалось ранее, в ответ на выполнение конечного условия, сервер 112 может быть выполнен с возможностью индексировать данные сегменты, которые еще не проиндексированы, которые расположены внутри только одной соответствующей зоны последующего уровня, и которые в результате "попадают" на последующий уровень, связаны с только одной соответствующей зоной последующего уровня (в данном случае, только одна соответствующая зона последующего уровня может быть данной зоной низшего уровня). Другими словами, при определении того, что выполняется конечное условие, сервер 112 может быть выполнен с возможностью индексировать все сегменты, которые "попадают" на последующий уровень, как связанные с соответствующими зонами на последующем уровне (в данном случае - соответствующие зоны на последующем уровне могут быть соответствующими зонами низшего уровня).

[171] Со ссылкой на Фиг. 7, как упоминалось ранее, показана древовидная структура 700, которая создавалась сервером 112 во время процесса создания индекса 150. Как уже ранее упоминалось, древовидная структура 700 включает в себя ряд нод на различных уровнях. Например, древовидная структура 700 включает в себя (i) корневую ноду на опорном уровне 450, (ii) четыре листовых ноды на первом уровне 460, (iii) пять листовых нод на втором уровне 470 и (iv) одну листовую ноду на третьем уровне 480.

[172] Каждая нода древовидной структуры 700 связана с соответствующей зоной, и сегменты были проиндексированы сервером 112 во время процесса создания индекса 150, как описано выше. Например, (i) корневая нода связана с опорной зоной 302, (ii) четыре листовых ноды на первом уровне 460 соответственно связаны с зонами 410, 420, 430 и 440 первого уровня, (iii) пять листовых нод на втором уровне 470 соответственно связаны с зонами 720 и 730 второго уровня зоны 410 первого уровня и с зонами 510. 530 и 540 второго уровня зоны 430 первого уровня, и (iv) одна листовая нода на третьем уровне 480 связана с зоной 620 третьего уровня зоны 510 второго уровня.

[173] Также следует отметить, что геомаркеры нод древовидной структуры 700 создаются таким образом, чтобы сервер 112, на основе геомаркеров, связанных с нодами был способен определить географическую связь межу данной нодой в древовидной структуре 700 и другой данной нодой в древовидной структуре 700. Можно сказать, что при сохранении геомаркеров, связанных с соответствующими нодами в древовидной структуре 700, древовидная структура 700 включает в себя в себя информацию о "географических связях" между нодами (соответтсвующими зонами).

[174] В некоторых вариантах осуществления настоящей технологии, сервер 112 может быть выполнен с возможность выполнять алгоритм маскирования для определения географической связи между двумя данными зонами (двумя данными нодами). Этот алгоритм маскирования, при выполнении сервером 112, может быть выполнен с возможностью определять, вдоль какого направления расположена (i) первая данная зона, связанная с первой данной нодой и первым данным геомаркером, (ii) вторая данная зона, связанная со второй данной нодой и вторым данным геомаркером, на основе значений цифр первого данного геомаркера и второго данного геомаркера.

[175] Например, алгоритм маскирования может содержать большое число эвристических правил, которые определяются оператором сервера 112 на основе способа, в соответствии с которым создаются геомаркеры для соответствующих зон. Можно сказать, что большое число эвристических правил алгоритма маскирования позволяют серверу 112 выполнять алгоритм маскирования для выполнения логического анализа на основе значений цифр геомаркеров для, в некотором смысле, "извлечения" географической связи между двумя данными зонами (например, две данных ноды в древовидной структуре 700). То, как именно сервер 112 выполнен с возможностью использоваться алгоритм маскирования для определения географических связей между нодами древовидной структуры 700 во время фазы использования индекса 150, будет описано далее со ссылкой на Фиг. 8.

[176] Возвращаясь к Фиг. 1, как упоминалось ранее, устройство 102 выполнено с возможностью создавать указание 164 на местоположение данной целевой точки. Например, картографическое представление 200 (см. Фиг. 2) карты может отображаться на устройстве 103 вывода (экране, соединяемом с устройством 102, например), и устройство 102 может получать указание на пользовательское взаимодействие пользователя 102 с частью картографического представления 200 - пользователь 104 может нажать, выбрать или "прикоснуться" (например, если устройство 103 отображения представляет собой сенсорный экран) к части картографического представления 200, тем самым указывая на местоположение данной целевой точки на картографическом представлении 200. Устройство 102 может получать это указание на пользовательское взаимодействие и передавать его серверу 112 через указание 164. Например, указание 164 может содержать геоданные, связанные с местоположением данной целевой точки.

[177] Сервер 112 выполнен с возможностью определять, находится ли местоположение целевой точки внутри или снаружи географической области, связанной с индексом 150. Подразумевается, что сервер 112 может быть выполнен с возможностью определять, находится ли местоположение целевой точки внутри или снаружи географической области на основе (i) местоположения целевой точки на карте (например, геоданных, связанных с целевой точкой), (ii) набора целевых сегментов из общего числа сегментов данного многоугольника, связанных с данной географической областью, в индексе 150 и (iii) выполнения алгоритма "бросания лучей" (ray casting).

[178] Одним из способов определения того, находится ли данное местоположение внутри или снаружи данного многоугольника, является проверка того, сколько раз луч, проецируемый из данного местоположения вдоль данного направления, пересекает сегменты данного многоугольника. В одном случае, если данное местоположение находится снаружи данного многоугольника, луч будет пересекать сегменты данного многоугольника четное число раз. В другом случае, если данное местоположение находится внутри данного многоугольника, луч будет пересекать сегменты данного многоугольника нечетное число раз.

[179] Таким образом, в широком смысле, сервер 112 может быть выполнен с возможностью:

- выполнять алгоритм "бросания лучей" для создания данного луча, который проецируется из местоположения целевой точки вдоль заранее определенного направления;

- извлекать геоданные о наборе целевых сегментов из общего числа сегментов данного многоугольника, связанного с данной географической областью в индексе 150; и

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

[180] То как именно сервер 112 выполнен с возможностью выполнять алгоритм "бросания лучей", как определяется заранее определенное направление данного луча, как извлекаются геоданные из набора целевых сегментов данного многоугольника из индекса 150, и как сервер 112 определяет число раз, когда данный луч пересекает сегменты в наборе целевых сегментов, будет описано со ссылкой на Фиг. 7 и 8.

[181] На Фиг. 8 показано визуальное представление 800 зон, которые связаны с соответствующими нодами древовидной структуры 700, показанной на Фиг. 7. Следует иметь в виду, что визуальное представление 800 представлено для визуальной иллюстрации того, как сервер 112 выполнен с возможностью получать доступ к древовидной структуре 700 индекса 150 - сервер 112 выполнен без возможности создавать или отрисовывать сам по себе визуальное представление 800.

[182] На Фиг. 8 показано местоположение 850 целевой точки на карте и луч 880, проецируемый из местоположения 850 в заранее определенном направлении. Заранее определение направление, вдоль которого проецируется луч 880, может быть определено сервером 112 на основе того, как закодированы географические связи между дочерними зонами данной родительской зоны.

[183] Например, с учетом того что сервер 112 может кодировать географические связи между дочерними зонами данной родительской зоны путем применения Z-кода для кодировки в качестве части алгоритма хеширования, причем географическая связь между данной дочерней зоной и другими дочерними зонами представляет собой (i) верх (сервер) или низ (юг) в общей родительской зоне, и (ii) лево (запад) или право (восток) в общей родительской зоне, и сервер может выполнять алгоритм "бросания лучей" таким образом, чтобы данный луч проецировался в одном из (i) северном направлении, (ii) южном направлении, (iii) западном направлении, и (iv) восточном направлении.

[184] Предположим, как показано на Фиг. 8, сервер 112 выполняет алгоритм "бросания лучей" таким образом, чтобы луч 880 проецировался из местоположения 850 вдоль заранее определенного направления, представляющее собой северное направление.

[185] Далее будет описано то, как сервер 112 выполнен с возможностью определять, находится ли местоположение 850 целевой точки внутри или снаружи географической области, представляющей собой парк 202. Тем не менее, следует иметь в виду, что сервер 112 может быть выполнен с возможностью определить, находится ли местоположение 850 целевой точки внутри или снаружи другой данной географической области (например, озеро 204, парковка 206 или дорога 208), способом аналогичным тому как сервер 112 выполнен с возможностью определить, находится ли целевая точка внутри или снаружи географической области, представляющей собой парк 202, не выходя за пределы настоящей технологии.

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

[187] Как было упомянуто ранее, для определения того, находится ли местоположение 850 целевой точки внутри или снаружи географической области, представляющей собой парк 202, сервер 112 может быть выполнен с возможностью извлекать информацию о начале целевых сегментов среди общего числа сегментов многоугольника 300, которые определяют границы 210 парка 202. Для извлечения информации о наборе целевых сегментов, сервер 112 может быть выполнен с возможностью получать доступ к индексу 150.

[188] Сервер 112 может быть выполнен с возможностью получать доступ к индексу 150 и определять целевую зону низшего уровня, связанную с местоположением 850 целевой точки в древовидной структуре 700. В общем случае, целевая зона низшего уровня представляет собой данную зону низшего уровня в древовидной структуре 700, которая соответствует местоположению 850 целевой точки или, другими словами, является данной зоной низшего уровня, которая включает в себя местоположение 850 целевой точки.

[189] В некоторых вариантах осуществления настоящей технологии, сервер 112 может быть выполнен с возможностью определять целевую зону низшего уровня, по меньшей мере частично на основе геомаркеров в индексе 150. Например, сервер 112 может быть выполнен с возможностью сравнивать местоположение 850 целевой точки с геомаркерами зон в индексе 150.

[190] В некоторых вариантах осуществления настоящей технологии, сервер 112 может быть выполнен с возможностью использовать алгоритм хеширования, как было описано выше, во время сравнения местоположения 850 целевой точки с геомаркерами зон в индексе 150. Например, сервер 112 может быть выполнен с возможностью использовать алгоритм хеширования для создания геохешированной строки из геоданных, связанных с местоположением 850 целевой точки, и сравнивать таким образом созданную геохешированную строку с геомаркерами нод, хранящихся в древовидной структуре 700.

[191] В соответствии с тем, что показано в визуальном представлении 800, путем сравнения местоположения 850 целевой точки с геомаркерами зон в индексе 150 (например, геомаркерами нод древовидной структуры 700), сервер 112 может быть выполнен с возможностью определить, что опорная зона 302, зона 430 первого уровня и зона 530 второго уровня соответствуют местоположению 850 целевой точки - другими словами, сервер 112 может определять, что местоположение 850 включено в каждую из опорной зоны 302, зоны 430 первого уровня и зоны 530 второго уровня. Сервер 112 может также определять, что целевая зона низшего уровня во второй зоне 530 второго уровня, поскольку она является зоной низшего уровня в древовидной структуре 700 среди опорной зоны 302, зоны 430 первого уровня и зоны 530 второго уровня.

[192] Когда сервер 112 определяет, что целевая зона низшего уровня для местоположения 850 целевой точки, сервер 112 может быть выполнен с возможностью определять другие целевые зоны, которые являются зонами, хранящимися как связанные с соответствующими нодами в индексе 150, и которые (i) по меньшей мере частично расположены вдоль заранее определенного направления (например, северное направление луча 880) на карте от целевой зоны низшего уровня, и (ii) по меньшей частично выровнены в заранее определенном направлении с целевой зоной низшего уровня. Другими словами, сервер 112 может определять другие зоны, связанные с нодами древовидной структуры 700, которые (i) по меньшей мере частично расположены вдоль северного направления от зоны 530 второго уровня и (ii) по меньшей мере частично выровнены в северном направлении с зоной 530 второго уровня.

[193] Подразумевается, что сервер 112 может быть выполнен с возможностью определять те другие целевые зоны на основе геомаркеров зон, хранящихся в индексе 150. Например, сервер 112 может быть выполнен с возможностью выполнять алгоритм маскирования на геомаркерах зон, хранящихся в индексе 150 для определения других цифровых зон в древовидной структуре 700.

[194] В этом случае, сервер 112 может определять, что другие целевые зоны представляют собой: зону 510 второго уровня, зону 620 третьего уровня, зону 430 первого уровня, зону 410 первого уровня, зону 730 второго уровня и опорную зону 302.

[195] Как было упомянуто ранее, эвристические правила алгоритма маскирования позволяют серверу 112 выполнять алгоритм маскирования для выполнения логического анализа на основе значений цифр геомаркеров для, в некотором смысле, "извлечения" географической связи между зонами, связанных с этими геомаркерами. Далее будет описано то, как именно сервер 112 выполнен с возможностью выполнять этот логический анализ путем выполнения алгоритма маскирования для определения других целевых зон, которые по меньшей мере частично расположены вдоль северного направления луча 880 из зоны 530 второго уровня, и которые по меньшей мере частично выровнены с зоной 530 второго уровня в северном направлении луча 880.

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

[197] Логический анализ, выполняемый сервером 112 с помощью выполнения алгоритма маскирования, инициируется (i) целевой зоной низшего уровня, являющейся зоной 530 второго уровня и (ii) заранее определенным направлением луча 880, являющегося северным направлением. Целью логического анализа является определение зон, которые (i) по меньшей мере частично расположены вдоль северного направления из зоны 530 второго уровня и (ii) по меньшей мере частично выровнены с зоной 530 второго уровня в северном направлении.

[198] В первом случае, сервер 112 может быть выполнен с возможностью "идти вверх" по древовидной структуре 700 из ноды зоны 530 второго уровня до ноды зоны 430 первого уровня, и выполнять алгоритм маскирования геомаркера "XXX10" зоны 430 первого уровня. Сервер 112 может, тем самым, определять, на основе геомаркеров зоны 530 второго уровня и зоны 430 первого уровня, что зона 430 первого уровня является родительской зоной для зоны 530 второго уровня. Поскольку зона 430 первого уровня является родительской зоной зоны 530 второго уровня, сервер 112 идентифицирует зону 430 первого уровня как одну из других целевых зон. В самом деле, поскольку зона 430 первого уровня является родительской зоной зоны 530 второго уровня, зона 430 первого уровня включает в себя зону 530 второго уровня и может, соответственно, быть (i) по меньшей мере частично расположена вдоль северного направления из зоны 530 второго уровня и (ii) по меньшей мере частично выровнена с зоной 530 второго уровня в северном направлении.

[199] После того как сервер 112 получается данную ноду в древовидной структуре 700, которая (i) связана с данной одной из других целевых зон и (ii) обладает дочерними нодами, сервер 112 может быть выполнен с возможностью "идти вниз" по древовидной структуре 700 из данной ноды к соответствующим дочерним нодам для определения того, связаны ли соответствующие дочерние ноды и/или другие ноды, происходящие из соответствующих дочерних нод, с зонами, предназначенными для включения в другие целевые зоны.

[200] Следовательно, во втором случае, сервер 112 может быть выполнен с возможностью "идти вниз" по древовидной структуре 700 из ноды зоны 430 первого уровня до других дочерних нод ноды зоны 430 первого уровня, и выполнять алгоритм маскирования геомаркеров других дочерних ноды ноды зоны 430 первого уровня. Другими словами, сервер 112 может выполнять алгоритм маскирования геомаркеров зон 510 и 540 второго уровня.

[201] Сервер 112 может быть выполнен с возможностью сравнивать геомаркер зоны 530 второго уровня с геомаркером зоны 540 второго уровня. Сервер 112 может определять, в данном случае на основе значений двух последних цифр каждого из геомаркеров зон 530 и 540 второго уровня, что зона 540 второго уровня (i) расположена вдоль восточного направления из зоны 530 второго уровня и/или не расположена по меньшей мере частично вдоль северного направления из зоны 530 второго уровня, и (ii) не выровнена с зоной 530 второго уровня в северном направлении. Таким образом, сервер 112 не идентифицирует зону 540 второго уровня как являющуюся одной из других целевых зон.

[202] Следует отметить, что если дополнительные ноды исходят из ноды зоны 540 второго уровня в древовидной структуре 700, причем сервер 112 может быть выполнен без возможности сравнивать или, иначе, "пропускать" сравнение между геомаркерами, связанными с этими дополнительными нодами и геомаркером зоны 530 второго уровня. В самом деле, зоны, связанные с этими дополнительными нодами, были включены в зону 540 второго уровня и, следовательно, поскольку зона 540 второго уровня не является одной из целевых зон, зоны, связанными с этими дополнительными нодами не могут быть (i) по меньшей мере частично расположены вдоль северного направления из зоны 530 второго уровня и (ii) по меньшей мере частично выровнены с зоной 530 второго уровня в северном направлении.

[203] Сервер 112 может быть выполнен с возможностью сравнивать геомаркер зоны 530 второго уровня с геомаркером зоны 510 второго уровня. Сервер 112 может определять, в данном случае на основе значений двух последних цифр каждого из геомаркеров зон 510 и 530 второго уровня, что зона 510 второго уровня (i) расположена по меньшей мере частично вдоль северного направления из зоны 530 второго уровня, и (ii) выровнена с зоной 530 второго уровня в северном направлении. Таким образом, сервер 112 идентифицирует зону 510 второго уровня как являющуюся одной из других целевых зон.

[204] В третьем случае, как описано выше, поскольку нода, связанная с зоной 510 второго уровня, являющаяся одной из других целевых зон, обладает данной дочерней нодой, сервер 112 может быть выполнен с возможностью "идти вниз" в древовидной структуре 700 из ноды зоны 510 второго уровня к данной дочерней ноде и выполнять алгоритм маскирования геомаркера данной дочерней ноды. Например, сервер 112 может быть выполнен с возможностью "идти вниз" по древовидной структуре 700 из ноды зоны 510 второго уровня до ноды, связанной с нодой 620 третьего уровня, и выполнять алгоритм маскирования геомаркера "XXX100001" зоны 620 третьего уровня.

[205] Сервер 112 определяет, на основе геомаркеров зона 620 третьего уровня и зона 530 второго уровня, нода зона 620 третьего уровня (i) является дочерней ноды для ноды, связанной с зоной 510 второго уровня, которая является одной из целевых зон и (ii) находится на третьем уровне 480 древовидной структуры 700, которая находится ниже второго уровня 470 зоны 530 второго уровня. Это означает, что зона 620 третьего уровня (i) включена в зону 510 второго уровня, которая была определена как одна из других целевых зон, и (ii) меньше по размеру, чем зона 530 второго уровня. В результате, зона 620 третьего уровня также (i) расположена вдоль северного направления из зоны 530 второго уровня и (ii) выровнена с зоной 530 второго уровня в северном направлении. Таким образом, сервер 112 идентифицирует зону 620 третьего уровня как являющуюся одной из других целевых зон.

[206] Следует отметить, что когда сервер 112 находится внизу данной ветви в древовидной структуре 700, сервер 112 может "идти вверх" обратно к ноде, из которой происходит данная ветвь. Например, в четвертом примере, когда сервер 112 находится на надое зоны 620 третьего уровня данной ветви древовидной структуры 700, которая происходит из ноды 430 первого уровня, сервер 112 может не "идти вниз" далее из ноды зоны 620 третьего уровня в древовидной структуре 700. В результате, сервер 112 выполнен с возможностью "идти вверх" обратно к ноде зоны 430 первого уровня, и далее оттуда "идти вверх" к корневой ноде опорной зоны 302.

[207] Таким образом, сервер 112 может выполнять алгоритм маскирования геомаркера "XXX" опорной зоны 302. Сервер 112 может определять, на основе геомаркера зоны 530 второго уровня и геомаркера опорной зоны 302, причем опорная зона 302 включает в себя зону 530 второго уровня. Сервер 112, тем самым, идентифицирует опорную зону 302 как являющуюся одной из других целевых зон. В самом деле, поскольку опорная зона 302 является зоной 530 второго уровня, опорная зона 302 может быть (i) по меньшей мере частично расположена вдоль северного направления из зоны 530 второго уровня и (ii) по меньшей мере частично выровнена с зоной 530 второго уровня в северном направлении.

[208] В пятом случае, как описано выше, поскольку корневая нода, связанная с опорной зоной 302, являющаяся одной из других целевых зон, обладает другими дочерними нодами, сервер 112 может быть выполнен с возможностью "идти вниз" в древовидной структуре 700 из корневой ноды к другим дочерним нодам и выполнять алгоритм маскирования геомаркеров других дочерних нод. Например, сервер 112 может быть выполнен с возможностью "идти вниз" по древовидной структуре 700 из корневой ноды опорной зоны 302 до нод, связанной с зонами 410, 420 и 430 первого уровня и выполнять алгоритм маскирования геомаркеров нод зон 410, 420 и 440 первого уровня.

[209] Следует учитывать, что геомаркеры зоны 420 и 440 первого уровня представляют собой соответственно "ХХХ01" и "ХХХ11", а геомаркер зоны 530 второго уровня представляет собой "ХХХ1010". В данном случае, сервер 112 может быть выполнен с возможностью сравнивать значения по меньшей мере двух цифр геомаркеров зоны 420 и 440 первого уровня со значениями двух цифр, предшествующих последним двум цифрам геомаркера зоны 530 второго уровня. Другими словами, сервер 112 может сравнивать "01" из геомаркера зоны 420 первого уровня и "11" из геомаркера зоны 440 первого уровня с "10" из геомаркера зоны 530 второго уровня.

[210] Следует отметить, что "10" из геомаркера зоны 530 второго уровня является закодированной географической связью данной зоны, включающей в себя зону 530 второго уровня, и которая расположена на том же уровне в древовидной структуре 700, что и зоны 420 и 440 первого уровня - другими словами, "10" из геомаркера зоны 530 второго уровня является закодированной географической связью между зоно1 430 первого уровня, которая включает в себя зону 530 второго уровня и зоны 410, 420 и 440 первого уровня.

[211] Следовательно, на основе "01" из первого геомаркера зоны 420 первого уровня и "10" из геомаркера зоны 530 второго уровня, сервер 112 может быть выполнен с возможностью определить, что зона 420 первого уровня (i) расположена вдоль северо-восточного направления из зоны 530 второго уровня, но (ii) не выровнена даже частично вдоль зоны 530 второго уровня в северном направлении. Также, на основе "01" из первого геомаркера зоны 420 первого уровня и "10" из геомаркера зоны 530 второго уровня, сервер 112 может быть выполнен с возможностью определить, что зона 420 первого уровня расположена вдоль восточного направления из зоны 530 второго уровня и/или не расположена вдоль северо-восточного направления из зоны 530 второго уровня, и не выровнена даже частично вдоль зоны 530 второго уровня в северном направлении. В результате, сервер 112 не идентифицирует зоны 420 и 440 первого уровня как соответствующие другие целевые зоны.

[212] Следует учитывать, что геомаркер зоны 410 первого уровня представляет собой соответственно "ХХХ00", а геомаркер зоны 530 второго уровня представляет собой "XXX1010". В данном случае, сервер 112 может быть выполнен с возможностью сравнивать значения по меньшей мере двух цифр геомаркера зоны 410 первого уровня со значениями двух цифр, предшествующих последним двум цифрам геомаркера зоны 530 второго уровня. Сервер 112 может быть выполнен с возможностью сравнивать "00" геомаркера зоны 410 первого уровня с "10" геомаркера зоны 530 второго уровня.

[213] Аналогично тому, что было описано выше во время сравнения геомаркеров зон 420 и440 первого уровня с геомаркером зоны 530 второго уровня, на основе "00" из первого геомаркера зоны 410 первого уровня и "10" из геомаркера зоны 530 второго уровня, сервер 112 может быть выполнен с возможностью определить, что зона 410 первого уровня (i) расположена вдоль северного направления из зоны 530 второго уровня, и (ii) выровнена по меньшей мере частично вдоль зоны 530 второго уровня в северном направлении. Таким образом, сервер 112 идентифицирует зону 410 первого уровня как являющуюся одной из других целевых зон.

[214] В шестом случае, как описано выше, поскольку нода, связанная с зоной 410 первого уровня, являющаяся одной из других целевых зон, обладает соответствующими дочерними нодами, сервер 112 может быть выполнен с возможностью "идти вниз" по древовидной структуре 700 из ноды зоны 410 первого уровня к соответствующим дочерним нодам и выполнять алгоритм маскирования геомаркеров соответствующих дочерних нод. Например, сервер 112 может быть выполнен с возможностью "идти вниз" по древовидной структуре 700 из ноды зоны 410 первого уровня до нод зон 720 и 730 второго уровня и выполнять алгоритм маскирования геомаркеров из нод зон 720 и 730 второго уровня.

[215] Сервер 112 может быть выполнен с возможностью сравнивать геомаркер зоны 530 второго уровня с геомаркером зоны 720 второго уровня. Следует учитывать, что геомаркер зоны 720 второго уровня представляет собой "ХХХ0001", а геомаркер зоны 530 второго уровня представляет собой "XXX1010". На основе двух цифр, предшествующих двум цифрам каждого из геомаркеров зон 720 и 530 второго уровня, которые являются "00" и "10" соответственно, сервер 112 может быть выполнен с возможностью определить, что родительская зона зоны 720 второго уровня расположена вдоль северного направления из родительской зоны зоны 530 второго уровня. Также на основе последних двух цифр каждого из геомаркеров зон 720 и 530 второго уровня, которые представляют собой "01" и "10", сервер 112 может определять зону 720 второго уровня как верхнюю правую (северо-восточную) зону в своей родительской зоне, а зона 530 второго уровня является нижней левой (юго-западной) зоной в своей родительской зоне. Следовательно, сервер 112 может определить, что зона 720 второго уровня (i) расположена вдоль северо-восточного направления из зоны 530 второго уровня, но (ii) не выровнена даже частично с зоной 530 второго уровня в северном направлении. Таким образом, сервер 112 не идентифицирует зону 720 второго уровня как являющуюся одной из других целевых зон.

[216] Сервер 112 может быть выполнен с возможностью сравнивать геомаркер зоны 530 второго уровня с геомаркером зоны 730 второго уровня. Следует учитывать, что геомаркер зоны 730 второго уровня представляет собой "ХХХ0010", а геомаркер зоны 530 второго уровня представляет собой "XXX1010". На основе двух цифр, предшествующих двум цифрам каждого из геомаркеров зон 730 и 530 второго уровня, которые являются "00" и "10" соответственно, сервер 112 может быть выполнен с возможностью определить, что родительская зона зоны 730 второго уровня расположена вдоль северного направления из родительской зоны зоны 530 второго уровня. Также на основе последних двух цифр каждого из геомаркеров зон 730 и 530 второго уровня, которые представляют собой "10" и "10", сервер 112 может определять зону 730 второго уровня как нижнюю левую (юго-западную) зону в своей родительской зоне, а зона 530 второго уровня является нижней левой (юго-западной) зоной в своей родительской зоне. Следовательно, сервер 112 может определить, что зона 730 второго уровня (i) расположена вдоль северного направления из зоны 530 второго уровня, и (ii) выровнена по меньшей мере частично с зоной 530 второго уровня в северном направлении. В результате, сервер 112 идентифицирует зону 730 второго уровня как являющуюся одной из других целевых зон.

[217] В общем, сервер 112 выполнен с возможностью выполнять алгоритм маскирования геомаркеров, связанных с нодами древовидной структуры 700 для определения того, какие ноды связаны с зонами, которые (i) по меньшей мере частично расположены вдоль северного направления из зоны 530 второго уровня и (ii) по меньшей мере частично выровнены с зоной 530 второго уровня в северном направлении. В самом деле, сервер 112 путем выполнения алгоритма маскирования может выполнять логический анализ на основе геомаркеров узлов древовидной структуры 700 для определения того, что другие целевые зоны представляют собой: зону 510 второго уровня, зону 620 третьего уровня, зону 430 первого уровня, зону 410 первого уровня, зону 730 второго уровня и опорную зону 302.

[218] Подразумевается, что сервер 112 может быть выполнен с возможностью формировать набор целевых зон (i) связанных с целевой точкой и заранее определенным направлением на карте и (ii) основанных на целевой зоне низшего уровня и других целевых зонах. В этом случае, сервер 112 может быть выполнен с возможностью формировать набор целевых зон, который представляет собой: зону 530 второго уровня, зону 510 второго уровня, зону 620 третьего уровня, зону 430 первого уровня, зону 410 первого уровня, зону 730 второго уровня и опорную зону 302.

[219] Сервер 112 может быть выполнен с возможностью извлекать геоданные, связанные с сегментами, сохраненными в индексе 150, которые связаны с нодами каждой из набора целевых зон. В данном случае, сервер 112 выполнен с возможностью извлекать геоданные, связанные с сегментом I-J из ноды, связанной с зоной 530 второго уровня, сегментом K-L из ноды, связанной с зоной 510 второго уровня, сегментом L-M из ноды, связанной с зоной 620 третьего уровня, сегментами H-I и J-K из ноды, связанной с зоной 430 первого уровня, сегментами О-Р и P-Q из ноды, связанной с зоной 410 первого уровня, сегментом N-O из ноды, связанной с зоной 730 второго уровня и сегментами А-В, D-E, F-G и M-N из корневой ноды, связанной с опорной зоной 302.

[220] Сервер 112 далее выполнен с возможностью создавать набор целевых сегментов путем группировки сегментов из набора целевых зон, которые связаны с многоугольником 300. В данном случае, все сегменты, извлеченные из нод, связанных с каждой из набора целевых зон, связаны с многоугольником 300. Тем не менее, следует иметь в виду, что это может быть необязательным в других вариантах осуществления настоящей технологии, где сегменты других потенциальных многоугольников хранятся в индексе 150.

[221] Следует отметить, что в данном случае набор сегментов включает в себя сегменты I-J, K-L, L-M, H-I, J-K, О-Р, P-Q, N-O, А-В, D-E, F-G и M-N из общего числа сегментов многоугольника 300. Другими словами, набор целевых сегментов не включает в себя сегменты Q-A, В-С, C-D, G-H и E-F из общего числа сегментов многоугольника 300. Следовательно, как упоминалось ранее, набор целевых сегментов включает в себя ряд сегментов из многоугольника 300, который меньше, чем общее число сегментов многоугольника 300.

[222] Сервер 112 может быть выполнен с возможностью геометрически определить число целевых сегментов из набора целевых сегментов, которые пересекают луч 880. Подразумевается, что поскольку ряд сегментов в наборе целевых сегментов меньше, чем общее число сегментов многоугольника 300, геометрическое определение того, сколько целевых сегментов из набора целевых сегментов пересекает луч 800, требует меньшей вычислительной мощности и времени, чем геометрическое определение того, сколько сегментов из всех сегментов многоугольника 300 пересекает луч 800. Таким образом, можно сказать, что путем создания набора целевых сегментов, как было описано выше, сервер 112 выполнен с возможностью определять подмножество сегментов многоугольника 300, которые потенциально могут быть пересечены лучом 880, и которые меньше, чем полный набор сегментов многоугольника 300.

[223] Сервер 112 может быть выполнен с возможностью геометрически определить, пересекает ли данный целевой сегмент из набора целевых сегментов луч 880 на основе геоданных данных целевых сегментов и геоданных луча 880.

[224] Как было описано ранее, в ответ на геометрическое определение того, что целевые сегменты пересекают луч 880 четное количество раз, сервер 112 выполнен с возможностью определять, что местоположение 850 целевой точки находится снаружи многоугольника 300 и, следовательно, снаружи парка 202. С другой стороны, в ответ на геометрическое определение того, что целевые сегменты пересекают луч 880 нечетное количество раз, сервер 112 выполнен с возможностью определять, что местоположение 850 целевой точки находится внутри многоугольника 300 и, следовательно, внутри парка 202.

[225] Предположим, что сервер 112 определяет, что местоположение 850 целевой точки -внутри парка 202. В результате, сервер 112 может быть выполнен с возможностью создавать ответ 166, содержащий зависящие от области данные, связанные с парком 202, и передавать их устройству 102 для отображения пользователю 104 с помощью устройства 103 вывода.

[226] В некоторых вариантах осуществления настоящего технического решения сервер 112 может быть выполнен с возможностью выполнять способ 900 для создания индекса 150. Например, сервер 112 может быть выполнен с возможностью выполнять способ 900 для индексирования множества сегментов многоугольника 300 и других потенциальных многоугольников. Различные этапы способа 900 будут описаны далее со ссылкой на Фиг. 9.

ЭТАП 902: Сегментирование опорной зоны на зоны первого уровня

[227] Способ 900 начинается на этапе 902, где сервер 112 выполнен с возможностью сегментировать опорную зону 302 на опорном уровне 450 на зоны 410, 420, 430 и 440 опорного уровня на первом уровне 460, как показано на Фиг. 4. Опорная зона 302 покрывает часть карты, которая включает в себя все сегменты многоугольника 300. В других вариантах осуществления настоящей технологии, данная опорная зона может покрывать всю карту. Опорная зона 302 является "родительской зоной" для зон 410, 420, 430 и 440 первого уровня.

[228] Зоны 410, 420, 430 и 440 первого уровня представлены как четыре квадратные зоны. Тем не менее, следует иметь в виду, что число и форма зон 410, 420, 430 и 440 первого уровня могут зависеть от, среди прочего, формы соответствующей опорной зоны 302, числа линий сегментирования, определенных сервером 112 и/или различных вариантов осуществления технологии. Зоны 410, 420, 430 и 440 первого уровня представлены как равные или, другими словами, занимающие равные области опорной зоны 302. Тем не менее, зоны 410, 420, 430 и 440 первого уровня могут занимать неравные области опорной зоны 302 в других вариантах осуществления, не выходя за границы настоящей технологии.

[229] В неограничивающем варианте осуществления Фиг. 4. после определения линий сегментирования 402 и 404, они используются сервером 112 для, в некотором смысле, для "тесселяции" опорной зоны 302 множеством одинаковых непрерывных квадратных ячеек или квадрантов (зоны 410, 420, 430 и 440 первого уровня) таким образом, чтобы образовалась сетка для опорной зоны 302.

ЭТАП 904: В ответ на то, что по меньшей мере один сегмент по меньшей мере частично расположен в более чем одной зоне первого уровня, индексирование по меньшей мере одного сегмента как связанного с опорной зоной

[230] Способ 900 продолжается на этапе 904, где сервер 112 выполнен с возможностью, в ответ по меньшей мере на один сегмент многоугольника 300, который по меньшей мере частично расположен внутри более чем одной из зон 410, 420, 430 и 440 первого уровня, индексирование по меньшей мере одного сегмента как связанного с опорной зоной 302.

[231] Другими словами, после того как опорная зона 302 сегментирована при выполнении этапа 902, сервер 112 выполнен с возможностью идентифицировать сегменты многоугольника 300 (или другие потенциальные многоугольники), которые расположены по меньшей мере частично в более чем одной из зон 410, 420, 430 и 440 первого уровня (например, более чем один квадрант сетки опорной зоны 302). Другими словами, сервер 112 может быть выполнен с возможностью идентифицировать сегменты многоугольника 300, которые пересекают по меньшей мере одну из линий 402 и 404 сегментирования, которые используются для сегментирования опорной зоны 302.

[232] В данном примере на Фиг. 4, сервер 112 идентифицирует сегменты А-В, D-E, F-G и M-N как по меньшей мере частично расположенную в более чем одной из зон 410, 420, 430 и 440 первого уровня. Таким образом идентифицированные сегменты А-В, D-E, F-G и M-N индексируются сервером 112 как связанные с опорной зоной 302.

[233] Подразумевается, что сервер 112 для индексирования сегментов А-В, D-E, F-G и М-N выполнен с возможностью осуществлять сохранение геоданных, связанных с сегментами А-В, D-E, F-G и M-N, которые связаны с опорной зоной 302 в базе 114 данных.

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

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

[236] Подразумевается, что создание геомаркера для опорной зоны 302 может выполняться сервером 112 с помощью алгоритма геохеширования, применяемого сервером 112. Как было описано выше, сервер 112 может применять алгоритм геохеширования для кодировки местоположения опорной зоны 302 как "XXX" на карте или с помощью любой подходящей геохешированной строки

[237] В некоторых вариантах осуществления настоящей технологии, со ссылкой на Фиг. 7, сервер 112 может быть выполнен с возможностью создавать для опорной зоны 302 корневую ноду на опорной уровне 450 древовидной структуры 700 и сохранять геоданные сегментов А-В, D-E, F-G и M-N, связанных с этой корневой нодой. Например, поскольку опорная зона 302 покрывает только часть карты, корневая нода может создаваться как связанная с геомаркером "XXX" опорной зоны 302.

[238] В некоторых вариантах осуществления настоящей технологии, выполнение этапа 904 способа 904 сервером 112 завершается созданием корневой ноды древовидной структуры 700, где хранятся геоданные сегментов А-В, D-E, F-G и M-N.

[239] После того как сегменты А-В, D-E, F-G и M-N индексированы, как описано выше, сервер 112 может быть выполнен с возможностью продолжать создание индекса 150 для индексирования других сегментов многоугольника 300 (отличных от сегментов А-В, D-E, F-G и M-N, поскольку они уже проиндексированы), связанных с зонами, отличными от опорной зоны.

ЭТАП 906: До момента выполнения конечного условия, итеративно (i) сегментирование данной зоны на зоны последующих уровней; и (ii) в ответ то, что по меньшей мере один другой сегмент по меньшей мере частично расположен внутри более чем одной зоны последующего уровня, индексирование по меньшей мере одного другого сегмента как связанного с данной зоной.

[240] Способ 900 продолжается на этапе 906, который итеративно повторяется сервером 112 по меньшей мере до выполнения конечного условия.

[241] Как часть этапа 906, сервер 112 выполнено с возможностью осуществлять (i) сегментирование данной зоны на данном уровне на зоны последующих уровней, причем данная зона является родительской зоной для соответствующих зон последующих уровней; и (ii) в ответ то, что по меньшей мере один другой сегмент по меньшей мере частично расположен внутри более чем одной соответствующей зоны последующего уровня, индексирование по меньшей мере одного другого сегмента как связанного с данной зоной.

[242] Например, первая итерация этапа 906 выполняется на зоне 430 первого уровня со ссылкой на Фиг. 5. В данном примере, сервер 112 сегментирует зону 430 первого уровня на первом уровне 470, таким образом, что зона 430 первого уровня является родительской зоной для зон 510, 520, 530 и 540 второго уровня. В данном примере, в ответ на то, что сегменты H-I и J-K по меньшей мере частично расположены более чем в одной соответствующей зоне 510, 520, 530 и 540 второго уровня, сервер 112 индексирует сегменты H-I и J-K, связанные с зоной 430 первого уровня.

[243] В другом примере, вторая итерация этапа 906 выполняется на зоне 510 второго уровня со ссылкой на Фиг. 6. В данном примере, сервер 112 сегментирует зону 510 второго уровня на втором уровне 470 на зоны 610, 620, 630 и 640 третьего уровня на третьем уровне 480, таким образом, что зона 510 второго уровня является родительской зоной для зон 610, 620, 630 и 640 третьего уровня. В данном примере, в ответ на то, что сегмент K-L по меньшей мере частично расположен более чем в одной соответствующей зоне 610, 620, 630 и 640 третьего уровня, сервер 112 индексирует сегмент K-L, связанный с зоной 510 второго уровня.

[244] Подразумевается, что во время данной итерации на этапе 906, для индексирования по меньшей мере одного сегмента как связанного с данной зоной, сервер 112 выполнен с возможностью осуществлять (i) создание геомаркера для данной зоны, которая указывает на местоположение данной зоны в отношении дочерней зоны и географическую связь между данной зоной и другими дочерними зонами соответствующей родительской зоны, и (ii) сохранение данных по меньшей мере об одном другом сегменте, связанном с геомаркером данной зоны.

[245] Например, во время первой итерации этапа 906, сервер 112 выполнен с возможностью создавать геомаркер "XXX10" для зоны 430 первого уровня.

[246] В некоторых вариантах осуществления настоящей технологии, для создания геомаркера для зоны 430 первого уровня, сервер 112 может быть выполнен с возможностью осуществлять: (i) кодировку географической связи между зоной 430 первого уровня, и зонами 410, 420 и 440 первого уровня, и (ii) если геомаркер был создан для дочерней зоны (в данном случае, опорной зоны 302), создавать геомаркер путем дополнения геомаркера родительской зоны с помощью соответствующей закодированной географической связи.

[247] Предположим, как упоминалось ранее, что геомаркер "XXX" был создан для опорной зоны 302. Таким образом, сервер 112 может создавать геомаркеры для зоны 430 первого уровня путем (i) кодирования географической связи между зоной 430 первого уровня и зонами 410, 420 и 440 первого уровня, и (ii) добавления соответствующей закодированной географической связи к геомаркеру "XXX".

[248] Географическая связь между зоной 430 первого уровня и зонами 410, 420 и 440 первого уровня может быть закодирована различными способами. В другом варианте осуществления технологии, сервер 112 может применять Z-код для кодировки как часть алгоритма хеширования, как было описано выше. Например, сервер 112 может применять Z-код для кодировки как часть алгоритма хеширования для создания закодированной географической связи "10" для зоны 430 первого уровня, поскольку зона 430 первого уровня является нижним левым (юго-западным) квадрантом сетки опорной зоны 302.

[249] Следует отметить, что геомаркер зоны 430 первого уровня указывает на (i) местоположение зоны 430 первого уровня в родительской зоне, представляющей собой опорную зону 302, и (ii) географическую связь между зоной 430 первого уровня и зонами 410, 420 и 440 первого уровня.

[250] В данном случае, закодированная географическая связь "10" для зоны 430 первого уровня включает в себя две цифры, где (i) первая цифра, обладающая значением "1", указывает на то, что зона 430 первого уровня является одной из нижних (южных) зон первого уровня в опорной зоне 302, и (ii) вторая цифра, обладающая значением "0", указывает на то, что зона 430 первого уровня является одной из левых (западных) зон первого уровня в опорной зоне 302. Следовательно, комбинация двух цифр, обладающих значениями "1" и "0" соответственно, указывает на то, что зона 430 первого уровня является нижней левой (юго-западной) зоной первого уровня среди зон 410, 420, 430 и 440 первого уровня в опорной зоне 302.

[251] Тем не менее, следует иметь в виду, что в других вариантах осуществления настоящей технологии, сервер 112 может быть выполнен с возможностью выполнять любой другой подходящий способ кодирования для кодировки географической связи между данной одной из зон 410, 420, 430 и 440 первого уровня и другими зонами 410, 420, 430 и 440 первого уровня, не выходя за пределы настоящей технологии.

[252] В другом примере, во время второй итерации этапа 906, сервер 112 выполнен с возможностью создавать геомаркер "XXX1000" для зоны 510 второго уровня. Сервер 112 может быть выполнен с возможностью создавать геомаркер "XXX1000" для зоны 510 второго уровня аналогично тому, как сервер 112 выполнен с возможностью создавать геомаркер "XXX10" для зоны 430 первого уровня, не выходя за пределы настоящей технологии.

[253] Как было упомянуто ранее, этап 906 способа 900 итеративно повторяется сервером 112 по меньшей мере до выполнения конечного условия. Подразумевается, что конечное условие может быть основано по меньшей мере на одном из: (i) число пикселей, включенных в по меньшей мере одну зону низшего уровня, и (ii) число сегментов, расположенных полностью в по меньшей мере одной зоне низшего уровня.

[254] Например, конечное условие может удовлетворяться в ответ на то, что сервер 112 определяет, что по меньшей мере одно из: (i) число пикселей, включенных в по меньшей мере одну зону низшего уровня, находится ниже заранее определенного минимума числа пикселей, которое будет включено по меньшей мере в одну зону низшего уровня, и (ii) число сегментов, расположенных полностью в по меньшей мере одной зоне низшего уровня, ниже заранее определенного минимального числа сегментов, предназначенных для расположения полностью в по меньшей мере одной зоне низшего уровня.

[255] Заранее определенное минимальное число пикселей, которые предназначены для включения по меньшей мере в одну зону низшего уровня и/или заранее определенное минимальное число сегментов, которые предназначены для расположения полностью по меньшей мере в одной зоне низшего уровня, могут быть определены оператором сервера 112. Например, оператор сервера 112 может определять заранее определенное минимальное число пикселей, предназначенных для включения по меньшей мере в одну зону низшего уровня и/или заранее определенное минимальное число сегментов, которые предназначены для расположения полностью по меньшей мере в одной зоне низшего уровня, для контроля за размером данной древовидной структуры, предназначенной для создания в качестве результата процесса создания индекса 150.

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

Изобретение относится к области вычислительной техники. Техническим результатом является обеспечение создания индекса сегментов по меньшей мере одного многоугольника, определяющего границы соответствующей географической области на карте. Раскрыт способ создания индекса сегментов по меньшей мере одного многоугольника, определяющего границы соответствующей географической области на карте. Способ включает в себя сегментирование опорной зоны, которая охватывает по меньшей мере часть карты, в которой находятся все сегменты многоугольника, на зоны первого уровня. В ответ на то что по меньшей мере один сегмент по меньшей мере частично расположен в более чем одной зоне первого уровня, способ включает в себя индексирование по меньшей мере одного сегмента как связанного с опорной зоной. Способ также включает в себя, до достижения конечных условий, итерационно: (i) сегментирование данной зоны на зоны последующих уровней, причем данная зона является родительской зоной для зон последующих уровней; и (ii) в ответ на то что по меньшей мере один другой сегмент по меньшей мере частично расположен внутри более чем одной зоны последующего уровня, индексирование по меньшей мере одного другого сегмента как связанного с данной зоной. 2 н. и 18 з.п. ф-лы, 9 ил.

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

сегментирование электронным устройством опорной зоны на опорном уровне на зоны первого уровня на первом уровне, причем опорная зона покрывает по меньшей мере часть карты, которая включает в себя все сегменты по меньшей мере одного многоугольника, причем опорная зона является родительской зоной для зон первого уровня;

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

сохранение электронным устройством данных по меньшей мере об одном другом сегменте, связанном с опорной зоной;

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

до достижения конечного условия, итерационно:

сегментирование электронным устройством данной зоны на данном уровне на зоны последующего уровня на последующем уровне, причем данная зона является родительской зоной в отношении зоны последующего уровня; и

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

создание электронным устройством геомаркера для данной зоны, причем геомаркер указывает на (i) расположение данной зоны в соответствующей родительской зоне, причем соответствующая родительская зона данной зоны находится на предыдущем уровне по отношению к данному, и (ii) географическую связь между данной зоной и другими дочерними зонами по отношению к соответствующей родительской зоне; и

сохранение электронным устройством данных по меньшей мере об одном другом сегменте, связанном с геомаркером данной зоны;

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

2. Способ по п. 1, в котором в ответ на то что удовлетворяется конечное условие, способ дополнительно включает в себя:

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

3. Способ по п. 1, в котором конечное условие соблюдается, когда по меньшей мере одно из:

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

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

4. Способ по п. 1, дополнительно включающий в себя:

получение электронным устройством указания на местоположение целевой точки на карте;

получение доступа электронным устройством к индексу для определения:

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

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

заранее определенное направление было определено на основе географической связи между дочерними зонами данной родительской зоны;

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

5. Способ по п. 4, в котором получение доступа к индексу для определения других целевых зон включает в себя:

выполнение электронным устройством алгоритма маскирования на геомаркерах зон, хранящихся в индексе, причем алгоритм маскирования выполнен:

на основе географической связи между дочерними зонами данной родительской зоны;

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

6. Способ по п. 4, дополнительно включающий в себя:

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

создание электронным устройством набора целевых сегментов путем группировки данных о сегментах, которые одновременно:

сохранены в индексе в виде связей с набором целевых зон; и

связаны с данным многоугольником;

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

в ответ на геометрическое определение того, что четное число целевых сегментов пересекает луч, определение электронным устройством того, что целевая точка находится снаружи данной географической области; и

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

7. Способ по п. 4, в котором карта отображается на экране, который можно соединить с электронным устройством, связанным с пользователем, и в котором получение электронным устройством указания на местоположение целевой точки на карте включает в себя получение указания на пользовательское взаимодействие на части карты.

8. Способ по п. 7, в котором пользовательское взаимодействие представляет собой клик или прикосновение на сенсорном экране.

9. Способ по п. 1, в котором создание геомаркера включает в себя применение электронным устройством алгоритма геохэширования.

10. Способ по п. 9, в котором применение алгоритма геохэширования включает в себя применение электронным устройством Z-порядка кодирования для кодировки географической связи для соответствующей зоны.

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

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

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

сохранение данных по меньшей мере об одном другом сегменте, связанном с опорной зоной;

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

до достижения конечного условия, итерационно:

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

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

создание геомаркера для данной зоны, причем геомаркер указывает на (i) расположение данной зоны в соответствующей родительской зоне, причем соответствующая родительская зона данной зоны находится на предыдущем уровне по отношению к данному, и (ii) географическую связь между данной зоной и другими дочерними зонами по отношению к соответствующей родительской зоне; и

сохранение данных по меньшей мере об одном другом сегменте в связи с геомаркером данной зоны;

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

12. Электронное устройство по п. 11, в котором в ответ на то что удовлетворяется конечное условие, электронное устройство дополнительно выполнено с возможностью осуществлять:

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

13. Электронное устройство по п. 11, в котором конечное условие соблюдается, когда по меньшей мере одно из:

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

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

14. Электронное устройство по п. 11, в котором электронное устройство дополнительно выполнено с возможностью осуществлять:

получение указания на местоположение целевой точки на карте;

получение доступа к индексу для определения:

целевой зоны низшего уровня, соответствующей местоположению целевой точки на основе геомаркеров зоны в индексе; и

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

заранее определенное направление было определено на основе географической связи между дочерними зонами данной родительской зоны;

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

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

выполнение алгоритма маскирования на геомаркерах зон, хранящихся в индексе, причем алгоритм маскирования выполнен:

на основе географической связи между дочерними зонами данной родительской зоны;

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

16. Электронное устройство по п. 14, в котором электронное устройство дополнительно выполнено с возможностью осуществлять:

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

создание набора целевых сегментов путем группировки данных о сегментах, которые одновременно:

сохранены в индексе в виде связей с набором целевых зон; и

связаны с данным многоугольником;

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

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

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

17. Электронное устройство по п. 14, в котором карта отображает на экране, который возможно соединить с электронным устройством, и в котором для получения указания на местоположение целевой точки на карте, электронное устройство выполнено с возможностью получать указание на пользовательское взаимодействие с частью карты.

18. Электронное устройство по п. 17, в котором пользовательское взаимодействие представляет собой клик или прикосновение на сенсорном экране.

19. Электронное устройство по п. 11, в котором для создания геомаркера электронное устройство выполнено с возможностью применять алгоритм геохэширования.

20. Электронное устройство по п. 19, в котором для применения алгоритма геохэширования устройство выполнено с возможностью применять Z-порядок кодирования для кодировки географической связи для соответствующей зоны.