СПОСОБ ОПРЕДЕЛЕНИЯ ТОЧКИ КРИВОЙ, БЛИЖАЙШЕЙ К ПОЗИЦИИ НА КАРТЕ Российский патент 2017 года по МПК G06T17/05 G01C21/14 G01S5/14 

Перекрестные ссылки

Отсутствуют.

Область техники

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

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

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

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

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

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

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

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

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

- оценивание координат позиции;

- оценивание координат объекта карты, имеющего кривую около позиции;

- определение точки кривой, ближайшей к позиции, упомянутое определение включает

- определение первого сегмента кривой, ограниченного первой областью и второго сегмента кривой, ограниченного второй областью;

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

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

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

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

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

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

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

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

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

- оценивание координат позиции;

- оценивание координат объекта карты, имеющего кривую около позиции;

- определение точки кривой, ближайшей к позиции, упомянутое определение включает

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

На Фиг. 1 проиллюстрирована компьютерная система 100, подходящая для использования с некоторыми вариантами осуществления настоящей технологии, компьютерная система 100 содержит различные аппаратные компоненты, содержащие один или более одно или многоядерных процессоров, коллективно представленных процессором 110, твердотельным диском 120, оперативным запоминающим устройством 130, интерфейсом дисплея 140 и входным/выходным интерфейсом 150. Коммуникации между различными компонентами компьютерной системы 100 могут быть обеспечены одной или несколькими внутренней и/или внешними шинами 160 (например, шина PCI, универсальная последовательная шина (USB), шина IEEE 1394 "Firewire", шина SCSI, шина Serial-ATA и т.д.), к которым подключаются различные аппаратные компоненты. Интерфейс дисплея 140 может быть подключен к монитору или сенсорному экрану (не показан). В соответствии с вариантами реализации настоящей технологии, твердотельный диск 120 хранит программные инструкции, подходящие для загрузки в оперативное запоминающее устройство 130 и выполнения процессором 110 для демонстрации позиции на карте. Например, программные инструкции могут быть частью картографического приложения, выполняемого процессором 110.

На Фиг. 2 проиллюстрировано сетевое компьютерное оборудование 200, подходящее для использования с некоторыми вариантами реализации настоящей технологии, сетевое компьютерное оборудование 200 содержит смартфон 220 (например, Apple iPhoneTM или Samsung Galaxy S4TM) с сенсорным экраном 222 для демонстрации информации пользователю 210 и получения сенсорных команд от пользователя 210, картографический сервер 230 связан со смартфоном 220 по коммуникационной сети 201 (например, Интернет) и спутник GPS 240, передает GPS сигнал 242 на смартфон 220. Наряду с сенсорным экраном 222, смартфон 220 также содержит внутренние аппаратные компоненты, содержащие один или более одно или многоядерных процессоров, коллективно представленных здесь как процессор 110, оперативное запоминающее устройство 130, каждый из которых аналогичен подобно пронумерованным аппаратным компонентам компьютерной системы 100, показанной на Фиг. 1, так же как сетевой интерфейс (не показан) для связи с картографическим сервером 320 по коммуникационной сети 201 и приемник GPS (не показан) для получения сигнала GPS 242 от спутника GPS 240. Должно быть понятно, что другие варианты реализации настоящей технологии могут использовать технологии позиционирования отличные о GPS.

Фиг. 3 иллюстрирует маршрут 300 от столицы до Спрингфилда, который может быть получен смартфоном 220 от картографического сервера 230 по коммуникационной сети 201, a GPS позиция 1 смартфона 220, которая может быть получена смартфоном 220 от спутника GPS 240 с помощью GPS сигнала 242, в соответствии с вариантом реализации настоящей технологии. Может быть полезным для картографического приложения, выполняемого процессором 110 смартфона 220, выполнение этапов оценивания маршрута 300, полученного от картографического сервера 230, оценивание GPS позиции 1 полученной от GPS спутника 240, определение точки маршрута 300, ближайшей к GPS позиции 1 (например, одной из точек-кандидатов 2,3 и 4, проиллюстрированных на Фиг. 3, лежащих на соответствующих расстояниях 2D, 3D и 4D от GPS позиции 1), и предоставление индикации ближайшей точки пользователю 210 смартфона 220.

В качестве первого примера, картографическое приложение может быть достаточно уверено (возможно, из-за конкретной вводной информации, полученной от пользователя 210) в том, что правильная позиция смартфона 220 располагается на маршруте 300, даже если GPS позиция 1 смартфона 220 полученная от GPS спутника 240 не располагается на маршруте 300. Например, пользователь 210 может запросить картографическое приложение определить маршрут 300 и продемонстрировать маршрут пользователю 300. В таком случае, картографическое приложение может определить ближайшую точку маршрута 300 к GPS позиции 1 как лучшую оценку актуальной правильной позиции смартфона 220 и вызывает отображение ближайшей точки маршрута 300 для пользователя 210 на карте.

Как второй пример, маршрут 300 может быть официальным велосипедным маршрутом из столицы до Спрингфилда и пользователь 210 смартфона 220 в позиции 1 (это время считается корректным) может быть велосипедистом отклонившимся от официального велосипедного маршрута. В этом случае, пользователь 210 может запросить помощь от картографического приложения с тем, чтобы вернуться на официальный велосипедный маршрут, вызывая определение картографическим приложением ближайшей точки маршрута 300 и отображения ее пользователю 210 на сенсорном экране 222 смартфона 220.

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

Фиг. 4 и Фиг. 5 иллюстрируют два альтернативных скриншота, которые могут демонстрироваться пользователю 210 в зависимости от которых точка-кандидат 3 и точка-кандидат 4 маршрута 300 - среди всех других не показанных точек-кандидатов маршрута 300, определены как точка маршрута 300, ближайшая к GPS позиции 1.

На Фиг. 4, точка-кандидат 3, на расстоянии 3D от GPS позиции 1, показана как ближайшая точка с помощью малого круга нарисованного на маршруте 300. Фиг. 5 иллюстрирует, как картографическое приложение может показывать пользователю 210 альтернативный результат, то есть, как точка-кандидат 4 на расстоянии 4 является ближайшей точкой на маршруте 300 к GPS позиции 1.

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

Фиг. 6 иллюстрирует маршрут 300, разбитый на восемь сегментов от 31 до 38, каждый ограниченный соответствующей областью от 31R до 38R. Каждый из сегментов 31-38 как сказано является "монотонным", поскольку он вообще не увеличивается или не уменьшается в любом измерении.

Например, проанализированные слева направо монотонные сегменты 31, 33, 35 и 37 никогда не уменьшаются в горизонтальном измерении (x-измерение) и они никогда не уменьшаются в вертикальном измерении (y-измерении). Наоборот, монотонные сегменты 32, 34, 36 и 38 никогда не увеличиваются в x-измерении или y-измерении. Монотонный сегмент может, тем не менее, иметь плоский участок, так что не увеличивается и не уменьшается в одном или более измерений, пока он одновременно не увеличивается или уменьшается в любом измерении.

Следует отметить, что хотя области 31R-38R, показанные на Фиг.6, являются прямоугольными, области имеющие другие формы (такие, как круги) также рассматриваются настоящей технологией. Особенно, если карта трехмерна, области, ограничивающие различные сегменты кривой, представленной объектом, таким как маршрут 300 могут также быть трехмерными, возможно принимая форму прямоугольного параллелепипеда (куба) или сферы, в качестве неограничивающих примеров. Хотя могут использоваться неправильные формы, варианты настоящей технологии рассматривают выбор форм, таким образом, чтобы граничные точки областей были известны без излишних расчетов. В частности, некоторые варианты настоящей технологии допускают то, что ближайшие и/или наиболее удаленные точки областей уже являются известными, как это станет ясно ниже.

Наряду с разбивкой маршрута 300 на области 31R-38 R, Фиг. 6 также иллюстрирует первый способ, в котором варианты настоящей технологии могут избегать расчета расстояния к некоторым из точек-кандидатов маршрута 300. Примем, во-первых, что наиболее удаленная точка области 35R, то есть, которая совпадает с точкой-кандидатом 5 маршрута 300, лежит на расстоянии 5D от GPS позиции 1. Далее, рассмотрим, что ближайшая точка области 38R, то есть, которая совпадает с точкой-кандидатом 6 маршрута 300, лежит на расстоянии 6D, большем, чем расстояние 5D от GPS позиции 1. Поскольку в области 38R нет точек ближе к GPS позиции 1, чем точка-кандидат 6, некоторые варианты реализации настоящей технологии могут таким образом обосновано решить, без расчета расстояния от GPS позиции 1 к любой другой точке-кандидату сегмента 38 маршрута 300, что ближайшая точка к GPS позиции 1 из сегментов 35 или 38 является ближайшая точка сегмента 35, а не ближайшая точка сегмента 38.

Полагая по-другому, варианты реализации настоящей технологии могут предположить, что кратчайшее расстояние от GPS позиции 1 к сегменту 35 является кратчайшим расстоянием от GPS позиции 1 к сегменту 35 и сегменту 38.

Фиг. 7 иллюстрирует способ, в котором варианты реализации настоящей технологии могут обходить расчет расстояния к некоторой из точек-кандидатов маршрута 300. Рассмотрим сегмент 32, ограниченный областью 32R, которая монотонно пролегает от GPS позиции 1 от известной ближайшей точки области 32R к GPS позиции 1, то есть к точке-кандидату 3 маршрута 300. Поскольку невозможно то, что любая точка-кандидат (например, точка-кандидат 7) сегмента 32 является ближайшей к GPS позиции 1, чем точка-кандидат 3, варианты реализации настоящей технологии могут таким образом обоснованно определить без расчета расстояния от GPS позиции 1 до любой точки-кандидата сегмента 32 маршрута 300, что кратчайшее расстояние от GPS позиции 1 к сегменту 32 является расстоянием от GPS позиции 1 к точке-кандидату 3.

Фиг. 8 подобна Фиг. 7, только она иллюстрирует другую GPS позицию 8, в это время расположенную в области 37R, которая ограничивает монотонный сегмент 37 маршрута 300 между столицей и Спрингфилдом. Как таковой, это представляет другой случай той же задачи представленной выше в соответствии с Фиг. 3 - Фиг. 7, то есть определение точки маршрута 300, ближайшей к GPS позиции 8. Точки-кандидаты 9, 10 и 11 показаны исключительно как примеры точек маршрута 300, которые могут быть определены как ближайшие точки.

Фиг. 9 иллюстрирует ближний вид (не в масштабе) монотонного сегмента 37 Фиг. 8, с GPS позицией 8 и точками-кандидатами 9 и 11, для иллюстрации дополнительных техник настоящей технологии. Монотонный сегмент 37 дополнительно разбивается на сегменты 371-377, каждый из которых ограничивается соответствующими областями 371R-377R. Будучи сегментами монотонного сегмента 37, каждый из сегментов 371-377 являются безусловно монотонными. В соответствии с показанным вариантом, области 371R-377R являются прямоугольными, но как ранее описано, в других вариантах они могут иметь другую форму, такую как круги (или прямоугольные параллелепипеды, сферы или другие трехмерные формы в случае трехмерных вариантов настоящей технологии).

Сегмент 377 (ограниченный областью 377R) целиком находится в 1^ой декартовой четверти по отношению к GPS позиции 8, означающее, что любая точка сегмента 377 имеет большие (или эквивалентные) значения координат, чем координаты GPS позиции 8 в x-измерении и y-измерении. Таким образом, сегмент 377 представляет ситуацию, аналогичную сегменту 32 на Фиг.7, в которой сегмент 377 монотонно пролегает от GPS позиции 8 от ближайшего угла (представленного точкой-кандидатом 11) области 377R.

Варианты реализации настоящей технологии могут, таким образом, обоснованно заключить, что кратчайшим расстоянием к любой точке сегмента 377 является расстояние 11D к известному ближайшему углу (точка-кандидат 11) области 377R. Также, сегмент 371 (ограниченный областью 377R) располагается полностью в 3^ей декартовой четверти по отношению к GPS позиции 8, означая, что каждая точка сегмента 371 имеет меньшие (или эквивалентные) значения координат, чем GPS позиция 8 в x-измерении и y-измерении, а наикратчайшим расстоянием от GPS позиции 8 к сегменту 377 является, таким образом, известное расстояние к ближайшему углу (не обозначено) области 371R.

В самом деле, некоторые варианты настоящей технологии могут разбивать монотонный сегмент, который располагается в обоих в 4^ой декартовой четверти (или, аналогично, 2^ой декартовой четверти) и в одной или обоих из 1^ой и 3^ей декартовых четвертях, на сегменты, содержащие сегменты целиком расположенные в одной из 1^ой and 3^ей декартовых четвертях, для конкретной цели отбрасывания любых точек-кандидатов этих сегментов, отличных от известной ближайшей точки области, ограничивающей этот сегмент.

Ситуация отличается для оставшихся сегментов (372-376), которые располагаются в 4^ой декартовой четверти по отношению к GPS позиции 8, так, что каждая точка сегментов 372-376 имеет большие (или эквивалентные) значения координат в x-измерении, но меньшие (или эквивалентные) значения координат в y-измерении, чем GPS позиция 8. В таком случае, фактически сегменты 372-376 монотонно увеличиваются как в x-измерении, так и в y-измерении, ближайший угол области в 4^ой декартовой четверти скорее не будет пересекать сегмент, который он ограничивает (исключением является сегмент, который пересекает ближайший контур области в задаче к позиции в задаче).

Например, ближайший угол 375С области 375R не является точкой сегмента 375, и таким образом, не является точкой-кандидатом ввиду того, что точка-кандидат 11 была ближайшим углом области 377R, расположенной в 1^ой декартовой четверти. Тем не менее, поскольку ближайший угол 375С является ближайшей точкой к любой точке области 375R, которая ограничивает сегмент 375, расстояние 375D от GPS позиции 8 к ближайшему углу 375С служит как крайняя нижняя граница на расстояние от GPS позиции 8 к любой точке сегмента 375.

Таким образом, необходимость расчета актуального расстояния к любой из точек сегмента 375 отпадает, поскольку более короткое расстояние, чем расстояние 375D к другой точке-кандидату сегмента 37, становится известным. Например, поскольку расстояние 9D от GPS позиции 8 к точке-кандидату 9 сегмента 373 определяется как меньшее, чем или эквивалентное расстоянию 375D, варианты настоящей технологии могут обоснованно заключить, что кратчайшее расстояние от GPS позиции 8 к сегменту 373 является кратчайшим расстоянием к каждому из сегментов 373 и 375, без расчета расстояния от GPS позиции 8 к любой из точек сегмента 375.

Изобретатель настоящей технологии предусмотрел, что в некоторых вариантах настоящей технологии может быть разбивка части монотонного сегмента (например, сегмента 37), расположенного в 4^ой четверти (или, аналогично, 2^ой четверти), на нечетное число сегментов (например, пять сегментов 372-376) и для выбора одного из сегментов (например, сегмента 374) как сегмента, скорее всего содержащего ближайшую точку к позиции (GPS позиции 8, в этом случае).

На Фиг. 10 проиллюстрирована блок-схема, соответствующая примерному способу реализации настоящей технологии. Более конкретно, Фиг. 10 иллюстрирует машиноисполняемый способ 400 для отображения позиции на карте, способ выполняется процессором электронного устройства.

Способ 400 может выполняться, например, с помощью смартфона 220, Фиг. 2, процессором 110, выполняющим программные инструкции, загруженные в его оперативное запоминающее устройство 130.

На этапе 410, оцениваются координаты позиции. Например, координаты GPS позиции 8 могут быть получены от GPS спутника 240 по сигналу GPS 242 или прочитаны процессором 110 смартфона 220 из его памяти 120.

На этапе 420, происходит оценивание координат объекта, имеющего кривую около позиции; Например, координаты маршрута 300 содержащего, среди других кривых, сегмент 37 около GPS позиции 8 Фиг. 9, могут быть получены смартфоном 220 от картографического сервера 230 по коммуникационной сети 201.

На этапе 430, определяется ближайшая к позиции точка кривой. Например, точка-кандидат 9 сегмента 37 Фиг. 9 может быть идентифицирована как точка сегмента 37 ближайшая к GPS позиции 8.

Этап 430 включает этап 432, в котором определяются первый сегмент кривой, ограниченный первой областью и второй сегмент кривой, ограниченный второй областью. Например, могут быть определены сегмент 373, ограничивающийся областью 373R, и сегмент 375, ограничивающийся сегментом 375R.

В некоторых вариантах, кривая может быть разбита на монотонные сегменты, содержащие первый сегмент и второй сегмент. Например, маршрут 300 может быть разбит на монотонные сегменты 31-38, как на Фиг. 6, или монотонный сегмент 37 может быть разбит на сегменты 371-377, как на Фиг. 9.

Этап 430 также включает этап 434, в котором определяется то, что расстояние от позиции к точке первого сегмента не больше, чем расстояние от позиции к известной ближайшей точке второй области. Например, может быть определено, что расстояние 9D к точке-кандидату 9 меньше, чем расстояние 375D к ближайшему углу 375С области 375R. В некоторых вариантах, может быть определено, что наиболее удаленная точка первой области является по меньшей мере так близкой как ближайшая точка второй области, как было в случае примера представленного выше в соответствии с Фиг. 6.

Этап 430 также включает в себя этап 436, в котором кратчайшего расстояние от позиции к первому сегменту рассчитывается, как кратчайшее расстояние от позиции к первому сегменту и второму сегменту без расчета расстояния от позиции к по меньшей мере одной точке второго сегмента, отличной от известной ближайшей точки второй области. Например, кратчайшее расстояние от GPS позиции 8 к сегменту 373 может быть рассчитано как кратчайшее расстояние от GPS позиции 8 к каждому из сегмента 373 и сегмента 375 без расчета расстояния к одной или более (или любой) из точек сегмента 375.

Наконец, на этапе 440, вызывается отображение на карте индикации точки кривой, ближайшей к позиции. Например, процессор 110 смартфона 220 может вызвать отображение интерфейсом дисплея 140 смартфона 220 точки на карте, демонстрируемой на сенсорном экране 222, таким образом, предоставляя пользователю 210 смартфона 220 индикацию точки (точка-кандидат 9) маршрута 300 ближайшего к его или ее GPS позиции 8.

Обратимся теперь к Фиг. 11, иллюстрирующей блок-схему, соответствующую примерному способу реализации настоящей технологии. Более конкретно, Фиг. 11 иллюстрирует машиноисполняемый способ 500 для отображения позиции на карте, способ выполняется процессором электронного устройства. Способ 500 может выполняться, например, с помощью смартфона 220 Фиг. 2 процессором 110, выполняющим программные инструкции, загруженные в его оперативное запоминающее устройство 130.

На этапе 510, оцениваются координаты позиции. Например, координаты GPS позиции 8 могут быть получены от GPS спутника 240 по сигналу GPS 242 или прочитаны процессором 110 смартфона 220 из его памяти 120. На этапе 520, происходит оценивание координат объекта, имеющего кривую около позиции; Например, координаты маршрута 300 содержащего, среди других кривых, сегмент 37 около GPS позиции 8 Фиг. 9, могут быть получены смартфоном 220 от картографического сервера 230 по коммуникационной сети 201.

На этапе 530, определяется ближайшая к позиции точка кривой. Например, точка-кандидат 9 сегмента 37 Фиг. 9 может быть идентифицирована как точка сегмента 37, ближайшая к GPS позиции 8.

Этап 530 включает этап 532, на котором определяется монотонный сегмент кривой, ограниченный областью, имеющей известную ближайшую точку к позиции. Например, может быть определен сегмент 377, ограничивающийся областью 377R, имеющей известный ближайший угол, совпадающий сточкой-кандидатом 11.

Этап 530 также включает этап 534, в котором определяется, что монотонный сегмент монотонно пролегает от позиции от известной ближайшей точки. Например, может быть определено, что сегмент 377 является монотонным сегментом, который от известной точки (точки-кандидата 11) области 377R, точка-кандидат 11 имеет большие значения координат в обоих x и y-измерениях, чем GPS позиция 8, монотонно пролегающая к другим точкам сегмента 377, имеющим соответственно большие (или эквивалентные) значения координат, чем точка-кандидат 11.

Этап 530 также включает в себя этап 536, в котором расстояние от позиции к известной ближайшей точке области рассчитывается как кратчайшее расстояние от позиции к монотонному сегменту без расчета расстояния от позиции к по меньшей мере одной точке монотонного сегмента, отличной, чем известная ближайшая точка области. Например, расстояние 11D от GPS позиции 8 к точке-кандидату 11 области 377R может быть рассчитано как кратчайшее расстояние от GPS позиции к одной или более (или любой) точек сегмента 377.

Наконец, на этапе 540, вызывается отображение на карте индикации точки кривой, ближайшей к позиции. Например, процессор 110 смартфона 220 может вызвать отображение интерфейсом дисплея 140 смартфона 220 точки на карте, демонстрируемой на сенсорном экране 222, таким образом, предоставляя пользователю 210 смартфона 220 индикацию точки (точка-кандидат 9) маршрута 300, ближайшего к его или ее GPS позиции 8.

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

Изобретение относится к технологиям отображения позиции на карте, включающим определение точки кривой, наиболее близкой к позиции. Техническим результатом является повышение быстродействия при поиске точки на кривой, ближайшей к текущей позиции, за счет исключения необходимости расчета расстояния до всех точек кривой. Предложен способ, реализованный на компьютере, для определения точки кривой, ближайшей к позиции на карте, выполняемый электронным устройством, вызывающим отображения карты. Способ содержит этап оценивания координат позиции, оценивания координат объекта карты, имеющего кривую около позиции. А также согласно способу включают определение точки кривой, ближайшей к позиции, которое включает определение первого сегмента кривой и второго сегмента кривой, ограниченного второй областью. 4 н. и 27 з.п. ф-лы, 11 ил.

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

оценивание координат позиции;

оценивание координат объекта карты, имеющего кривую около позиции;

определение точки кривой, ближайшей к позиции, которое включает:

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

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

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

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

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

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

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

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

6. Способ по п. 3 , в котором:

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

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

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

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

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

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

11. Способ по п. 1, в котором карта является двухмерной, вторая область является прямоугольником, а ближайшая точка второй области является ближайшим углом второй области.

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

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

оценивание координат позиции;

оценивание координат объекта карты, имеющего кривую около позиции;

определение точки кривой, ближайшей к позиции, которое включает:

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

определение того, что монотонный сегмент монотонно пролегает от позиции от ближайшей точки;

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

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

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

15. Способ по п. 13, в котором карта является двухмерной, область является прямоугольником, а ближайшая точка области является ближайшим углом области.

16. Способ по п. 13, в котором расчет расстояния от позиции к ближайшей точке области как кратчайшего расстояния от позиции к монотонному сегменту является расчетом расстояния от позиции к ближайшей точке области как кратчайшего расстояния от позиции к монотонному сегменту.

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

оценивание координат позиции;

оценивание координат объекта карты, имеющего кривую около позиции;

определение точки кривой, ближайшей к позиции, которое включает:

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

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

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

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

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

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

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

21. Носитель по п. 18, в котором хранящиеся программные инструкции обеспечивают:

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

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

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

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

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

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

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

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

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

оценивание координат позиции;

оценивание координат объекта карты, имеющего кривую около позиции;

определение точки кривой, ближайшей к позиции, включающее:

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

определение того, что монотонный сегмент монотонно пролегает от позиции от ближайшей точки;

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

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

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

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

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