ЭФФЕКТИВНЫЙ СПОСОБ ПРИВЯЗКИ МЕСТОПОЛОЖЕНИЯ

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

- является более эффективным, чем AGORA-C, без существенного негативного влияния на точность,

- не мешает доступным полосам пропускания для широковещательных данных,

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

- может быть полной заменой системе привязки TMC-местоположения,

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

- не требует периодического обслуживания.

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

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

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

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

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

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

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

(iv) сохранения последней линии или сегмента в списке путей в упомянутом списке для поиска маршрута, если еще не сохранены.

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Фиг. 6, 7 и 8 графически иллюстрируют различные возможности, возникающие при проверке того, что местоположение корректно покрывается посредством процедуры, проиллюстрированной на фиг. 5.

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

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

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

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

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

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

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

Что касается фиг. 2, дополнительно описывается процесс проверки достоверности "Check_Location", проиллюстрированный в 14 на фиг. 1. Все местоположения, которые не сохраняются в базе данных ранее кодированных местоположений, должны проверяться на предмет достоверности перед дальнейшей обработкой. В качестве первого этапа, на этапе 30 выполняется проверка возможности соединения. Проверка возможности соединения обеспечивает то, что входящее местоположение не разделяется на два или более различных отрезков, которые не соединены. Каждый соединенный участок должен быть обработан отдельно и представляет одно местоположение, которое должно быть кодировано независимо. Эта проверка происходит, если местоположение состоит только из одного соединенного участка.

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

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

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

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

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

Что касается фиг. 3, предоставляется описание этапа 16 Create_LocationReference (Создание привязки местоположения) на фиг. 1. После обработки достоверности, описанной выше, предоставляется достоверная последовательность сегментов, и она должна быть преобразована в привязку местоположения как дерево объектов, заданных в логическом формате данных, как описано ниже.

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

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

Поиск маршрута вычисляет кратчайший путь между начальным сегментом и конечным сегментом. Это вычисление выполняется итеративно, и после инициализации на этапе 50 основной цикл, включающий себя этапы 52, 54, 56, 58, должен вычислять кратчайший путь. Путь по кратчайшему маршруту должен проверяться в каждой итерации на этапе 56 (описано подробнее в дальнейшем со ссылкой на фиг. 5), чтобы устанавливать то, является или нет местоположение по-прежнему частью вычисленного дерева кратчайшего пути. Если местоположение более не покрывается посредством дерева кратчайшего пути, то вычисление маршрута прекращается и возвращает частичный маршрут (часть местоположения, которая покрывается к текущему моменту) на этапе 60, и сегмент, который должен использоваться в качестве промежуточной точки привязки местоположения, чтобы делать поиск маршрута уникальным и допускающим продолжение впоследствии. Этот промежуточный сегмент идентифицируется на этапе 44 на фиг. 3 и возвращается в алгоритм поиска маршрута как новый начальный сегмент, с которого должны осуществляться один или более дополнительных поисков маршрутов.

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

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

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

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

- если промежуточный сегмент идентифицируется.

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

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

Имеются различные специальные возможности для корректной идентификации и привязки промежуточного сегмента в зависимости от характера отклонения, которое возникает при вычислении кратчайшего пути, и они все описываются со ссылкой на фиг. 5, 6, 7 и 8.

Чтобы проверять совпадение кратчайшего пути, определенного к текущему моменту, последний сегмент, обнаруженный в местоположении во время поиска маршрута, сохраняется в списке для поиска маршрута (указывается в этапе 70 на фиг. 5) так, что может легко определяться то, какой сегмент должен быть следующим, поскольку только последующие сегменты, смежные с последним сохраненным сегментом или, по меньшей мере, имеющие совпадающие конечные и начальные узлы, соответственно, могут рассматриваться. Для экономии длины привязки местоположения фундаментальным является то, что поиск маршрута по кратчайшему пути эффективно исключает из привязки те сегменты, которые попадают на кратчайший путь, т.е. нет необходимости для них формировать часть привязки. Соответственно, в точках 72, 74 принятия решения осуществляются проверки того, что последний сегмент, формирующий часть списка маршрутов по кратчайшему пути, как существует или совпадает с кодируемым местоположением, так и корректно привязывается относительно кратчайшего пути с точки зрения указателей, которые идеально используются в списке кратчайших путей, чтобы привязываться к:

- следующему ожидаемому сегменту на кратчайшем пути, и

- предыдущему сегменту на упомянутом кратчайшем пути.

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

Тем не менее, разумеется, меньшие отклонения неизбежно обнаруживаются, и все возможные типы отклонений покрываются посредством различных ветвей блок-схемы последовательности операций по фиг. 5 и простых линейных чертежей на фиг. 6, 7 и 8. Если упростить, отклонение обнаруживается, если сегмент на пути местоположения в настоящий момент анализируется, но этот сегмент не согласован со следующим ожидаемым сегментом относительно списка кратчайших маршрутов. Отклонение также обнаруживается, если следующий ожидаемый сегмент списка кратчайших маршрутов находится в соответствии со следующим сегментом в списке путей местоположения, но предшествующий указатель для этого сегмента в списке кратчайших путей не указывает на местоположение. Это означает, что предшествующий указатель должен быть равным последнему сегменту, обнаруженному в местоположении. В обоих случаях необходимо идентифицировать надлежащее промежуточное звено. Следующие этапы определяют это промежуточное звено, и в специальном случае необходимо добавлять два промежуточных звена. Главное внимание при обнаружении надлежащего промежуточного звена сосредоточено на том, что используется сегмент, имеющий начальный узел, формирующий часть пересечения.

Ссылаясь сначала на фиг. 5 и 6, во всех случаях необходимо находить начало отклонения, указываемого на этапе 76. Фиг. 6 иллюстрирует простейший случай, в котором отклонение начинается до того, как последний сегмент сохранен как часть части списка кратчайших маршрутов и также формирует часть исходного списка путей местоположения. Полный путь местоположения, который должен быть описан, представляется посредством сегментов A, B, C, D, E, F и G. Кратчайший путь, достоверно определенный к текущему моменту и совпадающий с местоположением, представляется посредством сегментов A и D, выделенных полужирным на чертеже. По мере того, как поиск кратчайшего пути выполняется, в частности, между начальным сегментом A и конечным узлом сегмента E, обнаруживается отклонение H, которое меньше. В таком случае (который является наиболее распространенным случаем), идеально требуется находить сегмент, обнаруживаемый в местоположении и имеющий начальный узел, в котором отклонение начинается. В этом случае сегмент C должен быть включен как надлежащее промежуточное звено, поскольку это гарантирует то, что местоположению следуют в любом алгоритме кратчайшего пути, осуществляемом в процессе декодирования. Этот поиск эффективно проходит вновь по списку путей местоположения на предмет сегментов, которые удовлетворяют этому критерию, и это указано на этапах 78, 79 на фиг. 5. Хотя невозможно в отношении простого пути, показанного на фиг. 6, возможно, что такие сегменты могут не быть обнаружены. В этом случае сегмент, последний сохраненный в списке кратчайших маршрутов, может использоваться как промежуточное звено, как проиллюстрировано на этапе 80 как функция кратчайшего пути с использованием последнего сохраненного сегмента, поскольку его начало никогда не идентифицирует отклонения, начинающиеся перед ним.

В альтернативном варианте осуществления отклонение начинается после конца последнего сегмента, сохраненного в списке E для поиска маршрута, выделенном полужирным на фиг. 7. В этом случае кратчайший путь от A до E известен, и только сегменты между A и E сохранены. Кратчайший путь между сегментом A и конечным узлом сегмента F может фактически привязываться только посредством A и I, причем второе является отклонением от пути местоположения, который включает в себя F, и возникает после конца последнего сохраненного сегмента E. В этом случае промежуточное звено может создаваться от этого F сегмента, как указано на этапе 82 на фиг. 5, при условии, что предшествующий указатель для F сегмента фактически указывает обратно на сегмент в местоположении, в этом случае E. Эта проверка указывается на этапе 84.

В исключительном случае на фиг. 8, где предшествующий указатель для отклонения, возникающего после последнего сегмента, сохраненного как часть поиска самого короткого маршрута, фактически ссылается обратно на сегмент, не формирующий часть местоположения, как в случае сегмента K, ссылающегося обратно на сегмент J, то в качестве первого этапа, создается первый промежуточный сегмент E (как на этапе 82, поясненном ранее), и второй промежуточный сегмент D также сохраняется, поскольку это последний сегмент, возникающий в пути местоположения и начинающийся с пересечения, из которого сегмент J более короткого пути начинается. Эти этапы, в общем, указываются на этапах 86, 88 на фиг. 5 и необходимы, поскольку сохраненная привязка местоположения должна в конечном счете исключать оба сегмента J и K.

Обращаясь в завершение снова к фиг. 3, после того как обработка всего списка путей местоположения завершена, то все частичные идентифицированные кратчайшие пути комбинируются на этапе 46. Покрытие местоположения может состоять из нескольких вычисленных частичных маршрутов, если начальное вычисление маршрута определяет промежуточный сегмент. Этот промежуточный сегмент выступает в качестве дополнительной информации в привязке местоположения, чтобы направлять поиск маршрута для полного покрытия местоположения. Если поиск маршрута достигает конца местоположения, то все вычисленные частичные маршруты комбинируются, чтобы формировать путь, который полностью покрывает местоположение. Этот этап в одном варианте осуществления также может добавлять продления в начале и конце местоположения, вычисленном на этапах 36, 38, проиллюстрированных на фиг. 2. Первая и последняя точки привязки местоположения регулируются, и новые смещения, описывающие относительное положение исходного местоположения, вычисляются.

Чтобы предоставлять лучшее понимание метода, которым местоположение кодируется с использованием настоящего изобретения, дополнительный конкретный пример предоставляется со ссылкой на фиг. 9, 10, 11 и 12.

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

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

Кодирование

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Фиг. 13 показывает пример этой взаимосвязи. 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 значений привязки местоположения, то надлежащее преобразование должно выполняться, либо менее важные классы должны игнорироваться.

Сокращение:FRC Тип: целое число

1.1.3.3. Форма пути

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

Сокращение:FOW Тип: целое число

1.1.3.4. Азимут

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

Сокращение:BEAR Тип: целое число

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

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

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

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

Сокращение:DNP Тип: целое число

Фиг. 16 показывает пример вычисления и назначения расстояния. Эти три 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) является разностью начальной точки привязки местоположения и начальной точки требуемого местоположения вдоль пути привязки местоположения. Значение измеряется в метрах. Фиг. 17 показывает пример для вычисления положительного и отрицательного смещения. Линии указывают путь привязки местоположения, и штриховка указывает требуемое местоположение.

Сокращение:POFF Тип: целое число

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

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

Сокращение:NOFF Тип: целое число

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

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

Фиг. 18 показывает пример для взаимосвязи между 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 должны выбираться на реальных узлах сети.

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

1.4.3.3. Азимут (BEAR)

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

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

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

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

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

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

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

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

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

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

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

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

1.4.4.1. Версия (VER)

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

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

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

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

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

1.4.5. Смещения

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

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

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

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

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

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

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

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

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

1.5.1. Обзор

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

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

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

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

Вычисление размеров сообщений в зависимости от числа LRP может быть обнаружено в нижеприведенном разделе 1.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 дает краткий обзор использования каждого бита в байте состояния.

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

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

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

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

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

1.5.5. Атрибуты

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

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

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

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

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

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

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

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

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

1.5.6. Смещение

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

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 байта

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

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

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

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

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

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

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

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

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

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

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