BRPI0912270A2 - método de resolver uma localização de dados codificados representativos da mesma - Google Patents

Abstract

MÉTODO DE RESOLVER UMA LOCALIZAÇÃO DE DADOS CODIFICADOS REPRESENTATIVOS DA MESMA. A invenção provê um método de resolver uma localização a partir de uma lista ordenada de pontos de referência de localização sendo representativos de nós em um mapa digital de codificador e cada tendo atributos representativos de uma linha ou segmento especifico no mapa digital de codificador emanando de ou incidente naqueles nós. O método compreende as etapas de: (i) para cada ponto de referência de localização, identificar pelo menos um né candidato que existe em um segundo mapa digital, utilizando os atributos disponíveis daquele ponto de referência de localização, identificando pelo menos uma linha ou segmento candidato que existe no segundo mapa digital que emana a partir de ou incidente no né candidato, (ii) Executar uma busca de rota no segundo mapa digital entre: (a) Pelo menos um de pelo menos um né candidato e linha ou segmento candidato correspondente que emana a partir do mesmo ou incidente ao mesmo, e (b) Pelo menos um de um né candidato para o próximo ponto de referência de localização que aparece na lista e linha ou ?segmento correspondente que emana a partir do mesmo ou incidente ao mesmo, e extrair do segundo mapa digital cada linha ou segmento que faz parte da rota assim determinada entre os nós candidatos, (ii) Repetir a etapa (ii) para cada par consecutivo de pontos de referência de localização até e incluindo 0 ponto de referência de localização final que aparece na lista. Preferivelmente, a busca de rota é uma busca de rota de trajeto mais curto, mais preferivelmente que opera em pares respectivos de nós candidatos sucessivos, e inclui ?um meio de assegurar que a linha ou segmento correspondente do primeiro do par de nós parte da rota que resulta a partir dai.

Description

“MÉTODO DE RESOLVER UMA LOCALIZAÇÃO DE DADOS CODIFICADOS REPRESENTATIVOS DA MESMA” Campo da invenção A presente invenção se refere a um método de resolver uma localização represen- tada por dados codificados de acordo com um ou mais formatos predeterminados, e mais especificamente se refere a um método para determinar precisamente uma localização em . um mapa digital, como aqueles criados e vendidos por Tele Atlas B.V. e Navteq Inc., em um modo que não depende do mapa digital específico utilizado durante um processo de decodi- 7 ficação e ainda assim é idêntico à localização originalmente codificada. A esse respeito, o método pode ser considerado com mapa-agnóstico, porém o modo no qual a decodificação ocorre, ao contrário da resolução de dados decodificados em uma localização, será inevita- velmente dependente do formato predeterminado escolhido.

Embora o termo “localização” no contexto de mapeamento digital possa significar qualquer de uma variedade de características do mundo real físicas, diferentes (por exem- plo, localização de um ponto na superfície da terra, um trajeto ou rota contínua, ou uma ca- deia contígua desse tipo, de vias públicas navegáveis existentes na terra, ou uma área ou região na terra capaz, no caso de uma área retangular, quadrada ou circular, de ser definida por dois ou mais parâmetros), essa invenção é mais aplicável! a uma representação de da- dos codificados de um trajeto através de uma rede de estradas ou outras vias públicas na- vegáveis representadas em um mapa digital.

Antecedentes da invenção . No pedido complementar do requerente depositado na mesma data que o presente intitulado “An efficient location referencing method”, uma técnica é descrita para produzir - uma representação legível por máquina de uma localização em um modo que não somente é considerado otimizado no que se refere ao comprimento geral de bytes, como também é considerado como sendo mapa-agnóstico.

Qualquer mapa digital moderno (ou gráfico matemático, como às vezes são conhe- cidos) de uma rede de estradas, em sua forma mais simples, é efetivamente um banco de dados que consiste em uma pluralidade de tabelas definindo primeiramente nós (que podem ser considerados como pontos ou objetos de dimensão zero) mais comumente representati- vos de interseções de estrada, e em segundo lugar linhas entre esses nós que representam as estradas entre essas interseções. Em mapas digitais mais detalhados, linhas podem ser divididas em segmentos definidos por um nó de início e nó de final, que podem ser iguais no caso de um segmento de comprimento zero, porém são mais comumente separados, Nós — podem ser considerados reais ou “válidos” para fins desse pedido quando representam uma interseção de estradas na qual um mínimo de 3 linhas ou segmentos intersectam ao passo que nós “artificiais” ou “evitáveis” são aqueles que são fornecidos como âncoras para seg-

mentos não sendo definidos em uma ou ambas as extremidades por um nó real.

Esses nós artificiais são úteis em mapas digitais para fornecer, entre outras coisas, informações de formato para um trecho específico da estrada ou um meio de identificação a posição ao lon- go de uma estrada na qual alguma característica daquela estrada muda, por exemplo, um limitede velocidade.

Praticamente em todos os mapas digitais modernos, nós e segmentos (e/ou linhas) - são adicionalmente definidos por vários atributos que são novamente representados por dados nas tabelas do banco de dados, por exemplo, cada nó terá tipicamente atributos de r latitude e longitude para definir sua posição no mundo real.

O “gráfico” completo da rede de estradas é descrito por milhões de nós e segmentos para cobrir uma área de extensão de um ou mais países, ou parte da mesma.

No contexto de idealizar um meio de referenciar eficientemente ou descrever uma localização (isto é, um trajeto através de uma rede de estradas), não somente é altamente ineficiente simplesmente fornecer uma lista ordenada de todos os nós (e/ou segmentos, e opcionalmente seus atributos) compreendidos no mapa digital que fazem parte da localiza- ção, como tal método de referência necessitaria que exatamente o mesmo mapa digital fos- se utilizado durante qualquer falta de referência que ocorresse posteriormente, por exemplo, em um dispositivo móvel para o qual a referência de localização foi transmítida, porque nós, segmentos, linhas e seus atributos são praticamente somente exclusivamente definidos em uma versão específica de um mapa criado por um vendedor de mapa específico.

Mesmo atributos fundamentais como longitude e latitude para um nó específico poderiam diferir en- . tre mapas digitais diferentes.

Um atributo específico fornecido frequentemente em mapas digitais é uma referên- - cia de tabela de localização de Canal de Mensagem de tráfego (TMC). TMC é uma tecnolo- giapara distribuir informações de viagem e tráfego para usuários de veículo, e mais particu- larmente a sistemas de navegação (portáteis ou integrados) presentes nesses veículos e que incluem alguma forma de mapa digital.

Una mensagem TMC consiste em um código de evento (que não necessita ser específico de tráfego, embora esses sejam mais comuns) e um código de localização, frequentemente consistindo em uma lista ordenada de referências de localizaçãopor meio da qual a localização do evento de tráfego pode ser determinada no mapa digital e desse modo representada graficamente na tela do sistema de navegação.

Um número de nós predefinidos nos mapas digitais mais comercialmente disponíveis é atri- buído uma referência de localização TMC que é determinada com referência a uma tabela de localização limitada.

A tabela de localização consiste em 2"* referências de localização (65536) correspondendo a um número similar de localizações físicas ou mundo real, nor- malmente interseções de estrada, também identificáveis no mapa digital.

Embora mensagens TMC sejam muito eficientes em que podem ser tão curtas quanto 37 bits em comprimento e, portanto não incidem significativamente sobre a largura de banda disponível para dados broadcast, somente um número fixo de referência de locali- zação está disponível e, portanto tipicamente somente rodovias e principais estradas (ou interseções nas mesmas) em cada país que oferece TMC podem ser referenciadas.

Há vá- rias outras desvantagens de referências de localização TMC.

Por exemplo, tabelas de loca- lização TMC são - - frequentemente mantidas através de uma autoridade pública ou Governo nacional, - propensas à mudança entre ciclos de atualização, que são tradicionalmente bem M longos, - não existentes, ou disponíveis somente comercialmente, em alguns mercados.

Evidentemente, a decodificação de uma referência de localização TMC é intrinse- camente simples em que uma simples consulta pode ser executada no banco de dados de mapa digital para cada código de localização TMC resultando em identificação imediata dos nós e segmentos corretos relevantes (cada provedor de mapa incluirá códigos de localiza- ção TMC como parte do processo de produção de mapa assegurando precisão), e desse modo a localização pode ser imediatamente resolvida.

Entretanto, como está se tornando possível identificar acúmulo de tráfego em estradas secundárias e urbanas utilizando dados de sonda GPS e GSM (por exemplo, usuários de veículos possuem cada vez mais um tele- fone móvel ou um dispositivo de navegação de satélite conectado útil como sonda), códigos —delocalizaçãodeTMC são simplesmente inadequados no que se refere à resolução.

Uma tentativa para superar algumas das limitações de referências de localização - de TMC ou referências específicas de mapa é o projeto de Referência de localização dinã- mica, também conhecido como AGORA-C (no processo de padronização de acordo com o - número ISO 17572-1, 2 e 3). Embora uma descrição completa da abordagem de referência —delocalização AGORA-C esteja além do escopo desse pedido, os fundamentos da aborda- gem são que uma referência de localização pode ser totalmente especificada por um con- junto de pontos de localização, especificados por pares de coordenadas de latitude e longi- tude e ordenados em uma lista, cada ponto estando em conformidade com várias regras, porém mais importante sendo consecutivo em termos da localização sendo referenciada e o ponto anterior na lista, isto é, pontos sucessivos formam uma relação de ponto seguinte.

Como com outros sistemas de referência de localização, cada ponto é dotado de um núme- ro de atributos que auxilia em definir melhor aquele ponto, porém específico para o método AGORA-C é a identificação de cada ponto como um de um ponto de localização, um ponto de interseção, um ponto de roteamento, ou alguma combinação desses três.

Cada ponto ao longo da localização na qual a assinatura de seção de estrada muda é representada por um ponto de interseção, assim localizações sendo trajetos sobre uma rede de estrada e que passam através de interseções sem nenhuma alteração de assinatura de seção de estrada não necessitam ser referenciadas por um ponto de interseção. Por exemplo, se uma locali- zação inclui uma seção de rodovia que inclui junções que não são relevantes no que se re- fere à localização, então não há necessidade de incluir pontos de interseção para tais jun- ções. Uma das etapas anteriores no método de codificação AGORA-C é a determinação de todosos pontos de interseção intermediários entre um primeiro e um último ponto de inter- seção ao longo da localização na qual uma alteração de assinatura de seção de estrada - ocorre. Todos esses pontos são adicionados a uma tabela de pontos finalmente fazendo Ms parte da referência de localização AGORA-C. Dentro dessa tabela, pelo menos dois pontos de roteamento também terão sido identificados, de acordo com certas regras. Pontos de roteamento são fornecidos onde pontos de interseção sozinhos são insuficientes para de- terminar de forma não ambígua a localização correta no decodificador, e são adicionados como pontos separados, ou onde um ponto de roteamento exigido coincide com ponto de interseção existente, uma simples alteração de atributos no último é efetuada. Embora essa abordagem de referência seja abrangente em que é possível codificar e decodificar precisa e repetidamente qualquer localização existente em um sistema de in- formações geográficas, acredita-se que o sistema seja excessivo e possivelmente redun- dante em certos aspectos, e um sistema de codificação e decodificação mais eficiente é possível. Por exemplo, embora o método de referência seja independente de qualquer obra de pré-compilação e seja independente de mapa, o tamanho médio de mensagem AGORA- C é significativamente mais elevado do que 30 bytes por referência de localização. Em ter- - mos dos dispositivos que poderiam comumente decodificar referências e localização, como dispositivos de navegação pessoal, PDAs, telefones celulares, ou sistemas de navegação - integrados no carro, é desejável que a mensagem recebida seja tão curta quanto possível para permitir decodificação rápida e resolução final da localização representada desse mo- do.

Portanto, é um objetivo da presente invenção fornecer primariamente um método de resolver uma localização representada por dados estruturados, tipicamente um pacote de dados binários que resulta da codificação de uma lista ordenada de pontos de referência de localização representativos daquela localização de acordo com uma especificação de forma- to de dados físicos, que é tanto econômico em termos de processamento exigido, e que não obstante obtém taxas de sucesso muito elevadas em termos de recriar a localização correta apesar da brevidade relativa de dados recebidos independente do mapa digital utilizado.

SUMÁRIO DA INVENÇÃO De acordo com a invenção, é fornecido um método de resolver uma localização a partir de uma lista ordenada de pontos de referência de localização sendo representativa de nós em um mapa digital de codificador e cada tendo atributos representativos de uma linha ou segmento específico no mapa digital de codificador emanando de ou incidente naqueles nós, compreendendo as etapas de: i) Para cada ponto de referência de localização, identificar pelo menos um nó can- didato que existe em um segundo mapa digital, utilizando os atributos disponíveis daquele pontode referência de localização, identificar pelo menos uma linha ou segmento candidata existindo no segundo mapa digital que emana de ou incidente ao nó candidato, - ii) Executar uma busca de rota no segundo mapa digital entre: - pelo menos um de pelo menos um nó candidato e a linha ou segmento candidata MM correspondente que emana do mesmo ou incidente ao mesmo, e - pelo menos um de um nó candidato para o ponto de referência de localização se- guinte que aparece na lista e a linha ou segmento candidata correspondente que emana a partir do mesmo ou incidente ao mesmo, e extrair do segundo mapa digital cada linha ou segmento que faz parte da rota as- sim determinada entre os nós candidatos, ii) Repetir a etapa (ii) para cada par consecutivo de pontos de referência de locali- zação até e incluindo o ponto de referência de localização final que aparece na lista.

Preferivelmente, a busca de rota é uma busca de rota de trajeto mais curto, ou in- clui um elemento que é fundamentalmente relacionado à distância entre o ponto de início e final utilizado como entradas para a busca de rota.

Tipos diferentes de buscas de rota po- dem ser, portanto considerados, como algoritmo de Dijkstra ou A*. Preferivelmente, a busca de rota opera em pares respectivos de nós candidatos su- - cessivos, e inclui um meio de assegurar que a linha ou segmento correspondente do primei- ro do par de nós faz parte da rota resultando a partir daí. - Preferivelmente, os nós candidatos identificados são nós reais em que são repre- —sentativos de interseções de mundo real, que em toda probabilidade estarão, portanto pre- sentes no segundo mapa digital.

Preferivelmente a etapa de extrair cada linha ou segmento do segundo mapa digital é aumentada por armazenar cada das linhas ou segmentos extraídos em uma lista de trajeto de localização.

Além disso, cada lista de trajeto de localização desse modo criada para cada — busca de rota sucessiva é preferivelmente concatenada em uma etapa final ou alternativa- mente cada das linhas ou segmentos extraídos para uma busca de rota seguinte são apen- sas à lista de trajeto de localização preexistente, o efeito final sendo o mesmo, isto é, forne- cer um meio de identificar completamente a localização.

Preferivelmente, no caso onde mais de um nó candidato é identificado para um ponto de referência de localização, o método inclui a etapa adicional de classificação dos nós candidatos identificados de acordo com uma ou mais métricas prescritas, e desse modo identificar um nó candidato mais provável! ou fornecer uma classificação de nós candidatos.

Também preferivelmente no caso onde mais de uma linha ou segmento candidato existindo no segundo mapa digital é identificado para um nó candidato ou candidato mais provável, então o método inclui a etapa de classificação similarmente aquelas linhas ou segmentos candidatos resultando na identificação de uma linha ou segmento candidato mais provável oufornecendo uma classificação de linhas ou segmentos candidatos.

Em uma modalidade preferida, a etapa de classificação um ou ambos os nós can- . didatos e linhas ou segmentos candidatos é obtida por aplicação de uma função de classifi- cação. Preferivelmente, a função de classificação inclui uma parte de classificar nó candida- ' to e uma parte de classificar linha ou segmento candidato.

Mais preferivelmente, a parte de classificar nó candidato da função de classificar in- clui alguma dependência em uma distância calculada ou representativa entre o ponto de referência de localização ou suas coordenadas absolutas, e os nós candidatos ou suas co- ordenadas absolutas como aparecem em e extraídas do segundo mapa digital.

Mais preferivelmente, a parte de classificar segmento ou linha candidata da função de classificação inclui um meio de avaliar a similaridade dos atributos de linha ou segmento como aparecem no mapa digital de codificador e aqueles que aparecem no segundo mapa digital utilizado na resolução da localização.

Ainda preferivelmente, o método inclui as etapas adicionais de: - determinar, a partir do segundo mapa, um valor de comprimento de trajeto para cada trajelo entre nós candidatos sucessivos compreendidos no segundo mapa digital, o trajeto sendo estabelecido como resultado da busca de rota entre nós candidatos sucessi- - vos, - comparar o valor de comprimento de trajeto assim determinado com um atributo - DNP do primeiro dos dois pontos de referência de localização utilizados na busca de rota, e - no evento de uma discrepância grande demais entre o valor de comprimento de trajeto e o atributo de DNP, repetir a busca de rota utilizando nós candidatos alternativos e/ou linhas para um ou ambos de cada par sucessivo de pontos de referência de localização para tentar reduzir a discrepância entre valor de comprimento de trajeto e atributo de DNP, ou relatar um erro.

- 30 Ainda preferivelmente, o método inclui a etapa final de aplicar qualquer valor de deslocamento que possa ser associado aos primeiro e último pontos de referência de locali- zação nas primeira e última linhas na lista resultante de linhas ou segmentos presentes no segundo mapa digital e que juntos fomecem uma representação completa e contínua da localização.

Em um segundo aspecto da invenção, é fornecido um elemento de programa de computador que compreende meio de código de programa de comutador para fazer um computador executar o método como exposto acima. Ainda em um aspecto adicional, é for-

necido tal programa de computador incorporado em meio legível por computador.

Em um terceiro aspecto da invenção é fornecido um disposítivo de computação, op- cionalmente portátil e sendo de um dispositivo de navegação pessoal (PND), um assistente pessoal digital (PDA), telefone celular ou realmente qualquer aparelho de computação capaz de executar o programa de computador exposto acima, e incluindo como mínimo um pro- cessador e armazenagem no qual o programa pode residir, a armazenagem também inclu- - indo um mapa digital, e meio para saída de informações. Na maioria das modalidades, o meio para saída de informações consistirá em uma tela de display na qual uma representa- " ção gráfica do mapa digital pode ser exibida. Em uma modalidade preferida, a localização resolvida ou uma parte da mesma, é exibida em sobreposição, coberta, justaposta ou em combinação coma porção relevante do mapa digital a quai se refere. Em modalidades alter- nativas, o dispositivo de computação pode somente ou adicionalmente incluir meio de saída de informação de áudio.

A presente invenção provê vantagem excepcional em relação a técnicas conheci- das em que uma localização potencialmente longa pode ser resolvida utilizando somente relativamente poucos pontos de referência de localização e seus atributos correspondentes. Desses elementos básicos, nós candidatos e linhas ou segmentos podem ser identificados com referência a qualquer mapa digital moderno, visto que a invenção tira proveito do fato de que a maioria dos mapas digitais modernos inclui praticamente toda interseção de estra- daeprovêum nó para a mesma. Além disso, a maioria dos mapas digitais também inclui pelo menos alguns atributos básicos para a forma e classe de estradas entre tais interse- - ções. Se estiverem presentes no segundo mapa digital utilizado no processo de resolução, então é possível fazer uma comparação dos atributos e tomar uma decisão com relação a . se uma linha ou segmento identificado no segundo mapa digital é mais adequado do que outra. Finalmente, a invenção faz uso de um cálculo de posição para identificar adicional mente e de forma melhor linhas candidatas no segundo mapa digital, e fornecer um meio de classificar as mesmas onde muitas linhas candidatas são identificadas.

Deve ser mencionado que o atributo de posição é um atributo calculado tanto no la- do do codificador como durante o método de resolução e não um que genericamente faz —partedo mapa digital. Entretanto, pode ser calculado precisamente e é considerado com muito útil em identificar e/ou classificar precisamente linhas candidatas.

A busca de rota de trajeto mais curto também é útil visto que é um dos algoritmos de busca de rota mais simples disponíveis, bem conhecido e rápido de implementar e exe- cutar. Uma vantagem útil adiciona! é que o algoritmo de busca de rota empregado no codifi- —cadornão precisa necessariamente ser igual àquele utilizado durante resolução da localiza- ção pós-transmissão. Por exemplo, é possível implementar um A* no lado de codificador e um algoritmo Dijkstra no lado de decodificador. Como ambos esses algoritmos se baseiam principalmente em um parâmetro de distância entre ponto de início e final, resultarão na mesma rota.

No caso de A*, deve ser mencionado que o elemento heurístico do algoritmo A* necessitaria atender certas exigências, porém em todos os casos práticos, esse seria em qualquer evento o caso.

Por conseguinte, na presente invenção, somente é necessário que um trajeto mais curto seja encontrado.

Em redes de estradas reais, o trajeto mais curto é normalmente único, porém pode-se imaginar circunstâncias excepcionais, como grades arti- . ficiais ou rotas curtas em torno de layouts de estradas retangulares em cidades onde mais de uma única rota de trajeto mais curto pode ser identificada. ' Vantagens adicionais da invenção tornar-se-ão evidentes a partir da seguinte mo- dalidade específica da invenção que é descrita por meio de exemplo com referência aos desenhos em anexo.

Breve descrição dos desenhos A figura 1 mostra um fluxograma esquemático do método da presente invenção, As figuras 2-5 fornecem representações esquemáticas de um primeiro mapa digital —queincluinóse segmentos e em particular a figura 2 ilustra uma rede de exemplo, a figura 3 ilustra um trajeto de localização que se deseja ser codificado nessa rede, a figura 4 ilustra o trajeto mais curto entre nós de início e final de um trajeto estendido que parcialmente inclui aquela localização, e a figura 5 ilustra os pontos de referência de localização necessários para referenciar totalmente aquela localização, As figuras 6-11 fornecem representações esquemáticas de um segundo mapa digi- tal incluindo nós e segmentos e em particular a figura 6 ilustra a rede da figura 2, porém co- - mo representado por nós e segmentos que aparecem no segundo mapa digital, a figura 7 ilustra nós candidatos identificados no segundo mapa digital, a figura 8 ilustra as linhas can- - didatas identificadas no segundo mapa digital, e a figura 9 ilustra as linhas candidatas mais prováveis pelas quais a localização é totalmente referenciada, a figura 10 mostra o trajeto mais curto como algoritmicamente determinado entre as linhas mais prováveis, e a figura 11 mostra a localização como resolvida, As figuras 12-20 fornecem várias ilustrações esquemáticas úteis no contexto dos formatos de dados físicos e lógicos, descritos abaixo, e especificamente, a figura 12 mostra —. 30 aconexão consecutiva exigidade pontos de referência de localização (LRPs), a figura 13 ilustra como uma posição é calculada para um LRP em relação a um LRP seguinte, a figura 14 mostra como posições podem variar, a figura 15 demonstra como um atributo “distância até o ponto seguinte” é determinado para um LRP, a figura 16 ilustra o uso de deslocamen- tos, a figura 17 mostra o modo no qual LRPs são dotados de atributos, as figuras 18/19 ilus- tram nósa serem evitados durante a codificação de uma referência de localização, e a figu- ra 20 ilustra como valores de posição para um LRP caem em 1 de 32 setores discretos de um círculo.

Descrição detalhada A seguinte descrição da invenção é fornecida em termos de segmentos, porém de- ve ser entendido que o método pode ser aplicado igualmente a linhas, ou a combinações de linhas e segmentos que juntos são representativos de um trajeto contínuo através de uma rededeestradas.

É útil no contexto da presente invenção primeiramente fornecer uma breve descri- . ção do modo no qual uma referência de localização é codificada, e os formatos de dados lógicos e físicos específicos utilizados no processo de codificação.

Os últimos são forneci- " dos como Apêndice a esse relatório descritivo, e deve-se fazer referência a esse Apêndice emtodaa seguinte descrição.

Com referência primeiramente às figuras 2-5, um primeiro mapa digital (codificador) é mostrado na figura 2 e consiste em 15 nós e 23 linhas (linhas de dois sentidos são conta- das duas vezes). Os nós são numerados de 1 a 15. Os atributos necessários de linhas são mostrados ao lado de cada linha utilizando o formato: <FRC>, <FOW>, <comprimento em metro>. FRC é uma abreviatura para “Classe funcional de estrada” e FOW é uma abreviatu- ra para “forma de via”, ambos são descritos em maior detalhe no Apêndice abaixo.

As cabe- ças das setas indicam o sentido de direção possível para cada linha.

A localização a ser codificada é mostrada na figura 3 utilizando linhas em negrito.

À localização inícia no nó 3 e continua através dos nós 5, 7, 10, 11, 13, 14 e termina ho nó 15. Seucomprimento total no mapa de codificador é de 685 metros.

A lista ordenada de linhas e o mapa à ser utilizado durante codificação servem como entrada para o codificador. - Codificação: Na primeira etapa do processo de codificação a localização será primeiramente - checada em relação à validade.

Uma vez que a localização é conectada e dirigível e todas —asclassesfuncionais de estrada ao longo da localização estão entre 0 e 7, essa localização é considerada válida.

Embora seja possível no processo de codificação incluir uma verifica- ção com relação a se restrições de giro nos dados de mapa são habilitadas ou não, essa etapa é omitida para brevidade aqui.

A segunda etapa de codificador é checar o nó de início e final da localização como sendo nós reais de acordo com certas regras de formato de dados predeterminados.

O nó final 15 tem somente uma linha de entrada e é, portanto válido.

O nó de final 3 tem também duas linhas incidentes, porém aqui é uma linha de saída e uma linha de entrada.

Portanto, esse nó não é válido e o codificador busca um nó real fora da localização.

O codificador en- contrará o nó 1 como sendo um nó real e também expande a localização exclusivamente.

O —nó1é escolhido como o novo nó de início para a referência de localização e haverá um des- locamento positivo de 150 metros.

O comprimento total do trajeto de referência de localiza- ção resulta em 835 metros.

. CO AA terceira etapa de codificador é prosseguir para calcular um trajeto mais curto en- tre a linha de início (linha entre os nós 2 e 3) e a linha de final (linha entre nós 14 e 15) da localização. O trajeto mais curto resultante é delineado na figura 4 utilizando linhas em ne- grito. O trajeto mais curto tem um comprimento de 725 metros. A próxima (4º) etapa do processo de codificação é agora verificar se a localização está coberta pelo trajeto mais curto calculado. Determinará que esse não é o caso e há um - desvio após o nó 10. De acordo com os princípios delineados no pedido copendente do requerente da " mesma data, o codificador determinará a linha a partir do nó 10 para 11 como se tornando um novo ponto de referência de localização intermediário. O nó 10 é um nó real uma vez que não pode ser pulado durante busca de rota e o trajeto mais curto até essa linha cobre totalmente a parte correspondente da localização. O comprimento da localização sendo co- berta após esse primeiro cálculo de trajeto mais curto é 561 metros. A próxima etapa de codificação prepara o cálculo de rota para determinar um trajeto mais curto para a parte restante da localização (do nó 10 através de 11, 13e 14a 15) O cálculo de trajeto mais curto iniciará, portanto, na linha de 10 a 11 e termina na linha de 14 a

15. O codificador retorna à etapa 3 acima e determinará um trajeto mais curto (compri- mento: 274 metros) entre 10 e 15 e a etapa 4 acima retornará que a localização está agora totalmente coberta pelos trajetos mais curtos calculados. Como etapa seguinte, o trajeto de referência de localização será composto de dois - trajetos mais curtos e a lista ordenada de pontos de referência de localização será formada agora. A figura 5 mostra as linhas em negrito que são selecionadas para os pontos de refe- . rência de localização. O primeiro ponto de referência de localização aponta para a linha do nó1para3eindicao início do trajeto de referência de localização, o segundo ponto de refe- rência de localização aponta para a linha do nó 10 para 11 e essa linha foi necessária para evitar o desvio da localização. O último ponto de referência de localização aponta para a linha do nó 14 para 15 e indica o final do trajeto de referência de localização. A etapa final (excluindo quaisquer verificações de validade intermediárias) é a con- versão da lista ordenada de LRPs em uma referência de localização binária, e a descrição fornecida no Apêndice do presente tanto para formato de dados lógicos como formato de dados físicos como determinado pelo requerente auxiliará a compreensão do leitor. Deve ser enfatizado que a descrição fornecida no Apêndice e que fornece detalhes dos formatos específicos é fornecida somente como exemplo, e o leitor versado reconhecerá que outros formatossão possíveis. Voltando agora para a presente invenção, os dados físicos finalmente transmitidos são uma representação binária dos três pontos de referência de localização identificados acima e incluem dados de atributo para que as linhas apropriadas possam ser identificadas. Uma das bases fundamentais para essa invenção é que haja uma forte possibilidade de que os mapas digitais utilizados no codificador e decodificador serão diferentes. Evidentemente, podem ser iguais em cujo caso a localização pode ser resolvida levemente mais rapidamen- tevisto que as linhas de nós candidatos serão mais exata e rapidamente identificadas, po- rém em qualquer caso, o método da invenção deve ser ainda aplicado. . Com referência à figura 6, que mostra a representação da mesma parte de uma re- de de estradas que aquela mostrada na figura 2, porém de acordo com um segundo mapa Í digital diferente. Uma comparação das duas figuras identificará imediatamente que há dife- renças materiais no número e posição de nós e linhas.

Com referência também à figura 1 na qual um fluxograma de visão geral 100 do processo de acordo com uma modalidade da invenção é mostrado, a primeira etapa 102 no processo é decodificar os dados binários transmitidos sem fio ou de entrada (mais comu- mente no caso de um dispositivo móvel (ou XML ou outra representação legível por máqui- na) resultando do processo de codificação anterior e estruturado de acordo com o formato de dados físicos. A decodificação desses dados binários não é um elemento essencial da invenção, que se aplica à resolução de uma localização de uma lista de pontos de referência de localização — a decodificação dos dados binários é meramente um meio de identificar os pontos de referência de localização necessários.

Na etapa 104, uma verificação de validade é executada — a falha nessa etapa inicial resultará no término do procedimento e o relatório de um erro como indicado em 124. Deve - ser mencionado que o processo de codificação e redução em formato físico é um processo de perda, e, portanto as informações extraídas dos dados binários não serão tão precisas - quanto antes da criação do fluxo binário. Por conta do uso de intervalos para a posição e a distância até o ponto seguinte (DNP) o valor exato não pode ser extraído e, portanto, a pre- cisão é limitada a um pequeno intervalo contendo o valor exato.

As informações sendo extraídas do exemplo de dados binários são mostradas nas tabelas 1, 2 e 3 (e são adicionalmente referenciadas na figura 1 nas etapas 106, 108 e 110 respectivamente).

Índice de LRP Longitude Latitude 1 16.12682º 49.60850º un E) Tabela 1. Coordenadas decodificadas

Índice IFRC |FOW posição LFRCNP FRC3 [MULTIPLE CARRIAG |135.00º-146.25º |;FRC3 527.4m-586.0m . FRC3 [SINGLE CARRIAGEW |225.00*-236.25º [FRC5 234.4m -293.0m 3 FRC5 [SINGLE CARRIAGEW Tabela 2: informações LRP decodificadas Deslocamento valor Deslocamento positivo 117.2mM-175.8m Tabela 3: informações de deslocamento decodificadas Essas informações são suficientes para resolver a localização no mapa de decodifi- cadormostrado na figura 6. Esse mapa consiste em 17 nós e 26 linhas (linhas em dois sen- 7 tidos são contadas duas vezes). Para evitar confusão, todos os nós referenciados no mapa de decodificador são prefaciados com “X”. " Esse mapa diferente do mapa de codificador (vide a figura 2) de vários modos.

Al- guns valores de comprimento são diferentes (por exemplo, linha do nó x(3) a x(5), alguns —valoresde classe funcional de estrada mudaram (por exemplo, linha do nó X(3) para X(5)) e há mais dos nós x(16) e X(17) e também linhas adicionais conectando esses novos nós.

O desafio do decodificador é resolver a localização nesse mapa diferente.

Após validar os dados, e fornecer uma lista de pontos de referência de localização decodificados (LRPs) e seus atributos, como indicado na etapa 112 na figura 1, o decodifi- —cador então começa a processar cada LRP na lista na etapa 114 para primeiramente deter- minar nós candidatos para cada LRP.

O resultado desse processamento, que bem simples- mente é efetuado pelo uso das coordenadas LRP e identificando o(s) nó(s) mais próximo(s) que aparecem no mapa de decodificador 118 (como indicado genericamente em 116) é for- necer uma lista de nós candidatos para cada LRP.

Nós de mapa sendo distantes dos LRPs por um valor maior do que um valor limite predeterminado podem ser eliminados, como mostrado em 120, A figura 7 mostra os nós candidatos (círculo em negrito) que são posicio-

nados perto pelas coordenadas dos pontos de referência de localização. Para o ponto de referência de localização 1 e 2 (nas tabelas 1 & 2 acima), nesse exemplo, existe somente um nó candidato, porém para o último ponto de referência de localização dois nós candida- tos X(16) e X(17) são possíveis. Também como parte do processamento dos LRPs e seus atributos, linhas candida- tas para cada ponto de referência de localização são também identificadas. As linhas em ' negrito na linha 8 são as linhas candidatas para esse exemplo. O primeiro LRP é represen- tado pelo ponto candidato X(1) que, por sua vez tem duas linhas de saída como candidatos, 7 o segundo LRP tendo ponto de candidato X(10) tem três linhas de saída como candidato e o último ponto de referência de localização tem duas linhas de entrada (uma para cada nó candidato X(15) e X(16). Se o processamento conduzido em 114 falhar em identificar uma linha candidata para quaisquer dos LRPs, então o processo deve falhar, como indicado em 122, 124. Após conclusão do processamento, a(s) lista(s) de nós candidatos e linhas para cada LRP são fornecidas em 126.

Em uma modalidade da invenção, e particularmente onde mais de um nó candidato e/ou linha é identificada para cada LRP, algum meio de taxação ou classificação dos candi- datos é preferivelmente exigido. Por conseguinte, uma função de classificação 128 é aplica- da às listas de nós candidatos e/ou linhas (preferivelmente ambos) de acordo com sua con- formidade com os atributos do ponto de referência de localização. Genericamente, o aspec- toimportante para a função de classificação é que sua aplicação resultará em uma classíifi- cação de um, porém preferivelmente ambos os nós e linhas candidatos de acordo com uma - ou mais métricas. O leitor versado reconhecerá que muitas bases matemáticas e/ou estatís- ticas diferentes existem para funções de classificação, e no contexto desse pedido, portanto . é suficiente explicar que uma função de classificação ou parte da mesma específica a nós pode incluir alguma medição da distância de candidatos até a posição física ou geográfica do LRP decodificado, e que uma função de classificação ou parte da mesma específica a linhas candidatas incluirá algum meio de avaliar a correlação entre o tipo de linha candidata identificada e aquelas representadas nos dados decodificados e possivelmente também al- guma direção daquelas linhas candidatas e identificadas.

Após a função de classificação ter sido aplicada, candidatos mais prováveis são identificados na etapa 130 na figura 1, e isso pode ser visto na rede ilustrada na figura 9 — especificamente, as linhas candidatas mais prováveis são aquelas entre nós x(1) e x(3), en- tre x(10) e x(11), e entre x(14) e x(15). Essas linhas serão utilizadas para o seguinte cálculo de trajeto mais curto na etapa 132 do processo de resolução.

O cálculo de trajeto mais curto é executado em cada par sucessivo de LRPs inici- ando com os primeiro e segundo LRPs, e como mostrado pela seta 134 na figura 1, esse algoritmo de trajeto mais curto determina uma rota através do mapa digital 118 utilizando os nós e linhas candidatas mais prováveis que resultam finalmente na identificação da rota mostrada na figura 10. Cada trajeto mais curto assim determinado pode ser validado na eta- pa 136 por determinar um valor de comprimento de trajeto entre o nó de início e nó final da- quele trajeto, e então comparar esse valor com o atributo DNP disponível especificado nos —dadosparacada LRP, como indicado pela seta 138. O comprimento do primeiro trajeto mais curto (do nó X(1) até o nó X(10) é 557 metros e esse valor encaixa no intervalo DNP do pri- : meiro LRP visto acima na tabela 2 (572,4 metros — 586,0 metros). O comprimento do se- gundo trajeto mais curto (do nó X(10) até o nó X(15) é 277 metros e esse valor também se ' encaixa no intervalo DNP do segundo LRP (234,4 metros — 293,0 metros). Os trajetos mais curtos são, portanto validados e o decodificado não falha, porém em vez disso prossegue para as etapas 140 e 142, primeiramente fornecendo um formato concatenado, isto é, uma lista ordenada de todas as linhas presentes no trajeto completo, e finalmente na etapa 142, cortando o trajeto mais curto concatenado de acordo com os deslocamentos recuperados como mostrado esquematicamente pela seta 144. Nesse exemplo, somente um desloca- mento positivo é fornecido e, portanto o trajeto mais curto é cortado em seu início, como claramente mostrado na figura 11. O único encaixe de nó no intervalo de deslocamento po- sitivo (tabela 3 acima 117,2 metros — 175,8 metros) é nó x(3). Como pode ser visto a partir de acima, a presente invenção provê um método alta- mente confiável e eficiente de resolver uma localização a partir de dados codificados recebi- dos Os detalhes dos formatos de dados lógicos e físicos são agora fornecidos por meio . de exemplo. O leitor deve estar ciente de que o Apêndice a seguir provê somente uma de muitas definições específicas possíveis para esses formatos. . APÊNDICE A ESPECIFICAÇÃO PARA FORMATO DE DADOS LÓGICOS & FORMATO DE

DADOS FÍSICOS A seguinte tabela explica termos e abreviaturas comuns utilizados nesse documen- to e no contexto de referência de localização: AF Indicador de atributo — um indicador que indica que a representação bi- [E re antuêna do nase nai mameêcaaã ArF Indicador de área — um indicador que indica que a referência de localiza- [Qa sameôn e “SOCO BEAR Posição — ângulo entre a direção até um ponto na rede e uma direção de E a COORD Coordenadas — um par de valores (longitude e latitude) representado o fina nana TT

Distância até o próximo ponto — o comprimento em metros até o próximo ponto de referência de localização (medido ao longo do trajeto de refe- rência de localização entre esses dois LRP) FOW Forma de via — certos aspectos da forma físico que uma linha assume. O emos mameematdtn dm | FRC Classe funcional de estrada — uma classificação baseada na importância 1 do papel que a linha desempenha na conectividade da rede total de es- tradas LRP Ponto de referência de localização — um ponto da localização que retém informações relevantes que permitem uma referência de localização in- dependente de mapa; tipicamente uma coleção de informações que des- crevem um objeto no mapa; consiste em uma coordenada e informações adicionais sobre uma linha no mapa NOFF Deslocamento negativo — distância em metro ao longo do trajeto de refe- rência de localização entre o final real da localização e o final do trajeto de referência de localização Indicador de deslocamento negativo — um indicador que indica que um e aemeremomeanosndita ma rntnca drtato | ' POFF Deslocamento positivo — distância em metro ao longo do trajeto de refe- rência de localização entre o início do trajeto de referência de localização 7 e o início real da localização POffF Indicador de deslocamento positivo — um indicador que indica que um O Tsseenserame caindo raiva ão RFU Reservado para uso futuro — um bit em um fluxo binário que não tem o aa Simm ooo Tabela A1: explicação de abreviaturas comuns -

1.Formato de dados Uma referência de localização é uma descrição de uma parte designada de um mapa digital ou uma segiência de posições geográficas. Para essa descrição os requeren- tesutiizam o modelo de pontos de referência de localização (LRP, vide 1.1.1). Uma referência de localização para localizações de linha contém pelo menos dois LRPs, porém não há número máximo de LRP's definidos. O trajeto de referência de localiza- ção é o trajeto no mapa digital descrito pelos LRPs e pode ser encontrado por um cálculo de trajeto mais curto entre cada par consecutivo de LRPs.

1.1Especificação de formato de dados lógico O formato de dados lógico descreve o modelo lógico para referências de localiza- ção de acordo com o padrão MapLoc"Y"

1.1.1Ponto de referência de localização (LRP) A base de uma referência de localização é uma sequência de pontos de referência ' de localização (LRPs). Tal LRP contém um par de coordenadas, especificado em valores de longitude e latitude WGS84 e adicionalmente vários atributos. ' O par de coordenadas (vide 1.1.3.1) representa uma posição geográfica em um mapaf/rede e é obrigatório para um LRP. O par de coordenadas pertence a um nó “real” em uma rede, Os atributos (vide a seção 1.1.3.2 a 1.1.3.6) descrevem valores de uma linha em uma rede na qual a linha é incidente ao nó descrito pelo par de coordenadas. Nesse contex- to não é definido se os atributos se referem a uma linha de entrada ou de saída em relação aonó.lsso será especificado na seção 1.2.

1.1.2. Conexão topológica de LRPs Com referência à figura 12, os pontos de referência de localização serão armaze- nados em uma ordem topológica ou relação de “ponto seguinte" de LRPs sucessivos. O úl- timo ponto nessa ordem não terá ponto seguinte nessa relação.

A figura 12 mostra um exemplo dessa relação. Os LRPs são indicados por A1, B1 e C1 e as linhas pretas e setas indicam a ordem dos pontos a partir de A1 até C1 no trajeto de - referência de localização. Nesse exemplo o LRP A1 terá B1 como ponto seguinte, B1 terá C1 como ponto seguinte e C1 não terá ponto seguinte. 7 1.1.3 Componentes de LRPs Essa seção descreve os componentes de um ponto de referência de localização.

1.1.3.1 par de coordenadas Par de coordenadas quer dizer um par de valores de longitude (lon) e latitude (lat) WGSB84. Esse par de coordenadas específica um ponto geométrico em um mapa digital, Os valores lon e lat são armazenados em uma resolução de decamicrograus (10º, ou cinco pontosdecimais).

Abreviatura: COORD tipo: (flutuante, flutuante)

1.1.3.2 Classe funcional de estrada À classe funcional de estrada (FRC) é uma classificação de estrada baseada na importância de uma estrada. Os valores possíveis do atributo FRC são mostrados na tabela —A2.Sehouvermais valores FRC definidos do que esses 8 valores de referência de localiza- ção então um mapeamento adequado necessita ser feito ou classes menos importantes ne- cessitam ser ignoradas.

FRC FRC 0 — estrada principal FRC 1 — estrada de primeira classe FRC 2 — estrada de segunda classe FRC 3 — estrada de terceira classe FRC 4 — estrada de quarta classe NM FRC 5 — estrada de quinta classe FRC 6 — estrada de sexta classe ' FRC 7 — estrada de outra classe Tabela A2: formato lógico: classe funcional de estrada Abreviatura: FRC tipo: inteiro

1.1.3.3 forma de via A forma de via (FOW) descreve o tipo físico de estrada. Os valores possíveis do atributo FOW são mostrados na tabela A3.

Rodovia Uma rodovia é definida como uma estrada permitida para veículos motorizados somente em combinação com uma velocidade mínima determinada. Tem duas ou mais estradas fisicamente separadas e nenhum cruzamento de nível único MULTIPLE. CARRIAGEWAY | Uma estrada de rodagem múltipla é definida como uma es- 7 trada com estradas fisicamente separadas independente do número de pistas. Se uma estrada for também uma rodovia, Í deve ser codificada como tal e não como uma estrada de rodagem múltipla.

SINGLE CARRIAGEWAY Todas as estradas sem estradas separadas são considera- us asno cvatc amu stat de cimemina — Rotatória Uma rotatória é uma estrada que forma um anel no qual o rr ramoaemeno cnomteonumadesearmido.

TRAFFICSQUARE Um Traffic square é uma área aberta (parcialmente encerra- da por estradas que é utilizada para fins não de tráfego e que não é uma Rotatória.

SLIPROAD Uma Estrada de recuo é uma estrada especialmente projeta- A farsrgmarataardmia OUTRO O tipo físico de estrada é conhecido, porém não se encaixe

MAE Tabela A3: formato lógico: forma de via

Abreviatura: FOW tipo: inteiro

1.1.3.4 Posição A posição (BEAR) descreve o ângulo entre o verdadeiro Norte e uma linha que é definida pela coordenada do LRP e uma coordenada que é BEAREDIST ao longo da linha definida pelos atributos de LRP. Se o comprimento da linha for menor do que BEARDIST então o ponto oposto da linha é utilizado (independente de BEARDIST). A posição é medida 7 em graus e sempre positivo (medindo no sentido horário a partir do Norte). O parâmetro BEARDIST é definido na Tabela A4. ' Abreviatura: BEAR tipo: inteiro BEARDIST Distância entre duas coordenadas que formam | 20 O r Limememe catador É Tabela A4: formato lógico: parâmetro BEARDIST A figura 13 mostra como o segundo ponto para o cálculo de posição é determinado. A figura mostra uma linha de A2 até B2 que é mais longo do que BEARDIST. A parte som- breada dessa linha é exatamente BEARDIST metros de comprimento de modo que o ponto marcado com B' é BEARDIST metros de distância de A2 atravessando ao longo da linha de A2?atéB2 A linha reta de A2 a B' é agora considerada para o cálculo do valor de posição. Observe isso é diferente do ângulo que teria sido calculado se o nó oposto d elinha (nesse caso, isso seria B2) for utilizado. A figura 14 mostra dois exemplos do cálculo de valor de posição. Há duas linhas, 7 uma de A3 para B3 e uma de A3 para C3. Para as duas linhas os arcos indicam os ângulos paraoNorte. ' 1.1.3.5 distância até LRP seguinte Esse campo de DNP descreve a distância até o LRP seguinte na conexão topológi- ca dos LRPs. A distância é medida em metros e é calculada ao longo do trajeto de referên- cia de localização. O último LRP terá o valor de distância O. Abreviatura: DNP tipo: inteiro A figura 15 mostra um exemplo do cálculo de distância e atribuição. Os três LRPs estão em uma sequência de A4 sobre B4 até C4. portanto, a distância entre A4 e B4 ao lon- go do trajeto de referência de localização será atribuída a A4. O LRP B4 reterá a distância entre B4 e C4 e o LRP C4 terá um valor de distância de 0.

1.1.3.6 FRC mais baixo até o LRP seguinte O FRC mais baixo (LFRCNP) é o valor de FRC mais baixo que aparece no trajeto de referência de localização entre dois LRPs consecutivos. O valor de FRC mais elevado é O e o valor de FRC mais baixo possível! é avaliado com 7. Abreviatura: LERCNP — tipo: inteiro

1.1.4 deslocamentos Deslocamentos são utilizados para encurtar o trajeto de referência de localização em seu início e final. As posições novas ao longo do trajeto de referência de localização in- dicam o início real! e final da localização.

1.1.4.1 deslocamento positivo O deslocamento positivo (POFF) é a diferença do ponto de início da referência de ' localização e ponto de início da localização desejada ao longo do trajeto de referência de localização. O valor é medido em metros. A figura 16 mostra um exemplo para o cálculo do ? deslocamento positivo e negativo. As linhas estão indicando o trajeto de referência de locali- zaçãoeosombreado indica o local desejado.

Abreviatura: POFF tipo: inteiro

1.1.4.2 deslocamento negativo O deslocamento negativo (NOFF) é a diferença do ponto final da localização dese- jada e o ponto final da referência de localização ao longo do trajeto de referência de locali- zação. O valor é medido em metros. (vide a figura 16 também).

Abreviatura: NOFF — tipo: inteiro

1.2atributos de relação - LRP todos os atributos são ligados a um LRP. Para todos os LRPs (exceto aquele último LRP) os atributos descrevem uma linha de saída do nó na coordenada de LRP. Os atributos doúltimoLRP dirigem a uma entrada do nó na coordenada de LRP. A figura 17 mostra um exemplo para a relação entre um LRP e os atributos. As li- . nhas indicam o trajeto de referência de localização e os nós AS, B5 e C5 são os LRPs. Ob- serve que há também uma linha cujo nó de início e final não é um LRP (a terceira linha na 7 sequência). Essa linha não necessita ser referenciada porque é coberta pelo trajeto mais curtoentreosLRPsB5eCS5.

Os LRPs A5 e B5 dirigem para uma linha de saída e o último LRP C5 dirige para uma linha de entrada.

1.3 Regras de formato de dados Essas regras descrevem reguiações adicionais para referências de localização de — acordo com esse relatório descritivo. Essas regras são utilizadas para simplificar o processo de codificação e decodificação e aumentar a precisão dos resultados.

Regra 1 — a distância máxima entre dois pontos de referência de localização não excederá 15 km. A distância é medida ao longo do trajeto de referência de localização. Se essa condição não for atendida para uma referência de localização então um número sufici- — entedeLRPs adicionais será inserido.

A distância máxima entre dois pontos de referência de localização consecutivos é limitada para acelerar a computação de trajeto mais curto porque várias rotas curtas podem ser computadas mais rápidas do que uma rota grande se o algoritmo de roteamento tiver de considerar a rede inteira. A restrição também provê a oportunidade de formar um formato binário compacto com uma precisão aceitável.

Regra 2 — todos os comprimentos são valores de número inteiro. Se houver valores flutuantes disponíveis então arredondaremos esses valores para obter uma representação inteira. ' Mapas diferentes poderiam armazenar os valores de comprimento em formatos di- ferentes e também com precisão diferente e a base uniforme para tudo é o uso de valores ' inteiros. Também é mais compacto para transmitir valores inteiros em um formato binário do que utilizar valores flutuantes.

Regra 3 — dois LRPs são obrigatórios e o número de LRPs intermediários não é li- mitado.

Uma referência de localização de linha deve ter sempre pelo menos dois pontos de referência de localização indicando o início e o final da localização. Se o codificador detectar situações críticas onde o decodificador (em um mapa diferente) poderia ter problema, a refe- rência de localização poderia ser aumentada com LRP' intermediários adicionais.

Regra 4 — as coordenadas dos LRPs serão escolhidas em nós de rede real.

Esses nós de rede real serão junções no mundo real e espera-se que essas jun- ções possam ser encontradas em mapas diferentes com probabilidade mais elevada do que posições em outro lugar em uma linha. Adicionalmente nós serão evitados que podem ser facilmente pulados durante uma busca de rota. Nesses nós evitáveis não é possível desviar 7 de uma rota. Nós tendo somente uma linha de entrada e uma de saída serão evitados uma vez ' que esses nós não são relacionados a junções (vide a figura 18) e podem ser pulados du- rante busca de rota. Nós que têm duas linhas de entrada e duas de saída e há somente dois nós adjacente serão também evitados (vide a figura 19).

Se um desses nós for selecionado para um LRP então esse LRP será deslocado ao longo do trajeto de referência de localização para encontrar um nó adequado. Isso pode ser feito uma vez que um cálculo de rota pulará tais nós evitáveis sem deixar o trajeto desejado.

' 30 Se o início ou o final de uma localização for colocado em nós evitáveis então o codi- ficador deve expandir a localização exclusivamente e deve encontrar um nó apropriado fora da localização. Essa expansão nunca deve entrar na localização porque isso encurtará a localização.

1.3.1 Visão geral das regras de formato de dados A seguinte tabela resume as regras de formato de dados. o o gg

E E JO Regra 2 Valores de comprimento de estrada Tratados como valores intei- 0 A A Regra 4 Nós evitáveis LRPs serão colocados em nós de rede real (também ' válido para início e final de uma localização) ' Tabela A5: visão geral de regras de formato de dados

1.4 representação binária O formato de dados básicos descreve um formato de fluxo orientado por byte para o formato de dados lógicos especificado acima. Utiliza os componentes descritos no formato —dedadoslógicosna seção 1.1.

1.4.1 tipos de dados O formato de dados físicos utiliza os seguintes tipos de dados. A tabela fornece uma visão geral de todos os tipos de dados disponíveis e específica o nome, o tipo e o ta- manho designado de cada tipo de dados. Nas seguintes seções os nomes de tipo de dados sãoutilizados para indicar o tamanho e tipo para cada componente de dados. Nome do tipo de/Tipo tamanho faixa dado Booleano Indicador com verdadeiro = 1,] 1 bit — FE E eos me os | slnteger Inteiro marcado 4 bytes -2147483648 - se o Eres SO mesa me era rea oe e rama | Tabela A6: formato físico: tipos de dados Valores inteiros negativos são armazenados no formato de complemento de dois.

1.4.2 Coordenadas (COORD)

Cada ponto em um mapa consiste em um par de coordenadas “longitude” (lon) e “latitude” (lat) representado em coordenadas WGS84. As direções norte e leste são repre- sentadas por valores positivos (longitude e latitude respectivamente). Os valores lon e lat são armazenados em uma resolução de decamicrograus (10 *, cinco decimais). Os valores de coordenadas serão transmitidos como valores inteiros. Esses valores serão gerados utilizando equação E1 que calcula uma representação de número inteiro de 1 24 bits. O parâmetro de resolução é definido em 24. Essa versão leva a um erro de aproxi- madamente 2,4 metros no máximo. A versão para trás é descrita na equação E2. As duas 7 equações fazem uso da função de signo que é -1 para valores negativos, 1 para valores positivos e O de outro modo. Resolution int= (sencoo) *0.5 EO) 360º Equação E1: transformação de coordenadas decimais em valores inteiros (int sen(int) *0.5) * 360º deg = [sea ana) Equação E2: transformação de valores inteiros em coordenadas decimais O formato físico faz uso de um formato de coordenadas absoluto e relativo. O for- - mato absoluto representa os valores designados da posição geográfica e o valor relativo é o deslocamento das coordenadas relativas à coordenada precedente. . 1.4.2.1 formato absoluto O formato absoluto descreve posição geográfica em uma resolução de 24 bits. À tabela A7 mostra o tipo de dados utilizado para o formato absoluto. Tabela A7: formato físico: formato de coordenadas (absoluto)

1.4.2.2 Formato relativo O formato relativo é utilizado para descrever diferenças entre duas coordenadas consecutivas. A diferença é calculada para cada valor (lon/lat) separadamente como mos- trado na equação E3. Os valores atual e anterior representam o valor de latitude (longitude) em graus. A diferença entre esses dois valores é multiplicada por 100000 para resolver um valorinteiro. Relative = round (100000* (currentPoint — previousPoint) Equação E3: cálculo de coordenadas relativas A Tabela A8 mostra as distâncias máximas que são possíveis utilizando uma repre-

sentação de 16 bits. As figuras são calculadas para uma coordenada fixa em lon = 5º e lat = 52º (localização na Holanda). E — s— byte = — Tr LA te Fm mm mm A Tabela A9 mostra o tipo de dados para deslocamentos de 2 bytes. : Tabela AS: formato físico: formato de coordenadas (relativo) 1,4.3 valores de atributo O formato binário dos atributos seguirá nessa seção.

1.4.3.1 classe funcional de estrada (FRC) A classe funcional de estrada (FRC) pode reter oito valores diferentes como des- crito no formato lógico. Esses oito valores são representados por 3 bits e o mapeamento é mostrado na tabela A1O. Tipo dej|valor (inteiro) — |Valor (binário) [descrição dados sea PT reter E ez Eras de seguras desse | Eb es rs TE des | Ea ereean ass : E esmas amadas E eram sed Tabela A10: formato físico: classe funcional de estrada

1.4.3.2 Forma de via (FOW) A forma de via (FOW) pode reter oito valores diferentes como descrito no formato lógico. Esses oito valores são representados por 3 bits e o mapeamento é mostrado na Ta- bela AI1. Tipo de|Valor (inteiro) |Valor (binário) — Idescrição dados Biraga PT se LL o Eb EAR —

POE pe —) Poe e E es Po ss Tabela 11A formato físico: forma de via ' 1.4.3.3 Posição (BEAR) A posição descreve o ângulo entre a Estrada e o Norte verdadeiro como descrito no ' formato lógico. O formato de dados físicos define 32 setores pelo que cada setor cobre

11.25º do círculo. Esses 32 setores são representados por 5 bits. A tabela A12 mostra o tipo de dados para o atributo de posição e a Tabela A13 mostra o mapeamento a partir dos seto- res para o valor concreto. [75605 dados TvRor [DSO bitField[5] 0-31 | Número do setor no qual o ângulo entre o Norte e a linha especi- ficada no formato de dados lógicos é localizada; o círculo inteiro é Tabela A12: formato físico: posição [) 000.00º <=x< 011.25º [16 180.00º <=x< 191.25º : « [es la poa Tosa ram sra Pes serr — Es Ses pr ser E sr oRaT) aa rasa) pass ssa) ss — ss [Eres saca)

168.75º <= x <31 [348.75º <= x <360.00º

ECA Tabela A13: formato físico: definição de valor de posição A equação E4 delineia o cálculo do valor de posição e a figura 20 provê uma visão geral gráfica dos setores.

. value = EA , 0º < angle < 360º

11.25º ] Equação E4: cálculo do valor de posição

1.4.3.4 Distância até o LRP seguinte (DNP) O atributo de DNP mede a distância entre dois LRPs consecutivos ao longo do tra- jeto de referência de localização como descrito no formato lógico.

O formato de dados físicos define uma representação de 8 bits e a Tabela A14 mostra o tipo de dados utilizado para DNP. Essa representação define 255 intervalos e em combinação com a regra 1 das regras de formato de dados (comprimento máximo entre dois LRPs consecutivos é limitado por 15000 m) cada intervalo terá um comprimento de 58,6 metros.

Tabela A14: formato físico: distância até o próximo ponto A Equação E5 mostra como os valores DNP podem ser calculados.

value = E . 58.6m Equação E5: cálculo do valor de DNP

1.4.3.5 FRC mais baixo até o próximo ponto (LFRCNP) O FRC mais baixo até o próximo ponto indica a classe funcional mais baixa de es- trada utilizada no trajeto de referência de localização até o próximo LRP. Essa informação poderia ser utilizada para limitar o número de classes de estrada que necessitam ser varri- dasdurante a decodificação. Vide a Tabela A15 para uma definição do tipo de dados.

Tabela A15: formato físico: FRC mais baixo até o próximo ponto

1.4.4 Cabeçalho de referência de localização O cabeçalho de referência de localização contém informações gerais sobre a refe- rência.

1.4.4.1 versão (VER)

A versão é utilizada para distinguir entre vários formatos físicos e dados para refe- rências de localização. O número de versão é representado por 3 bits e o tipo de dados é mostrado na Tabela A16. Tabela A16: formato físico: versão ' 5 1.4.4.2 Indicador de atributo (AF) O indicador de atribuo indica se há atributos apensos em cada LRP ou não. O valor : de AF é O se nenhum atributo for apenso e, portanto a referência de localização somente consiste em coordenadas. De outro modo um valor de 1 indica que atributos são apensos a cada LRP. O tipo de dados para o AF é mostrado nas Tabelas A17 e A18. booleano 0,1 Indicador, indicando se atributos são apensos ou não em cada Co pn TT Tabela A17: formato físico: indicador de atributo so Po [o ema Tabela A18: formato físico: valores de indicador de atributo

1.4,4.3 indicador de área (ArF) O indicador de área indica se a referência de localização descreve ou não uma : área. Se esse indicador for definido então a localização será conectada e será descrita uma área, como visto nas Tabelas A19 e A20 abaixo. OO presas Tra Tasso SS booleano 0,1 Indicador, indicando se a referência de localização des- Ca ea rss TT Tabela A18: formato físico: indicador de área

FR RR [o eERamE EEE Tabela A20: formato físico: valores de indicador de área

1.4.5 Deslocamentos Deslocamentos são utilizados para localizar o início e fina! de uma localização mais precisado que limite aos nós em uma rede. O formato lógico define dois deslocamentos, um no início da localização e um no final da localização e os dois deslocamentos operam ao longo das linhas da localização e são medidos em metros. Os valores de deslocamento não são obrigatórios e um valor de deslocamento ausente significa um deslocamento de O metro.

Deslocamentos são também somente válidos para localizações de linha que têm atributos incluídos.

1.4.5.1 indicadores de deslocamento Indicadores de deslocamento indicam se os dados incluem ou não uma informação de deslocamento específico. O formato de dados físicos lida com dois indicadores corres- pondendo a dois valores de deslocamento diferentes. O indicador de deslocamento positivo 7 (PoffF) e o indicador de deslocamento negativo (NoffF) são descritos nas Tabelas A21 e A22. OO esa TT Ts — booleano 0,1 Indicador, indicando se o valor de deslocamento corres- Tabela A21: formato físico: indicador de deslocamento Dados de referência de localização NÃO incluem as informações de [O fases "0 Dados de referência de localização incluem as informações de deslo- CO Qro TETO Tabela A22: formato físico: valores de indicador de deslocamento

1.4.5.2 Valores de deslocamento Os valores de deslocamento (positivo e negativo, POFF e NOFF) indicam a distân- cia entre o início (final) do trajeto de referência de localização e o início (final) “real” da loca- ' lização. O formato de dados físicos define uma representação de 8 bits para cada valor de ' deslocamento. A Tabela A23 mostra o tipo de dados utilizado para POFF e NOFF. Essa representação permite que se defina 256 intervalos com um comprimento de cada intervalo de 58,6 metros. O cálculo de número de intervalo para deslocamentos é delineado na equa- ção E6. BitField[S] 0-255 Intervalo de comprimento de deslocamento de O e arts TO Tabela A23: formato físico: deslocamento value = | 2

58.6m Equação E6: cálculo de valores de deslocamento

1.5 Especificação de formato de dados físicos Essa seção descreve a disposição dos campos de dados em um fluxo de bytes. É assumido que se tenha um fluxo orientado em byte e que possa utilizar 8 bits por byte.

1.5.1 Visão geral A estrutura principal do formato binário é: Cabeçalho, primeiro LRP, LRPs seguintes, último LRP, e deslocamentos O cabeçalho, o primeiro LRP e o último LRP são obrigatórios e o número de LRPs seguintes não é limitado.

O último LRP tem sua própria estrutura devido a um nível de in- formação diferente.

Deslocamentos são opcionais e a existência será indicada por indicado- ' res nos atributos do último LRP.

A tabela A244 fornece uma visão geral da estrutura principal.

O fluxo pode ser lido : da esquerda para a direita, de modo que o primeiro byte recebido será o byte de status.

Pa- racada coordenada o primeiro valor recebido será o valor de longitude seguido pelo valor de tatitude.

O cálculo de tamanhos de mensagem dependendo do número de LRPs pode ser encontrado na seção 1.6 abaixo

. 29 + - le e a

ENI ii | é oe ” Ss

E BE é :z Edo LL be Bo | ds) ão

EB LE E Ls) po ê 1 É 3 Ee] : EE Bo LE) ode: ã o Ee : ã EE Ê E ol be: E bh | hi) e s z 8 " F . E H H - 3 H E HÁ E kJ Es

1.5.2 byte de status O byte de status é transmitido uma vez para cada referência de localização e con- tém o indicador de área (ArF, seção 1.4.4.3), indicador de atributo (AF, seção 1.4.4.2) e a informação de versão (VER, seção 1.4.4.1). Os bits 7, 6 e 5 são reservados para uso futuro (RFU)eserão0O.A Tabela A25 fornece uma visão geral do uso de cada bit no byte de sta- tus. o PER RE RETA Utilizado | RFU RFU RFU ArF AF VER e Tabela A25: byte de status Nessa versão específica do formato, atributos são adicionados a cada LRP e áreas não são descritas. Se a “versão atual” for 2, o byte de status terá o valor mostrado na tabela AZ6:

EF EEE EE EE pr E Tabela A26: valor de byte de status

1.5.3 primeiras coordenadas de LRP As coordenadas do primeiro LRP são transmitidas em um formato absoluto (vide a seção 1.4.2.1) e, portanto cada valor (lon e lat) utilizará 3 bytes. A Tabela A27 mostra a or- demde bytes para valores de longitude e latitude. 2/2|2 1/1/1/1/1/1/1 119/19 7 3 — EEB E GERE TATA Usado | Byte mais elevado Byte médio Byte mais baixo ss E Tabela A27: primeiras coordenadas de LRP

1.5.4 Coordenadas de LRP seguintes As coordenadas dos LRP seguintes e o último LRP são transmitidas em um formato relativo (vide a seção 1.4.2.2) e, portanto cada valor (lon e lat) utilizará 2 bytes. A Tabela A2Z8mostraa ordem de bytes para os valores de longitude e latitude. e mr ETNIA PIO Tabela A28: coordenadas de LRPs seguintes

1.5.5 Atributos Atributos são adicionados a cada LRP. Há 4 tipos diferentes de atributos depen- dendo da posição de um LRP na referência de localização.

1.5.5.1 byte de primeiro atributo (atr. 1) O byte de primeiro atributo contém os atributos FRC (vide a seção 1.4.3.1) e FOW

(vide a seção 1.4.3.2) e dois bits são reservados para uso futuro. A tabela A29 mostra o uso de cada bit.

R PF Nm...

Tabela AZ9: byte de primeiro atributo — válido para todos os LRPs

1.5.5.2 byte de segundo atributo (atr. 2) ' 5 O byte de segundo atributo contém os atributos LERCNP (vide a seção 1.4.3.5) e . BEAR (vide a seção 1.4.3.3). a tabela A3SO mostra o uso de cada bit. Esse atributo não é válido para o último LRP uma vez que não há informação de LERCNP disponível.

a cr Tabela A3O: byte de segundo atributo — válido para todos os LRPs, exceto o último

LRP

1.5.5.3 (byte de terceiro atributo (atr. 3) O byte de terceiro atributo contém o atributo DNP (vide a seção 1.4.3.4) como mos- trado na Tabela A31. Esse atributo não é válido para o último LRP uma vez que não há in- formação de DNP disponível.

ee rr E Er) Usado para DNP Tabela A31: byte de terceiro atributo — válido para todos os LRP's, exceto o último 7 15 LRP

1.5.5.4 byte de quarto atributo (atr. 4) ' O atributo 4 contém as informações de BEAR, os indicadores de deslocamento po- sitivo e negativo (vide a seção 1.4.5.1) e um bit é reservado para uso futuro. Esse atributo é utilizado para o último LRP, como mostrado na tabela A32.

E TE E E EE Er) Usado | RFU NOffF BEAR o da as Tabela A32: bytes de quarto atributo — válido somente para o último LRP

1.5.6 deslocamento O deslocamento positivo (POFF) e deslocamento negativo (NOFF) são somente in- cluídos se os indicadores correspondentes no atributo 4 indicarem sua existência. Valores de deslocamento ausentes indicam um deslocamento de O metro. Os valores de desloca- —mentosão calculados de acordo com a seção 1.4.5, e o uso de bit para esses deslocamen- tos é mostrado nas tabelas A33, A34. EEN E ET)

Tabela A33: valor de deslocamento positivo TI 7 Tabela A34: valor de deslocamento negativo . 1.6 Cálculo de tamanho de mensagem O tamanho de mensagem de uma referência de localização depende do número de - 5 —LRPsincluídos na referência de localização.

Deve haver pelo menos dois LRPs na referên- cia de localização.

Também é obrigatório o cabeçalho com as informações de status.

O se- guinte cálculo e Tabela A35 mostram tamanhos de mensagem dependendo do número de LRPs. . Cabeçalho : Status de 1 byte Total: 1 byte . Primeiro LRP. 6 bytes COORD (3 bytes cada para lon / lat) Atributos de 3 bytes Total: 9 bytes . LRPs seguintes 4 bytes COORD (2 bytes cada para lon/lat) . Atributos de 3 bytes Total: 7 bytes v 20 . último LRP 4 bytes COORD (2 bytes cada para lon / lat) Atributos de 2 bytes Total: 6 bytes . deslocamento (se incluído) Deslocamento positivo de 1 byte (se incluído) Deslocamento negativo de 1 byte (se incluído) Total: 0 — 2 bytes No. de LRPs Tamanho de mensagem [LL faso EMESSTARE CT emeEa TazEStTAS —

[FT os TETE TSE STE — [E ua Tamen e To TAS THE [Epa ee a TRA STE — e : Tabela A35: tamanhos de mensagem dependendo do número de LRPs . Um exemplo específico do modo no qual os formatos acima são utilizados é forne- cido agora com referência a referência de localização descrita acima com referência às figu- ras 2, 3, 4€ 5 nas quais três pontos de referência de localização (nós 1, 10 e 15 e linhas 1- 3,10-11e14-15)são identificados como precisamente descrevendo uma localização. A referência de localização consiste em três pontos de referência de localização e a Tabela A36 abaixo mostra as coordenadas para os nós 1, 10 e 15. Esses nós são os nós correspondentes para os pontos de referência de localização. Na preparação do formato binário essa tabela também mostra as coordenadas relativas. O nó 1 corresponde ao ponto dereferência de localização 1 e terá coordenadas em formato absoluto. O nó 10 correspon- dendo ao ponto de referência de localização 2 terá coordenadas relativas para o ponto de referência de localização. O nó 15 correspondendo ao ponto de referência de localização 2 também terá coordenadas relativas, porém agora com referência ao ponto de referência de localização 2. ' ID de nó |Índice de LRP [longitude latitude Longitude relativa |Latitude relativa For e E — EE es es e rg eee ae a Tabela A36: coordenadas de exemplo As longitude e latitude relativas são calculadas de acordo com a equação E3 acima. Os deslocamentos sendo calculados na etapa 2 do processo de codificação são mostrados na Tabela A37. Nos dados binários somente o deslocamento positivo aparecerão porque o deslocamento negativo é O e um deslocamento ausente será tratado como O,

ESSE NR Tabela A37: valores de deslocamento de exemplo A tabela A38 abaixo coleta os dados relevantes para cada ponto de referência de localização a partir do mapa digital subjacente, e através de cálculo. Isso inclui a classe fun- cional de estrada, a forma de via e a posição da linha correspondente. As informações ne-

cessárias sobre o trajeto entre dois pontos de referência de localização subsequentes tam- bém são mostradas (classe de estrada funcional mais baixa e distância até o próximo ponto de referência de localização).

Índice de LRP FRC FOW BEAR LFRCNP |DNP FRC3 [MULTIPLE CARRIAGEWAY FRC3 . FRC3 [SINGLE CARRIAGEWAY FRC5 : Tabela A38: pontos de referência de localização determinados durante codificação Os atributos BEAR, LERCNP e DNP são determinados como descrito acima: As seguintes tabelas acima contêm todas as informações relevantes para criar os dados binários. As seguintes tabelas delineiam os dados binários de acordo com o Formato de dados físico: . byte de status: vide a tabela A39 10 . LRP 1: vide a tabela A40 até a tabela A44 - LRP 2: vide a tabela A45 até tabela A49 . LRP 3: vide a Tabela ASO até a Tabela A53 . deslocamento: vide a Tabela AS4 pr Ns a NB a o Te | [Desenção |RFU [RFO JREU [Am ARO vesão | i ee o o o o o Tabela A39: exemplo Binário: byte de status [SE Rs esto TTeeo — SS TE EEE ET E EE EEE E EEE FE) Dar [| 11) var o |o jo o [oji Jojo o 7 o|1 17 ol 1 fo lTjo[1 1191) Tabela A40: exemplo binário: LRP 1 — longitude absoluto [7EEEERITTEEER TER IS Te EEE EI E TE EEE er EEE) [sed re FT e e e ee Tabela A41: exemplo binário: LRP 1 — longitude absoluto [e BE E E | PB Er e | | deserção [REU [REG Rr row or [E | [ee o e) Tabela A42: exemplo binário: LRP1 — atributo 1

FT IT E E EEE EE E PTE E EEE

: 35 Tabela A43: exemplo binário: LRP1 — atributo 2

E E E E RP FR] O A reer o Tabela A44: exemplo binário: LRP1 — atributo 3 | 7185 [43 [2 [1 [o |7 615 14 [> |? [1 1º) . [eerjo [o jo jo jo lo [o fo [+ fo jo 17 [7 lo 7 11) Tabela A45: exemplo binário: LRP2 — longitude relativa 6 o O aggito O | 7 ss [a 3 2 [7 o 7 6 [5 14 19 12 [7 Jo ee jd ja jo o fo a e do Tabela A46: exemplo binário: LRP2 — latitude relativa Bro e so E Bo e je een a Tabela A47: exemplo binário: LRP2 — atributo 1 er Rs a e Rr 1 e | ae o - Tabela A48: exemplo binário: LRP2 — atributo 2 e sa Bo a je o RR] OO Deer do Jo oo o e e Tabela A49: exemplo binário: LRP2 — atributo 3 7 ss [4] 12 [1 [o 76 |5s fa 15 (2 [1 10) per nr ja ja a | 1 jo 11 jo 11 11) Tabela ASO: exemplo binário: LRP3 — longitude relativa | 7815 [a [3/2 [1 o |7 16 [5 [4 [o |? |[' jo) eo a dj ja fd jo 11 le Jo jo |1 [1 Tabela A51: exemplo binário: LRP3 — latitude relativa fem es a ao Rr 1 e Leer Tabela A52: exemplo binário: LRP3 — atributo 1

' 36 .

ETF EFE E EE RE [a Ro Tm e ss —

FTP IR ET Tabela A53: exemplo binário: LRP3 — atributo 4

BR TE E EE EXT O RR e . Tabela A54: exemplo binário; deslocamento positivo O fluxo de dados binários total! terá um comprimento de 24 bytes e consiste no que se segue (ordenado como bytes da esquerda para a direita e de cima para baixo): 00001010 00000100 01011011 01011011 00100011 01000110 11110100 00011010 01101100 00001001 00000000 10011011 11111110 00111011 00011011 10110100 00000100 11111111 11101011 11111111 10100011 00101011 01011001 00000010

Claims (4)

REIVINDICAÇÕES

1. Método de resolver uma localização a partir de uma lista ordenada de pontos de referência de localização sendo representativos de nós em um mapa digital de codificador e cada tendo atributos representativos de uma linha específica ou segmento no mapa digital de codificador que emana a partir de ou incide naqueles nós, CARACTERIZADO pelo fato de que compreende as etapas de: 7 i) para cada ponto de referência de localização, identificar pelo menos um nó candi- Ú dato que existe em um segundo mapa digital, utilizando os atributos disponíveis daquele ' ponto de referência de localização, identificando pelo menos uma linha ou segmento candi- datoque existe no segundo mapa digital que emana a partir de ou incide no nó candidato, ji) executar uma busca de rota no segundo mapa digital entre: pelo menos um de pelo menos um nó candidato e linha ou segmento candidato cor- respondente que emana a partir do mesmo ou incide ao mesmo, e pelo menos um de um nó candidato para o próximo ponto de referência de localiza- ção que aparece na lista e linha ou segmento correspondente que emana a partir do mesmo ou incide ao mesmo, e extrair do segundo mapa digital cada linha ou segmento que faz parte da rota as- sim determinada entre os nós candidatos, iii) repetir a etapa (ii) para cada par consecutivo de pontos de referência de locali- zação até e incluindo o ponto de referência de localização final que aparece na lista.

2. Método, de acordo com a reivindicação 1, CARACTERIZADO pelo fato de que a 7 busca de rota é uma busca de rota de trajeto mais curto.

3. Método, de acordo com a reivindicação 1 ou 2, CARACTERIZADO pelo fato de ' que a busca de rota opera em pares respectivos de nós candidatos sucessivos.

4, Método, de acordo com qualquer uma das reivindicações 1 a 3, CARACTERIZADO pelo fato de que a busca de rota inclui um meio de assegurar que a li- nha ou segmento correspondente do primeiro do par de nós faz parte da rota resultante a partir daí.

5. Método, de acordo com qualquer uma das reivindicações | a 4, - 30 “CARACTERIZADO pelo fato de que nós candidatos identificados são nós reais em que são representativos de interseções de mundo real.

6. Método, de acordo com qualquer uma das reivindicações 1 a 5, CARACTERIZADO pelo fato de que a etapa de extrair cada linha ou segmento do segundo mapa digital é aprimorada pela armazenagem de cada linha ou segmento extraídos em uma listadetrajeto de localização.

7. Método, de acordo com a reivindicação 6, CARACTERIZADO pelo fato de que cada lista de trajeto de localização criada para cada busca de rota sucessiva é concatenada.

: 2 .

8. Método, de acordo com a reivindicação 6, CARACTERIZADO pelo fato de que as linhas ou os segmentos extraídos durante uma busca de rota seguinte são apensas a uma lista de trajeto de localização preexistente.

9. Método, de acordo com qualquer uma das reivindicações | a 8, CARACTERIZADO pelo fato de que inclui a etapa adicional de classificação dos nós candi- datos identificados de acordo com uma ou mais métricas determinadas no caso onde mais 1 de um nó candidato é identificado para um ponto de referência de localização.

10. Método, de acordo com qualquer uma das reivindicações 1 a 9, ' CARACTERIZADO pelo fato de que inclui a etapa adicional de linhas ou segmentos candi- datos para identificar uma linha ou segmento candidato mais provável de acordo com uma ou mais métricas determinadas no caso onde mais de uma linha ou segmento candidato existente no segundo mapa digital é identificado.

11. Método, de acordo com qualquer uma das reivindicações 9 ou 10, CARACTERIZADO pelo fato de que a etapa de classificação é obtida utilizando uma função declassificação.

12. Método, de acordo com a reivindicação 11, CARACTERIZADO pelo fato de que a função de classificação inclui uma parte de classificação de nó candidato e uma parte de classificação de segmento ou linha candidato.

13. Método, de acordo com a reivindicação 12, CARACTERIZADO pelo fato de que apartede classificação de nó candidato da função de classificação inclui alguma dependên- cia em uma distância calculada ou representativa entre o ponto de referência de localização : ou suas coordenadas absolutas, e os nós candidatos ou suas coordenadas absolutas como aparecem em e extraídas do segundo mapa digital. ' 14. Método, de acordo com a reivindicação 12, CARACTERIZADO pelo fato de que apartede classificação de segmento ou linha da função de classificação inclui um meio de avaliar a similaridade dos atributos de linha ou segmento como aparecem no mapa digital de codificador e aqueles que aparecem no segundo mapa digital utilizado na resolução da loca- lização.

15. Método de acordo com qualquer uma das reivindicações 1 a 14, CARACTERIZADO pelo fato de que o método inclui as etapas adicionais de: -determinar a partir do segundo mapa digital, um valor de comprimento de trajeto para cada trajeto entre nós candidatos sucessivos no segundo mapa digital, o trajeto sendo estabelecido como um resultado da busca de rota entre os nós candidatos sucessivos, - comparar o valor de comprimento de trajeto assim determinado com um atributo de DNP do primeiro dos dois pontos de referência de localização utilizados na busca de ro- ta e - no evento de uma discrepância muito grande entre o valor de comprimento de tra-

: 3 + jeto e o atributo de DNP, repetir a busca de rota utilizando nós candidatos alternativos e/ou linhas para um ou ambos de cada par sucessivo de pontos de referência de localização para tentar reduzir a discrepância entre valor de comprimento de trajeto e atributo de DNP, ou relatar um erro. -

16. Método, de acordo com qualquer uma das reivindicações | a 15, CARACTERIZADO pelo fato de que o método inclui a etapa de aplicar qualquer valor de í deslocamento que possa ser associado com os primeiro e segundo pontos de referência de 7 localização às primeira e última linhas extraídas do segundo mapa digital como resultado da ' busca de rota no mesmo.

17. Elemento de programa de computador CARACTERIZADO pelo fato de que compreende meio de código de programa de computador para fazer com que um computa- dor execute o método como definido em qualquer uma das reivindicações 1 a 16.

18. Elemento de programa de computador, de acordo com a reivindicação 17, CARACTERIZADO por ser incorporado em meio legível por computador.

19. Dispositivo de computador CARACTERIZADO por incluir um processador, uma armazenagem na qual um elemento de programa de computador como definido na reivindi- cação 17 ou 18 pode residir e que juntos fornecem um ambiente de execução para aquele programa, um recurso de programa sendo um mapa digital que pode ser armazenado em armazenagem igual ou diferente, e um meio de saída de informação.

20. Dispositivo de computação, de acordo com a reivindicação 19, CARACTERIZADO pelo fato de que o meio de saída de informação provê pelo menos um Í de uma saída audível, uma saída impressa ou uma saída visível em uma tela de display capaz de exibir uma representação gráfica do mapa digital. ' 21. Dispositivo de computação, de acordo com a reivindicação 20, CARACTERIZADO pelo fato de que uma localização resolvida ou uma porção da mesma é exibida em sobreposição, coberta, justaposta ou em combinação com a porção relevante do mapa digital ao qual se refere.

- 1 | decodificar áado: Hados binário álidos? 104 108 102 converter coor- | |resolver informal | extrair valores Henadas relativad ções de intervalqd de desloca- em coordenadas| | em limites supe- mento absolutas rior e inferior 106 Ns... tio fornecer lista indexada de pon- 112 tos de referência de localização & atributos 138 114 Bric 120 processar liminar nós ar LRPs & atri- " mapa digital Ko KA) candidatos : butos remotos 116 inha candidata | 134 encontrada para fala atar cada LRP? Pt 12 128 listas de nós função de &linhas candida- 126 Classificação => tos existentes em 144 mapa digital 132 algoritmo de lista de nós & 130 trajeto mais linhas candidatos curto mais adequados 11 142

136. eómprimento We lista ordenada de oncatenar & rajeto = atributg linhas em mapa cortar desloca-) < DNP? digital mento. Outro candidato não selecionado e 100%” Fig. 1

- 2 ( 2,2,145 3,2,150 o Y ú GS) 0,1,205 3,2,175 NS)

V & Q 0,1,200 2,2,96 2,3,50 Sé Y (E R (8) i 8,7,99 0,1,144 V MW, 2,2,210 & KT 8,7,86 3,3,73 Y A 0,1,56

AD A V 5,3,75 (2 a 3,3,83 5,3,101 À 15 Ga 5,3,25

OB Fig. 2

- 3

D 2,2,145 3,2,150

F SS R o 0,1,205 3,2,175 a À (5) 0,1,200 2,2,96 2,3,50 SÉ (6)< R (8) : 8,7,99 0,1,144 Mv A; 2,2,210 € o 8786 — 3373 A 0,1,56

AD A V 5,3,75, E SA, 3,3,83 (3 5,3,101 A Fá ás 5,3,25

OB Fig. 3

. 4 oO 2,2,145 3,2,150

GS D (3) 0,1,205 3,2,175 a R (5) 0,1,200 2,2,96 2,3,50 SP SA V E R (8) | 8,7,99 0,1,144 V A, 2,2,210 O (7 8,7,86 33,73 * A 0,1,56 Av AV 5,3,75 (2 a 3,3,83 53107, 4 a 5,3,25

OB Fig. 4

: s

RR 3,2,150

É % G E< SW x (8) Í ) Í W V ' 2 a "E 5,3,25

OB Fig.5

- 6 x(D) 2,2,145 2,2,150 kk S) x(D G) R 2,2,172 0,1,205 SN x(3) x(a) R 2,2,99 0,1,200 NL /5 NJ 2,3,50 Ps : 8,7,98 x(5) MW, 2,2,208 do Te 8,7,86

A AD 6,3,45 WV 4,3,75 S 2) & 8, xa? x 4 3,3,84 14,3,75 5,3,105 À PP? XÚ4) 5,3,24 XGB) Sao Fig. 6

. 7 x(1) 2,2,145 2,2,150 7 SN) x(2) (3) R 2,2,172 0,1,205 | x(s) x(4) R 2,2,99 0,1,200 2,350 SÉ YV | X(6)< (7) (8) f. | 8,7,98 x() W 2,2,208 (10 Ts 8,7,86 Vá AD 6,3,45 WY 4,3,75 S 2) & 53, x? x ) 33,84 [4,3,75 5,3,105

À PP XU4 5,3,24 XÓ3) é 3 ás Fig. 7

- 8 x(1) 2,2,145 2,2,150 x (GS) R 2,2,172 0,1,205 S) x (5) xa) R 2,2,99 0,1,200 NS. / Ni 2,3,50 . (6)< (7) (8) ss : 8,7,98 x(5) MW 2,2,208

O Te 8,7,86

A AD 6,3,4 AV 4,3,75 S 2 & 8, xúG7 x D 3,3,84 4,3,75 5,3,105

A XU4 5,3,24 RÓB) É Odo Fig. 8

- 9 Xx(1) 2,2,145 2,2,150

DP À x(D) G) R 2,2,172 0,1,205 S) x(5) x(4 R 2,2,99 0,1,200 2,3,50 SÉ NV | x(6)< (7) (8) Ms i 8,7,98 x) NW ; 2,2,208 (19 Vs 8,7,86 (S AD 63,4 WY 4,3,75 S 2) e 8, x? x ) 3,3,84 14,3,75 5,3,105 À a

XI 5,3,24 313) X

SEXTA Fig. 9

+ 10 Xx(1) 2,2,145 2,2,150

P A x) (3) R 2,2,172 0,1,205

M RS x(4) SS R 2,2,99 0,1,200 2,3,50 SÉ YV À X(6) < (7) (8) Tm 8,7,98 N/ 2,2,208

SN Xx(9) TA & 8,7,86

A AD 6,3,4 WVY 1,3,75 S 2) 4 3, x? x ) 3,3,84 4,3,75 5,3,105 A j? XU4

À V 5,3,24 313) 69 Fig. 10

. 111 x() 2,2,145 2,2,150 lg Si x(D (3) R 2,2,172 0,1,205 M RS) Xx(4) S R 2,2,99 0,1,200 2,3,50 SP NV : X(6)< (7) (8) Te 8,7,98 x(5) A, 2,2,208 (O Ts 8,7,86 fS AD 63,45, WV 14,3,75 S po 4 8, xG7? x 3,3,84 14,3,75 5,3,105 SN j? XU4 a V 5,3,24 IB

X O GO Fig. 11

: 12 ee — A1 B1 c1 Conexão de LRPS Fig. 12 - B | | |

Í B2 A2 Formato lógico: ponto de posição Fig. 13

N w< |: : Í B3 S : Formato lógico: posição Fig. 14 e A4 B4 c4 Formato lógico: distância até ponto seguinte Fig. 15

- 18 *PorFF noFP Formato lógico: deslocamento positivo e negativo Fig. 16 — |FRC B5,"FOW

BEAR FRC e —- | FOW 4 . AS5 BEAR ; FRC FRC ] é W FOW FOW |

BEAR BEAR Relação : atributos — LRP Fig. 17 para evitar Evitar nós (1) Fig. 18 para evitar O—6o— o evitar nós (2) Fig. 19

Qd”