Способ (варианты) и электронное устройство (варианты) определения расположения точки относительно первого многоугольника в многомерном пространстве

Иллюстрации

Показать все

Группа изобретений относится к компьютерным системам, направленным на определение расположения точки относительно многоугольника в многомерном пространстве. Техническим результатом является расширение арсенала технических средств для определения расположения точки относительно многоугольника в многомерном пространстве. Предложен способ определения расположения точки относительно первого многоугольника в многомерном пространстве. Способ содержит этап, на котором осуществляют получение процессором координат первого многоугольника, определяющих расположение и форму первого многоугольника в многомерном пространстве, а также осуществляют получение процессором координат точки, определяющих расположение точки в многомерном пространстве. Далее определяют посредством процессора по меньшей мере одну область в многомерном пространстве, включающую в себя соответствующую часть координат первого многоугольника и представляющую первый многоугольник в упрощенном виде. 6 н. и 37 з.п. ф-лы, 12 ил.

Реферат

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

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

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

Во многих компьютерных приложениях первые данные могут быть представлены в виде многоугольника, находящегося в двух или более измерениях многомерного пространства, а вторые данные могут быть представлены точкой в том же многомерном пространстве. Многоугольник может представлять собой цепочку сегментов, которая образует замкнутую кривую. Некоторые компьютерные приложения могут требовать определения того, находится ли точка, представляющая собой вторые данные, внутри многоугольника, представляющего собой первые данные. Определение того, находится ли точка, представляющая собой вторые данные, внутри многоугольника, представляющего собой первые данные, находит применение во многих сферах, включая такие как: обработка геометрических данных, например, компьютерной графики, компьютерное зрение, географические информационные системы (GIS), навигационные системы, планирование движений и/или системы автоматизированного проектирования (CAD).

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

на Фиг. 3-5 показаны снимки экрана с приложением карт, которое отображает вариант осуществления настоящей технологии;

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

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

на Фиг. 11 и 12 показаны блок-схемы, отображающие соответствующие этапы двух способов, реализуемых варианты осуществления настоящей технологии.

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

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

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

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

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

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

Функции различных элементов, показанных на фигурах, включая функциональный блок, обозначенный как "процессор", могут быть обеспечены с помощью специализированного аппаратного обеспечения или же аппаратного обеспечения, способного использовать подходящее программное обеспечение. Когда речь идет о процессоре, функции могут обеспечиваться одним специализированным процессором, одним общим процессором или множеством индивидуальных процессоров, причем некоторые из них могут являться общими. Более того, использование термина "процессор" или "контроллер" не должно подразумевать исключительно аппаратное обеспечение, способное поддерживать работу программного обеспечения, и может включать в себя, без установления ограничений, цифровой сигнальный процессор (DSP), сетевой процессор, интегральная схема специального назначения (ASIC), программируемую пользователем вентильную матрицу (FPGA), постоянное запоминающее устройство (ПЗУ) для хранения программного обеспечения, оперативное запоминающее устройство (ОЗУ) и энергонезависимое запоминающее устройство. Также может быть включено другое аппаратное обеспечение, обычное и/или специальное.

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

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

На Фиг. 1 показана диаграмма компьютерной системы 100, которая подходит для некоторых вариантов осуществления настоящей технологии, компьютерная система 100 включает в себя различные аппаратные компоненты, включая один или несколько одно- или многоядерных процессоров, которые представлены процессором 110, твердотельный накопитель 120, ОЗУ 130, интерфейс 140 монитора, и интерфейс 150 ввода/вывода.

Связь между различными компонентами компьютерной системы 100 может осуществляться с помощью одной или несколько внутренних и/или внешних шин 160 (например, шины PCI, универсальной последовательной шины, высокоскоростной шины IEEE 1394, шины SCSI, шины Serial ATA и так далее), с которыми электронно соединены различные аппаратные компоненты. Интерфейс 140 монитора может быть соединен с монитором 142 (например, через HDMI-кабель 144), наблюдаемым пользователем 170, интерфейс 150 ввода/в