СПОСОБ ОПРЕДЕЛЕНИЯ МЕСТОПОЛОЖЕНИЯ ИЗ КОДИРОВАННЫХ ДАННЫХ, ПРЕДСТАВЛЯЮЩИХ ЕГО Российский патент 2013 года по МПК G06Q50/30 G01C21/34 H04W4/00 

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

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

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

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

В дополнительной поданной в один день с данной заявке заявителя, озаглавленной "Efficient Location Referencing Method", описывается технология для формирования машиночитаемого представления местоположения таким способом, который не только считается оптимизированным относительно полной длины в байтах, но и который также считается независимым от карты.

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

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

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

Одним конкретным атрибутом, зачастую предоставленным в цифровых картах, является таблица привязок местоположений канала сообщений о дорожном движении (TMC). TMC - это технология для доставки информации о дорожном движении и поездке пользователям транспортных средств, а более конкретно, в навигационные системы (портативные или интегрированные), присутствующие в этих транспортных средствах и которые включают в себя некоторую форму цифровой карты. TMC-сообщение состоит из кода события (который не обязательно должен быть конкретным для дорожного движения, хотя они наиболее распространены) и кода местоположения, зачастую состоящего из упорядоченного списка привязок местоположений, посредством которых местоположение события дорожного движения может быть определено в цифровой карте и тем самым представлено графически на экране навигационной системы. Определенному числу заранее заданных узлов в большинстве предлагаемых на рынке цифровых карт назначается точка привязки TMC-местоположения, которая определяется с привязкой на ограниченную таблицу местоположений. Таблица местоположений состоит из 2¹⁶ (65536) привязок местоположений, соответствующих аналогичному числу физических или реальных местоположений, обычно пересечений дорог, также идентифицируемых на цифровой карте.

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

- зачастую поддерживаются через орган государственной власти или национальное правительство,

- часто меняются между циклами обновления, которые являются традиционно весьма длинными,

- не существуют или доступны только коммерчески на некоторых рынках.

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

Одной попыткой преодолевать некоторые из ограничений TMC-привязок местоположений или конкретных для карты привязок является проект динамической привязки местоположения, также известный как AGORA-C (в процессе стандартизации согласно ISO 17572-1, 2 и 3). Хотя полное описание подхода к привязке местоположения AGORA-C выходит за рамки данной заявки, фундаментальные основы подхода заключаются в том, что привязка местоположения может полностью указываться посредством набора точек местоположения, указываемых посредством пар координат широты и долготы и упорядоченных в списке, причем каждая точка удовлетворяет различным правилам, но, наиболее важно, является последовательной с точки зрения привязываемого местоположения и предыдущей точки в списке, т.е. последовательные точки формируют взаимосвязь "следующая точка". Как и в других системах привязки местоположения, каждая точка содержит определенное число атрибутов, которые помогают в лучшем задании этой точки, но конкретным для AGORA-C способом является идентификация каждой точки как одной из точки местоположения, точки пересечения, точки маршрутизации или некоторой комбинации вышеозначенных трех точек. Каждая точка вдоль местоположения, в котором изменяется характерный признак участка дороги, представляется посредством точки пересечения, тем самым местоположения, которые являются путями по дорожной сети и которые проходят через пересечения без изменений характерного признака участка дороги, не должны привязываться посредством точки пересечения. Например, если местоположение включает в себя часть автомагистрали, которая включает в себя перекрестки, которые не являются релевантными относительно местоположения, то нет необходимости включать точки пересечения для таких перекрестков. Одним из предшествующих этапов способа кодирования AGORA-C является определение всех прошедших точек пересечения между первой и последней точкой пересечения вдоль местоположения, в котором происходит изменение характерного признака участка дороги.

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

Хотя этот подход к привязке является всеобъемлющий в том, что можно точно и повторяемо кодировать и декодировать любое местоположение, существующее в рамках системы географической информации, считается, что система является чрезмерной и, возможно, избыточной в определенных аспектах, и возможна более эффективная система кодирования и декодирования. Например, хотя способ привязки является независимым от задач предварительной компиляции и является независимым от карты, средний размер сообщения AGORA-C намного превышает 30 байтов в расчете на привязку местоположения. С точки зрения устройств, которые могут в большинстве случаев декодировать привязки местоположения, таких как персональные навигационные устройства, PDA, мобильные устройства или встроенные в автомобиль интегрированные навигационные системы, требуется, чтобы принимаемое сообщение являлось максимально коротким, чтобы иметь возможность предоставлять быстрое декодирование и окончательное определение местоположения, представленное посредством этого.

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

Сущность изобретения

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

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

(ii) выполнения поиска маршрута в рамках упомянутой второй цифровой карты между:

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

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

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

(iii) повторения этапа (ii) для каждой последовательной пары точек привязки местоположения вплоть до и включая конечную точку привязки местоположения, обнаруживаемую в списке.

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

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

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

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

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

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

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

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

Дополнительно предпочтительно, способ включает в себя дополнительные этапы:

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Фиг. 12-20 предоставляют различные схематические иллюстрации, применимые в контексте логических и физических форматов данных, описанных ниже, и в частности, фиг. 12 показывает требуемое последовательное соединение точек привязки местоположения (LRP), фиг. 13 иллюстрирует, как азимут вычисляется для одной LRP относительно следующей LRP, фиг. 14 показывает, как азимуты могут варьироваться, фиг. 15 демонстрирует, как атрибут "расстояние до следующей точки" определяется для LRP, фиг. 16 иллюстрирует использование смещений, фиг. 17 показывает способ, которым для LRP предоставляются атрибуты, фиг. 18/19 иллюстрируют узлы, которые должны исключаться в ходе кодирования привязки местоположения, и фиг. 20 иллюстрирует, как значения азимута для LRP попадают в 1 из 32 дискретных секторов круга.

Подробное описание изобретения

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

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

Ссылаясь сначала на фиг. 2-5, первая цифровая карта (кодера) показана на фиг. 2 и состоит из 15 узлов и 23 линий (двухсторонние линии подсчитываются два раза). Узлы пронумерованы от (1) до (15). Необходимые атрибуты линий показаны около каждой линии с использованием формата: <FRC>,<FOW>,<длина в метрах>. FRC - это сокращение для "функционального класса дороги", и FOW - это сокращение для "формы пути", оба из которых описываются более подробно в нижеприведенном приложении. Острия стрелок указывают возможное направление движения для каждой линии.

Местоположение, которое должно быть кодировано, показано на фиг. 3 с помощью полужирных линий. Местоположение начинается в узле (3) и проходит по узлам (5), (7), (10), (11), (13), (14) и завершается в узле (15). Его общая длина на карте кодера составляет 685 метров. Упорядоченный список линий и карта, которая должна использоваться в ходе кодирования, выступают в качестве входных данных для кодера.

Кодирование

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

Второй этап кодера заключается в том, чтобы проверять начальный и конечный узел местоположения как являющиеся реальными узлами согласно конкретным заранее определенным правилам для форматов данных. Конечный узел (15) имеет только одну входящую линию, и, следовательно, является достоверным. Начальный узел (3) также имеет две инцидентных линии, но здесь это одна исходящая и одна входящая линия. Следовательно, данный узел не является достоверным, и кодер выполняет поиск реального узла вне местоположения. Кодер должен обнаруживать, что узел (1) является реальным узлом, и он также уникально продляет местоположение. Узел (1) выбирается как новый начальный узел для привязки местоположения, и будет положительное смещение в 150 метров. Общая длина пути привязки местоположения приводит к 835 метрам.

Третий этап кодера заключается в том, чтобы переходить к тому, чтобы вычислять кратчайший путь между начальной линией (линией между узлами (1) и (3)) и конечной линией (линией между узлами (14) и (15)) местоположения. Результирующий кратчайший путь выделяется на фиг. 4 с помощью полужирных линий. Кратчайший путь имеет длину в 725 метров.

Следующий (4-й) этап процесса кодирования теперь состоит в том, чтобы проверять то, покрывается или нет местоположение посредством вычисленного кратчайшего пути. Он определяет то, что это не так, и имеется отклонение после узла (10).

Согласно принципам, указанным в находящейся одновременно на рассмотрении и поданной в один день с данной заявке заявителя, кодер должен определять линию от узла (10) к (11) как новую промежуточную точку привязки местоположения. Узел (10) является реальным узлом, поскольку он не может быть пропущен во время поиска маршрута, и кратчайший путь к этой линии полностью покрывает соответствующую часть местоположения. Длина местоположения, покрываемого после этого первого вычисления кратчайшего пути, составляет 561 метр.

Следующий этап кодирования подготавливает вычисление маршрута, чтобы определять кратчайший путь для оставшейся части местоположения (от узла (10) через (11), (13) и (14) к (15)). Вычисление кратчайшего пути, следовательно, начинается в линии от (10) к (11) и завершается в линии от (14) к (15).

Кодер возвращается к вышеприведенному этапу 3 и определяет кратчайший путь (длина: 274 метра) между (10) и (15), и вышеприведенный этап 4 возвращает то, что местоположение теперь полностью покрывается посредством вычисленных кратчайших путей.

В качестве следующего этапа, путь привязки местоположения будет состоять из двух кратчайших путей, и далее формируется упорядоченный список точек привязки местоположения. Фиг. 5 показывает полужирным линии, которые выбираются для точек привязки местоположения. Первая точка привязки местоположения указывает на линию от узла (1) к (3) и указывает начало пути привязки местоположения, вторая точка привязки местоположения указывает на линию от узла (10) к (11), и эта линия требуется для того, чтобы не допускать отклонения от местоположения. Последняя точка привязки местоположения указывает на линию от узла (14) к (15) и указывает конец базового опорного пути.

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

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

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

Ссылаясь также на фиг. 1, на которой показана краткая блок-схема 100 последовательности операций способа для процесса согласно одному варианту осуществления изобретения, первый этап 102 в процессе заключается в том, чтобы декодировать входящие или передаваемые в беспроводном режиме (обычно в случае мобильного устройства) двоичные данные (или XML либо другое машиночитаемое представление), являющиеся результатом предшествующего процесса кодирования и структурированные согласно физическому формату данных. Декодирование этих двоичных данных не является существенным элементом изобретения, которое применяется к определению местоположения из списка точек привязки местоположения - декодирование двоичных данных является просто средством идентификации требуемых точек привязки местоположения.

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

Информация, извлеченная из примера двоичных данных, показана в таблицах 1, 2 и 3 (и дополнительно содержится на фиг. 1 на этапах 106, 108 и 110, соответственно).

Таблица 1
Декодированные координаты Индекс LRP Долгота Широта 1 6,12682° 49,60850° 2 6,12838° 49,60397° 3 6,12817° 49,60304°

Таблица 2
Декодированная информация LRP Индекс LRP FRC FOW Азимут LFRCNP DNP 1 FRC3 MULTIPLE_CARRIAGEWAY 135,00°-146,25° FRC3 527,4-586,0 м 2 FRC3 SINGLE_CARRIAGEWAY 225,00°-236,25° FRC5 234,4-293,0 м 3 FRC5 SINGLE_CARRIAGEWAY 281,25°-292,50° - 0 м

Таблица 3
Декодированная информация смещения Смещение Значение Положительное смещение 117,2-175,8 м Отрицательное смещение Нет доступного смещения

Этой информации достаточно для того, чтобы определить местоположение на карте декодера, показанной на фиг. 6. Эта карта состоит из 17 узлов и 26 линий (двухсторонние линии подсчитываются два раза). Чтобы не допускать путаницы, все узлы, указываемые на карте декодера, предваряются "X".

Эта карта отличается от карты кодера (см. фиг. 2) несколькими аспектами. Некоторые значения длины являются различными (например, линия от узла X(3) к X(5)), некоторые значения функционального класса дороги изменены (например, линия от узла X(3) к X(5)), и имеется еще два узла X(16) и X(17), а также дополнительные линии, соединяющие эти новые узлы. Задача декодера заключается в том, чтобы определить местоположение в этой другой карте.

После проверки достоверности данных и предоставления списка декодированных точек привязки местоположения (LRP) и их атрибутов, как указано на этапе 112 на фиг. 1, декодер затем начинает обрабатывать каждую LRP в списке на этапе 114, чтобы сначала определять узлы-кандидаты для каждой LRP. Результат этой обработки, которую достаточно просто осуществлять посредством использования LRP-координат и идентификации ближайшего узла(лов), обнаруживаемых на цифровой карте декодера 118 (как указано, в общем, на 116), состоит в том, чтобы предоставлять список узлов-кандидатов для каждой LRP. Узлы карты, удаленные от LRP более чем на заранее определенное пороговое значение, могут исключаться, как показано на 120. Фиг. 7 показывает узлы-кандидаты (полужирный круг), которые размещаются рядом, посредством координат точек привязки местоположения. Для точки 1 и 2 привязки местоположения (в вышеприведенных таблицах 1 и 2), в этом примере, существует только один узел-кандидат, но для последней точки привязки местоположения возможны два узла-кандидата X(16) и X(17).

Так же, в качестве части обработки LRP и их атрибутов, линии-кандидаты для каждой точки привязки местоположения также идентифицируются. Полужирные линии на фиг. 8 - это линии-кандидаты согласно этому примеру. Первая LRP представляется посредством точки-кандидата X(1), которая, в свою очередь имеет две исходящих линии в качестве кандидатов, вторая LRP, имеющая точку-кандидат X(10), имеет три исходящих линии в качестве кандидатов, и последняя точка привязки местоположения имеет две входящие линии (по одной для каждого узла-кандидата X(15) и X(16)). Если обработка, осуществляемая на 114, не может идентифицировать линию-кандидата для любого из LRP, то процесс должен завершаться неудачно, как указано на этапах 122, 124. После того как обработка завершена, список(ки) узлов-кандидатов и линий-кандидатов для каждой LRP предоставляются на 126.

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

После того как функция оценки применена, наиболее вероятные кандидаты идентифицируются на этапе 130 на фиг. 1, и это может наблюдаться в сети, проиллюстрированной на фиг. 9; в частности, наиболее вероятными линиями-кандидатами являются линии между узлами X(1) и X(3), между X(10) и X(11) и между X(14) и X(15). Эти линии должны использоваться для последующего вычисления кратчайшего пути на этапе 132 процесса определения.

Вычисление кратчайшего пути выполняется для каждой последовательной пары LRP начиная с первой и второй LRP, и, как показано посредством стрелки 134 на фиг. 1, этот алгоритм поиска кратчайшего пути определяет маршрут через цифровую карту 118 с помощью упомянутых наиболее вероятных узлов-кандидатов и линий-кандидатов, приводя в конечном счете к идентификации маршрута, показанного на фиг. 10. Достоверность каждого кратчайшего пути, определенного таким образом, может проверяться на этапе 136 посредством определения значения длины пути между начальным узлом и конечным узлом этого пути и последующего сравнения этого значения с доступным атрибутом DNP, указываемым в данных для каждой LRP, как указано посредством стрелки 138. Длина первого кратчайшего пути (от узла X(1) к узлу X(10)) составляет 557 метров, и это значение вписывается в интервал DNP первой LRP, наблюдаемый выше в таблице 2 (527,4-586,0 метров). Длина второго кратчайшего пути (от узла X(10) к узлу X(15)) составляет 277 метров, и это значение также вписывается в интервал DNP второй LRP (234,4-293,0 метра). Достоверность кратчайших путей, следовательно, подтверждается, и декодер не завершает проверку неудачей, а вместо этого переходит к этапам 140 и 142, сначала предоставляя конкатенированный формат, т.е. упорядоченный список всех линий, присутствующих в полном пути, и, в завершение, на этапе 142 урезая конкатенированный кратчайший путь согласно смещениям, извлеченным так, как показано схематично посредством стрелки 144. В этом примере, только положительное смещение предоставляется, и, следовательно, кратчайший путь урезается в своем начале, как понятно показано на фиг. 11. Единственным узлом, вписывающимся в интервал положительного смещения (таблица 3 выше, 117,2-175,8 метров), является узел X(3).

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

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

ПРИЛОЖЕНИЕ A

Спецификация логического формата данных и физического формата данных

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

Таблица A1
Пояснение общих сокращений Сокращение Описание AF Флаг атрибута - это флаг, который указывает, что двоичное представление привязки местоположения включает в себя информацию атрибутов ArF Флаг области - это флаг, который указывает, что привязка местоположения описывает область BEAR Азимут - это угол между направлением к точке в сети и опорным направлением (здесь: географическим севером) COORD Координаты - это пара из двух значений (долгота и широта), представляющих положение в двумерной сети DNP Расстояние до следующей точки - это длина в метрах до следующей точки привязки местоположения (измеренной вдоль пути привязки местоположения между этими двумя LRP) FOW Форма пути - это определенные аспекты физической формы, которую принимает линия. Она основана на определенном числе конкретных физических свойств и свойств дорожного движения FRC Функциональный класс дороги - это классификация на основе важности роли, которую линия играет в связанности всей дорожной сети lat Широта - это географическая координата, используемая для измерения по направлению север-юг LFRCNP Наименьший функциональный класс дороги к следующей точке lon Долгота - это географическая координата, используемая для измерения по направлению восток-запад LRP Точка привязки местоположения - это точка местоположения, которая хранит релевантную информацию, предоставляющую независимую от карты привязку местоположения; типично набор информации, описывающей объект на карте; состоит из координаты и дополнительной информации о линии на карте NOFF Отрицательное смещение - это расстояние в метрах вдоль пути привязки местоположения между реальным концом местоположения и концом пути привязки местоположения NOffF Флаг отрицательного смещения - это флаг, который указывает, что отрицательное смещение включено в привязку местоположения POFF Положительное смещение - это расстояние в метрах вдоль пути привязки местоположения между началом пути привязки местоположения и реальным началом местоположения POffF Флаг положительного смещения - это флаг, который указывает, что отрицательное смещение включено в привязку местоположения RFU Зарезервировано для будущего использования - это бит в двоичном потоке, который еще не имеет использования VER Версия - это информация о версии

1. Формат данных

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

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

1.1. Спецификация логического формата данных

Логический формат данных описывает логическую модель для привязок местоположения согласно стандарту MapLoc™.

1.1.1. Точка привязки местоположения (LRP)

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

Пара координат (см. 1.1.3.1) представляет географическое положение в рамках карты/сети и является обязательной для LRP. Пара координат принадлежит "реальному" узлу в рамках сети.

Атрибуты (см. раздел 1.1.3.2-1.1.3.6) описывают значения линии в рамках сети, в которой линия является инцидентной узлу, описанному посредством пары координат. В этом контексте она не задается, если атрибуты упоминаются как входящая или исходящая линия касательно узла. Это указывается в разделе 1.2.

1.1.2. Топологическое соединение LRP

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

Фиг. 12 показывает пример этой взаимосвязи. LRP указываются посредством A1, B1 и C1, и черные линии и стрелки указывают порядок точек от A1 к C1 на пути привязки местоположения. В этом примере LRP A1 имеет B1 в качестве следующей точки, B1 имеет C1 в качестве следующей точки, а C1 не имеет следующей точки.

1.1.3. Компоненты LRP

Этот раздел описывает компоненты точки привязки местоположения.

1.1.3.1. Пара координат

Пара координат означает пару из значений WGS84 долготы (lon) и широты (lat). Эта пара координат определяет геометрическую точку на цифровой карте. Значения lon и lat сохраняются при определении в декамикроградусах (10^-5 или пять десятичных знаков).

Сокращение: COORD

Тип: (плавающий, плавающий)

1.1.3.2. Функциональный класс дороги

Функциональный класс дороги (FRC) является классификацией дороги на основе важности дороги. Возможные значения атрибута FRC показаны в таблице A2. Если задано больше значений FRC, чем эти 8 значений привязки местоположения, то надлежащее преобразование должно выполняться, либо менее важные классы должны игнорироваться.

Таблица A2
Логический формат: функциональный класс дороги   FRC 0 - это главная дорога   FRC 1 - это дорога первого класса   FRC 2 - это дорога второго класса   FRC 3 - это дорога третьего класса   FRC 4 - это дорога четвертого класса   FRC 5 - это дорога пятого класса   FRC 6 - это дорога шестого класса   FRC 7 - это дорога другого класса  

Сокращение: FRC

Тип: целое число

1.1.3.3. Форма пути

Форма пути (FOW) описывает физический тип дороги. Возможные значения атрибута FOW показаны в таблице A3.

Таблица A3
Логический формат: форма пути FOW Описание UNDEFINED (Не задан) Физический тип дороги неизвестен MOTORWAY (Автомагистраль) Автомагистраль задается как дорога, разрешенная для моторизованных транспортных средств только в комбинации с заданной минимальной скоростью. Она имеет две или более физически разделенных проезжих части и не имеет одноуровневых перекрестков MULTIPLE_CARRIAGEWAY Многорядная проезжая часть задается как дорога с физически разделенными проезжими частями независимо от числа полос движения. Если дорога также является автомагистралью, она должна кодироваться так, а не как многорядная проезжая часть SINGLE_CARRIAGEWAY Все дороги без разделенных проезжих частей рассматриваются как дороги с одной проезжей частью ROUNDABOUT (Кольцевое пересечение дорог) Кольцевое пересечение дорог - это дорога, которая формирует кольцо, на котором разрешается движение трафика только в одном направлении TRAFFICSQUARE (Площадь на дороге) Площадь на дороге - это открытая область, (частично) окруженная дорогами, которая используется для не связанных с дорожным движением целей и которая не является кольцевым пересечением дорог SLIPROAD (Съезд с автомагистрали) Съезд с автомагистрали - это дорога, специально предназначенная для того, чтобы входить или покидать дорогу OTHER (Другое) Физический тип дороги известен, но не вписывается ни в одну из других категорий

Сокращение: FOW

Тип: целое число

1.1.3.4. Азимут

Азимут (BEAR) описывает угол между географическим севером и линией, которая задается посредством координаты LRP и координаты, которая является BEARDIST вдоль линии, заданной посредством атрибутов LRP. Если длина линии меньше BEARDIST, то противоположная точка линии используется (независимо от BEARDIST). Азимут измеряется в градусах и является всегда положительным (измеряется по часовой стрелке от севера). Параметр BEARDIST задается в таблице A4.

Сокращение: BEAR

Тип: целое число

Таблица A4
Логический формат: параметр BEARDIST Сокращение Описание Значение Единица измерения BEARDIST Расстояние между двумя координатами, которые формируют линию для вычисления значения азимута 20 метры

Фиг. 13 показывает, как определяется вторая точка для вычисления азимута. Фигура показывает линию от A2 к B2, которая имеет большую длину, чем BEARDIST. Затененная часть этой линии составляет ровно BEARDIST метров по длине, так что точка, помеченная с помощью B', отстоит на BEARDIST метров от A2, при проходе вдоль линии от A2 к B2. Прямая линия от A2 к B' теперь рассматривается для вычисления значения азимута. Следует отметить, что он отличается от угла, который должен вычисляться, если противоположный узел линии (в данном случае, это B2) используется.

Фиг. 14 показывает два примера вычисления значения азимута. Представлено две линии, одна от A3 к B3, и одна от A3 к C3. Для обеих линий дуги указывают углы на север.

1.1.3.5. Расстояние до следующей LRP

Это поле DNP описывает расстояние до следующей LRP на топологическом соединении LRP. Расстояние измеряется в метрах и вычисляется вдоль пути привязки местоположения. Последняя LRP имеет значение расстояния в 0.

Сокращение: DNP

Тип: целое число

Фиг. 15 показывает пример вычисления и назначения расстояния. Эти три LRP находятся в последовательности от A4 через B4 к C4. Следовательно, расстояние между A4 и B4 вдоль базового опорного пути должно назначаться для A4. LRP B4 сохраняет расстояние между B4 и C4, а LRP C4 имеет значение расстояния в 0.

1.1.3.6. Наименьший FRC до следующей LRP

Наименьший FRC (LFRCNP) является наименьшим значением FRC, которое появляется на пути привязки местоположения между двумя последовательными LRP. Наибольшее значение FRC равно 0, а наименьшее возможное значение FRC имеет значение в 7.

Сокращение: LFRCNP

Тип: целое число

1.1.4. Смещения

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

1.1.4.1. Положительное смещение

Положительное смещение (POFF) является разностью начальной точки привязки местоположения и начальной точки требуемого местоположения вдоль пути привязки местоположения. Значение измеряется в метрах. Фиг. 16 показывает пример для вычисления положительного и отрицательного смещения. Линии указывают путь привязки местоположения, и штриховка указывает требуемое местоположение.

Сокращение: POFF

Тип: целое число

1.1.4.2. Отрицательное смещение

Отрицательное смещение (NOFF) является разностью конечной точки требуемого местоположения и конечной точки привязки местоположения вдоль пути привязки местоположения. Значение измеряется в метрах (см. также фиг. 16).

Сокращение: NOFF

Тип: целое число

1.2. Взаимосвязь "атрибуты-LRP"

Все атрибуты связаны с LRP. Для всех LRP (за исключением последней LRP) атрибуты описывают исходящую линию узла в LRP-координате. Атрибуты последней LRP направляют к входящей узла в LRP-координате.

Фиг. 17 показывает пример для взаимосвязи между LRP и атрибутами. Линии указывают путь привязки местоположения, и узлы A5, B5 и C5 являются LRP. Следует отметить, что предусмотрена также линия, начальный и конечный узел которой не является LRP (третья линия в последовательности). Эта линия не должна использоваться для привязки, поскольку она покрывается посредством кратчайшего пути между LRP B5 и C5.

LRP A5 и B5 направляют к исходящей линии, а последнюю LRP C5 направляют к входящей линии.

1.3. Правила для форматов данных

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

Правило 1. Максимальное расстояние между двумя точками привязки местоположения не должно превышать 15 км. Расстояние измеряется вдоль пути привязки местоположения. Если это условие не удовлетворяется для привязки местоположения, то достаточное число дополнительных LRP должно быть включено.

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

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

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

Правило 3. Два LRP являются обязательными, и число промежуточных LRP не ограничено.

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

Правило 4. Координаты LRP должны выбираться на реальных узлах сети.

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

Следует устранять узлы, имеющие только одну входящую и одну исходящую линию, поскольку эти узлы не связаны с перекрестками (см. фиг. 18) и могут быть пропущены во время поиска маршрута. Узлы, которые имеют две входящих и две исходящих линии и имеют только два смежных узла, также должны устраняться (см. фиг. 19).

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

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

1.3.1. Краткий обзор правил для форматов данных

Следующая таблица обобщает правила для форматов данных.

Таблица A5
Краткий обзор правил для форматов данных Правило Описание Значение Правило 1 Максимальное расстояние между двумя последовательными LRP 15000 м Правило 2 Значения длины дороги Трактуются как целочисленные значения Правило 3 Число LRP По меньшей мере, две LRP Правило 4 Устранимые узлы LRP должны быть помещены на реальные узлы сети (также действительно для начала и конца местоположения)

1.4. Двоичное представление

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

1.4.1. Типы данных

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

Таблица A6
Физический формат: типы данных Название типа данных Тип Размер Диапазон Boolean Флаг с верно=1, ложно=0 1 бит 0-1 uByte Целое число без знака 1 байт 0-255 uShort Целое число без знака 2 байта 0-65535 uSmalllnt Целое число без знака 3 байта 0-16777215 ulnteger Целое число без знака 4 байта 0-4294967295 sByte Целое число со знаком 1 байт -128-127 sShort Целое число со знаком 2 байта -32768-32767 sSmalllnt Целое число со знаком 3 байта -8388608-8388607 slnteger Целое число со знаком 4 байта -2147483648-2147483647 String[n] Матрица из n символов n байтов Переменный размер BitField[n] Матрица из n битов n битов Переменный размер

Отрицательные целочисленные значения сохраняются в формате дополнения до двух.

1.4.2. Координаты (COORD)

Каждая точка на карте состоит из пары координат "долгота" (lon) и "широта" (lat), представленных в координатах WGS84. Направления на север и восток представляются посредством положительных значений (долгота и широта, соответственно). Значения lon и lat сохраняются при определении в декамикроградусах (10^-5, пять десятичных чисел).

Значения координат передаются как целочисленные значения. Эти значения формируются с помощью уравнения E1, которое вычисляет 24-битовое целочисленное представление. Параметр определения задается равным 24. Эта трансляция приводит к ошибке самое большее приблизительно в 2,4 метра. Обратная трансляция описывается в уравнении E2. Оба уравнения используют знаковую функцию, которая равна -1 для отрицательных значений, 1 для положительных значений и 0 в противном случае.

Уравнение E1: Преобразование из десятичных координат в целочисленные значения

Уравнение E2: Преобразование из целочисленных значений в десятичные координаты

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

1.4.2.1. Абсолютный формат

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

Таблица A7
Физический формат: формат координат (абсолютный) Тип данных Значение Описание sSmalllnt -8388608-+8388607 24-битовое представление

1.4.2.2. Относительный формат

Относительный формат используется для того, чтобы описывать разности между двумя последовательными координатами. Разность вычисляется для каждого значения (lon/lat) отдельно, как показано в уравнении E3. Текущее и предыдущее значения представляют значение широты (долготы) в градусах. Разность между этими двумя значениями умножается на 100000, чтобы определить целочисленное значение.

relative=round(100000*(currentPoint-previousPoint))

Уравнение E3: Вычисление относительных координат

Таблица A8 показывает максимальные расстояния, которые являются возможными с использованием 16-битового представления. Цифры вычисляются для фиксированной координаты при lon=5° и lat=52° (местоположение в Нидерландах).

Таблица A8
Физический формат: диапазоны долготы/широты для относительных координат Байт Широта Долгота Нижний предел Верхний предел Нижний предел Верхний предел 2 -36459 м 36460 м -22504 м 22504 м

Таблица A9 показывает тип данных для 2-байтовых смещений.

Таблица A9
Физический формат: формат координат (относительных) Тип данных Значение Описание sShort -32768-+32767 2-байтовые относительные координаты

1.4.3. Значения атрибутов

Двоичный формат атрибутов приводится ниже в этом разделе.

1.4.3.1. Функциональный класс дороги (FRC)

Функциональный класс дороги (FRC) может хранить восемь различных значений, как описано в логическом формате. Эти восемь значений представляются посредством 3 битов, и преобразование показано в таблице A10.

Таблица A10
Физический формат: функциональный класс дороги Тип данных Значение (целочисленное) Значение (двоичное) Описание BitField[3] 0 000 FRC - главная дорога   1 001 FRC 1 - дорога первого класса   2 010 FRC 2 - дорога второго класса   3 011 FRC 3 - дорога третьего класса   4 100 FRC 4 - дорога четвертого класса   5 101 FRC 5 - дорога пятого класса   6 110 FRC 6 - дорога шестого класса   7 111 FRC 7 - дорога другого класса

1.4.3.2. Форма пути (FOW)

Форма пути (FOW) может хранить восемь различных значений, как описано в логическом формате. Эти восемь значений представляются посредством 3 битов, и преобразование показано в таблице A11.

Таблица A11
Физический формат: форма пути Тип данных Значение (целочисленное) Значение (двоичное) Описание BitField[3] 0 000 UNDEFINED 1 001 MOTORWAY 2 010 MULTIPLE_CARRIAGEWAY 3 011 SINGLE_CARRIAGEWAY 4 100 ROUNDABOUT 5 101 TRAFFICSQUARE 6 110 SLIPROAD 7 111 OTHER

1.4.3.3. Азимут (BEAR)

Азимут описывает угол между дорогой и географическим севером, как описано в логическом формате. Физический формат данных задает 32 сектора, посредством чего каждый сектор покрывает 11,25° круга. Эти 32 сектора представляются посредством 5 битов. Таблица A12 показывает тип данных для атрибута азимута, а таблица A13 показывает преобразование из секторов в конкретное значение.

Таблица A12
Физический формат: азимут Тип данных Значение Описание BitField[5] 0-31 Номер сектора, в котором находится угол между севером и линией, указываемой в логическом формате данных; полный круг разделяется на 32 сектора, каждый из которых покрывает угол в 11,25°

Таблица A13
Физический формат: Задание значения азимута Значение Сектор Значение Сектор 0 000,00°<=x<011,25° 16 180,00°<=x<191,25° 1 011,25°<=x<022,50° 17 191,25°<=x<202,50° 2 022,50°<=x<033,75° 18 202,50°<=x<213,75° 3 033,75°<=x<045,00° 19 213,75°<=x<225,00° 4 045,00°<=x<056,25° 20 225,00°<=x<236,25° 5 056,25°<=x<067,50° 21 236,25°<=x<247,50° 6 067,50°<=x<078,75° 22 247,50°<=x<258,75° 7 078,75°<=x<090,00° 23 258,75°<=x<270,00° 8 090,00°<=x<101,25° 24 270,00°<=x<281,25° 9 101,25°<=x<112,50° 25 281,25°<=x<292,50° 10 112,50°<=x<123,75° 26 292,50°<=x<303,75° 11 123,75°<=x<135,00° 27 303,75°<=x<315,00° 12 135,00°<=x<146,25° 28 315,00°<=x<326,25° 13 146,25°<=x<157,50° 29 326,25°<=x<337,50° 14 157,50°<=x<168,75° 30 337,50°<=x<348,75° 15 168,75°<=x<180,00° 31 348,75°<=x<360,00°

Уравнение E4 указывает вычисление значения азимута, а фиг. 20 предоставляет графический краткий обзор секторов.

Уравнение E4: Вычисление значения азимута

1.4.3.4. Расстояние до следующей LRP (DNP)

Атрибут DNP измеряет расстояние между двумя последовательными LRP вдоль пути привязки местоположения, как описано в логическом формате.

Физический формат данных задает 8-битовое представление, и таблица A14 показывает тип данных, используемый для DNP. Это представление задает 255 интервалов, и в комбинации с правилом 1 из правил для форматов данных (максимальная длина между двумя последовательными LRP ограничена 15000 м) каждый интервал имеет длину в 58,6 метров.

Таблица A14
Физический формат: расстояние до следующей точки Тип данных Значение Описание BitField[5] 0-255 Интервал расстояния согласно уравнению E5

Уравнение E5 показывает, как значения DNP могут вычисляться.

Уравнение E5: Вычисление значения DNP

1.4.3.5. Наименьший FRC до следующей точки (LFRCNP)

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

Таблица A15
Физический формат: наименьший FRC до следующей точки Тип данных Значение Описание BitField[3] 0-7 Хранит значения, совпадающие с описанными в таблице А10

1.4.4. Заголовок привязки местоположения

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

1.4.4.1. Версия (VER)

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

Таблица A16
Физический формат: версия Тип данных Значение Описание BitField[3] 0-7 Номер текущей версии

1.4.4.2. Флаг атрибута (AF)

Флаг атрибута указывает, добавляются или нет атрибуты к каждой LRP. Значение AF равно 0, если атрибуты не добавляются, и, следовательно, привязка местоположения состоит только из координат. Иначе, значение 1 указывает, что атрибуты добавляются к каждой LRP. Тип данных для AF показан в таблицах A17 и A18.

Таблица A17
Физический формат: флаг атрибута Тип данных Значение Описание Boolean 0,1 Флаг, указывающий то, добавляются или нет атрибуты к каждой LRP

Таблица A18
Физический формат: значения флагов атрибутов Значение Описание 0 Атрибуты не добавляются 1 Для каждой LRP набор атрибутов добавляется

1.4.4.3. Флаг области (ArF)

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

Таблица A19
Физический формат: флаг области Тип данных Значение Описание Boolean 0,1 Флаг, указывающий то, описывает или нет привязка местоположения область

Таблица A20
Физический формат: значения флагов областей Значение Описание 0 Привязка местоположения не описывает область 1 Привязка местоположения описывает область

1.4.5. Смещения

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

1.4.5.1. Флаги смещения

Флаги смещения указывают, включают или нет в себя данные конкретную информацию смещения. Физический формат данных рассматривает два флага, соответствующие двум различным значениям смещения. Флаг положительного смещения (POffF) и флаг отрицательного смещения (NOffF) описываются в таблицах A21 и A22.

Таблица A21
Физический формат: флаг смещения Тип данных Значение Описание Boolean 0,1 Флаг, указывающий то, включается или нет соответствующее значение смещения в данные

Таблица A22
Физический формат: значения флага смещения Значение Описание 0 Данные привязки местоположения не включают в себя соответствующую информацию смещения 1 Данные привязки местоположения включают в себя соответствующую информацию смещения

1.4.5.2. Значения смещения

Значения смещения (положительное и отрицательное, POFF и NOFF) указывают расстояние между началом (концом) пути привязки местоположения и "реальным" началом (концом) местоположения.

Физический формат данных задает 8-битовое представление для каждого значения смещения. Таблица A23 показывает тип данных, используемый для POFF и NOFF. Это представление дает возможность задавать 256 интервалов с длиной каждого интервала в 58,6 метров. Вычисление числа интервалов для смещений указано в уравнении E6.

Таблица A23
Физический формат: смещение Тип данных Значение Описание BitField[5] 0-255 Интервал длины смещения согласно уравнению E6

Уравнение E6: Вычисление значений смещения

1.5. Спецификация физического формата данных

Этот раздел описывает компоновку полей данных в потоке байтов. Допускается, что имеется байтовый поток, и можно использовать 8 битов в расчете на байт.

1.5.1. Обзор

Основная структура двоичного формата следующая:

Заголовок, первая LRP, следующие LRP, последняя LRP и смещения

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

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

Вычисление размеров сообщений в зависимости от числа LRP может быть обнаружено в нижеприведенном разделе 1.6.

Таблица A24
Краткий обзор двоичного формата Структура ... Последняя LRP Положительное смещение Отрицательное смещение Название... ... Относительная долгота Относительная широта атр. 1 атр. 4 Смещение Смещение Число байтов ... 2 2 1 1 1 1 Описание ... Раздел 1.5.3 Раздел 1.5.3 Раздел 1.5.5.1 Раздел 1.5.5.4 Раздел 1.5.6 Раздел 1.5.6

1.5.2. Байт состояния

Байт состояния передается один раз для каждой привязки местоположения и содержит флаг области (ArF, раздел 1.4.4.3), флаг атрибута (AF, раздел 1.4.4.2) и информацию версии (VER, раздел 1.4.4.1). Биты 7, 6 и 5 зарезервированы для будущего использования (RFU) и должны равняться 0. Таблица A25 дает краткий обзор использования каждого бита в байте состояния.

Таблица A25
Байт состояния Бит 7 6 5 4 3 2 1 0 Используется для RFU RFU RFU ArF AF VER

В этой конкретной версии формата атрибуты добавляются к каждой LRP, и области не описываются. Если "текущая версия" равна 2, то байт состояния имеет значение, показанное в таблице A26:

Таблица A26
Значение байта состояния Бит 7 6 5 4 3 2 1 0 Значение 0 0 0 0 1 010

1.5.3. Координаты первой LRP

Координаты первой LRP передаются в абсолютном формате (см. раздел 1.4.2.1), и, следовательно, каждое значение (lon и lat) должно использовать 3 байта. Таблица A27 показывает последовательность байтов относительно значений долготы и широты.

Таблица A27
Координаты первой LRP Бит 2
3 2
2 2
1 2
0 1
9 1
8 1
7 1
6 1
5 1
4 1
3 1
2 1
1 1
0 9 8 7 6 5 4 3 2 1 0 Исполь-зуется для старший байт средний байт младший байт

1.5.4. Координаты следующих LRP

Координаты следующих LRP и последней LRP передаются в относительном формате (см. раздел 1.4.2.2), и, следовательно, каждое значение (lon и lat) должно использовать 2 байта. Таблица A28 показывает последовательность байтов относительно значений долготы и широты.

Таблица A28
Координаты следующих LRP Бит 15 14 13 12 11 10 9 8 7 6 5 4 3 2 1 0 Используется для старший байт младший байт

1.5.5. Атрибуты

Атрибуты добавляются к каждой LRP. Предусмотрено 4 различных типа атрибутов в зависимости от положения LRP в привязке местоположения.

1.5.5.1. Первый байт атрибута (атр. 1)

Первый байт атрибута содержит атрибуты FRC (см. раздел 1.4.3.1), и FOW (см. раздел 1.4.3.2), и два бита зарезервированы для будущего использования. Таблица A29 показывает использование каждого бита.

Таблица A29
Первый байт атрибута - достоверный для всех LRP Бит 7 6 5 4 3 2 1 0 Используется для RFU RFU FRC FOW

1.5.5.2. Второй байт атрибута (атр. 2)

Второй байт атрибута содержит атрибуты LFRCNP (см. раздел 1.4.3.5) и BEAR (см. раздел 1.4.3.3). Таблица A30 показывает использование каждого бита. Этот атрибут не является достоверным для последней LRP, поскольку нет доступной информации LFRCNP.

Таблица A30
Второй байт атрибута - достоверный для всех LRP, кроме последней LRP Бит 7 6 5 4 3 2 1 0 Используется для LFRCNP BEAR

1.5.5.3. Третий байт атрибута (атр. 3)

Третий байт атрибута содержит атрибут DNP (см. раздел 1.4.3.4), как показано в таблице A31. Этот атрибут не является достоверным для последней LRP, поскольку нет доступной информации DNP.

Таблица A31
Третий байт атрибута - достоверный для всех LRP, кроме последней LRP Бит 7 6 5 4 3 2 1 0 Используется для DNP

1.5.5.4. Четвертый байт атрибута (атр. 4)

Атрибут 4 содержит информацию BEAR, флаги положительных и отрицательных смещений (см. раздел 1.4.5.1), и один бит зарезервирован для будущего использования. Этот атрибут используется для последней LRP, как показано в таблице A32.

Таблица A32
Четвертый байт атрибута - достоверный только для последней LRP Бит 7 6 5 4 3 2 1 0 Используется для RFU POffF NOffF BEAR

1.5.6. Смещение

Положительное смещение (POFF) и отрицательное смещение (NOFF) включаются только в том случае, если соответствующие флаги в атрибуте 4 указывают их наличие. Отсутствующие значения смещения указывают смещение в 0 метров. Значения смещения вычисляются согласно разделу 1.4.5, и использование битов для этих смещений показано в таблицах A33, A34.

Таблица A33
Значение положительного смещения Бит 7 6 5 4 3 2 1 0 Используется для POFF

Таблица A34
Значение отрицательного смещения Бит 7 6 5 4 3 2 1 0 Используется для NOFF

1.6. Вычисление размеров сообщений

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

- Заголовок

1 байт - состояние

Всего: 1 байт

- Первая LRP

6 байтов - COORD (по 3 байта для lon/lat)

3 байта - атрибуты

Всего: 9 байтов

- Следующие LRP

4 байта - COORD (по 2 байта для lon/lat)

3 байта - атрибуты

Всего: 7 байтов

- Последняя LRP

4 байта - COORD (по 2 байта для lon/lat)

2 байта - атрибуты

Всего: 6 байтов

- Смещение (если включено)

1 байт - положительное смещение (если включено)

1 байт - отрицательное смещение (если включено)

Всего: 0-2 байта

Таблица A35
Размеры сообщений в зависимости от числа LRP Число LRP Размер сообщения 2 16 байтов (смещение на +1 или +2 байта, если включено) 3 23 байта (смещение на +1 или +2 байта, если включено) 4 30 байтов (смещение на +1 или +2 байта, если включено) 5 37 байтов (смещение на +1 или +2 байта, если включено) 6 44 байта (смещение на +1 или +2 байта, если включено) 7 51 байт (смещение на +1 или +2 байта, если включено) 8 58 байтов (смещение на +1 или +2 байта, если включено) ... ... n (n>1) 1+9+(n-2)*7+6 байтов (смещение на +1 или +2 байта, если включено)

Конкретный пример метода, которым используются вышеуказанные форматы, теперь предоставляется в отношении привязки местоположения, описанной выше со ссылкой на фиг. 2, 3, 4 и 5, в которой три точки привязки местоположения (узлы (1), (10) и (15) и линии (1)-(3), (10)-(11) и (14)-(15)) идентифицируются как точное описание местоположения. Привязка местоположения состоит из трех точек привязки местоположения, и таблица A36 ниже показывает координаты для узлов (1), (10) и (15). Эти узлы являются соответствующими узлами для точек привязки местоположения. При подготовке двоичного формата эта таблица также показывает относительные координаты. Узел (1) соответствует точке 1 привязки местоположения и должен иметь координаты в абсолютном формате. Узел (10), соответствующий точке 2 привязки местоположения, имеет относительные координаты относительно точки 1 привязки местоположения. Узел (15), соответствующий точке 2 привязки местоположения, также имеет относительные координаты, но теперь привязывается к точке привязки местоположения.

Таблица A36
Примерные координаты Идентификатор узла Индекс LRP Долгота Широта Относительная долгота Относительная широта (1) 1 6,12683° 49,60851° ... ... (10) 2 6,12838° 49,60398° 155 -453 (15) 3 6,12817° 49,60305° -21 -93

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

Таблица A37
Примерные значения смещения Поле Значение Положительное смещение 150 Отрицательное смещение 0

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

Таблица A38
Точки привязки местоположения, определенные в ходе кодирования Индекс LRP FRC FOW BEAR LFRCNP DNP 1 FRC3 MULTIPLE_CARRIAGEWAY 135° FRC3 561 2 FRC3 SINGLE_CARRIAGEWAY 227° FRC5 274 3 FRC5 SINGLE_CARRIAGEWAY 290° ... ...

Атрибуты BEAR, LFRCNP и DNP определяются так, как описано выше.

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

- Байт состояния: см. таблицу A39

- LRP 1: см. таблицы A40-A44

- LRP 2: см. таблицы A45-A49

- LRP 3: см. таблицы A50-A53

- Смещение: см. таблицу A54

Таблица A39
Двоичный пример: байт состояния Бит 7 6 5 4 3 2 1 0 Описание RFU RFU RFU ArF AF Версия Значение 0 0 0 0 1 0 1 0

Таблица A40
Двоичный пример: LRP 1 - абсолютная долгота Байт Первый Второй Третий Бит 7 6 5 4 3 2 1 0 7 6 5 4 3 2 1 0 7 6 5 4 3 2 1 0 Значение 0 0 0 0 0 1 0 0 0 1 0 1 1 0 1 1 0 1 0 1 1 0 1 1

Таблица A41
Двоичный пример: LRP1 - абсолютная широта Байт Первый Второй Третий Бит 7 6 5 4 3 2 1 0 7 6 5 4 3 2 1 0 7 6 5 4 3 2 1 0 Значение 0 0 1 0 0 0 1 1 0 1 0 0 0 1 1 0 1 1 1 1 0 1 0 0

Таблица A42
Двоичный пример: LRP1 - атрибут 1 Бит 7 6 5 4 3 2 1 0 Описание RFU RFU FRC FOW Значение 0 0 0 1 1 0 1 0

Таблица A43
Двоичный пример: LRP1 - атрибут 2 Бит 7 6 5 4 3 2 1 0 Описание LFRCNP Азимут Значение 0 1 1 0 1 1 0 0

Таблица A44
Двоичный пример: LRP1 - атрибут 3 Бит 7 6 5 4 3 2 1 0 Описание DNP Значение 0 0 0 0 1 0 0 1

Таблица A45
Двоичный пример: LRP2 - относительная долгота Байт Первый Второй Бит 7 6 5 4 3 2 1 0 7 6 5 4 3 2 1 0 Значение 0 0 0 0 0 0 0 0 1 0 0 1 1 0 1 1

Таблица A46
Двоичный пример: LRP2 - относительная широта Байт Первый Второй Бит 7 6 5 4 3 2 1 0 7 6 5 4 3 2 1 0 Значение 1 1 1 1 1 1 1 0 0 0 1 1 1 0 1 1

Таблица A47
Двоичный пример: LRP2 - атрибут 1 Бит 7 6 5 4 3 2 1 0 Описание RFU RFU FRC FOW Значение 0 0 0 1 1 0 1 1

Таблица A48
Двоичный пример: LRP2 - атрибут 2 Бит 7 6 5 4 3 2 1 0 Описание LFRCNP Азимут Значение 1 0 1 1 0 1 0 0

Таблица A49
Двоичный пример: LRP2 - атрибут 3 Бит 7 6 5 4 3 2 1 0 Описание DNP Значение 0 0 0 0 0 1 0 0

Таблица A50
Двоичный пример: LRP3 - относительная долгота Байт Первый Второй Бит 7 6 5 4 3 2 1 0 7 6 5 4 3 2 1 0 Значение 1 1 1 1 1 1 1 1 1 1 1 0 1 0 1 1

Таблица A51
Двоичный пример: LRP3 - относительная широта Байт Первый Второй Бит 7 6 5 4 3 2 1 0 7 6 5 4 3 2 1 0 Значение 1 1 1 1 1 1 1 1 1 0 1 0 0 0 1 1

Таблица A52
Двоичный пример: LRP3 - атрибут 1 Бит 7 6 5 4 3 2 1 0 Описание RFU RFU FRC FOW Значение 0 0 1 0 1 0 1 1

Таблица A53
Двоичный пример: LRP3 - атрибут 4 Бит 7 6 5 4 3 2 1 0 Описание RFU POffF NOffF Азимут Значение 0 1 0 1 1 0 0 1

Таблица A54
Двоичный пример: положительное смещение Бит 7 6 5 4 3 2 1 0 Описание POFF Значение 0 0 0 0 0 0 1 0

Полный поток двоичных данных должен иметь длину в 24 байта и составлен следующим образом (в порядке байтов слева направо и сверху вниз):

00001010 00000100 01011011 01011011 00100011 01000110 11110100 00011010 01101100 00001001 00000000 10011011 11111110 00111011 00011011 10110100 00000100 11111111 11101011 11111111 10100011 00101011 01011001 00000010

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

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

2. Способ по п.1, в котором поиск маршрута является поиском маршрута по кратчайшему пути.

3. Способ по п.1 или 2, в котором поиск маршрута работает для соответствующих пар последовательных узлов-кандидатов.

4. Способ по п.1, в котором идентифицированные узлы-кандидаты являются реальными узлами в том, что они представляют реальные пересечения.

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

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

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

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

9. Способ по п.8, в котором этап оценки выполняют с использованием функции оценки.

10. Способ по п.9, в котором функция оценки включает в себя часть оценки узлов-кандидатов и часть оценки линий-кандидатов или сегментов-кандидатов.

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

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

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

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

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

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

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

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