СПОСОБ И ЭЛЕКТРОННОЕ УСТРОЙСТВО ДЛЯ СОЗДАНИЯ ИНДЕКСА СЕГМЕНТОВ МНОГОУГОЛЬНИКОВ

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-порядок кодирования для кодировки географической связи для соответствующей зоны.