KR20160132075A

KR20160132075A - 전자 지도 데이터를 이용한 경로들 재구축

Info

Publication number: KR20160132075A
Application number: KR1020167028024A
Authority: KR
Inventors: 에브헤네이 하브릴로브
Original assignee: 톰톰 네비게이션 비.브이.
Priority date: 2014-03-07
Filing date: 2015-03-06
Publication date: 2016-11-16
Anticipated expiration: 2035-03-06
Also published as: JP6616778B2; EP3114433A2; JP2017509021A; GB201404040D0; US10731990B2; CN106537091A; KR102369560B1; CN106537091B; US20170016730A1; WO2015132407A2; EP3114433B1; WO2015132407A3

Abstract

내비게이션 디바이스는 운행 가능한 네트워크를 통한 원하는 경로의 원점 및 목적지를 나타내는 데이터를 서버로 전송한다. 상기 서버는 추천 경로를 생성하고 그리고 상기 경로를 나타내는 데이터를 상기 경로를 표현하는 폴리라인을 제공하는 시스템으로 제공한다. 상기 폴리라인은 상기 내비게이션 디바이스에게 제공되며, 그 내비게이션 디바이스는 상기 경로를 재구축하기 위해서 상기 폴리라인 데이터를 이용한다. 상기 내비게이션 디바이스는 자신이 소유한 전자 지도 데이터에 관련하여 상기 경로를 재구축하기 위해서 상기 폴리라인 데이터를 이용하여 상기 네트워크를 통한 최저 비용 경로를 결정한다. 이것은 세그먼트들의 상기 폴리라인으로부터의 거리에 종속하여 그 세그먼트들에 벌점을 부여하며 수행되며, 그래서 상기 폴리라인으로부터 더 멀리에 있는 세그먼트들이 상기 경로 내에 덜 포함될 수 있도록 한다.

Description

전자 지도 데이터를 이용한 경로들 재구축 {RECONSTRUCTING ROUTES USING ELECTRONIC MAP DATA}

본 발명은 운행 가능한 (navigable) 네트워크를 표현하는 전자 지도에 관련하여 상기 운행 가능한 네트워크를 통한 경로를 생성하기 위한 방법들 및 시스템들에 관한 것이며, 그리고 그런 경로들을 생성하도록 구성된 내비게이션 디바이스로도 또한 확장된다. 본 발명은 상기 전자 지도에 관련하여 상기 운행 가능한 네트워크를 통한 경로를 재구축하기 위해서 발생하는 경로의 생성에 적용 가능하다. 본 발명의 예시적인 실시예들은 휴대용 내비게이션 디바이스들 (소위 말하는, PND들)에 관련되며, 특히 글로벌 포지셔닝 시스템 (GPS) 신호 수신 및 프로세싱 기능성을 포함한 PND들에 관련된다. 다른 실시예들은 경로 계획 기능성, 그리고 바람직하게는 또한 내비게이션 기능성을 제공하기 위해 내비게이션 소프트웨어를 실행하도록 구성된 임의 유형의 프로세싱 디바이스에 더욱 일반적으로 관련된다.

GPS (Global Positioning System) 신호 수신 및 프로세싱 기능성을 포함하는 휴대용 내비게이션 디바이스들 (PND들)은 잘 알려져 있으며, 그리고 차량-내 또는 다른 차량 내비게이션 시스템으로 널리 사용된다.

일상적인 말로, 현대의 PND는 프로세서, 메모리 (휘발성 및 비-휘발성 중 적어도 하나, 그리고 보통은 둘 모두), 그리고 상기 메모리 내 저장된 지도 데이터를 포함한다. 상기 프로세서와 메모리는 협업하여 실행 환경을 제공하며, 그 실행 환경에서 운영 시스템이 설립될 수 있을 것이며, 그리고 추가적으로는 제어될 상기 PND의 기능성을 가능하게 하고, 그리고 다양한 다른 기능들을 제공하기 위해 하나 또는 그 이상의 추가적인 소프트웨어 프로그램들이 제공되는 것은 일상적인 것이다.

전형적으로 이 디바이스들은 사용자가 상기 디바이스와 상호 작용하게 하고 그 디바이스를 제어하게 하도록 하는 하나 또는 그 이상의 입력 인터페이스들, 그리고 정보가 상기 사용자에게 중계될 수 있도록 하는 하나 또는 그 이상의 출력 인터페이스들을 더 포함한다. 출력 인터페이스들의 예시적인 예들은 시각적인 디스플레이 그리고 청각적인 출력을 위한 스피커를 포함한다. 입력 인터페이스들의 예시적인 예들은 상기 디바이스의 온/오프 동작 또는 다른 특징들을 제어하기 위한 하나 또는 그 이상의 물리적인 버튼들 (이 버튼들은 반드시 상기 디바이스 상에 존재할 필요는 없으며 그 디바이스가 차량 내에 설치된다면 운전대 상에 존재할 수 있을 것이다), 그리고 사용자가 말하는 것을 탐지하기 위한 마이크로폰을 포함한다. 특히 상기 출력 인터페이스 디스플레이의 바람직한 설비는 사용자가 터치에 의해 디바이스를 동작시킬 수 있는 입력 인터페이스를 추가적으로 제공하기 위해 (터치 감지 오버레이 또는 다른 것에 의한) 터치 감지 디스플레이로서 구성될 수 있을 것이다.

이런 유형의 디바이스들은 하나 또는 그 이상의 물리적인 커넥터 인터페이스들을 또한 종종 포함할 것이며, 이 물리적인 커넥터 인터페이스에 의해 전력, 그리고 옵션으로는 데이터 신호들이 상기 디바이스로 전송되고 상기 디바이스로부터 수신될 수 있으며, 그리고 옵션으로는 셀룰러 원거리 통신 그리고 다른 신호 및 데이터 네트워크들, 예를 들면, Wi-Fi, Wi-Max, GSM 등을 통한 통신을 허용하기 위해 하나 또는 그 이상의 무선 전송기/수신기들을 포함한다.

이런 유형의 PND 디바이스들은 GPS 안테나를 또한 포함하며, 그 GPS 안테나에 의해, 상기 디바이스의 현재 로케이션을 판별하기 위해서 로케이션 데이터를 포함하는 위성-브로드캐스트 신호들이 수신되어, 이어서 프로세싱될 수 있다.

상기 PND 디바이스는 전자 자이로스코프들 및 가속도계들을 또한 포함할 수 있으며, 이것들은 상기 디바이스 그리고 그 디바이스가 설치된 차량의 현재 각 가속도 및 선형 가속도, 그리고 상기 GPS 신호로부터 유도된 로케이션 정보에 관련하여, 속도 및 상대적인 변위를 판별하기 위해 프로세싱될 수 있는 신호들을 산출한다. 전형적으로 그런 특징들은 차량-내 내비게이션 시스템들 내에 대부분 일반적으로 제공되지만, 편리한 경우에는, PND 디바이스들 내에 또한 제공될 수 있을 것이다.

그런 PND들의 유용함은 제1 로케이션 (보통은 시작점 또는 현재 로케이션) 및 제2 로케이션 (보통은 목적지) 사이의 경로를 결정하기 위한 그 PND들의 능력에서 주로 명백해진다. 이 로케이션들은, 예를 들면, 우편번호, 거리 이름 및 집 번호, (유명한 곳들과 같은) 이전에 저장된 "잘 알려진" 목적지, (운동장 또는 수영장 또는 다른 관심 포인트들과 같은) 국지적인 로케이션들, 그리고 선호하거나 최근에 방문했던 목적지들에 의한 아주 다양한 상이한 방법들에 의해 상기 디바이스의 사용자에 의해 입력될 수 있다.

보통은, 상기 PND는 상기 지도 데이터로부터 시작 및 목적지 주소 로케이션들 사이의 "최선" 또는 "최적" 경로를 계산하기 위한 소프트웨어에 의해 기능이 주어진다. "최선" 또는 "최적" 경로는 미리 정해진 기준을 기초로 하여 정해지며 그리고 반드시 가장 빠른 또는 가장 최단의 경로일 필요는 없다. 운전자를 안내하는 경로를 선택하는 것은 매우 복잡할 수 있으며, 그리고 그 선택된 경로는 이력적인, 현존하는 그리고/또는 예측된 트래픽 정보 및 도로 정보를 고려할 수 있을 것이다.

추가로, 상기 디바이스는 도로 및 트래픽 상태들을 계속해서 모니터할 수 있을 것이며, 그리고 변경된 상태들로 인해서 나머지 여정이 가야할 경로를 바꿀 것을 제안하거나 선택할 수 있을 것이다. 트래픽 지연들을 식별하기 위해 그리고 그 정보를 통지 시스템들로 공급하기 위해 다양한 기술들 (예를 들면, 모바일 전화 데이터 교환들, 고정 카메라들, GPS 플릿 트래킹 (fleet tracking))에 기초한 실시간 트래픽 모니터링이 사용되고 있다.

이런 유형의 PND들은 차량의 대시보드 또는 앞유리 상에 설치되는 것이 보통일 것이지만, 또한 차량의 온-보드 컴퓨터의 일부로서 또한 형성될 수 있을 것이며 또는 실제로 차량 그 자체의 제어 시스템의 일부로서 형성될 수 있을 것이다. 상기 내비게이션 디바이스는 또한 PDA (Portable Digital Assistant), 미디어 플레이어, 모바일 폰 등과 같은 핸드-헬드 시스템의 일부일 수 있으며, 그리고 이런 경우들에서, 상기 핸드-헬드 시스템의 보통의 기능성은 경로 계산 그리고 계산된 경로를 따른 내비게이션 둘 모두를 수행하기 위해 그 디바이스 상에 소프트웨어를 설치한 것에 의해 확장된다.

적절한 소프트웨어를 동작시키는 데스크탑 또는 모바일 컴퓨팅 리소스에 의해 경로 계획 및 내비게이션 기능성이 또한 제공될 수 있을 것이다. 예를 들면, 온-라인 경로 계획 및 내비게이션 설비는 routes.tomtom.com에서 제공되며, 이 설비는 사용자가 시작 포인트 및 목적지를 입력하는 것을 허용하며, 그러면 상기 사용자의 PC가 연결된 서버는 경로를 계산하며, 지도를 생성하고, 그리고 상기 선택된 시작 포인트로부터 상기 선택된 목적지까지 상기 사용자를 안내하기 위한 총망라된 내비게이션 지시들의 세트를 생성한다. 상기 설비는 계산된 경로의 의사 3차원 렌더링 그리고 사용자가 상기 경로를 따라 이동하는 것을 시뮬레이션하며 그리고 그럼으로써 그 사용자에게 상기 계산된 경로의 미리보기를 제공하는 경로 미리 보기 기능성을 또한 제공한다.

PND의 환경에서, 일단 경로가 계산되면, 사용자는 내비게이션 디바이스와 상호작용하여 상기 소망된 계산된 경로를 선택하며, 옵션으로는 제안된 경로들의 목록으로부터 선택한다. 옵션으로, 상기 사용자는, 예를 들면, 특정 경로들, 도로들, 로케이션들 또는 기준들이 회피되어야 한다거나 또는 특별한 여정을 위해 필수적이라는 것을 지정함으로써 상기 경로 선택 프로세스에 개입하거나 또는 안내할 수 있을 것이다. PND의 경로 계산 모습은 한가지 주요한 기능을 형성하며, 그리고 그런 경로를 따르는 내비게이션은 다른 주요한 기능이다.

계산된 경로를 따른 내비게이션 동안에, 그런 PND들이 그 경로의 끝, 즉, 소망된 목적지까지의 선택된 경로를 따라서 그 사용자를 안내하기 위해 시각적인 그리고/또는 청각적인 지시들을 제공하는 것은 일상적인 것이다. PND들이 그 내비게이션 동안에 디스플레이 정보를 스크린 상에 디스플레이하는 것 또한 일상적인 것이며, 그런 정보는 스크린 상에 정기적으로 업데이트되어, 디스플레이된 지도 정보가 상기 디바이스의 현재 로케이션을 표현하도록 하며, 그래서 그 디바이스가 차량-내 내비게이션을 위해 사용되고 있다면 그 사용자 또는 사용자의 차량의 현재 로케이션을 표현하도록 한다.

스크린 상에 디스플레이된 아이콘은 현재 디바이스 로케이션을 보통 표시하며, 그리고 현재 도로의 지도 정보와 함께 중심에 위치하며 그리고 현재 디바이스 로케이션 근방의 주변 도로 및 다른 지도 특징들이 또한 디스플레이된다.

추가적으로, 내비게이션 정보가 디스플레이되며, 옵션으로는 디스플레이된 지도 정보의 위에, 아래에 또는 한 측면에 있는 상태 바 내에 디스플레이될 수 있으며, 내비게이션 정보의 예들은 사용자에 의해 취해질 것이 요청되는 현재 도로로부터 다음 이탈점까지의 거리, 특별한 유형, 예를 들면 좌회전 또는 우회전의 이탈점을 암시하는 추가의 아이콘에 의해 아마도 표현되는 그 이탈점의 속성을 포함한다. 상기 내비게이션 기능은 사용자가 상기 경로를 따라서 안내받을 수 있는 청각적인 지시들의 내용, 지속시간 및 타이밍을 또한 결정한다. 알 수 있듯이, "100m에서 좌회전"과 같은 간단한 지시들은 중대한 프로세싱 및 분석을 필요로 한다. 이전에 언급된 것처럼, 상기 디바이스와의 사용자 상호작용은 터치 스크린에 의한 것일 수 있으며, 또는 추가적으로 또는 대안으로 조향축에 설치된 원격 제어에 의한 것이거나, 음성 활성화에 의한 것이거나 또는 어떤 다른 적합한 방법에 의한 것일 수 있다.

상기 디바이스에 의해 제공된 추가의 중요한 기능은 다음과 같은 이벤트에서의 자동적인 경로 재-계산이다: 사용자가 내비게이션 동안에 이전에 계산된 경로로부터 벗어난다 (사고에 의해 또는 고의적으로 중 어느 하나); 실시간 트래픽 상태들로 인해 대안의 경로가 더 유리할 것이라고 지시받으며 그리고 상기 디바이스는 그런 상태들을 자동적으로 인식하는 것이 적절하게 가능해지며, 또는 어떤 이유로 인해 사용자가 능동적으로 상기 디바이스로 하여금 경로 재-계산을 수행하게 하도록 한다.

비록 상기 경로 계산 및 내비게이션 기능들이 PND들의 전체적인 활용에 근본적이지만, 그 디바이스를 순수하게 정보 디스플레이, 또는 "자유-운전"을 위해 사용하는 것이 가능하며, 그 경우 현재 디바이스 로케이션에 관련된 지도 정보만이 디스플레이되며, 그리고 그 경우 그 디바이스에 의해서는 어떤 경로도 계산되지 않으며 그리고 어떤 내비게이션도 현재 수행되지 않는다. 그런 동작 모드는 사용자가 이동하기를 바라는 경로를 이미 알고 있으며 그리고 내비게이션 보조를 필요로 하지 않을 때에 종종 적용 가능하다.

위에서 설명된 유형의 디바이스들은 사용자들이 한 위치로부터 다른 위치로 운행하는 것을 가능하게 하기 위한 신뢰할 수 있는 수단을 제공한다.

더 최근에, 내비게이션 디바이스가 독립적인 방식으로 경로를 독립적으로 생성하는 설비와 연관된 몇몇의 문제점들이 있을 수 있다는 것이 인식되었다. 종종 사용자들은 내비게이션 디바이스의 전자 지도 데이터를 정기적으로 업데이트하지 않으며, 이는 그 디바이스 의해 최적이 경로들이 생성되는 것을 방해할 수 있을 것이다. 더욱이, 그런 디바이스들의 저장 및 프로세싱 용량은 본래 제한되어 있으며, 이는 경로 생성 프로세스를 어렵게 할 수 있을 것이며, 그리고 생성된 경로에 관련하여 상기 디바이스가 제공할 수 있는 정보의 양을 제한할 수 있을 것이다. 예를 들면, 상기 디바이스는 오디오 거리 이름 프롬프트들과 같이, 상기 경로에 관련하여 그 사용자에게 흥미있을 수 있는 추가적인 핵심적이지 않은 정보를 제공할 수 없을 수 있다.

경로들을 생성하기 위한 하나의 대안의 접근 방식은 모든 전자 지도 데이터 및 경로 설정 (routing) 기능성이 클라이언트 내비게이션 디바이스들 대신에 서버에서 제공되도록 하는 것이다. 그러면 내비게이션 디바이스는 경로에 대한 요청을 서버에게 제출할 것이다. 상기 서버는 상기 디바이스 대신에 그 경로를 생성하며, 그리고 그 경로를, 몇몇의 경우들에서는, 상기 경로를 사용하기 위해서 상기 디바이스가 필요로 할 것인 상기 전자 지도 데이터와 함께 상기 디바이스에게 전송한다. 이것은 상기 경로 생성이 내비게이션에 의해 완전하게 수행되는 시스템들과 연관된 문제점들 중 몇몇을 극복할 수 있을 것이다. 예를 들면, 서버는 최신의 전자 지도 데이터에 대해 액세스를 할 수 있을 것이며, 그리고 더욱 복잡한 경로 설정 프로세스들을 수행하기 위한 프로세싱 및 저장 용량을 가질 것이다. 상기 서버는 더욱 상세한 경로 데이터를 상기 내비게이션 디바이스에게 제공하여, 상기 디바이스가 더욱 상세한 전자 지도 데이터 그 자체를 저장할 필요 없이 그런 데이터를 사용하는 것을 가능하게 한다. 그러나, 이 방식에서 경로 설정 기능성을 제공하기 위해 서버에게 전적으로 의존하는 것은 문제가 될 수 있다. 예를 들면, 내비게이션 디바이스가 상기 서버와의 통신을 설립할 수 없을 때에, 경로 생성은 가능하지 않을 것이다. 지도 데이터를 획득하기 위해서 상기 서버와 통신할 수 있는 내비게이션 디바이스에게 또한 의존하는 설비들에서 어려움들은 복합된다.

이런 특정 문제점들을 중점을 두어 다루기 위해서, 내비게이션 또는 서버 중 어느 하나에서 경로 생성을 전적으로 하도록 하는 것보다는, 경로 생성이 일부는 상기 내비게이션 디바이스에 의해서, 그리고 일부는 그 내비게이션 디바이스와 통신하는 서버에 의해 수행되도록 하는 것이 유리할 수 있다. 이런 유형의 시스템은 "하이브리드" 경로 설정 시스템으로 알려져 있다. 이 설비들에서, 서버 및 내비게이션 디바이스 둘 모두는 전자 지도 데이터에 대해 액세스한다. 내비게이션 디바이스는 원점, 현재 위치 또는 사용자 특정 위치의 여부, 그리고 소망된 경로를 위한 목적지에 관한 상세 내용들을 서버에게 제공하고, 그리고 상기 서버가 상기 원점과 목적지 사이의 경로를 생성할 것을 요청할 수 있다. 상기 서버는 그러면 자기 자신의 전자 지도 데이터에 관련하여 상기 경로를 생성할 수 있다. 상기 서버가 클라이언트 내비게이션 디바이스보다 더 큰 프로세싱 능력과 저장 용량을 가질 것이기 때문에, 그 서버는 더욱 복잡한 경로 설정 프로세스들을 사용할 수 있을 것이다. 또한, 상기 서버는 더욱 최신의 그리고 광범위한 전자 지도 데이터에 액세스할 수 있을 것이다. 상기 전자 지도 데이터는 독점적인 방식으로 커스텀화될 수 있을 것이다. 예를 들면, 서버는 차량 제조자의 차량들의 사용자들과 관련된 것으로 여겨지는 관심 데이터의 포인트를 통합한, 상기 차량 제조자로부터의 전자 지도 데이터를 이용하여 경로를 생성할 수 있을 것이다.

일단 경로가 생성되면, 상기 서버는 경로를 요청했던 클라이언트 내비게이션 디바이스에게 상기 경로를 전송한다. 그래서, 상기 경로 생성은 오프-보드 (off-board)로, 즉, 상기 내비게이션 디바이스의 외부에서 일어난다. 상기 클라이언트 내비게이션 디바이스가, 예를 들면, 내비게이션 지시들을 제공하고 그리고/또는 상기 경로를 디스플레이하기 위해서 상기 수신된 경로를 사용하기 이전에, 그 디바이스는 상기 수신된 경로를 자기 자신의 로컬 전자 지도 데이터와 관련하여 재구축하기 위한 동작을 수행해야 한다. 이것은 상기 수신된 경로가 상기 내비게이션 디바이스가 필요로 하는 포맷과 동일한 포맷이 아닐 수 있으며, 그리고 그 수신된 경로는 상기 내비게이션 디바이스가 보유한 것과 동일한 전자 지도 데이터에 관련하여 생성되지 않았을 것이 일반적이기 때문이다. 상기 생성된 경로와 연관된 로케이션들을 상기 디바이스의 로컬 전자 지도 내 로케이션들과 매칭하는 것이 필요하다. 예를 들면, 서버는 생성된 경로 정보를 통상적인 포맷으로 클라이언트에게 제공할 수 있으며, 그 생성된 경로 정보로부터 상기 개별 디바이스들은 그 후에 자기 자신의 특정 전자 지도 데이터와의 호환성을 위해 필요한 방식으로 경로들을 재구축할 수 있을 것이다.

그런 하이브리드 경로 설정 시스템들이 내비게이션 디바이스 또는 서버 중 어느 하나에서의 단독의 경로 생성과 연관된 이점들 중 몇몇은 유지할 수 있을 것이며, 그런 시스템들에서의 약점들 중 몇몇은 완화시킨다는 것을 알 수 있을 것이다. 하이브리드 경로 설정 시스템들의 예들은 "Intelligent Location Based Services and Navigation Hybrid System" 제목의 WO 2007/079042 A2 그리고 "Mobile Navigation System" 제목의 WO 00/40930 A1에서 설명된다.

하이브리드 경로 설정 시스템들을 구현함에 있어서 결부된 몇몇의 난제들이 존재한다. 하나의 특별한 문제는 클라이언트 내비게이션 디바이스에 의한 수신 경로들의 재구축과 관련된다. 이것을 하기 위해서, 상기 내비게이션 디바이스는 서버로부터 수신한 경로 내에 포함될 로케이션들을 나타내는 데이터를 자기 자신의 전자 지도 데이터에 의해 표현된 로케이션들과 상관 (correlate)시키는 것이 가능해야할 필요가 있다.

이것을 달성하기 위한 한 방식은 상기 서버가 상기 경로를 생성할 때에 상기 내비게이션 디바이스에 의해 사용된 로컬 전자 지도와 동일한 지도를 사용하는 것이다. 그러면 상기 내비게이션 디바이스는 상기 수신된 생성된 경로 정보로부터의 경로 내에 포함하는 것을 위해 특정된 운행 가능 세그먼트들을 간단하게 식별할 수 있을 것이며, 이는 상기 운행 가능 세그먼트들은 지도 데이터의 양 세트들 내에 동일한 식별자를 가질 것이기 때문이다. 그러나, 실제로는, 그런 설비들은 과도하게 제한한다.

내비게이션 디바이스에 의해 사용된 동일한 전자 지도에 관련하여 상기 경로를 생성할 것을 서버에게 요청하지 않으면서도 상기 내비게이션 디바이스가 그 서버로부터 수신한 경로를 재구축하는 것을 허용하기 위해 의도된 다양한 기술들이 제안되었다. 한 가지 그런 기술은 상기 서버가 생성된 경로를 중간지점들 (waypoints)의 목록의 모습으로 전송하는 것을 포함한다. 상기 내비게이션 디바이스는 그러면 상기 중간지점들을 자기 자신의 전자 지도에 의해 표현된 로케이션들과 상관시키며, 그리고 그 중간지점들을 통해 지나가는 경로를 구축한다. 그러나, 그런 방법들은 생성된 경로를 정확하게 기술하기 위해서 많은 개수의 중간지점들이 필요할 것이라는 점에서 비효율적일 수 있다. 또한, 수신된 중간지점들을 상기 내비게이션 디바이스의 로컬 전자 지도 내 로케이션들과 매칭하는 것에 많은 어려움들이 존재하며, 특히, 디바이스 지도 데이터가 상기 서버 지도 데이터보다 아주 더 낮은 품질 또는 해상도인 경우에 그렇다. 예를 들면, 상기 서버는 중간지점의 좌표들을 전송할 수 있을 것이다. 그러나, 이 좌표들은 상기 디바이스 지도에서 상기 서버 지도에서와는 상이한 위치에 상관될 수 있을 것이다.

서버 전자 지도와 디바이스 전자 지도 사이의 차이들로 인해 일어나는 문제점들을 피하려고 시도하는 한 방법은 지도 불가지론적 로케이션 참조 (map agnostic location reference)를 사용하는 것이다. 상기 서버는 자신의 전자 지도와 관련하여 경로를 생성하고, 그리고 그 경로 정보를, 예를 들면, 중간지점들을 내비게이션 디바이스로의 전송을 위한 지도 불가지론적 모습으로 변환할 수 있다. 이것은, 예를 들면, 중간지점들의 로케이션들을지도 불가지론적 로케이션 참조 시스템에 따라 인코딩함에 의해 수행될 수 있을 것이다. 상기 디바이스 지도는 상기 인코딩된 로케이션 정보를 수신하고, 그리고 원래에 인코딩도었던 상기 서버의 전자 지도에서의 로케이션에 대응하는 자기 자산의 전자 지도 내 로케이션을 획득하기 위해 그 정보를 디코딩한다. 그런 지도 불가지론적 시스템은 AGORA-C, OpenLRTM 및 TPEG-ULR을 포함한다. 이 기술들은 경로를 위도 및 경도의 좌표 쌍들에 의해 특정된 로케이션 포인트들의 세트로서 인코딩하는 것이 보통이다; 상기 로케이션 포인트들 각각에는 상이한 전자 지도 상의 라인 로케이션을 디코딩할 때에 로케이션을 더 양호하게 정의하는데 있어서 도울 수 있는 (보통은 상기 전자 지도 데이터로부터 유도된) 하나 또는 그 이상의 추가적인 속성들이 제공된다.

지도 매칭과의 어려움에 추가하여, 현존하는 하이브리드 경로 설정 시스템들과의 한 가지 추가의 약점은 상기 수신된 경로를 재구축할 때에, 상기 내비게이션 디바이스가 상기 서버에 의해 생성된 상기 경로를 재현하려고, 즉, 복제하려고 시도한다는 것이다. 예를 들면, 상기 디바이스에게 이용 가능한 라이브 데이터 (live data)가 상기 경로의 적어도 일부로의 대안이 바람직할 수 있다고 제안한다면, 상기 내비게이션 디바이스는 상기 경로를 수정하기 위해 위도를 가지지 않는다. 예를 들면, 상기 디바이스는 상기 경로의 일부가 혼잡에 의해 영향을 받는가는 것을 표시하는 라이브 트래픽 정보에 대해 엑세스할 수 있을 것이다.

본 출원인은 상기 네트워크를 표현하는 전자 지도에 관련하여 운행 가능한 네트워크를 통해 주어진 경로의, 예를 들면, 내비게이션 디바이스에 의한 재구축을 가능하게 하는 향상된 방법들 및 시스템들에 대한 필요성이 있다는 것을 인식했다. 서버로부터 내비게이션 디바이스에 의해 수신된 경로의 재구축을 가능하게 하는 하이브리드 경로 설정의 환경에서 특히 유리하지만, 본 발명의 방법들 및 시스템들은 단순한 이전에 계산된 경로의 재구축에서의 적응성보다 더 넓은 적응성을 가지며, 그리고 이전에 이동했던 경로의 재구축에서와 같이 경로를 재구축하는 것이 소망되는 경우인 환경에서 또한 사용될 수 있을 것이다.

본 발명의 첫 번째 모습에 따라서, 전자 지도에 의해 커버된 영역에서 운행 가능한 네트워크를 통해 경로를 재구축하는 방법이 제공되며, 상기 전자 지도는 상기 운행 가능한 네트워크의 운행 가능한 세그먼트들을 표현하는 복수의 세그먼트들을 포함하며, 상기 방법은:

상기 운행 가능 네트워크를 통한 경로를 표현하는 폴리라인을 나타내는 데이터를 획득하는 단계로, 상기 경로는 상기 전자 지도에 관련하여 재구축될 것인, 획득 단계; 그리고

상기 전자 지도에 의해 표현된 상기 운행 가능한 네트워크를 통해 경로를 생성하는데 있어서 상기 폴리라인을 표시하는 상기 획득된 데이터를 이용하는 단계를 포함하며, 상기 생성된 경로는 상기 전자 지도와 관련하여 상기 운행 가능 네트워크를 통해 상기 폴리라인에 의해 표현된 상기 경로의 재구축을 제공하며, 그리고 상기 경로를 생성하는 것은 상기 전자 지도 상에 표현된 상기 폴리라인에 아주 더 근접한 상기 생성된 경로 내에 포함되는 것을 위해서 상기 전자 지도의 세그먼트들을 선호하는 것을 포함한다.

본 발명에 따라서, 그러므로, 폴리라인을 나타내는 데이터가 획득되며, 이는 전자 지도에 의해 커버된 영역 내 운행 가능한 네트워크를 통한 경로를 표현한다. 상기 경로는 상기 전자 지도를 참조함으로써 재구축할 것이 소망되는 경로이다. 폴리라인을 나타내는 상기 데이터는 그러면 상기 전자 지도에 의해 표현된 상기 운행 가능 네트워크를 통한 경로를 생성하는데 있어서 사용되며, 이 생성된 경로는 상기 폴리라인에 의해 표현된 상기 경로의 소망된 재구축을 제공한다.

상기 전자 지도 상에 재구축될 상기 경로를 표현하는 폴리라인을 나타내는 데이터를 제공하고, 그리고 그 후에 상기 폴리라인 데이터를 이용하여 상기 전자 지도에 의해 표현된 상기 운행 가능 네트워크를 통한 경로를 생성함으로써 상기 경로를 재구축함으로써, 더욱 유연성있는 방식으로 경로가 재구축될 수 있으며, 경로 설정 프로세스에서 다른 소망된 팩터들이 고려되는 것을 가능하게 한다. 이것은 재구축될 상기 경로가 추천 경로인 경우에 특히 유용하다. 상기 재구축 경로를 제공하기 위한 상기 경로 생성은 어떤 통상적인 소명된 경로 생성 선호들에 따라서, 그리고 바람직하게는 상기 운행 가능 네트워크 내 라이브 상태들을 고려하여 수행될 수 있지만, 상기 폴리라인 데이터를 추가적으로 고려하는 방식으로는 수행되지 않는다. 상기 폴리라인 데이터는 상기 생성된 경로가 상기 폴리라인을 대체적으로 따르도록 하고, 상기 경로 생성 프로세스에 있어서 어떤 다른 제한들이나 선호들에 종속하기 쉽도록 하기 위해 사용될 수 있다. 그러나, 상기 경로 생성 프로세스는 전자 지도 상에서 표현된 상기 폴리라인을 재현할 것을 단순히 시도하도록 강제되지는 않는다. 예를 드련, 상기 전자 지도에서 표현된 상기 폴리라인의 일부에 대응할 수 있을 세그먼트가 폐쇄되거나, 또는 트래픽 혼잡에 의해 영향을 받는 경우에, 상기 경로 설정 프로세스는 폴리라인 데이터를 사용하지 않는 보통의 경로 생성 프로세스 동안처럼 이 세그먼트 주위에서 자유롭게 경로를 설정한다. 그래서, 상기 폴리라인 데이터는 경로 생성 동안에 보통 사용될 수 있을 다른 데이터, 예를 들면, 상기 재구축된 경로를 제공하기 위한 다른 비용 데이터에 추가하여 사용된다

상기 경로의 재구축은 상기 경로가 관련하여 구축될 동일한 전자 지도에 관련하여 재구축될 상기 경로를 나타내는 정보를 필요로 하지 않는 방식으로 또한 달성된다. 상기 폴리라인 데이터는 상기 폴리라인을 정확하게 재생성하는 경로를 산출하기 위해서가 아니라, 예를 들면, 재구축된 경로를 제공하는 프로세스를 안내하기 위해서 상기 경로 생성 프로세스 동안에 사용될 수 있으며, 그러므로 그것은, 상기 폴리라인이 상기 전자 지도의 세그먼트들과 정확하게 매치될 수 없거나 그리고/또는 상기 폴리라인을 산출하기 위해 사용된 전자 지도의 세그먼트들에 정확하게 대응하지 않는 세그먼트들에 매치된다면, 대단이 중요한 것은 아니다. 본 발명이 이전에 이동했던 경로를 재구축하는 것에 적용되는 실시예들에서, 상기 재구축된 경로가 원래의 경로에 가능한 같은 모양이 되는 것이 바람직할 때에, 상기 폴리라인을 사용하는 것은, 동일한 지도에 관련하여 상기 경로를 초기에 기록하는 것을 필요로 하지 않으면서도, 어떤 소망된 전자 지도에 관련하여 경로를 재구축하는 것을 용이하게 한다.

전자 지도에 관련하여 상기 경로를 재구축하는 것은, 예를 들면, 내비게이션 지시들을 발행하는 것, 경로를 디스플레이하는 것 등의 동작들이 상기 경로에 관련하여 수행될 것을 가능하게 할 것이다. 여기에서 상기 경로를 "재구축하는 것"을 언급하는 것은 (비록 몇몇의 상황들에서는, 예를 들면, 이전에 이동했던 경로가 재구축되는 경우에는 그렇다고 하더라도) 그 재구축된 경로가 재구축될 경로를 정확하게 재생성하도록 시도해야만 한다는 것을 필요로 하지 않는다는 것이 인정될 것이다. 대신에 상기 경로의 재구축은 재구축될 경로에 적어도 대체적으로 대응하는 폴리라인 데이터를 이용하여 상기 전자 지도 데이터에 관련하여 경로를 생성하는 프로세스를 언급한다. 그러나, 상기 재구축된 경로는 어떤 다른 소망되는 팩터들을, 예를 들면, 라이브 데이터 및/또는 선호들을 계획하는 것을 고려하고, 그리고, 적절하다면, 예를 들면, 트래픽 상태들, 도로 폐쇄 등으로 인해 재구축될 경로부터 벗어나기 위한 자유를 가지는 방식으로 생성될 수 있을 것이다.

본 발명의 모습들 또는 실시예들에서 본 발명의 방법의 단계들은 서버에 의해 일부가 수행되고 그리고 내비게이션 디바이스에 의해 일부가 수행될 수 있을 것이다. 상기 방법의 단계들은 서버 상에서 독점적으로 수행되거나, 또는 일부는 서버 상에서 그리고 다른 것들은 내비게이션 디바이스 상에서 임의 조합으로 수행되거나, 또는 내비게이션 디바이스 상에서 독점적으로 수행될 수 있을 것이다. 그래서, 아래에서 설명되는 본 발명의 추가의 모습들에서 본 발명의 시스템은 내비게이션 디바이스나 다른 모바일 디바이스에 의해 일부가 제공되며, 그리고 서버에 의해 일부가 제공될 수 있다.

본 발명의 경로를 재구축하는 방법은 내비게이션 동작의 환경에서 바람직하게 구현된다. 그래서, 상기 방법은 내비게이션 기능성을 구비한 디바이스나 시스템의 하나 또는 그 이상의 프로세서들의 세트에 의해 바람직하게 수행된다. 그러나, 상기 방법들은 경로 생성 기능을 구비하지만, 반드시 내비게이션 기능성을 가져야 하는 것은 아닌 어떤 적합한 시스템에 의해 또한 수행될 수 있을 것이라는 것이 인정될 것이다. 예를 들면, 상기 방법들은 내비게이션 기능성을 가지지 않은 컴퓨터 시스템, 예를 들면, 데스크탑 시스템 또는 랩탑 시스템에 의해 구현될 수 있을 것이다.

바람직한 실시예들에서, 상기 폴리라인 데이터를 획득하고 그리고 상기 폴리라인에 의해 표현된 상기 경로를 재구축하기 위해 경로 생성에 있어서 상기 데이터를 사용하는 단게들은 내비게이션 디바이스에 의해 수행되며, 그리고 본 발명은 본 발명의 실시예들이나 모습들 중 어느 하나에서의 방법의 그런 단계들을 수행하도록 구성된 내비게이션 디바이스로 확장된다. 상기 디바이스는 바람직하게는 모바일 디바이스이다. 상기 내비게이션 디바이스는 개인용 내비게이션 디바이스 (PND) 또는, 예를 들면, 차량 내 통합된 디바이스일 수 있다. 본 발명의 경로 재구축의 방법은 내비게이션 디바이스에 의해 구현될 때에 특히 유리하여, 상기 디바이스가 수신된 경로를 더욱 효율적인 방식으로 재구축하는 경로를 생성하는 것을 가능하게 하며, 그리고 상기 재구축된 경로를 위해 라이브 데이터를 고려하기 위한 기회를 제공한다. 그래서, 이 바람직한 실시예들에서, 본 발명은 수신된 경로를 하이브리드 경로 설정 시스템에서 재구축하기 위한 향상된 방법을 제공할 수 있어서, 내비게이션 디바이스로 하여금 상기 내비게이션 디바이스가 소유한 전자 지도 데이터에 관련하여, 예를 들면, 서버에 의해 외부에서 생성된 경로를 재구축하는 것을 가능하게 한다.

본 발명의 모습들 또는 실시예들 중 어느 하나에 따라서, 상기 내비게이션 디바이스는 상기 전자 지도를 사용자에게 디스플레이하기 위한 디스플레이, 상기 전자 지도 데이터에 액세스하도록 구성되며 그리고 상기 전자 지도가 디스플레이를 경유하여 사용자에게 디스플레이되도록 하는 하나 또는 그 이상의 프로세서들의 세트, 그리고 사용자가 상기 디바이스와 상호작용하는 것을 가능하게 하기 위해 사용자에 의해 동작가능한 사용자 인터페이스를 포함할 수 있다. 그래서, 본 발명의 상기 시스템은 시스템, 예를 들면, 내비게이션 디바이스의 프로세싱 디바이스일 수 있다.

본 발명은 여기에서 설명된 본 발명의 모습들이나 실시예들 중 어느 하나에 따른 방법을 수행하기 위해 시스템으로 확장된다.

본 발명의 두 번째 모습에 따라, 전자 지도에 의해 커버된 영역 내 운행 가능한 네트워크를 통한 경로를 재구축하기 위한 경로 설정 시스템이 제공되며, 상기 전자 지도는 상기 운행 가능한 네트워크의 운행 가능한 세그먼트들을 표현하는 복수의 세그먼트들을 포함하며, 상기 시스템은:

상기 운행 가능한 네트워크를 통한 경로를 표현하는 폴리라인을 나타내는 데이터를 획득하기 위한 수단으로, 그 경로는 상기 전자 지도에 관련하여 재구축될 것인, 수단; 그리고

상기 전자 지도에 의해 표현된 상기 운행 가능 네크워크를 통해 경로를 생성하는데 있어서 상기 폴리라인을 나타내는 상기 획득된 데이터를 이용하기 위한 수단을 포함하며, 상기 생성된 경로는 상기 전자 지도와 관련하여 상기 폴리라인에 의해 표현된 상기 경로의 재구축을 제공하며, 그리고 상기 경로를 생성하는 것은 상기 전자 지도 상에 표현된 상기 폴리라인에 아주 더 근접한 상기 생성된 경로 내에 포함되는 것을 위해서 상기 전자 지도의 세그먼트들을 선호하는 것을 포함한다.

바람직하게는 상기 시스템은, 폴리라인을 나타내는 데이터를 획득하기 위한 수단 그리고 경로를 생성하는데 있어서 상기 획득된 폴리라인 데이터를 사용하기 위한 수단을 제공하는 내비게이션 디바이스를 포함하거나, 또는 그 내비게이션 디바이스이다.

본 발명이 속한 기술 분야에서의 통상의 지식을 가진 자들이 인정할 것처럼, 본 발명의 이 추가의 모습은 적절하게, 본 발명의 다른 모습들 중 어느 하나에 관련하여 본원에서 설명된 본 발명의 바람직한 그리고 옵션의 특징들 중 어느 하나 또는 그 이상 또는 모두를 포함할 수 있고 그리고 바람직하게는 모두 포함한다. 명시적으로 선언되지 않았다면, 여기에서의 본 발명의 시스템은 본 발명의 모습들이나 실시예들 어느 하나에서 본 발명의 방법에 관련하여 설명된 어떤 단계를 수행하기 위한 수단을 포함할 수 있으며, 그 반대도 마찬가지이다.

본 발명은 컴퓨터로 구현된 발명이며, 그리고 본 발명의 모습들이나 실시예들 중 어느 하나에 관련하여 설명된 단계들 중 어느 것이라도 하나 또는 그 이상의프로세서들의 세트의 제어 하에서 수행될 수 있다. 상기 시스템에 관련하여 설명된 단계들 중 어느 하나를 수행하기 위한 수단은 하나 또는 그 이상의 프로세서들의 세트일 수 있다.

따라서, 본 발명의 경로 재구축 방법은, 또는 적어도 경로 생성에 있어서 상기 폴리라인 데이터를 획득하고 이용하는 단계들은 내비게이션 디바이스에 의해 수행되는 것이 바람직하며, 그리고 본 발명의 상기 경로를 재구축하기 위한 시스템은, 적어도 일부가 내비게이션 디바이스에 의해 바람직하게 제공받는다. 상기 내비게이션 디바이스는 상기 전자 지도 데이터를 액세스하는 디바이스이다. 상기 내비게이션 디바이스는 그러면 상기 폴리라인 데이터를 획득하고 그리고 경로를 생성하는데 있어서 상기 데이터를 이용하는 단계들을 수행하거나, 또는 수행하기 위한 수단을 포함한다. 상기 경로를 생성하는 단계는 상기 내비게이션 디바이스의 경로 설정 엔진에 의해 수행되는 것이 바람직하다. 내비게이션 디바이스가 사용되는 실시예들 중 어느 하나에서, 바람직하게는 상기 내비게이션 디바이스는 상기 전자 지도, 즉, 전자 지도 데이터를 저장한다. 상기 내비게이션 디바이스는 상기 전자 지도를 저장하기 위한 수단을 포함할 수 있다. 상기 저장되는 상기 전자 지도 데이터는 본 발명에 따라서 경로 재구축에서 사용하기 위해 수신되고 저장되었던 데이터일 수 있다. 예를 들면, 상기 디바이스는 경로 재구축에 사용하기 위해 상기 폴리라인 데이터를 적절한 전자 지도 데이터와 함께 서버로부터 수신할 수 있으며, 또는 서버로부터 상기 전자 지도 데이터가 인출될 수 있을 로케이션을 나타내는 데이터를, 옵션으로는 폴리라인 데이터와 함께 수신할 수 있으며, 이는 상기 디바이스가 그 데이터를 자신에게 전송할 것을 요청하는 것을 가능하게 하며, 그래서 상기 전자 지도 데이터가 상기 폴리라인 데이터와 분리하여 그리고 상기 폴리라인 데이터에 계속해서 수신되록 한다. 그래서, 상기 디바이스는 완전한 전자 지도를 저장하지 않을 수 있으며, 대신에, 자신이 본 발명의 방법들을 수행하는 것을 가능하게 하기 위해서, 예를 들면, 상기 디바이스의 현재 위치 그리고/또는 재구축될 경로에 기초하여 서버로부터 적절한 전자 지도 데이터를 수신할 수 있다.

본 발명에 따라, 재구축될 네트워크를 통한 경로를 표현하는 폴리라인 데이터가 획득된다. "폴리라인 (polyline)"의 용어는 여기에서는 그 용어의 전통적인 의미로 사용된다. 상기 폴리라인은 라인 세그먼트들에 의해 연결된 일련의 포인트들에 의해 정의된다. 상기 폴리라인을 나타내는 데이터는 상기 폴리라인을, 직접적으로 또는 간접적으로 관계없이, 어떤 방식으로라도 나타낼 수 있을 것이다. 예를 들면, 상기 폴리라인 데이터는, 상기 포인트들을 연결하는 라인 세그먼트들을 표시하는 데이터 및/또는 폴리라인을 정의하는 포인트들의 목록을 (예를 들면, 위도 및 경도 좌표들의 모습으로) 포함할 수 있다. 상기 포인트들은 20 미터 내지 100 미터 사이에서 떨어져서 이격될 수 있다; 이는 최적의 프로세싱 효율을 제공하기 위한 것이다. 여기에서 사용되는 "폴리라인"의 용어는 폐쇄된 폴리라인인 폴리라인의 가능성도 포함한다. 폐쇄된 폴리라인은 시작 포인트와 종료 포인트가 동일한 경우인 경로를 표현하기 위해 사용될 수 있다. 상기 폴리라인은 자신이 표현하는 경로를 위한 시작 로케이션 및 종료 로케이션을 나타낸다.

본 발명의 바람직한 실시예들에서, 상기 폴리라인 데이터는 포인트들의 시퀀스로, 예를 들면, 좌표 쌍들로 구성된다. 다른 실시예들에서, 상기 폴리라인 데이터는, 예를 들면, OpenLRTM, AGORA-C 및 TPEG-ULR와 같은 로케이션 참조 시스템을 이용하여 지도 불가지론적 (map agnostic) 방식으로 인코딩된 스트레치 (stretch)들의 시퀀스를 포함할 수 있다.

상기 폴리라인을 나타내는 데이터는 재구축될 경로를 표현한다. 재구축될 상기 경로는 상기 운행 가능한 네트워크를 통한 임의 통로일 수 있다. 상기 통로는 이동될 통로, 예를 들면, 추천 경로일 수 있으며, 또는 이전에 이동했던 통로일 수 있다. 여기에서 사용된 "경로 (route)"는, 예를 들면, 제1 로케이션과 제2 로케이션 사이의 미리-계획된 경로일 필요는 없다는 것이 인정될 것이다. 몇몇의 실시예들에서, 상기 경로는 상기 운행 가능한 네트워크를 통해 이전에 이동했던 통로이다. 대안으로 상기 경로는 예측된 미래의 통로일 수 있다.

몇몇의 바람직한 실시예들에서 재구축될 상기 경로는 미리-계획된 경로이다. 상기 미리-계획된 경로는 가까운 또는 미래의 이동을 위한 경로일 수 있다. 미리-계획된 경로는 미리-계산된 경로, 즉, 경로 설정 알고리즘에 의해 계산되었던 경로일 수 있다. 상기 경로는 바람직하게는 외부에서 생성된 경로이다. 상기 경로는, 상기 경로를 재구축하는데 있어서 폴리라인 데이터를 획득하고 이용하는 단계들을 수행하는 디바이스, 예를 들면, 내비게이션 디바이스의 외부에서 생성된다. 다른 말로 하면, 상기 경로는 오프-보드 (off-board)로 생성된다. 바람직하게는, 상기 경로는 서버에 의해 생성되었던 경로이다. 몇몇의 실시예들에서, 상기 경로는 내비게이션 디바이스, 예를 들면, 상기 폴리라인 데이터를 획득하고 사용한 디바이스에 의한 요청에 응답하여 생성되었던 경로이다. 그러나, 반드시 그런 것은 아니다. 예를 들면, 상기 경로는 사용자의 경로 계획 웹사이트와의 상호작용에 의해 생성되었던 경로일 수 있다. 본 발명이 폴리라인 표현의 모습인 상기 재구축될 경로를 나타내는 데이터를 제공하고, 그리고 관련된 전자 지도에 관련하여 상기 경로를 재구축하기 위해 사용되기 때문에, 경로 재구축은 아주 다양한 포맷들인 초기 경로 데이터를 기초로 하여 달성될 수 있으며, 현존하는 하이브리드 경로 설정 시스템보다 더 큰 유연성을 제공한다. 상기 초기 경로 데이터는 어떤 특정 모습일 필요는 없다. 그래서, 상기 초기 경로는 어떤 경로 계획 시스템을 이용하여 생성된 경로일 수 있다. 예를 들면,일반적인 경로 계획 웹사이트가 사용될 수 있을 것이며, 또는 경로 계획 웹사이트 또는 그에 유사한 것은 특별한 차량 제조자 등에 의해 제공된다. 상기 방법은 재구축될 상기 미리-계획된 경로를 생성하는 단계로 확장될 수 있다. 그래서, 상기 미리-계획된 경로는 임의 모습의 추천 경로일 수 있다.

미리-계획된 경로는 운행 가능 네트워크를 통한 이동을 시작하기 이전에, 또는 예를 들면, 이동되고 있는 경로의 나머지에 관련하여 상기 운행 가능 네트워크를 통한 이동 동안에 생성된 경로일 수 있다. 예를 들면, 상기 미리-계획된 경로는 현재 이동되고 있는 경로에서 문제가 생겼을 때에 이동하는 중의 대안으로서 생성된 경로일 수 있다. 상기 미리-계획된 경로는 이전에 계획된 경로로부터 탐지된 벗어남에 응답하여, 예를 들면, 원래의 경로로 돌아가기 위해서 생성된 경로일 수 있다.

일반적으로, 적어도 서버에 의한 미리-계획된 경로가 클라이언트 디바이스에 의해 재구축되는 바람직한 실시예에서, 본 발명은 서버 측 경로 계획이 클라이언트 측 경로 계획과 분리되는 것을 허용한다는 것을 알 수 있을 것이다. 상기 경로가 미리-계획된 경로인 이 실시예들에서, 상기 경로는, 예를 들면, 반드시 직전의 과거일 필요는 없는 상기 경로의 재구축 이전의 어느 때에나, 서버 또는 다른 경로 계획 시스템에 의해 계획되었던 경로일 수 있다. 예로서, 사용자는 다음날 따르기로 한 경로를 계획하기 위해 웹사이트를 이용할 수 있을 것이다. 상기 경로를 표현하는 폴리라인 데이터를 이용하여 상기 경로를 재구축하는 것은 다음날 출발 직전에 내비게이션 디바이스에 의해 실행될 수 있다. 이것은 상기 미리-계획된 경로에 대체적으로 같은 모양이 되게 하면서, 라이브 데이터, 예를 들면, 트래픽 데이터를 고려하여 상기 경로를 재구축하는 것을 가능하게 할 것이다

그것이 미리-계획된 경로이건 또는 아니건간에, 재구축될 상기 경로는 제1 로케이션과 제2 로케이션 사이의 경로일 수 있다. 상기 제1 경로는 현재 위치, 또는 원점일 수 있다. 상기 현재 위치는 내비게이션 디바이스의 현재 위치일 수 있으며, 그리고 바람직하게는 상기 경로를 재구축하는데 있어서 상기 폴리라인 데이터를 이용하는 상기 내비게이션 디바이스의 현재 위치일 수 있다. 상기 제2 위치는 목적지일 수 있다. 상기 경로가 미리-계획되는 실시예들에서, 상기 제1 로케이션 및 제2 로케이션 중 하나 또는 둘 모두는 사용자 특정되거나 그리고/또는 상기 미리-계획된 경로를 생성하는데 있어서의 사용을 위해 내비게이션 디바이스로부터 수신될 수 있다. 예를 들면, 사용자는 적절한 경로 계획자에게 상기 로케이션(들)을 입력할 수 있으며, 또는 내비게이션 디바이스는 상기 제1 및 제2 로케이션들을 나타내는 데이터를 상기 제1 및 제2 로케이션들 사이에서 계획될 경로에 대한 요청과 함께, 예를 들면, 서버로 전송할 수 있다. 물론, 상기 제1 및 제2 로케이션들은, 예를 들면, 서버 등에 의해 어떤 다른 방식으로 특정될 수 있을 것이다. 재구축될 경로를 생성하는 단계로 확장되는 실시예들에서, 상기 방법은 서버가 생성될 경로에 대한 요청을 내비게이션 디바이스 (바람직하게는 상기 폴리라인 데이터를 획득하고 사용하는 내비게이션 디바이스)로부터 수신하는 단계를 포함할 수 있으며, 상기 요청은 상기 경로가 그 사이에서 생성될 제1 및 제2 로케이션들을 나타내는 데이터를 포함하며, 상기 방법은 서버가 상기 제1 로케이션 및 제2 로케이션 사이에서 경로를 생성하는 단계를 포함한다. 대안으로 또는 추가적으로, 상기 제1 로케이션 및 제2 로케이션 중 하나 또는 둘 모두는, 예를 들면, 상기 내비게이션 디바이스에 의해 자동적으로 결정될 수 있다. 예를 들면, 제1 로케이션은 현재 이동되고 있는 경로의 나머지를 따른 로케이션으로, 예를 들면, 트래픽 상태들을 고려하여 그 로케이션으로부터 상기 경로를 재-계획할 것이 소망되는 로케이션이다. 몇몇의 실시예들에서, 내비게이션 디바이스는 상기 디바이스의 현재 위치를 나타내는 데이터를 서버로 주기적으로 제공할 수 있다는 것이 예견된다.

상기 폴리라인은, 경로들이 그 사이에서 재구축될 것인 상기 제1 로케이션으로부터 상기 제2 로케이션으로 확장될 수 있으며 또는 확장되지 않을 수 있을 것이다. 그러나, 바람직한 실시예들에서 상기 폴리라인은 상기 제1 로케이션으로부터 상기 제2 로케이션으로 확장한다.

아래에서 더욱 상세하게 설명되는 다른 실시예들에서, 미리-계획된 경로가 아니라, 재구축될 상기 경로는, 예를 들면, 차량에 의해 상기 네트워크를 통해 이전에 이동했던 경로일 수 있다.

상기 폴리라인을 나타내는 데이터를 획득하는 상기 단계는, 상기 데이터를 상기 경로를 재구축하는데 있어서 사용하는 내비게이션 디바이스에 의해 바람직하게 수행되며, 상기 데이터를 수신하는 단계를 포함할 수 있다. 상기 폴리라인을 나타내는 상기 데이터는 바람직하게는 무선 통신 링크를 통해 수신된다. 상기 폴리라인을 나타내는 데이터는 임의 소스 또는 소스들로부터 획득될 수 있다. 바람직하게는 상기 방법은 상기 폴리라인을 나타내는 데이터를 하나 또는 그 이상의 외부 소스들로부터 수신하는 단계를 포함한다. 그래서 상기 데이터는, 경로 재구축에서 상기 데이터를 사용하는 디바이스의, 예를 들면, 내비게이션 디바이스의 외부인 소스 또는 소스들로부터 수신된다. 몇몇의 바람직한 실시예들에서, 상기 폴리라인을 나타내는 데이터가 획득되며, 즉, 하나 또는 그 이상의 서버로부터 수신된다. 상기 폴리라인이 표현하는 재구축될 경로가 생성되는 실시예들에서, 상기 서버는 상기 폴리라인이 표현하는 상기 재구축될 그런 경로를 생성한 것과 같은 서버일 수 있으며 또는 같은 서버가 아닐 수 있을 것이다. 예를 들면, 하이브리드 경로 설정 시스템에 적용가능한 이 바람직한 실시예들에서, 경로를 재구축하기위해 상기 폴리라인 데이터를 사용하는 디바이스는 상기 폴리라인이 표현한 상기 경로에 엑세스할 필요가 없으며, 또는 적어도 그 경로를 생성할 필요가 없다. 다른 실시예들에서 상기 폴리라인을 나타내는 데이터를 획득하는 단계는 재구축될 상기 운행 가능한 네트워크를 통한 상기 경로를 나타내는 데이터를 이용하여 상기 폴리라인을 나타내는 데이터를 생성하는 단계를 포함할 수 있다. 그런 단계는 내비게이션 디바이스에 의해 수행될 수 있을 것이다.

폴리라인 데이터가 수신되는 경우에, 그 데이터는 다른 경로 관련된 데이터와 함께 수신될 수 있을 것이다. 몇몇의 실시예들에서, 상기 폴리라인 데이터는, 재구축될 상기 경로가 그 사이에서 확장되는 제1 로케이션 및 제2 로케이션을 나타내는 데이터와 함께 수신된다. 이것은 상기 폴리라인 그 자체가 이런 로케이션들로, 또는 그 로케이션들로 정확하게 확장되지 않는 경우에 적합할 수 있다. 그런 데이터는 상기 경로를 재구축하기 위한 경로 생성에 있어서 유용할 수 있다.

상기 방법이 상기 폴리라인 데이터를 수신하는 단계를 포함하는 몇몇의 실시예들에서, 상기 방법은 상기 경로가 재구축되는 것에 관련된 전자 지도 데이터를 수신하는 단계를 더 포함할 수 있다. 상기 전자 지도 데이터는 상기 폴리라인 데이터와 연관되어 또는 그것과는 분리하여, 예를 들면, 연속하여 수신될 수 있다. 예를 들면, 상기 전자 지도 데이터는 상기 폴리라인 데이터를 수신한 이후에 만들어진 더 나중의 요청에 응답하여 수신될 수 있다. 전자 지도 데이터가 수신된 실시예들에서, 상기 데이터는 서버로부터 수신될 수 있다. 상기 방법은, 예를 들면, 서버가 상기 전자 지도 데이터를, 예를 들면, 내비게이션 디바이스에게 이용 가능하게 만드는 단계로 확장된다. 이 실시예들은, 상기 폴리라인 데이터를 획득하고, 즉, 데이터를 수신하고, 그리고 상기 경로를 재구축하기 위해 그 데이터를 이용하는 단계들이 내비게이션 디바이스에 의해 수행되는 경우에 특히 적용 가능하다. 상기 전자 지도 데이터가 상기 디바이스에게 이용 가능하도록 추가적으로 만들어서, 관련된 구역을 위해 상기 디바이스가 미리 전자 지도 데이터를 저장하는 것이 필요하지 않다. 상기 방법은 상기 전자 지도 데이터를, 옵션으로는 상기 폴리라인 데이터와 함께 전송하는 단계를 포함할 수 있다. 상기 전자 지도 데이터는 상기 내비게이션 디바이스로 직접적으로, 또는 상기 디바이스에 의한 요청에 응답하여 전송될 수 있을 것이라는 것이 인정될 것이다. 상기 방법은, 상기 전자 지도 데이터가 디바이스에 의해 나중에 인출되는 것을 가능하게 하기 위해 상기 전자 데이터가 상기 디바이스에게 이용 가능하도록 만드는 단계를 포함할 수 있다. 몇몇의 실시예들에서, 상기 방법은 서버가 로케이션을 나타내는 데이터를 연관된 내비게이션 디바이스에게 제공하는 단계를 포함하며, 상기 전자 지도 데이터는 그 로케이션으로부터 상기 디바이스에 의해 인출될 수 있다. 이것은 링크 또는 유사한 모습일 수 있다. 상기 로케이션을 나타내는 상기 데이터는 상기 폴리라인 데이터와 함께 상기 디바이스로 전송될 수 있다. 이 단계는 상기 로케이션 데이터를 내비게이션 디바이스로 전송하는 서버에 의해 수행될 수 있다. 상기 디바이스는 필요하면 상기 서버로부터 적합한 전자 지도 데이터를 인출할 수 있다. 그러나 그리고 그것이 전송될 때마다, 수신된 상기 전자 지도 데이터는 상기 폴리라인 데이터에 의해 표시된 상기 경로의 로케이션 그리고/또는 상기 디바이스의 현재 위치를 기초로 할 수 있다. 이 실시예들에서, 재구축될 상기 경로는 보통은 더 긴 경로의 일부이며, 상기 서버는 상기 경로의 재구축을 위해 상기 디바이스에 의해 요청된 관련 전자 지도 데이터를 상기 디바이스에게 이용 가능하게 만드는 것은 물론이며, 상기 경로의 일부를 표현하는 폴리라인을 나타내는 데이터를 전송한다. 상기 방법은 수신된 전자 지도 데이터를 저장하는 내비게이션 디바이스를 포함할 수 있다. 몇몇의 실시예들에서, 상기 수신된 폴리라인 데이터는 재구축에서의 사용을 위해 상기 전자 지도 데이터와 연관되며, 또는 상기 전자 지도 데이터를 인출하기 위해 사용될 수 있는 데이터와 연관되며, 상기 방법은 경로 재구축에서의 사용을 위해 상기 전자 지도 데이터를 수신하고 저장하는 단계를 더 포함한다.

본 발명의 실시예들에 따르는, 그리고 그리고 상기 시스템의 어느 컴포넌트(들)가 상기 단계를 수행하는가에 관계없이 상기 방법은 재구축될 운행 가능 네트워크를 통한 상기 경로를 표현하는 상기 폴리라인 데이터를 생성하기 위해, 상기 재구축될 운행 가능 네트워크를 통한 상기 경로를 나타내는 데이터를 이용하는 단계로 확장될 수 있다. 상기 단계는 서버 또는 내비게이션 디바이스에 의해 수행될 수 있다. 예를 들면, 하이브리드 경로 설정 유형의 실시예들에서 또는 그렇지 않고 상기 경로가 미리-계획된 경로인 경우에, 상기 단계는 내비게이션 디바이스로의 전송을 위해 폴리라인 데이터를 획득하기 위해서 서버에 의해 보통 수행될 수 있다. 다른 실시예들에서, 내비게이션 디바이스는 몇몇의 방식으로 상기 디바이스에 의해 획득되었던 경로 데이터를 이용하여 이 단계를 수행할 수 있다. 예를 들면, 외부 경로 계획 시스템에 의해 계획된 경로를 나타내는 경로 데이터는 사용자에 의해 상기 디바이스로 입력될 수 있다. 폴리라인 데이터를 생성하기 위해 경로 데이터를 이용하는 상기 단계가 서버에 의해 수행되는 경우에, 그런 단계가 수행되는 실시예들에서, 상기 서버는 재구축될 상기 경로를 생성한 것과 동일한 서버일 수도 있고 아닐 수도 있을 것이다. 다른 실시예들에서, 내비게이션 디바이스는, 예를 들면, 사용자에 의해 외부 소스로부터 제공된 재구축될 경로를 나타내는 데이터를 이용하여, 또는 이동했던 경로를 나타내는 타임-스탬프 위치 데이터를 이용하여 상기 단계를 수행할 수 있다.

본 발명의 실시예들 중 어느 실시예에서, 그런 단계가 수행되는 곳에서는 어디든지, 폴리라인 데이터를 생성하는데 있어서 사용하기 위해 상기 경로 데이터를 획득하는 단계는 어떤 적합한 방식으로, 예를 들면, 무선 통신 링크를 경유하여 상기 경로 데이터를 수신하는 단계를 포함할 수 있다. 재구축될 경로를 나타내는 데이터는 외부 소스, 예를 들면, 서버로부터 수신될 수 있다. 몇몇의 실시예들에서, 서버는 다른 서버로부터 상기 경로 데이터를 수신할 수 있으며, 그리고 경로 재구축에서 사용할 용도로 내비게이션 디바이스로의 전송을 위해 상기 폴리라인 데이터를 생성하기 위해서 상기 데이터를 이용할 수 있다. 물론, 상기 외부 소스는 임의의 디바이스일 수 있으며, 그리고 서버일 필요는 없다. 다른 실시예들에서, 내비게이션 디바이스는 상기 경로 데이터를 수신하고 그리고 상기 폴리라인을 생성하기 위해 그 데이터를 사용할 수 있다. 상기 데이터는 상기 디바이스로 자동적으로 또는 사용자에 의한 요청에 응답하여 전송될 수 있다. 사용자는 계획된 경로의 상세 내용들을 경로 계획 기능성을 가진 시스템이나 다른 디바이스로부터 상기 디바이스로 전달할 수 있다. 위에서 설명된 것처럼, 재구축될 경로를 나타내는 데이터는 본 발명에서의 사용을 위해 넓은 범위의 소스들로부터 획득될 수 있다. 상기 경로 데이터를 획득하는 단계는 위에서 설명된 방식들 중 어느 방식에서 미리-계획된 경로를 제공하기 위해 경로를 생성하는 단계를 대안으로 포함할 수 있다. 다른 실시예들에서, 예를 들면, 재구축될 상기 경로가 이전에 이동했던 경로인 경우에, 상기 폴리라인 데이터를 생성하는 단계는 내비게이션 디바이스, 예를 들면, 상기 경로를 재구축할 동일한 디바이스에 의해 상기 이동했던 경로를 나타내는 데이터를 이용하여 수행될 수 있다는 것이 예견된다. 재구축될 상기 경로를 나타내는 데이터를 획득하는 단계는 그러면 아래에서 더욱 상세하게 설명되는 상기 경로를 나타내는 타임-스탬프 위치 데이터를 획득하는 단계를 포함할 수 있다.

재구축될 경로를 나타내는 데이터를 이용하여 상기 폴리라인을 나타내는 데이터를 생성하는 단계를 상기 방법이 포함하는 본 발명의 실시예들 중 어느 실시예에서의 본 발명에 따라서, 상기 방법은 전자 지도에 관련하여 재구축될 경로를, 바람직하게는 상이한 전자 지도에 관련하여 재구축될 경로를 나타내는 정보를 획득하는 단계를 포함하며, 그리고 옵션으로 상기 폴리라인 데이터를 생성하는데 있어서 사용하기 위해 지도 불가지론적 모습으로 상기 경로 데이터를 변환하는 단계를 포함한다. 예를 들면, 어떤 적합한 지도 불가지론적 로케이션 참조 시스템은 위에서설명된 OpenLRTM, AGORA-C 및 TPEG-ULR 방법들처럼, 또는 어떤 다른 그런 시스템들처럼 사용될 수 있다. 이것은 폴리라인 데이터가 위에서 설명된 바람직한 실시예들에서처럼 그런 지도 불가지론적 로케이션 참조 시스템에 관련하여 획득되는 것을 가능하게 할 수 있다.

상기 폴리라인 데이터를 생성하는데 있어서 사용되는 재구축될 경로를 나타내는 데이터는 상기 경로를 나타내는 어떤 데이터일 수 있다. 그 데이터는 상기 경로 내에 포함된 운행 가능한 네트워크의 운행 가능한 세그먼트들의 목록을 나타내는 데이터일 수 있다. 비록 전자 지도에 대한 참조에 의해서일 수 있지만, 운행 가능 세그먼트들의 목록은 지도 불가지론적 로케이션 참조 시스템에 의해 바람직하게 참조된다. 상기 운행 가능 세그먼트들을 나타내는 데이터는 상기 폴리라인을 정의하는 일련의 포인트들을 획득하기 위해 사용될 수 있다. 획득된 상기 폴리라인 데이터는 재구축될 경로를 대표한다. 실시예들에서, 재구축될 경로를 나타내는 데이터를 이용하여 상기 폴리라인 데이터를 생성하는 단계는 재구축될 상기 경로 내에 포함된 운행 가능한 세그먼트들을 나타내는 데이터를 이용하여 상기 폴리라인 데이터를 생성하는 단계를 포함할 수 있다. 몇몇의 실시예들에서, 상기 방법은 상기 폴리라인 내에 포함되는 것을 위해 라인 세그먼트들을 식별하기 위해서 상기 경로 내에 포함된 상기 운행 가능 세그먼트들을 나타내는 데이터를 이용하는 것을 포함할 수 있다. 상기 폴리라인 데이터에 의해 기술된 상기 폴리라인이 재구축될 상기 경로와 동일할 수 있으며 또는 적어도 그 경로와 유사할 수 있다는 것이 인정될 것이다. 상기 폴리라인은 재구축될 상기 경로와 근사할 수 있다. 상기 폴리라인을 생성하는 단계는 상기 데이터의 몇몇의 일반화를 포함할 수 있으며, 예를 들면, 상기 경로의 재구축 동안에 상기 폴리라인의 프로세싱을 용이하게 하기 위해 필요하다면 상기 폴리라인을 정의하는 포인트들의 개수에서의 축소를 포함할 수 있다

재구축될 상기 경로가 이동될 미리-계획된 경로인 경우인 실시예들을 특히 참조하여 본 발명이 설명되었지만, 본 발명의 상기 방법들은 이전에 이동했던 경로를 구축하는 것에도 동등하게 적용 가능하다. 상기 방법은 상기 경로를 표현하는 폴리라인 데이터를 획득하는데 있어서 이전에 이동했던 경로를 표시하는 데이터를 이용하는 단계로 확장될 수 있다. 상기 단계는 내비게이션 디바이스에 의해 수행될 수 있으며, 이 내비게이션 디바이스는 상기 경로를 이동했던 내비게이션 디바이스인 것이 바람직하며, 그리고 경로 재구축을 수행한다. 상기 방법은 이전에 이동했던 경로를 나타내는 데이터를 획득하는 단계로 확장될 수 있다. 상기 데이터를 획득하는 단계는 이전에 이동했던 경로를 나타내는 저장된 데이터에 액세스하는 단계를 포함할 수 있으며, 또는 이전에 이동했던 경로를 나타내는 데이터를 생성하는 단계로 확장될 수 있다. 이 실시예들에서, 상기 데이터를 획득하고 그리고/또는 상기 데이터를 상기 폴리라인 데이터를 획득하는데 있어서 사용하는 단계들은 내비게이션 디바이스에 의해 바람직하게 수행되며, 이 내비게이션 디바이스는 상기 경로를 재구축하기 위해 상기 폴리라인 데이터를 이용하는 디바이스인 것이 바람직하다. 이전에 이동했던 경로를 나타내는 데이터를 사용하는 실시예들 중 어느 실시예에서, 상기 이전에 이동했던 경로를 나타내는 상기 데이터는 상기 이전에 이동했던 경로를 따라서 시간에 대해 상기 디바이스 또는 어떤 디바이스의 움직임에 관련된 데이터를 포함하는 것이 바람직하다. 상기 이전에 이동했던 경로는 제1 로케이션 및 제2 로케이션 사이에서의 운행 가능한 네트워크를 통한 어떤 통로일 수 있다. 상기 경로는 미리-계획되었던 경로일 필요는 없다.

이전에 이동했던 경로를 나타내는 상기 데이터는 바람직하게는 연관된 타이밍 데이터를 구비한 위치 데이터 (예를 들면, 경도 및 위도와 같은 지리적인 좌표들)이며, 예를 들면, 타임-스탬프 위치 데이터이다. 타임-스탬프 위치 데이터가 바람직하게 사용되지만, 연관된 타이밍 데이터를 가진 어떤 위치 데이터가 여기에서 설명된 실시예들에서 사용될 수 있을 것이며, 그리고 "타임-스탬프 위치 데이터"를 언급하는 것은, 상호 불일치하지 않는 정도까지는, "연관된 타이밍 데이터를 구비한 위치 데이터"를 언급하는 것과 교체될 수 있다는 것이 이해되어야 한다. 상기 위치 데이터는 글로벌 내비게이션 위성 시스템 (global navigation satellite system (GNSS)) 수신기, 또는 모바일 원거리통신 네트워크 (예를 들면, GSM)을 사용하는 것과 같은 어떤 다른 적합한 위치 판별 수단으로부터 획득될 수 있다. 상기 데이터는 이력적인 위치 데이터이다. 연관된 타이밍 데이터를 구비한 상기 위치 데이터는 위치 트레이스 (positional trace)의 모습일 수 있다. 바람직한 실시예들에서, 상기 이전에 이동했던 경로는 상기 폴리라인 데이터를 획득하기 위해 상기 데이터를 이용한 상기 내비게이션 디바이스가 이동했던 경로이다. 그러나, 상기 경로는 다른 디바이스가 이동했던 경로일 수 있다. 상기 디바이스는 본 발명의 목적들을 위해 위치 데이터 및 충분한 연관된 타이밍 데이터를 제공할 수 있는 어떤 디바이스일 수 있으며, 그리고 내비게이션 디바이스일 수 있고 또는 아닐 수도 있다. 상기 경로 데이터를 획득하는 단계는 상기 네트워크를 따라 시간에 대하여 어떤 디바이스 또는 상기 디바이스의 움직임에 관련된 데이터를 수신하는 단계를 포함할 수 있다. 몇몇의 실시예들에서, 상기 방법은 상기 이전에 이동했던 경로를 나타내는 상기 데이터를 제공하기 위해 경로를 따른 상기 디바이스의 이동 동안에, 시간에 대해 어떤 디바이스 또는 상기 디바이스의 움직임을 나타내는 데이터, 예를 들면, 타임-스탬프 위치 데이터를 저장하는 단계로 확장될 수 있다. 바람직한 실시예들에서, 이 단계는 경로 재구축을 수행하는 상기 동일한 내비게이션 디바이스에 의해, 그리고 바람직하게는 그 동일한 디바이스의 이전의 움직임에 관련된 데이터를 이용하여 수행된다. 본 발명은 이전에 이동했던 경로들을 나타내는 그런 데이터가 상기 특별한 디바이스의 전자 지도 데이터에 관련하여 상기 경로들을 재구축하기 위해 사용되는 것을 가능하게 한다.

바람직한 실시예들에서, 이전에 이동했던 경로를 표현하는 폴리라인을 획득하기 위해 사용된 데이터는 시간에 대해 디바이스의 위치를 나타내는 데이터이며, 그런 데이터는 본래 지도 불가지론적일 것이다. 폴리라인을 이용하여 그런 데이터를 표현하는 중간 단계를 수행함으로써, 상기 경로는 지도 업데이트 동작들 또는 유사한 것 이후에도 정확함을 유지할 수 있는 방식으로 특별한 전자 지도에 관련하여 구축될 수 있다. 데이터베이스가 생성되어 여러 이전에 이동했던 경로들을 나타내는 데이터를 저장하는 것이 예견된다. 본 발명의 실시예들에 따라서 각각의 그런 경로를 표현하는 폴리라인 데이터를 획득하고 그리고 주어진 지도에 관련하여 상기 경로를 재구축하기 위해 상기 폴리라인 데이터를 이용함으로써, 특별한 전자 지도에 관련하여 이전에 이동했던 경로들의 데이터베이스가 생성될 수 있다. 상기 데이터베이스는 상기 경로들을 재구축했던 상기 내비게이션 디바이스에 의해 저장될 수 있다. 내비게이션 디바이스를 이용하여 이전에 이동했던 경로들을 구축하려는 이전의 시도들은 관련된 시간에 상기 디바이스의 전자 지도 데이터에 관련하여 상기 경로들을 주변에 저장하는 것에 결부될 것이다. 예를 들면, 상기 경로는 상기 전자 지도의 특정 세그먼트들에 관하여 발생했던 조치 (manoeuvre)들에 관하여 저장될 것이다. 그러나, 그런 경로들은 그러면 신뢰성이 없을 것이며 또는 심지어는 상기 디바이스의 전자 지도의 업데이트 다음의 나중에는 사용할 수 없을 것이다. 본 발명의 이런 추가의 실시예들은, 예를 들면: 빈번하게 이동했던 경로들; 집, 직장, 체육관과 같은 특정 관심 포인트들 사이에서의 경로들 등인 이전에 이동했던 경로들에 관련하여 사용될 수 있다.

상기 폴리라인 데이터를 획득하며 그리고 상기 운행 가능한 네트워크를 통한 경로들을 재구축하기 위해 상기 데이터를 이용하는 단계들이 내비게이션 디바이스에 의해 수행되는 몇몇의 실시예들에서, 상기 방법은 상기 내비게이션 디바이스가 상기 디바이스의 전자 지도에 의해 커버된 영역 내 상기 운행 가능한 네트워크를 통해 상기 디바이스가 이전에 이동했던 하나 또는 그 이상의, 그리고 바람직하게는 복수의 경로들을 나타내는 데이터를 저장하는 단계, 상기 경로를 표현하는 폴리라인을 나타내는 데이터를 생성하기 위해 상기 이전에 이동했던 경로 데이터를 이용하는 단계, 상기 전자 지도에 의해 표현된 상기 운행 가능한 네트워크를 통해 경로를 생성하기 위해 상기 폴리라인을 나타내는 상기 획득된 데이터를 이용하는 단계로, 상기 생성된 경로는 상기 폴리라인에 의해 표현된 상기 경로의 재구축을 제공하는, 단계, 그리고 상기 재구축된 경로를 나타내는 데이터를 저장하는 단계를 포함한다. 상기 이전에 이동했던 경로를 나타내는 상기 데이터는 위에서 설명된 유형, 즉, 타임-스탬프 위치 데이터처럼, 상기 경로를 따른 이동 동안에 시간에 관하여 상기 디바이스의 움직임을 나타내는 데이터인 것이 바람직하다. 상기 방법은 상기 전자 지도에 관련하여 복수의 경로들을 재구축하기 위해 이 단계들을 반복하는 단계, 그리고 상기 재구축된 경로들을 나타내는 데이터를 저장하는 데이터베이스를 생성하는 단계를 포함할 수 있다. 상기 디바이스는 경로 재구축에 있어서 사용하기 위해 상기 이전에 이동했던 경로를 제공할 수 있는 복수의 이전에 이동했던 경로들을 나타내는 데이터를 포함하는 데이터베이스를 저장할 수 있다.

재구축될 경로를 표현하는 상기 폴리라인에 의해 표현된 상기 경로는 재구축될 경로의 전체일 수도 있고 아닐 수도 있다는 것이 인정될 것이다. 대안으로 또는 추갖거으로, 재구축될 상기 경로는 계획된 경로의 전체일 수 있고 또는 아닐 수도 있다. 상기 폴리라인에 의해 표현된 상기 경로는 재구축될 더 긴 경로의 단지 일부일 수 있다. 그래서 상기 경로는 그 자체가 서브-경로일 수 있다. 상기 경로가 제1 로케이션 및 제2 로케이션 사이에 존재하는 경우에, 상기 제1 로케이션 및 제2 로케이션 중 하나 또는 둘 모두는 재구축될 더 긴 경로를 따른 로케이션들일 수 있다. 상기 경로는 더 긴 미리-계획된 경로의 일부일 수 있으며, 또는 계획될 경로의 나머지의 일부일 수 있다. 예를 들면, 전체 경로가 일부분들에서 계획될 수 있으며, 관련 폴리라인 데이터는 각 일부에 대해 생성되며 그리고 재구축에서의 사용을 위해 획득되며, 또는 전체 경로가 계획될 수 있으며, 폴리라인 데이터는 일부분 기반에 의해 일부분 상에서 생성된다. 대안으로 또는 추가로, 상기 획득된 폴리라인 데이터는 어느 데이터가 결정되는가의 면에서 폴리라인의 일부를 나타낼 수 있을 것이라는 것이 또한 예견된다. 예를 들면, 서버는 전체 경로를 표현하는 폴리라인 데이터를 획득할 수 있으며, 그리고 재구축에서의 사용을 위해 상기 경로의 일부분들에 관하여 상기 폴리라인 데이터의 일부분들을 내비게이션 디바이스로 전송할 수 있다. 상기 폴리라인 데이터의 일부분들은 상기 디바이스의 현재 위치를 기반으로 하여 전송을 위해 선택될 수 있다.

본 발명의 모습들이나 실시예들 중 어느 하나에서의 본 발명에 따라서, 상기 방법은 상기 전자 지도에 의해 표현된 상기 운행 가능한 네트워크를 통해 경로를 생성하기 위해 상기 폴리라인을 나타내는 데이터 ("상기 폴리라인 데이터")를 이용하는 단계를 포함할 수 있으며, 이 생성된 경로는 상기 전자 지도에 관련하여 상기 폴리라인에 의해 표시된 경로의 재구축을 제공한다.

상기 방법은 상기 전자 지도 상에 상기 폴리라인을 표현하는 단계를 더 포함할 수 있다. 이 단계는 상기 경로 재구축을 수행하는 내비게이션 디바이스에 의해 수행될 수 있다. 이것은 어떤 적합한 방식으로 수행될 수 있다. 예를 들면, 상기 폴리라인의 세그먼트들은 상기 전자 지도에 의해 표현된 상기 운행 가능 네트워크의 세그먼트들에 매칭될 수 있으며, 또는 상기 폴리라인은 자신을 상기 전자 지도의 세그먼트들에 매칭하려고 특별히 시도하지 않으면서 상기 전자 지도 상에 단순하게 겹쳐질 수 있다. 그런 단계들은 상기 폴리라인을 위해 사용된 로케이션 참조 시스템에 따라서 상기 폴리라인의 세그먼트들의 로케이션에 대한 참조에 의해 수행될 수 있다. 이것은 그러면 상기 전자 지도에 의해 표현된 적절한 로케이션들로 번역될 수 있다. 이전에 논의된 것처럼, 본 발명의 실시예들에서, 상기 폴리라인 세그먼트들이 상기 전자 지도의 세그먼트들에 정밀하게 매치되거나 매치될 수 있다는 것은 대단히 중요한 것은 아니다.

상기 폴리라인 데이터를 이용하여 경로를 생성하는 단계는 상기 전자 지도에 상에 표현된 상기 폴리라인에 더욱 근접한 상기 생성된 경로 내에 포함되는 것을 위해 상기 전자 지도의 세그먼트들을 선호하는 단계를 포함한다. 다른 말로 하면, 상기 전자 지도 상에 표시된 폴리라인에 상대적으로 더 가까운 세그먼트들은 상기 전자 지도 상에 표시된 폴리라인으로부터 상대적으로 더 먼 세그먼트들보다 경로 생성 프로세스에서 더 선호된다. 이 방식에서, 상기 폴리라인에 더욱 근접한, 즉, 상기 전자 지도의 다른 세그먼트들보다 상기 폴리라인에 상대적으로 더 가까운 세그먼트들은 상기 생성된 경로 내에 포함될 가능성이 더 크다. 여기에서 상기 폴리라인에 더 가까운 또는 더 먼 상기 전자 지도의 세그먼트들을 참조하는 것은, 명시적으로 선언되지 않았다면, 상기 전자 지도 상의 표시된 폴리라인으로부터 더 가깝게 또는 더 멀리 있는 세그먼트들을 언급하는 것이라는 것이 인정될 것이다.

상기 폴리라인에 근접한 세그먼트들을 선호함으로써, 그 결과인 생성된 경로는 상기 폴리라인을 향하여 끌어 당겨질 것이다. 그러나, 상기 생성된 경로는 상기 폴리라인에 동일하도록 강제되지 않는다. 그래서, 상기 세그먼트들은 상기 폴리라인에 덜 근접하게 있는 세그먼트들보다 경로 설정 엔진에 의해 더 유리하게 취급된다. 상기 세그먼트들은 상기 세그먼트들에게 긍정적인 가중 팩터들을 적용함으로써 그리고/또는 상기 전자 지도 상에 표현된 폴리라인에 덜 근접하게 있는 세그먼트들에게는 벌점을 부여함으로써, 선호될 수 있다. 이것은 경로 생성에 있어서 사용되는 세그먼트들과 연관된 비용의 적절한 조작에 의해 달성될 수 있으며, 즉, (상기 경로 설정 엔진에 의해 사용된 비용 함수를 적용한 이후에) 세그먼트를 통과하는 비용은 수정되며, 보통은 축소되어, 보통의 경우에 비해서 상기 경로 설정 엔진에 의해 더욱 선호되도록 한다; 이것은 아래에서 더욱 상세하게 설명될 것이다.

상기 세그먼트들은 상기 폴리라인에 대한 그 세그먼트들의 근접함에 기초하여, 그리고 상기 경로 설정 프로세스에 부과된 어떤 다른 선호들 및/또는 제한들을 고려하지 않으면서, 상기 전자 지도의 다른 세그먼트들에 비해 선호된다는 것이 인정될 것이다. 경로 생성 프로세스에서, 상기 폴리라인에 대한 근접함은 고려될 수 있을 여러 팩터들 중 한 한가지 팩터이다. 예를 들면, 본 발명이 속한 기술 분야에서 잘 알려진 것처럼, 세그먼트들의 길이, 세그먼트들에 대한 통과 시간, 혼잡의 가능성 등와 같은 팩터들이 고려될 수 있다. 그래서, 모든 관련된 팩터들이 고려될 때에 상기 폴리라인에 더 가까운 세그먼트가 더 멀리 있는 대안의 세그먼트보다 상기 경로 내에 항상 더 많이 포함될 것이라는 것은, 반드시 그런 것은 아니다. 이것이, 적절하다면, 예를 들어, 폴리라인을 따른 또는 근접한 세그먼트가 폐쇄되거나 또는 혼잡에 의해 영향을 받는다면, 그 경로로부터 벗어나는 능력을 가지면서도, 상기 폴리라인으로 대체적으로 끌어 당겨지는 재구축된 경로를 제공하는 유연성을 본 발명에게 제공하는 것이다. 선호되거나, 또는 몇몇의 경우들에는 본 발명에 따라 벌점이 부여되는 세그먼트들은 경로 생성의 목적들을 위해 고려된 세그먼트들이라는 것이 인정될 것이다. 그 세그먼트들은 상기 전자 지도의 세그먼트들의 부분집합일 수 있다. 예를 들면, 상기 세그먼트들은 라우팅 회랑의 세그먼트들일 수 있다.

폴리라인에 대한 세그먼트의 근접함은 어떤 적합한 방식으로 평가될 수 있다. 몇몇의 실시예들에서, 상기 방법은 상기 전자 지도 상에 표현된 폴리라인에 기초한 영역을 한정하는 단계, 그리고 그 영역 내에 있는 것으로 간주된 상기 전자 지도의 세그먼트들을 선호하는 단계를 포함한다. 몇몇의 실시예들에서, 이것은 상기 영역 내에 있는 것으로 고려되지 않는 세그먼트들에게 벌점을 부여함으로써 부분적으로 또는 전체적으로 달성된다. 상기 영역은 상기 폴리라인을 포함하는, 예를 들면, 그 폴리라인 상에 중심을 둔 영역일 수 있다. 세그먼트는 그 영역 내에 완전하게 위치할 때에, 또는 원하는 대로, 적어도 주어진 일부가 상기 영역 내에 있는 경우에 그 영역 내에 있는 것으로 고려될 수 있다. 상기 영역은 임의 형상일 수 있다. 바람직한 실시예들에서 상기 영역은 상기 폴리라인을 따라 확장하여 그 폴리라인을 포함하는 회랑의 모습이다. 다른 실시예들에서, 상기 폴리라인은 그 자체가 상기 영역을 한정할 수 있을 것이며, 상기 폴리라인은 상기 영역의 경계를 정하는 폐쇄된 루프를 형성하며, 그리고 상기 운행 가능한 네트워크를 통한 상기 경로는 상기 영역에 의해 표현된다는 것이 예견된다.

상기 전자 지도 상에 표현된 폴리라인에 기초한 상기 영역 내에 있는 것으로 고려되지 않는 세그먼트가 상기 경로 내에 포함되기 위해 벌점이 부여된 몇몇의 실시예들에서, 상기 방법은 그 세그먼트들이 상기 경로 내에 포함되는 것을 배제하는 단계를 포함할 수 있다. 다른 실시예들에서, 세그먼트들이 포함되는 것을 방해하지 않으면서 상기 세그먼트들이 상기 경로 내에 덜 포함되도록 만들기 위해서, 벌점 팩터가 상기 세그먼트들에 적용될 수 있다. 그 벌점 팩터는 아래에서 설명되듯이 상기 폴리라인으로부터의 세그먼트의 길이에 종속하여 가변인 벌점 팩터일 수 있다.

본 발명에 따라, 상기 생성된 경로 내에 포함시키기 위해 세그먼트를 선호하고 또는 벌점을 부여하는 것은 상기 세그먼트가 경로 생성의 목적을 위해 고려된 상기 전자 지도의 다른 세그먼트들보다, 상기 생성된 경로 내에 각각 더 많이 또는 더 작게 포함될 것이라는 가능성의 결과가 된다. 이것은 상기 세그먼트가 상기 경로의 일부를 형성할 것이 요청되고 그리고/또는 그렇게 하는 것이 방지되는 결과가 되지 않는 방식으로 수행되는 것이 바람직하다. 세그먼트를 선호하는 것은 그 세그먼트가 경로 생성에서 고려되며, 그리고 상기 폴리라인에 덜 근접한 상기 전자 지도의 다른 운행 가능한 세그먼트들에 상대적으로 상기 경로 내에 더욱 많이 포함될 것 같다는 결과가 된다. 세그먼트를 선호한다는 것은, 즉, 긍정적인 가중 팩터가 적용되지 않았던 경우의 상황에 비교하여 그 세그먼트가 상기 생성된 경로 내에 포함될 가능성을 증가시키기 위해서 상기 긍정적인 가중 팩터를 그 세그먼트에게 부여하는 것을 수반할 수 있으며, 그리고/또는 다른 운행 가능한, 즉, 상기 폴리라인으로 더 조금 근접한 세그먼트들에 벌점을 부여함으로써 달성될 수 있다. 세그먼트에 벌점을 부여하는 것은, 즉, 벌점 팩터가 적용되지 않았던 상황에 비교하여 그 세그먼트가 상기 생성된 경로 내에 포함되는 가능성을 줄이기 위해서 그 세그먼트에 벌점 팩터를 적용하는 것을 수반할 수 있다. 바람직한 실시예들에서, 본 발명에 따라 상기 폴리라인에 더 많이 근접한 세그먼트들을 선호하는 것은, 운행 가능한 세그먼트들의 상기 전자 지도 상에 표시된 폴리라인으로의 근접함에 기초하여 그 운행 가능한 세그먼트들에게 벌점을 부여함으로써 구현된다. 그런 실시예들은 세그먼트들과 연관된 다른 비용들과 유사한 방식으로, 경로 생성 동안에 고려될 수 있을 적합한 벌점 팩터를 비용 함수의 일부로서 적용함으로써 쉽게 구현될 수 있으며, 세그먼트들의 상기 폴리라인으로의 근접함이, 최소 비용 통로를 결정할 때에 고려될 다른 팩터로서 취급되는 것을 가능하게 한다.

세그먼트들이 벌점을 부여받아서, 그 세그먼트들이 선호되는 폴리라인으로 더 많이 근접하는 결과가 되는 경우를 참조하여, 본 발명의 몇몇의 바람직한 실시예들이 이제 설명될 것이다. 그렇지만, 더 멀리에 있는 세그먼트들에게 부정적인 벌점 팩터를 부여하는 것이 아니라 상기 폴리라인에 더 가까운 세그먼트들에게 긍정적인 가중 팩터를 대신 부여함으로써, 세그먼트들이 유사한 방식으로 자신들의 상기 폴리라인으로의 근접함에 종속하는 정도까지 대신하여 선호될 수 있다는 것이 예견된다. 긍정적인 가중 팩터는 가변으로 적용될 수 있을 것이며, 상기 폴리라인으로부터의 증가하는 거리에 대해서는 감소한다.

몇몇의 실시예들에서, 위에서 설명된 것처럼, 상기 방법은 상기 폴리라인에 기초하여 주어진 영역 내에 있는 운행 가능한 세그먼트들을, 상기 영역 외부의 세그먼트들이 상기 생성된 경로 내에 포함되는 것을 배제함으로써, 선호하는 단계를 포함할 수 있다. 그러나, 바람직한 실시예들에서, 상기 방법은 운행 가능한 세그먼들에게 그 세그먼트들의 상기 폴리라인으로의 근접성에 종속하는 상이한 등급들로 벌점을 부여하는 것을 수반한다. 이것은 상기 폴리라인이 상기 경로를 "끌어 당기"도록 행동하는 결과를 가져오며, 끌어 당김의 정도는 상기 폴리라인이 가까와지면 증가한다.

바람직하게는 상기 전자 지도 상에 표현된 폴리라인에 더욱 근접한 상기 전자 지도 상의 세그먼트들을 선호하는 단계는 그 전자 지도의 세그먼트들에게 상기 전자 지도 상에 표현된 폴리라인까지의 그 세그먼트들 각자의 근접함에 종속하는 등급으로 벌점을 부여하는 것을 수반하며, 이 경우에 상기 폴리라인으로부터 더 멀리에 있는 세그먼트들은 그 폴리라인에 더 가까운 세그먼트들보다 더 큰 등급으로 벌점을 부여받는다. 상기 폴리라인으로부터의 거리에 종속하는 다른 가변의 벌점 팩터가 부여될 수 있다. 벌점 팩터들은 상기 폴리라인에 상대적으로 가까운 세그먼트들을 포함하는 모든 세그먼트들에 적용될 수 있을 것이며, 또는 상기 폴리라인에 기초한 영역, 예를 들면, 상기 폴리라인을 따라서 확장하는 회랑의 외부에 있는 세그먼트들에게만 적용될 수 있을 것이다. 그래서 상기 폴리라인에 기초한 영역 내의 세그먼트들이 선호되는 상기 설명된 실시예들과 조합하여 가변의 벌점 팩터가 적용될 수 있다. 이 실시예들에서, 상기 영역 내 세그먼트들은 그 세그먼트들에 적용된 벌점 팩터를 가지지 않음으로써 선호될 수 있을 것이며, 이 경우에 상기 영역 외부의 세그먼트들은 상기 폴리라인으로부터의 거리에 따라 가변인 등급으로 벌점을 부여받는다.

바람직하게는, 운행 가능한 세그먼트는 상기 전자 지도 상에 표현된 상기 폴리라인 및 상기 운행 가능한 세그먼트 사이의 거리를 기초로 하는 등급으로 벌점을 부여받는다. 그래서, 상기 세그먼트에 부여된 벌점 팩터는 상기 운행 가능 세그먼트와 상기 표현된 폴리라인 사이의 거리를 기초로 하여 결정될 수 있다. 운행 가능 세그먼트가 벌점을 부여받는 등급이 더 클수록, 상기 운행 가능한 세그먼트와 상기 전자 지도 상에 표시된 폴리라인 사이의 거리는 더 커진다. 그래서 상기 벌점 팩터는 더 커지면, 상기 운행 가능한 세그먼트와 상기 폴리라인 사이의 거리도 더 커진다. 운행 가능한 세그먼트가 벌점을 부여받는 등급은 상기 전자 지도 상에 표현된 상기 폴리라인과 상기 운행 가능한 세그먼트 사이의 거리에 비례할 수 있으며, 그리고 가장 바람직하게는 상기 거리의 제곱 또는 더 높은 차수의 거듭제곱에 비례할 수 있다.

세그먼트에 적용된 벌점 팩터, 또는 상기 세그먼트가 벌점을 부여받은 등급은 상기 세그먼트 그리고 상기 폴리라인의 길이를 따른 그 폴리라인의 표현 사이의 거리에서의 변이를 고려할 수 있다. 예를 들면, 상기 벌점은 상기 세그먼트와 상기 폴리라인 사이의 평균 거리에 기초할 수 있다. 이것은 어떤 적합한 방식으로 달성될 수 있을 것이다. 몇몇의 바람직한 실시예들에서, 상기 세그먼트를 따른 복수의 상이한 위치들 각각 그리고 상기 폴리라인의 표현 사이의 거리들을 고려하는 등급으로 벌점이 부여된다. 몇몇의 바람직한 실시예들에서 벌점 팩터들은 상기 세그먼트를 따른 복수의 상이한 위치들 각각에 대해 결정되며, 각각은 각자의 위치에서의 상기 세그먼트 그리고 상기 폴리라인의 상기 표현 사이의 거리에 기초한다. 상기 방법은 상기 세그먼트를 따른 복수의 위치들 각각에 대해 벌점 팩터를 결정하는 단계를 포함할 수 있으며, 각 위치에 대한 벌점 팩터는 각자의 위치 그리고 상기 전자 지도 상에 표현된 폴리라인 사이의 거리를 기초로 하며, 그리고 상기 운행 가능한 세그먼트에 적용될 전체적인 벌점 팩터를 유도하기 위해 각 벌점 팩터를 이용하는 단계를 포함할 수 있다. 상기 세그먼트에 대한 벌점 팩터는 상기 세그먼트를 따른 복수의 위치들 각각에 대해 결정된 벌점 팩터들을 조합하여 획득될 수 있다. 예를 들면, 상기 위치들 각각에 대한 벌점 팩터들은 합산될 수 있다. 상기 운행 가능한 세그먼트를 따를 위치를 참조하는 것은 상기 전자 지도에 의해 표현된 실제의 운행 가능한 세그먼트, 또는 그것의 근사에 따른 위치에 관련될 수 있다. 운행 가능한 세그먼트를 따른 여러 위치들이 고려되는 경우에, 상기 위치들을 이격시키는 것은 결과들에서의 정밀도 그리고 필요한 프로세싱 시간 및 전력 사이의 균형을 제공하기 위해 원하는대로 선택될 수 있다. 예를 들면, 더 가깝게 이격시키는 것은 상기 세그먼트가, 예를 들어, 하나 또는 그 이상의 형상 포인트들을 이용하여 설명되는 더욱 복잡한 형상을 가지는 경우에 필요할 수 있을 것이다

프로세싱 효율을 위해서, 상기 세그먼트의 대체적인 위치를 표시하기 위해 상기 세그먼트의 근사가 사용될 수 있다는 것이 인정될 것이며, 이 경우에 예를 들면, 상기 세그먼트의 길이를 따른 상세한 형상 포인트들을 무시한다. 그래서 운행 가능한 세그먼트 그리고 상기 폴리라인의 상기 표현 사이의 거리는 상기 운행 가능한 세그먼트의 근사 그리고 상기 폴리라인의 상기 표현 사이의 거리를 기초로 할 수 있다. 예를 들면, 운행 가능한 세그먼트는 상기 세그먼트의 말단 노드들을 연결하는 직선에 의해 근사화될 수 있다. 몇몇의 실시예들에서, 상기 거리를 결정할 때에 상기 운행 가능한 세그먼트의 근사를 또는 상기 운행 가능한 세그먼트의 실제의 진로를 사용하는가의 여부에 대한 결정은 상기 운행 가능한 세그먼트의 복잡성 그리고/또는 상기 세그먼트의 상기 폴리라인에 대한 관계에 종속할 수 있다. 이런 상황들에서, 상기 운행 가능한 세그먼트의 진로의 근사를 사용하는 것은 상기 세그먼트와 상기 폴리라인 사이의 거리에 대한 부정확한 결정의 결과가 더 많이 될 수 있다. 예를 들면, 운행 가능한 세그먼트를 따른 위치들의 상기 폴리라인 상으로의 투사가 상기 폴리라인의 하나보다 많은 세그먼트를 넘어 확장되는 경우에, 상기 운행 가능한 세그먼트의 중간 형상 포인트들이 고려될 수 있다.

바람직한 실시예들에서, 세그먼트를 따른 여러 위치들 그리고 상기 폴리라인의 상기 표현 사이의 각각의 거리들이 상기 세그먼트에 벌점을 부여하는데 있어서 고려되면, 예를 들면, 벌점 팩터를 결정할 때에 고려되면, 다른 설비들이 가능하다. 예를 들면, 세그먼트는 상기 운행 가능한 세그먼트를 따른 레퍼런스 위치 그리고 상기 폴리라인의 상기 표현, 또는 상기 세그먼트의 평균 위치를 나타내는 대표 위치 그리고 상기 폴리라인의 상기 표현 사이의 거리를 기초로 하는 정도로 벌점이 부여될 수 있다.

운행 가능 세그먼트, 또는 그 운행 가능 세그먼트 상의 위치, 그리고 상기 전자 지도 상에 표현된 상기 폴리라인 사이의 거리는 어떤 적합한 방식으로 측정될 수 있다. 상기 거리는 상기 운행 가능 세그먼트, 또는 그 운행 가능 세그먼트 상의 위치, 그리고 상기 폴리라인의 가장 가까운 부분 사이에서 측정될 수 있다. 바람직하게는, 상기 거리는 상기 세그먼트 또는 그 세그먼트의 근사, 또는 상기 세그먼트 상의 위치 또는 그것의 근사를 상기 폴리라인의 상기 표현 상으로 투사한 것이다.

세그먼트에 대해 또는 상기 세그먼트를 따른 위치에 대해 적합한 경우에 벌점 팩터를 결정하는 것은 상기 세그먼트나 그 세그먼트 상의 위치 그리고 상기 폴리라인 사이의 거리에만 종속할 수 있으며, 또는 추가적인 팩터들을 고려할 수 있다. 운행 가능한 세그먼트에 대한 벌점 팩터는 상기 폴리라인의 해상도의 레벨 또는 적어도 그것의 일부에 의해 영향을 받을 수 있다. 바람직하게는 상기 벌점 팩터가 더 커지면, 상기 폴리라인의 해상도도 더 커진다. 상기 폴리라인의 해상도의 레벨을 표시하는 한 팩터는 상기 폴리라인의 전체 길이에 대한 상기 폴리라인의 개별 세그먼트들의 길이이다. 몇몇의 실시예들에서 세그먼트에 대한 벌점 팩터는 상기 운행 가능한 세그먼트에 근접한 상기 폴리라인의 세그먼트의 길이에 의해 영향을 받는다. 상기 운행 가능한 세그먼트에 근접한 상기 폴리라인의 세그먼트는, 상기 운행 가능한 세그먼트, 또는 그 위의 위치 그리고 상기 폴리라인 사이의 거리가 결정되는 것에 관련된 세그먼트인 것이 바람직하다. 예를 들면, 세그먼트, 또는 그 위의 위치 그리고 상기 폴리라인의 상기 표현 사이의 거리가 상기 세그먼트, 그 위의 위치의 투사, 그리고 상기 폴리라인을 기반으로 하는 실시예들에서, 상기 세그먼트, 또는 그 위의 위치에 대한 벌점 팩터는 상기 세그먼트나 위치가 그 위로 투사되는 상기 폴리라인의 세그먼트의 길이를 추가로 고려할 수 있다. 몇몇의 실시예들에서, 운행 가능한 세그먼트 또는 그 위의 위치에 대한 벌점 팩터는 상기 폴리라인의 세그먼트, 예를 들면, 폴리라인에 근접한 세그먼트의 길이에 역으로 관련된다. 그래서, 상기 세그먼트가 상대적으로 길어서, 적어도 그 부분에서 상기 폴리라인의 거친 해상도를 나타내는 경우에, 상기 벌점 팩터는 상대적으로 짧은 폴리라인 세그먼트의 경우보다는 더 작을 것이다. 이 방식에서, 상기 폴리라인의 이런 부분들에는 더 작은 가중치가 주어지며, 그래서 상기 생성된 경로가 더 거친 해상도의 폴리라인이나 그 폴리라인의 일부에게로, 더욱 정밀한 해상도의 폴리라인이나 그 폴리라인의 일부에 관하여 동일한 정도로, 끌려가지 않도록 한다.

몇몇의 실시예들에서, 내비게이션 세그먼트에 대한 상기 벌점 팩터는 상기 폴리라인의 말단에 대한 상기 세그먼트의 근접함에 의해 영향을 받을 수 있다. 몇몇의 실시예들에서, 상기 폴리라인의 말단들에 더욱 가까운 운행 가능한 세그먼트들에 적용된 벌점 팩터들은 상기 폴리라인의 중간에 더 가까운 운행 가능한 세그먼트들에 적용된 것보다 상대적으로 더 작다. 그래서, 상기 폴리라인으로부터 동일한 거리에 대해서, 예를 들면, 말단 세그먼트인 상기 폴리라인의 세그먼트 상의로의 투사를 구비한, 또는 상기 폴리라인의 말단 세그먼트로부터 주어진 개수의 세그먼트들 내의, 또는 상기 폴리라인의 말단의 주어진 거리 내에 있는, 상기 폴리라인의 말단에 더 가까운 운행 가능한 세그먼트는 상기 폴리라인의 중간으로 향하는 것보다 더 작은 벌점 팩터를, 예를 들면, 말단으로 향하는 것으로 고려되지 않는 것보다 더 작은 벌점 팩터를 수신할 것이다. 이것은 상기 폴리라인으로의 그 폴리라인의 말단들로 향하는 더 약한 끌어당기는 힘이라는 결과가 될 수 있으며, 예를 들면, 상기 폴리라인이 이 포인트들 사이에서 정밀하게 확장되지 않는 경우에, 생성된 경로로 하여금 재구축될 경로를 위해 특정된 제1 로케이션 및 제2 로케이션으로 돌아가는 것을 허용한다.

세그먼트와 상기 폴리라인 사이의 거리에 기초한 정도로 상기 세그먼트가 벌점을 부여받는 바람직한 경우들에서, 상기 폴리라인은 자석으로서 행동할 수 있으며, 상기 생성된 경로를 거꾸로 상기 폴리라인의 상기 표현을 향하여 끌어당기지만, 상기 폴리라인으로부터의 거리에 따라서 증가하게 정도로 끌어 당기지는 않는다. 그래서, 상기 폴리라인으로부터 아주 더 먼 거리에 있는 세그먼트들은 더 가깝게 있는 세그먼트들보다 아주 더 큰 정도로 벌점을 부여받을 것이다.

상기 운행 가능한 네트워크를 통해 생성된 상기 경로는, 예를 들면, 통상적인 경로 설정 엔진을 이용하여 표준의 방식으로 생성될 수 있을 것이지만, 추가적으로 상기 폴리라인 데이터를 고려한다. 그래서, 보통의 경로 계획 선호들 또는 세팅들이 유지될 수 있으며, 상기 폴리라인 데이터는, 예를 들면, 더 멀리에 있는 것들보다 더 많이 선호되는 상기 폴리라인에 더 가까운 세그먼트들의 결과를 가져오기 위해 사용되는 추가의 입력을 제공한다. 몇몇의 실시예들에서, 재구축될 경로가 제1 로케이션 및 제2 로케이션 사이에 확장되는 그런 제1 로케이션 및 제2 로케이션을 나타내는 데이터가 추가적으로 사용될 수 있다. 이것은, 상기 폴리라인이 그 자체로는 그런 로케이션들 사이에서 확장되지 않는 경우에 적절하다. 상기 제1 로케이션 데이터 및 제2 로케이션 데이터는, 예를 들면, 내비게이션 디바이스에 의해, 예를 들면, 폴리라인 데이터와 함께 수신될 수 있으며, 또는 그렇지 않다면, 예를 들어, 재구축될 상기 경로가 내비게이션 디바이스의 요청 시에 생성된 경우에, 그 내비게이션 디바이스에 알려질 수 있을 것이다. 상기 방법은 경로 재구축에서 사용하기 위해 상기 폴리라인을 상기 제1 위치 및 제2 위치로 확장하는 단계를 포함할 수 있다.

상기 폴리라인 데이터를 이용하여 상기 전자 지도에 의해 표현된 상기 운행 가능한 네트워크를 통해 생성된 상기 경로는 제1 위치 및 제2 위치 사이에서의 경로이다. 상기 제1 경로 및 제2 경로는 상기 폴리라인 데이터에 대한 참조에 의해 바람직하게 결정된다. 상기 경로는 상기 운행 가능한 네트워크의 운행 가능한 세그먼트들을 통과하는 비용에 기반하여 바람직하게 생성된다. 운행 가능한 세그먼트를 통과하는 상기 비용은 비용 함수를 이용하여 결정될 수 있다. 적합한 비용 함수들은 당 기술 분야에 잘 알려져 있다. 세그먼트를 통과하는 비용은 그 세그먼트와 연관된 하나 또는 그 이상의 속성들을 기초로 하여 결정될 수 있다. 바람직하게는, 상기 경로는 상기 운행 가능한 네트워크를 통한 최소 비용 경로이다. 최소 비용 경로는 상기 운행 가능한 네트워크의 세그먼트들을 통과하는 것과 연관된 비용을 최소하하는 것을 기초로 할 수 있으며, 그 비용은 적합한 비용 함수를 이용하여 결정되며, 즉, 이는 더 낮은 비용은 특히 바람직한 것으로 간주되는 속성을 가진 세그먼트들과 연관되며, 또는 더 높은 비용은 바람직하지 않은 것으로 간주된 세그먼트들과 연관되는 결과가 된다. 예를 들면, 상기 비용 함수는, 예를 들면, 사용자 입력을 기초로 하여 적절하게 선택될 수 있으며, 최단 경로, 가장 빠른 경로, 가장 생태학적인 경로 등인 최소 비용 경로의 결과를 가져온다.

상기 폴리라인에 아주 근접한 세그먼튿들이 경로 생성의 목적들을 위해 바람직하게 선호되는 바람직한 실시예들에서, 상기 세그먼트들은 경로 생성 동안에 고려된 상기 네트워크의 세그먼트들을 통과하는 것에 연관된 각자의 비용들의 조작 (manipulation)에 의해 바람직하게 선호된다. 이것은, 세그먼트의 상기 폴리라인으로의 근접함을 기초로 하는 상기 세그먼트를 위한 비용 팩터 그리고/또는 상기 세그먼트의 상기 폴리라인으로의 근접함을 기반으로 하는 상기 세그먼트에 대한 비용 팩터에 적어도 관련하여 더 높은 비용을 다른 세그먼트들에게 제공함에 의해서 그 다른 세그먼트들에게 벌점을 부여하는 것에 적어도 관련하여, 다른 세그먼트들보다 상대적으로 더 낮은 비용으로 선호되는 세그먼트들을 제공함에 의해 달성될 수 있다. 벌점 팩터를 세그먼트들에 적용하여 세그먼트들이 벌점을 부여받는, 위에서 설명된 바람직한 실시예들에서, 경로 생성에 있어서 고려되는 상기 세그먼트를 통과하는 것과 연관된 비용 팩터를 제공하기 위해, 그리고 상기 세그먼트의 상기 폴리라인으로의 근접함을 기초로 하는 상기 비용 팩터를 제공하기 위해 상기 벌점 팩터는 바람직하게 사용된다. 바람직하게는 상기 벌점 팩터가 더 커지면, 그 벌점 팩터를 기반으로 하는 비용 팩터도 더 커진다. 상기 벌점 팩터는 상기 세그먼트의 상기 폴리라인으로의 근접함을 기초로 하는 상기 세그먼트를 통과하기 위해 비용 팩터를 제공함에 있어서 직접적으로 또는 간접적으로 사용될 수 있다. 세그먼트의 폴리라인으로의 근접함을 기초로 하는 상기 비용 팩터는, 예를 들어, 최소 비용 경로를 획득하기 위해 경로 생성 프로세스에서 사용되는 세그먼트를 통과하기 위한 전체적인 비용을 획득하는데 있어서 사용될 수 있다. 상기 비용 팩터는 상기 세그먼트를 통과하기 위한 전체적인 비용을 제공하기 위해 비용 함수에서 사용될 수 있다. 바람직하게는, 상기 비용 팩터는 상기 세그먼트를 통과하기 위한 전체적인 비용을 획득하기 위해 사용되는 상기 운행 가능한 세그먼트와 연관된 복수의 비용 팩터들 중 하나이다. 이 방식에서, 경로 생성은 세그먼트들의 상기 폴리라인으로의 근접성과 상기 폴리라인에 대체적으로 대응하는 경로를 획득하기 위한 다른 팩터들과의 균형을 맞출 수 있지만, 이는 다른 선호들 등을 또한 고려할 수 있다. 세그먼트들과 연관된 다른 이용 팩터(들)는 상기 세그먼트들의 하나 또는 그 이상의 속성들을 기초로 한다. 고려될 수 있을 세그먼트들과 연관된 속성들은 상기 세그먼트들의 길이, 통행 시각, 통과의 평균 속도, 곡률 또는 연로 소모를 포함한다.

몇몇의 바람직한 실시예들에서, 운행 가능한 네트워크를 통해 경로를 생성하는 단계는 "라이브 (live)" 데이터를 이용하여 수행된다. 본 발명의 모습들이나 실시예들 중 어느 하나에 따라서 여기에서 사용된 라이브 데이터는, 상대적으로 현재이며 그리고 상기 네트워크 내 상대적인 상태들에 대한 표시를 제공하는 데이터를 언급하는 것이다. 상기 라이브 데이터는 지난 30분, 15분, 10분 또는 5분 내의 상태들을 언급하는 것이 일반적이다. "이력적인" 데이터는 대조적으로 라이브가 아닌 데이터를 언급하는 것이며, 과거에 또는 최근의 (아마도 대략적으로 지난 5분, 10분, 15분 또는 30분 내) 상기 네트워크의 상태들을 직접적으로 반영하지 않는 데이터를 언급하는 것이다.

본 발명에 따라서 사용될 수 있을 상기 라이브 데이터는 현재의 상태들 하에서 상기 운행 가능한 네트워크에서의 경로 선택에 영향을 줄 수 있는 어떤 팩터 또는 팩터들을 나타내는 라이브 데이터일 수 있다. 상기 팩터 또는 팩터들은 상기 운행 가능한 네트워크의 세그먼트들을 따른 트래픽의 흐름에 영향을 줄 임의 팩터들일 수 있다. 상기 라이브 데이터는 라이브 트래픽 데이터, 도로 폐쇄들을 나타내는 데이터 또는 도로 공사들을 나타내는 데이터 중 하나 또는 그 이상을 포함할 수 있다. 바람직한 실시예들에서, 상기 라이브 데이터는 하나 또는 그 이상의 서버들과 같은 외부의 소스로부터의 경로 구축을 수행하는 내비게이션 디바이스에 의해 수신되었던 데이터이다. 라이브 데이터의 사용은 미리-계획된 경로를 재구축하는 환경에서 특히 유용하다. 이것은, 예를 들면, 외부의 경로 계획 시스템에 의해 경로가 미리-계획되는 것을 가능하게 하며, 반드시 출발 직전일 필요가 없으며, 네트워크 상에서 라이브 상태들을 고려하는 방식으로 예정된 출발 시각에 또는 그 출발 시각 근방에 수행되는 상기 내비게이션 디바이스에 의한 재구축을 구비한다. 예를 들면, 상기 폴리라인에 가까운 세그먼트들에 영향을 주는 혼잡 또는 도로 폐쇄가 있을 수 있다. 상기 경로 설정 엔진은 그러면 통상적인 경로 계획 동작에서처럼 그런 세그먼트들 주위로 경로를 설정할 수 있을 것이다.

비록 바람직한 실시예들에서 상기 폴리라인 데이터를 이용하여 상기 경로를 생성하는 상기 방법이 상기 폴리라인에 아주 근접한 상기 전자 지도의 세그먼트들을 선호하는 것을 수반하지만, 상기 폴리라인은 다른 방식들로 사용될 수 있다. 이런 기술들은, 재구축될 경로가 이동될 미리-계획된 경로인 실시예들에 특히 적절하다. 이것은 상기 미리-계획된 경로에 대체적으로 같은 모양이 되는 경로를 생성하기 위한 능력을 제공하지만, 다른 경로 계획 선호들, 그리고 바람직하게는 라이브 데이터가 고려되는 것을 가능하게 한다. 재구축될 상기 경로가 이전에 이동했던 경로인 실시예들에서, 상기 폴리라인에 의해 표현된 경로를 더욱 면밀하게 복제하기 위해 시도하는 방식으로 경로 재구축이 진행될 수 있다. 상기 방법은 상기 폴리라인의 각 세그먼트를 상기 전자 지도의 운행 가능한 세그먼트에 매치하기 위해 시도하는 단계를 포함할 수 있다. 상기 방법은 상기 전자 지도를 참조함으로써 상기 재구축된 경로를 나타내는 정보를 획득하고 저장하는 단계를 포함할 수 있다. 상기 데이터는 세그먼드 식별자 또는 유사한 것의 목록의 모습일 수 있다.

본 발명의 모습들이나 실시예들 중 어느 하나에서의 본 발명의 방법들은 재구축될 하나 또는 그 이상의 경로들에 관련하여 수행될 수 있다. 몇몇의 실시예들에서, 상기 방법들은 복수의 그런 경로들에 관련하여 수행된다.

상기 폴리라인에 의해 표현된 상기 경로의 재구축을 제공하는 상기 생성된 경로는 어떤 원하는 방식으로 사용될 수 있을 것이다. 상기 방법은 상기 생성된 경로를 표시하는 데이터를 저장하고 그리고/또는 상기 경로를 사용자에게 출력하는 단계들을 포함할 수 있다. 상기 방법은 다음의 것들 중 하나 또는 그 이상을 수행하는 단계로 확장될 수 있다: 상기 생성된 경로를 나타내는 데이터를 저장하는 단계; 상기 생성된 경로를 디스플레이하는 단계; 그리고 상기 생성된 경로를 따라서 사용자를 안내하기 위한 내비게이션 지시들의 세트를 출력하는 단계. 상기 생성된 경로를 나타내는 데이터가 저장되는 실시예들에서, 그 데이터는 바람직하게는 상기 전자 지도 데이터와 연관하여 저장된다. 유사하게, 상기 생성된 경로는 디스플레이하는 단계는 상기 경로를 상기 전자 지도 상에 디스플레이하는 단계를 포함하는 것이 바람직하다.

하나 또는 그 이상의 세그먼트들에 관련하여 "연관된다"의 어구는 데이터 저장 로케이션들에 관해 어떤 특별한 제한을 필요로 한다고 해석되지 않아야 한다는 것에 유의해야 한다. 상기 어구는 상기 특징들이 세그먼트에 관련하여 식별 가능하다는 것을 필요로 할 뿐이다. 그러므로, 연관은 예를 들면 잠재적으로는 원격 서버에 위치한 사이드 파일을 참조하여 달성될 수 있을 것이다.

여기에서 사용된 "세그먼트 (segment)"의 용어는 당 기술 분야에서 그 용어의 일상적인 의미를 가진다. 세그먼트는 두 개의 노드들을 연결하는 운행 가능한 링크, 또는 그것의 일부일 수 있다. 본 발명의 실시예들이 도로 세그먼트들을 참조하여 설명되었지만, 본 발명은 통로, 강, 운하, 자전거 도로, 견인 통로, 철로, 또는 유사한 것의 세그먼트들과 같은 다른 운행 가능한 세그먼트들에도 또한 적합하다는 것을 깨달아야 한다. 참조의 편이를 위해서, 이것들은 도로 세그먼트로 공통적으로 언급되지만, "도로 세그먼트"에 대한 어떤 참조도 "운행 가능한 세그먼트" 또는 그런 세그먼트들의 어떤 특정 유형 또는 유형들에 대한 참조로 대체될 수 있다.

본 발명에 따른 방법들 중 어느 것도 소프트웨어, 예를 들면, 컴퓨터 프로그램들을 이용하여 적어도 부분적으로 구현될 수 있다. 본 발명은 그래서 본 발명의 모습들 또는 실시예들 중 어느 것에 따른 방법을 수행하거나, 또는 내비게이션 디바이스 및/또는 서버로 하여금 본 발명의 모습들 또는 실시예들 중 어느 것에 따른 방법을 수행하도록 하기 위해 실행 가능한 컴퓨터 판독가능 지시들을 포함하는 컴퓨터 프로그램으로 또한 확장된다.

본 발명은, 데이터 프로세싱 수단을 포함하는 시스템이나 장치를 작동시키기 위해 사용될 때에, 상기 데이터 프로세싱 수단과 함께 상기 장치나 시스템이 본 발명의 방법들의 단계들을 수행하도록 하는 그런 소프트웨어를 포함하는 컴퓨터 소프트 캐리어로 따라서 확장된다. 그런 컴퓨터 소프트웨어 캐리어는 ROM 칩, CD ROM 또는 디스크와 같은 비 일시적인 물리적 저장 매체일 수 있으며, 또는 와이어를 통한 전기적인 신호, 광학 신호 또는 위성와 같은 라디오 신호 또는 유사한 것과 같은 신호일 수 있다. 본 발명은 기계에 의해 독출될 때에 그 기계로 하여금 본 발명의 실시예들이나 모습들 중 어느 것의 방법에 따라 동작하도록 하는 지시들을 포함한 기계 판독 가능 매체를 제공한다.

구현에 무관하게, 본 발명에 따라 사용된 내비게이션 장치는 프로세서, 메모리, 및 상기 메모리 내 저장된 디지털 지도를 포함할 수 있다. 상기 프로세서 및 메모리는 소프트웨어 운영 시스템이 설립될 수 있을 실행 환경을 제공하기 위해 협응한다. 제어될 상기 장치의 기능성을 가능하게 하기 위해, 그리고 다양한 다른 기능을 제공하기 위해 하나 또는 그 이상의 소프트웨어 프로그램들이 제공될 수 있다. 본 발명의 내비게이션 장치는 GPS (Global Positioning System), 신호 수신 및 프로세싱 기능성과 같은 GNSS (Global Navigation Satellite System)를 바람직하게 포함할 수 있다. 상기 장치는 하나 또는 그 이상의 출력 인터페이스들을 포함할 수 있으며, 그 출력 인터페이스에 의해 정보가 사용자에게 중계될 수 있다. 상기 출력 인터페이스(들)는 시각적인 디스플레이에 추가로 청각적인 출력을 위한 스피커를 포함할 수 있다. 상기 장치는 입력 인터페이스들을 포함할 수 있으며, 이는 상기 장치의 온/오프 동작 또는 다른 특징들을 제어하기 위한 하나 또는 그 이상의 물리적인 버튼들을 포함한다.

다른 실시예들에서, 상기 내비게이션 장치는 특정 내비게이션 디바이스의 일부를 형성하지 않는 프로세싱 디바이스의 적용에 의해 적어도 부분적으로 구현될 수 있다. 예를 들어, 본 발명은 내비게이션 소프트웨어를 실행하도록 구성된 적합한 컴퓨터 시스템을 이용하여 구현될 수 있다. 상기 시스템은 모바일 또는 휴대용 컴퓨터 시스템, 예를 들어, 모바일 전화기 또는 랩탑일 수 있으며, 또는 데스크탑 시스템일 수 있다.

명시적으로 선언되지 않은 경우에는, 본 발명의 모습의 어느 하나에서의 본 발명은 본 발명의 실시예들이나 모습들에 관하여 설명된 특징들의 어느 하나 또는 모두를, 그 특징들이 상호 배타적이지 않은 정도까지 포함할 수 있다는 것이 인정될 것이다. 특히, 동작들의 다양한 실시예들이 상기 장치에 의해 그리고 상기 방법에서 실행될 수 있는 것으로 설명되었지만, 이 동작들의 어느 하나 또는 그 이상 또는 모두는 원하는대로 그리고 적절하게 어떤 조합으로라도 상기 방법에서 그리고 상기 장치에 의해 수행될 수 있을 것이라는 것이 인정될 것이다.

이 실시예들의 유리함들이 이제 제시되며, 그리고 이 실시예들 각각의 추가의 상세 내용들 및 특징들은 동반 독립 청구항들에서 그리고 다음의 상세한 설명의 다른 곳에서 정의된다.

본 발명의 효과는 본 명세서의 해당되는 부분들에 개별적으로 명시되어 있다.

본 발명의 실시예들이 동반된 도면들을 참조하여, 예시의 목적으로만 이제 설명될 것이다.
도 1은 내비게이션 디바이스에 의해 사용 가능한 글로벌 포지셔닝 시스템 (GPS)의 예시적인 일부의 개략적인 도시이다.
도 2는 내비게이션 디바이스와 서버 사이의 통신을 위한 통신 시스템의 개략적인 예시이다.
도 3은 도 2의 내비게이션 디바이스 또는 다른 적합한 내비게이션 디바이스의 전자 컴포넌트들의 개략적인 예시이다.
도 4는 내비게이션 디바이스를 마운트하고 그리고/또는 도킹하는 설비의 개략적인 도면이다.
도 5는 몇몇의 실시예들에 따른 본 발명의 방법들을 구현하기 위해 사용될 수 있을 시스템을 도시한다.
도 6은 몇몇의 실시예들에 따른 방법의 단계들을 요약한 흐름도이다.
도 7은 몇몇의 실시예들에 따른 방법의 단계들을 요약한 흐름도이다.
도 8a는 본 발명의 일 실시예를 구현하기 위해 사용될 수 있을 타임-스탬프 GPS 데이터의 세트를 도시한다.
도 8b는 운행 가능한 네트워크를 통해 도 8a의 타임-스탬프 GPS 데이터에 의해 기술된 경로의 재구축을 도시한다.
도 8c는 상기 재구축된 경로에 대응하는 전자 지도의 세그먼트들을 도시한다.

본 발명의 실시예들은 휴대용 내비게이션 디바이스 (Portable Navigation Device (PND))를 특히 참조하여 이제 설명될 것이다. 그러나, 본 발명의 교시들은 PND들로 한정되지 않으며, 대신에 경로 계획 및 내비게이션 기능성을 제공하기 위해서 휴대 방식으로 내비게이션 소프트웨어를 실행하도록 구성된 임의 유형의 프로세싱 디바이스에 범용적으로 적용 가능하다는 것을 기억해야 한다. 그러므로, 본원의 맥락에서, 내비게이션 디바이스는 임의 유형의 경로 계획 및 내비게이션 디바이스를 (제한없이) 포함하는 것으로 의도된 것으로, 이는 그 디바이스가 PND, 자동차와 같은 차량, 또는 실제로 휴대용 컴퓨팅 자원, 예를 들면, 경로 계획 및 내비게이션 소프트웨어를 실행하는 휴대용 개인용 컴퓨터 (PC), 모바일 전화기 또는 개인용 디지털 보조기 (Personal Digital Assistant (PDA))로서 구현되는가의 여부에 무관한 것이라는 것이 결론이 된다.

또한, 본 발명의 실시예들은 도로 세그먼트들을 참조하여 설명된다. 본 발명이 보도, 강, 운하, 싸이클 경로, 예인선 경로, 철로 등의 세그먼트들과 같은 다른 운행 가능한 세그먼트들에 또한 적용 가능할 것이라는 것이 실감되어야 한다.

본 발명의 교시들이 한 포인트로부터 다른 포인트로 어떻게 운행하는가에 관한 지시들을 사용자가 찾지 않고, 다만 주어진 위치를 고려하여 제공되기를 바라는 환경들에서까지 유용함을 가진다는 것이 또한 다음의 내용으로부터 또한 명백할 것이다. 그런 환경들에서, 사용자에 의해 선택된 "목적지" 위치는 그 사용자가 운행하는 것을 시작하기를 바라는 대응하는 시작 위치를 가질 필요가 없으며, 그리고 그 결과로, "목적지" 위치 또는 실제 "목적지" 뷰 (view)를 여기에서 참조한다는 것은 경로를 생성하는 것이 본질적이며, 그 "목적지"로의 이동이 발생해야만 하며, 또는 실제로 목적지의 존재는 대응하는 시작 위치의 목적지를 필요로 한다는 것을 의미하는 것으로 해석되지 않아야 한다

상기의 조건들을 염두에 두면, 도 1의 글로벌 포지셔닝 시스템 (Global Positioning System (GPS)) 및 유사한 것은 다양한 목적들을 위해 사용된다. 일반적으로, 상기 GPS는 연속적인 위치, 속도, 시각, 및 몇몇의 예들에서의 무제한의 사용자들을 위한 방향 정보를 결정할 수 있는 위성-라디오 기반의 내비게이션 시스템이다. 이전에 NAVSTAR로 알려진 상기 GPS는 극도로 정밀한 궤도들에서 지구의 궤도에 진입한 복수의 위성들을 편입한다. 이런 정밀한 궤도들을 기초로 하여, GPS 위성들은 자신들의 위치를 임의 개수의 수신 유닛들에게 GPS 데이터로서 중계할 수 있다. 그러나, 글로벌 포지셔닝 시스템들은 GLOSNASS, 유럽의 갈릴레오 (Galileo) 포지셔닝 시스템, COMPASS 포지셔닝 시스템 또는 IRNSS (Indian Regional Navigational Satellite System)처럼 사용될 수 있을 것이라는 것이 이해될 것이다.

GPS 데이터를 수신하기 위해 특별하게 장착된 디바이스가 GPS 위성 신호들을 위한 라디오 주파수들을 스캐닝하는 것을 시작할 때에 상기 GPS 시스템이 구현된다. GSP 위성으로부터 라디오 신호를 수신하면, 상기 디바이스는 복수의 상이한 전통적인 방법들을 통해서 그 위성의 정밀한 위치를 판별한다. 상기 디바이스는 대부분의 경우들에서 적어도 세 개의 상이한 위성 신호들을 획득할 때까지 신호들을 계속해서 스캐닝할 것이다 (정상적이지는 않지만, 다른 삼각 측량 기술들을 이용하여 단 두 개의 신호들을 이용하여 위치가 판별될 수 있다는 것에 유의한다). 기하학적인 삼각 측량을 구현하면, 수신기는 상기 위성들에 상대적인 자신의 2차원적인 위치를 판별하기 위해 상기 3개의 알려진 위치들을 활용한다. 이것은 알려진 방식으로 행해질 수 있다. 추가적으로, 네 번째 위성 신호를 획득하는 것은 상기 수신 디바이스가 알려진 방식으로 동일한 기하학적 계산에 의해 자신의 3차원적인 위치를 계산하는 것을 가능하게 한다. 상기 위치 및 속도 데이터는 무제한 수의 사용자들에 의해 연속적인 것에 근거하여 실시간으로 업데이트될 수 있다.

도 1에서 보이는 것처럼, 상기 GPS 시스템 (100)은 지구 (104) 주위에 궤도를 선회하는 복수의 위성들 (102)을 포함한다. GPS 수신기 (106)는 GPS 데이터를 여러 복수의 위성들 (102)로부터 확산 스펙트럼 GPS 위성 데이터 신호들로서 수신한다. 상기 확산 스펙트럼 데이터 신호들 (108)은 각 위성 (102)으로부터 계속해서 전송되며, 전송된 상기 확산 스펙트럼 데이터 신호들 (108) 각각은 상기 데이터 스트림이 비롯된 특별한 위성 (102)을 식별하는 정보를 구비한 데이터 스트림을 포함한다. 상기 GPS 수신기 (106)는 2차원 위치를 계산할 수 있기 위해서 적어도 세 개의 위성들 (102)로부터의 확산 스펙트럼 데이터 신호들을 일반적으로 필요로 한다. 네 번째 확산 스펙트럼 데이터 신호를 수신하는 것은 상기 GPS 수신기 (106)가 알려진 기술을 이용하여 3차원적인 위치를 계산하는 것을 가능하게 한다.

도 2로 돌아가서, GPS 수신기 디바이스 (106)를 포함하거나 그 디바이스에 연결된 내비게이션 디바이스 (즉, PND)는 디지털 접속, 예를 들면, 알려진 블루투스 기술을 경유한 디지털 접속을 설립하기 위해서 필요하다면 모바일 디바이스 (도시되지 않음), 예를 들면, 모바일 전화기, PDA 및/또는 모바일 전화기 기술을 구비한 임의 디바이스를 경유하여 "모바일" 또는 원거리 통신 네트워크의 네트워크 하드웨어와의 데이터 세션을 설립할 수 있다. 그 이후에, 네트워크 서비스 제공자를 통해, 상기 모바일 디바이스는 (예를 들면 인터넷을 통해서) 서버 (150)와 네트워크 접속을 설립할 수 있다. 그처럼, "모바일" 네트워크 접속은 상기 내비게이션 디바이스 (200) (이것은 단독으로 이동하고 그리고/또는 차량 내에 있을 때에 이동성일 수 있으며, 그리고 종종 이동성이다)와 상기 서버 (150) 사이에 설립되어, 정보를 위한 "실시간"의 또는 적어도 매우 "최신"의 게이트웨이를 제공한다.

(서비스 제공자를 경유한) 상기 모바일 디바이스 그리고 상기 서버 (150)와 같은 다른 디바이스 사이에서 예를 들면 인터넷을 이용하여 네트워크 접속을 설립하는 것은 알려진 방식으로 행해질 수 있다. 이런 면에서, 임의 개수의 적절한 데이터 통신 프로토콜들, 예를 들면, TCP/IP 계층 프로토콜이 사용될 수 있다. 또한, 상기 모바일 디바이스는 CDMA2000, GSM, IEEE 802.11 a/b/c/g/n 등과 같은 임의 개수의 통신 표준들을 활용할 수 있다.

그래서, 인터넷 접속이 활용될 수 있으며, 이는 데이터 접속을 경유하여, 예를 들면, 상기 내비게이션 디바이스 (200) 내 모바일 전화기들 또는 모바일 전화 기술을 경유하여 활용될 수 있을 것라는 것을 알 수 있다.

비록 도시되지 않았지만, 상기 내비게이션 디바이스 (200)는 (안테나를 포함한, 예를 들면, 또는 옵션으로 상기 내비게이션 디바이스 (200)의 내부 안테나를 이용한) 그 내비게이션 디바이스 (200) 자신 내에 자기 자신의 모바일 전화기 기술을 물론 포함할 수 있을 것이다. 상기 내비게이션 디바이스 (200) 내 상기 모바일 전화 기술은 내부의 컴포넌트들을 포함할 수 있으며, 그리고/또는, 예를 들면, 필요한 모바일 전화 기술 및/또는 안테나가 완비된 삽입 가능한 카드 (예를 들면, 가입자 신원 모듈 (Subscriber Identity Module (SIM)) 카드)를 포함할 수 있다. 그처럼, 상기 내비게이션 디바이스 (200) 내 모바일 전화 기술은 모바일 디바이스의 접속과 유사한 방식으로, 예를 들면 인터넷을 경유하여 상기 내비게이션 디바이스 (200)와 상기 서버 (150) 사이에서의 네트워크 접속을 유사하게 설립할 수 있다

전화기 세팅들을 위해서, 블루투스 가능 내비게이션 디바이스는 모바일 전화기 모델들, 제조자 등의 변하는 스펙트럼과 올바르게 동작하기 위해 사용될 수 있을 것이며, 모델/제조자 특정 세팅들은 예를 들면 상기 내비게이션 디바이스 (200) 상에 저장될 수 있을 것이다. 이 정보를 위해 저장된 상기 데이터는 업데이트될 수 있다.

도 2에서, 상기 내비게이션 디바이스 (200)는 임의 개수의 상이한 설비들에 의해 구현될 수 있는 일반적인 통신 채널 (152)을 경유하여 상기 서버 (150)와 통신하는 것으로 도시된다. 상기 통신 채널 (152)은 상기 내비게이션 디바이스 (200)와 상기 서버 (150)를 연결시키는 전파 매체 (propagating medium) 또는 경로를 일반적으로 나타낸다. 상기 서버 (150) 및 상기 내비게이션 디바이스 (200)는 상기 통신 채널 (152)을 경유한 접속이 상기 서버 (150)와 상기 내비게이션 디바이스 (200) 사이에서 설립될 때에 통신할 수 있다 (그런 접속은 모바일 디바이스를 경유한 데이터 접속, 인터넷을 경유한 개인용 컴퓨터를 통한 직접 접속 등일 수 있다는 것에 유의한다).

상기 통신 채널 (152)은 특별한 통신 기술로 제한되지 않는다. 추가로, 상기 통신 채널 (152)은 단일의 통신 기술로 제한되지 않는다; 즉, 상기 채널 (152)은 다양한 기술을 사용한 여러 통신 링크들을 포함할 수 있다. 예를 들면, 상기 통신 채널 (152)은 전기적인, 광학적인, 그리고/또는 전자기적인 통신들 등을 위한 경로를 제공하기 위해 적응될 수 있다. 그처럼, 상기 통신 채널 (152)은 다음의 것들 중 하나 또는 그것들의 조합을 포함하지만, 그것들로 제한되지는 않는다: 전기적 회로들, 와이어들 및 동축 케이블들과 같은 전기적인 도체들, 광섬유 케이블들, 컨버터들, 라디오-주파수 (RF) 파형들, 대기 (atmosphere), 자유 공간 등. 또한 상기 통신 채널 (152)은, 예를 들면, 라우터들, 리피터들, 버퍼들, 전송기들, 및 수신기들과 같은 중간의 디바이스들을 포함할 수 있다.

한 예시적인 설비에서, 상기 통신 채널 (152)은 전화 네트워크 및 컴퓨터 네트워크를 포함한다. 또한, 상기 통신 채널 (152)은 무선 통신, 예를 들면, 적외선 통신, 마이크로파 주파수 통신 등과 같은 라디오 주파수 통신을 수용할 수 있을 것이다. 추가로, 상기 통신 채널 (152)은 위성 통신을 수용할 수 있다.

상기 통신 채널 (152)을 통해 전송된 통신 신호들은 주어진 통신 기술을 위해 필요한 또는 소망될 수 있을 신호들을 포함하지만, 그것들로 한정되지는 않는다. 예를 들면, 상기 신호들은 TDMA (Time Division Multiple Access), FDMA (Frequency Division Multiple Access), CDMA (Code Division Multiple Access), GSM (Global System for Mobile Communications), GPRS (General Packet Radio Service) 등과 같은 셀룰러 통신에서 사용되기 위해 적응될 수 있을 것이다. 디지털 신호 및 아날로그 신호 둘 모두는 상기 통신 채널 (152)을 통해 전송될 수 있다. 이 신호들은 상기 통신 기술을 위해 원하는대로 변조되고, 암호화되고 그리고/또는 압축된 신호들일 수 있다.

상기 서버 (150)는, 도시되지 않을 수 있을 다른 컴포넌트들에 추가로, 프로세서 (154)를 포함하며, 이 프로세서는 메모리 (156)에 작동적으로 연결되며 그리고 유선의 또는 무선의 접속 (158)을 경유하여 대용량 데이터 저장 디바이스 (160)에 더 작동적으로 연결된다. 상기 대용량 저장 디바이스 (160)는 내비게이션 데이터 및 지도 정보의 저장부를 포함하며, 그리고 상기 서버 (150)와는 분리된 디바이스일 수 있으며 또는 상기 서버 (150)에 통합될 수 있다. 상기 프로세서 (154)는 전송기 (162) 및 수신기 (164)에 작동적으로 더 연결되어, 통신 채널 (152)을 경유하여 내비게이션 디바이스 (164)에 정보를 전송하고 그 디바이스로부터 정보를 수신한다. 송신된 그리고 수신된 신호들은 데이터, 통신, 및/또는 다른 전파된 신호들을 포함할 수 있을 것이다. 상기 전송기 (162) 및 수신기 (164)는 내비게이션 시스템 (200)의 통신 설계에서 사용된 통신 기술 및 통신 요구사항들에 따라 설계되거나 선택될 수 있을 것이다. 또한, 상기 전송기 (162) 및 수신기 (164)의 기능들은 단일의 트랜시버로 조합될 수 있을 것이라는 것에 유의해야 한다.

위에서 언급된 것처럼, 상기 내비게이션 디바이스 (200)는 통신 채널 (152)을 통해 신호들 및/또는 데이터를 송신하고 수신하기 위해 전송기 (166) 및 수신기 (168)를 이용하여 상기 통신 채널 (152)을 통해 상기 서버 (150)와 통신하도록 구성될 수 있으며, 이 디바이스들은 서버 (150)가 아닌 디바이스들과 통신하기 위해 또한 사용될 수 있다는 것에 유의한다. 또한, 상기 전송기 (166) 및 수신기 (168)는 내비게이션 시스템 (200)을 위한 통신 설계에서 사용된 통신 기술 및 통신 요구사항들에 따라 설계되거나 선택될 수 있을 것이며 그리고 상기 전송기 (162) 및 수신기 (164)의 기능들은 도 2에 관련하여 위에서 설명된 것처럼 단일의 트랜시버로 조합될 수 있을 것이다. 물론, 상기 내비게이션 디바이스 (200)는 다른 하드웨어 및/또는 기능 파트들을 포함하며, 이것들은 본원에서 나중에 더욱 상세하게 설명될 것이다.

서버 메모리 (156) 내에 저장된 소프트웨어는 상기 프로세서 (154)를 위한 지시들을 제공하고 그리고 상기 서버 (150)가 내비게이션 디바이스 (200)에게 서비스들을 제공하도록 허용한다. 상기 서버 (150)에 의해 제공된 한 서비스는 내비게이션 디바이스 (200)로부터의 요청들을 프로세싱하고 그리고 대용량 데이터 저장부 (160)로부터 내비게이션 디바이스 (200)로 내비게이션 데이터를 전송하는 것을 포함한다. 상기 서버 (150)에 의해 제공될 수 있는 다른 서비스는 소망된 애플리케이션들을 위한 다양한 알고리즘들을 이용하여 상기 내비게이션 데이터를 프로세싱하고 그리고 이 계산들의 결과들을 상기 내비게이션 디바이스 (200)에게 송신하는 것을 포함한다.

상기 서버 (150)는 무선 채널을 경유하여 내비게이션 디바이스 (200)에 의해 액세스 가능한 데이터의 원격 소스를 구성한다. 상기 서버 (150)는 LAN (local area network), WAN (wide area network), VPN (virtual private network) 등에 위치한 네트워크 서버를 포함할 수 있다.

상기 서버 (150)는 데스크탑 또는 랩탑 컴퓨터와 같은 개인용 컴퓨터를 포함할 수 있으며, 그리고 상기 통신 채널 (152)은 상기 개인용 컴퓨터와 상기 내비게이션 디바이스 (200) 사이에 연결된 케이블일 수 있다. 대안으로, 개인용 컴퓨터는 상기 서버 (150)와 상기 내비게이션 디바이스 (200) 사이에서의 인터넷 접속을 설립하기 위해 상기 내비게이션 디바이스 (200)와 상기 서버 (150) 사이에 연결될 수 있다.

상기 내비게이션 디바이스 (200)는 정보 다운로드들을 경유하여 상기 서버 (150)로부터 정보를 제공받을 수 있으며, 이 정보 다운로드는 때때로 자동적으로 업데이트될 수 있을 것이며 또는 사용자가 상기 내비게이션 디바이스 (200)로부터 상기 서버 (150)로 접속시키면 자동적으로 업데이트될 수 있을 것이며 그리고/또는 예를 들면 무선 모바일 접속 디바이스 및 TCP/IP 접속을 경유하여 상기 서버 (150)와 내비게이션 디바이스 (200) 사이에서 만들어진 더욱 일정한 또는 빈번한 접속 시에 더욱 동적일 수 있을 것이다. 많은 동적인 계산들을 위해서, 서버 (150) 내 프로세서 (154)는 많은 프로세싱 필요성들을 처리하기 위해 사용될 수 있을 것이지만, 상기 내비게이션 디바이스 (200)의 프로세서 (도 2에는 도시되지 않음)는 때로는 서버 (150)로의 접속에 독립적으로 많은 프로세싱 및 계산을 또한 처리할 수 있다.

도 3을 참조하면, 상기 내비게이션 디바이스 (200)의 블록도는 상기 내비게이션 디바이스의 모든 컴포넌트들을 포함하는 것이 아니며, 많은 예시의 컴포넌트들을 대표하는 것일뿐이라는 것에 유의해야 한다. 상기 내비게이션 디바이스 (200)는 하우징 (도시되지 않음) 내에 위치한다. 상기 내비게이션 디바이스 (200)는, 예를 들면, 위에서 언급된 프로세서 (202)를 구비한 프로세싱 회로를 포함하며, 상기 프로세서 (202)는 입력 디바이스 (204) 및 디스플레이 디바이스, 예를 들면, 디스플레이 스크린 (206)에 연결된다. 비록 여기에서는 상기 입력 디바이스 (204)를 단수로 참조하지만, 통상의 지식을 가진 자는 상기 입력 디바이스 (204)가 키보드 디바이스, 음성 입력 디바이스, 터치 패널 및/또는 정보를 입력하기 위해 활용되는 어떤 다른 알려진 입력 디바이스를 포함하는 임의 개수의 입력 디바이스들을 대표한다는 것을 인정해야 한다. 유사하게, 상기 디스플레이 스크린 (206)은, 예를 들면, LCD (Liquid Crystal Display)와 같은 임의 유형의 디스플레이 스크린을 포함할 수 있다.

한 설비에서, 입력 디바이스 (204)의 한 모습, 터치 패널, 및 디스플레이 스크린 (206)은 통합된 입력 및 디스플레이 디바이스를 제공하기 위해 통합되며, 터치 패널 스크린을 통한 (직접 입력, 메뉴 선택 등을 경유한) 정보의 입력 및 정보의 디스플레이 둘 모두를 가능하게 하기 위해 터치패드 또는 터치스크린 입력 (도 4)를 포함하여, 사용자가 복수의 디스플레이 선택들 중 하나를 선택하거나 복수의 가상 또는 "소프트" 버튼들 중 하나를 활성화하기 위해 디스플레이 스크린 (206)의 일부만을 터치할 필요가 있도록 한다. 이런 면에서, 상기 프로세서 (202)는 상기 터치스크린과 함께 작동하는 그래픽 사용자 인터페이스 (GUI)를 지원한다.

상기 내비게이션 디바이스 (200)에서, 상기 프로세서 (202)는 입력 디바이스 (204)에 작동적으로 연결되어 참조번호 210의 접속을 경유하여 상기 입력 디바이스로부터 입력 정보를 수신할 수 있으며, 그리고 각자의 출력 접속들 (212)을 경유하여 상기 디스플레이 스크린 (206) 및 상기 출력 디바이스 (208) 중 적어도 하나에 작동적으로 연결되어 그것들에게 정보를 출력한다. 상기 내비게이션 디바이스 (200)는 출력 디바이스 (208), 예를 들면, 가청 출력 디바이스 (예를 들면, 라우드스피커)를 포함할 수 있다. 상기 출력 디바이스 (208)가 상기 내비게이션 디바이스 (200)의 사용자를 위해 들을 수 있는 정보를 생성할 수 있기 때문에, 입력 디바이스 (204)는 입력 음성 명령들을 마찬가지로 수신하기 위한 마이크로폰 및 소프트웨어를 포함할 수 있다는 것이 마찬가지로 이해되어야 한다. 또한, 상기 내비게이션 디바이스 (200)는 예를 들면 오디오 입력/출력 디바이스들과 같은 어떤 추가의 입력 디바이스 (204) 및/또는 어떤 추가의 출력 디바이스를 또한 포함할 수 있다.

상기 프로세서 (202)는 참조번호 216의 접속을 경유하여 메모리 (214)에 작동적으로 연결되며 그리고 참조번호 200의 접속을 경유하여 입력/출력 (I/O) 포트들 (218)로/로부터 정보를 수신/송신하도록 더 적응되며, 이 경우 상기 I/O 포트 (218)는 상기 내비게이션 디바이스 (200)에 외부인 I/O 디바이스 (222)에 연결 가능하다. 상기 외부 I/O 디바이스 (222)는 예를 들면 이어폰과 같은 외부의 청취 디바이스를 포함할 수 있을 것이지만, 그것으로 제한되지는 않는다. I/O 디바이스 (222)로의 접속은 핸드-프리 동작을 위한 그리고/또는 예를 들면 음성 활성 동작을 위한, 이어폰이나 헤드폰으로의 접속을 위한 그리고/또는 예를 들면 모바일 전화기로의 접속을 위한, 자동차 스테레오 유닛과 같은 어떤 다른 외부 디바이스로의 유선 또는 무선 접속일 수 있으며, 이 경우에 상기 모바일 전화기 접속은 예를 들면 상기 내비게이션 디바이스 (200) 및 상기 인터넷 또는 어떤 다른 네트워크 사이에서의 데이터 접속을 설립하기 위해, 그리고/또는 예를 들면 인터넷 또는 몇몇의 다른 네트워크를 경유하여 서버로의 접속을 설립하기 위해 사용될 수 있다.

상기 내비게이션 디바이스 (200)의 메모리 (214)는 (예를 들면, 프로그램 코드를 저장하기 위해서) 비-휘발성 메모리의 일부 그리고 (예를 들면 프로그램 코드가 실행될 때에 데이터를 저장하기 위해서) 휘발성 메모리의 일부를 포함한다. 상기 내비게이션 디바이스는 참조번호 230의 접속을 경유하여 프로세서 (202)와 통신하는 포트 (228)를 또한 포함하여, 탈부착 가능한 메모리 카드 (보통은 카드로 언급됨)가 상기 디바이스 (200)에 추가되는 것을 허용한다. 설명되는 본 실시예에서 상기 포트는 SD (Secure Digital) 카드가 추가될 것을 허용하도록 구성된다. 다른 실시예들에서, 상기 포트는 (캠팩트 플래시 (CF) 카드들, 메모리 스틱들, xD 메모리 카드들, USB (Universal Serial Bus) 플래시 드라이브들, MMC (MultiMedia) 카드들, 스마트미디어 카드들, 마이크로드라이브들 등과 같은) 다른 포맷의 메모리가 연결되는 것을 허용할 수 있을 것이다.

도 3은 참조번호 226의 접속을 경유한 프로세서 (202) 및 안테나/수신기 (224) 사이의 작동적 접속을 더 도시하며, 여기에서 상기 안테나/수신기 (224)는 예를 들면, GPS 안테나/수신기일 수 있으며 그리고 그 자체로 도 1의 GSP 수신기처럼 기능할 수 있을 것이다. 참조번호 224에 의해 표시된 상기 안테나 및 수신기는 예시를 위해 도면처럼 조합되지만, 상기 안테나 및 수신기는 분리하여 배치된 컴포넌트들일 수 있으며, 그리고 상기 안테나는 예를 들면 GPS 패치 안테나 또는 나선형 안테나일 수 있다는 것이 이해되어야 한다.

물론, 도 3에서 보이는 전자 컴포넌트들은 통상적인 방식으로 하나 또는 그 이상의 전력 소스들 (도시되지 않음)에 의해 전력을 공급받는다는 것이 본 발명이 속한 기술 분야에서의 통상의 지식을 가진 자에 의해 이해될 것이다. 그런 전력 소스들은 내부 배터리 및/또는 저 전압 DC 공급을 위한 입력 또는 어떤 다른 적합한 설비를 포함할 수 있을 것이다. 본 발명이 속한 기술 분야에서의 통상의 지식을 가진 자에 의해 이해될 것처럼, 도 3에서 보이는 컴포넌트들의 상이한 구성들이 예측된다. 예를 들면, 도 3에서 보이는 컴포넌트들은 유선 및/또는 무선 접속들 등을 경유하여 서로 통신할 수 있다. 그래서, 본원에서 설명된 상기 내비게이션 디바이스 (200)는 휴대용 또는 핸드헬드 내비게이션 디바이스 (200)일 수 있다.

추가로, 도 3의 상기 휴대용 또는 핸드헬드 내비게이션 디바이스 (200)는 예를 들면 자전거, 모터바이크, 차 또는 보트와 같은 차량에 알려진 방식으로 연결되거나 "도킹"될 수 있다. 그런 내비게이션 디바이스 (200)는 그러면 휴대용 또는 핸드헬드 내비게이션 사용을 위해, 도킹된 위치로부터 탈착 가능하다. 실제, 다른 실시예들에서, 상기 디바이스 (200)는 사용자의 내비게이션을 허용하기 위해 핸드헬드이도록 구성될 수 있을 것이다.

도 4를 참조하면, 상기 내비게이션 디바이스 (200)는 통합된 입력 및 디스플레이 디바이스 (206) 및 도 2의 다른 컴포넌트들 (내부 GPS 수신기 (224), 프로세서 (202), 파워 서플라이 (도시되지 않음), 메모리 시스템 (214) 등을 포함하지만, 그것들로 한정되지는 않음)을 포함하는 유닛일 수 있다.

상기 내비게이션 디바이스 (200)는 암 (252) 상에 놓여질 수 있으며, 이 암 그 자체는 석션 컵 (254)을 이용하여 차량 대시보드/창/등에 안전하게 부착될 수 있다. 이 암 (252)은 상기 내비게이션 디바이스 (200)가 도킹될 수 있는 도킹 스테이션의 한 예이다. 상기 내비게이션 디바이스 (200)를 예를 들면 상기 암 (252)에 스냅 연결시킴으로써 상기 내비게이션 디바이스 (200)는 상기 도킹 스테이션의 암 (252)에 도킹되거나 또는 그렇지 않고 연결될 수 있다. 상기 내비게이션 디바이스 (200)는 그러면 상기 암 (252) 상에서 회전 가능할 수 있다. 내비게이션 디바이스 (200)와 도킹 스테이션 사이의 연결을 풀기 위해서, 예를 들면 상기 내비게이션 디바이스 (200) 상의 버튼 (도시되지 않음)이 눌려질 수 있다. 상기 내비게이션 디바이스 (200)를 도킹 스테이션에 연결하고 연결해제하기 위한 다른 동등하게 적합한 설비는 본 발명이 속한 기술 분야에서의 통상의 지식을 가진 자들에게 잘 알려져 있다.

설명된 상기 실시예에서, 상기 내비게이션 디바이스의 프로세서 (202)는 안테나 (224)에 의해 수신된 GPS 데이터를 수신하기 위해 그리고 때로는 상기 내비게이션 디바이스의 위치의 기록을 구축하기 위해서 그 GPS 데이터를 GPS 데이터가 수신되었을 때의 타임 스탬프와 함께 상기 메모리 (214) 내에 저장하기 위해 프로그램된다. 그렇게 저장된 각 데이터 기록은 GPS 픽스 (fix)으로서 생각될 수 있을 것이다; 즉, 그것은 상기 내비게이션 디바이스의 위치의 픽스이며 그리고 위도, 경도, 타임 스탬프 및 정밀도 보고를 포함한다.

일 실시예에서, 상기 데이터는 예를 들면 매 5초마다 실질적으로 주기적으로 저장된다. 통상의 지식을 가진 자는 다른 주기들이 가능할 것이며 그리고 데이터 해상도와 메모리 용량 사이에서는 균형 (balance)이 존재할 것이라는 것을 인정할 것이다; 즉, 더 많은 샘플들을 취함으로써 상기 데이터의 해상도가 증가되면, 그 데이터를 유지하기 위해 더 많은 메모리가 필요하다. 그러나, 다른 실시예들에서, 상기 해상도는 실질적으로 매 1초, 10초, 15초, 20초, 30초, 45초, 1분, 2.5분 일 수있다 (또는 실제로, 이 주기들 사이에서의 어느 한 주기일 수 있다). 그래서, 상기 디바이스의 메모리 내에, 포인트들에서 상기 디바이스 (200)의 소재 (whereabouts)의 시간 상의 기록이 구축된다.

몇몇의 실시예들에서, 캡쳐된 데이터의 품질은 상기 주기가 증가할수록 감소되며 그리고 저하의 정도는 상기 내비게이션 디바이스 (200)가 이동하고 있던 속도에 적어도 부분적으로 의존할 것이기 때문에 대략적으로 15초의 주기는 적절한 상단 한계를 제공할 수 있을 것이다.

상기 내비게이션 디바이스 (200)는 자신의 소재의 기록을 구축하도록 보통 구성되며, 몇몇의 실시예들은 미리 정해진 주기 및/또는 시작점에서의 미리 정해진 거리 또는 여행의 끝에 대해서는 데이터를 기록하지 않는다. 그런 설비는 상내비게이션 디바이스 (200)의 사용자의 프라이버시를 보호하는 것을 도우며, 이는 사용자의 집 및 다른 빈번하게 찾는 목적지의 위치를 보호할 것이기 때문이다. 예를 들면, 상기 내비게이션 디바이스 (200)는 대략적으로 여행의 처음 5분에 대해서 그리고/또는 대략적으로 여행의 첫 번째 마일에 대해서는 데이터를 저장하지 않도록 구성될 수 있을 것이다.

다른 실시예들에서, 상기 GPS는 주기적으로 저장되지 않을 수 있지만 미리 정해진 이벤트가 발생할 때에 그 메모리 내에 저장될 수 있을 것이다. 예를 들면, 상기 프로세서 (202)는 상기 디바이스가 도로 교차로, 도로 세그먼트를 지나갈 때에, 또는 다른 그런 이벤트 때에 GPS 데이터를 저장하도록 프로그램될 수 있을 것이다.

또한, 상기 프로세서 (202)는 상기 디바이스 (200)의 소재의 기록 (즉, 상기 GPS 데이터 및 상기 타임 스탬프)을 상기 서버 (150)로 업로드하도록 때로는 설정된다. 상기 내비게이션 디바이스 (200)가 자신을 상기 서버 (150)로 연결시키는, 영구적으로 또는 적어도 일반적으로 존재하는 통신 채널 (152)을 구비하는 몇몇의 실시예들에서, 상기 데이터를 업로드하는 것은 주기으로 발생하며, 이 주기는 예를 들면 매 24시간마다 한번일 수 있다. 통상의 지식을 가진 자는 다른 주기들이 가능하며 그리고 다음의 주기들 중 실질적으로 어느 하나일 수 있다는 것을 인정할 것이다: 15분마다, 30분마다, 시간마다, 매 2시간마다, 매 5시간마다, 매 12시간마다, 매 2일마다, 매 주마다, 또는 이것들 중에서 어느 하나. 실제로, 그런 실시예들에서 상기 프로세서 (202)는 실질적으로 실시간을 기반으로 하여 상기 소재의 기록을 업로드하도록 구성될 수 있을 것이며, 비록 이것이 데이터가 실제로 전송들 사이에서 상대적으로 짧은 주기로 때때로 전송된다는 것을 불가피하게 의미할 수 있으며 그리고 이것이 그처럼 의사 실시간인 것으로 더 올바르게 생각될 수 있다고 하더라도 그렇다. 그런 의사 실시간 실시예들에서, 상기 내비게이션 디바이스는 상기 GPS 픽스들을 상기 메모리 (214) 내에 그리고/또는 상기 포트 (228)에 삽입된 카드 상에서 버퍼링하고 그리고 미리 정해진 개수가 저장된 때에 이것들을 전송하도록 구성될 수 있을 것이다. 이 미리 정해진 개수는 20, 36, 100, 200 또는 이것들 사이에서의 어느 개수의 차수 (order)일 수 있다. 통상의 지식을 가진 자는 상기 미리 정해진 개수가 상기 포트 (228) 내 카드 또는 상기 메모리 (214)의 크기에 의해 부분적으로 좌우된다는 것을 인정할 것이다.

일반적으로 존재하는 통신 채널 (152)을 구비하지 않은 다른 실시예들에서, 상기 프로세서 (202)는 통신 채널 (152)이 생성될 때에 상기 기록을 상기 서버 (152)로 업로드하도록 구성될 수 있다. 이것은 예를 들면 상기 내비게이션 디바이스 (200)가 사용자의 컴퓨터에 연결될 때일 수 있다. 다시, 그런 실시예들에서, 상기 내비게이션 디바이스는 상기 GPS 픽스들을 메모리 (214) 내에 또는 상기 포트 (228) 내에 삽입된 카드 상에 버퍼링하도록 구성될 수 있다. 이 메모리 (214) 또는 상기 포트 (228) 내에 삽입된 카드가 GPS 픽스들로 가득찬다면 상기 내비게이션 디바이스는 가장 오래된 GPS 픽스들을 제거하도록 구성되며 그리고 그처럼 그것은 선입 선출 (First in First Out (FIFO)) 버퍼로서 생각될 수 있을 것이다.

설명되고 있는 실시예에서, 상기 소재의 기록은 하나 또는 그 이상의 트레이스들을 포함하며, 그 트레이스들 각각은 24시간 주기 내에 그 내비게이션 디바이스 (200)의 움직임을 나타낸다. 각각 (24)은 달력 날짜와 일치하도록 구성되지만, 다른 실시예들에서는, 사실 그럴 필요는 없다.

일반적으로, 내비게이션 디바이스 (200)의 사용자는 업로드될 상기 디바이스들 소재의 기록에 대한 자신의 동의를 상기 서버 (150)에게 수여한다. 어떤 동의도 수여되지 않는다면, 어떤 기록도 상기 서버 (150)로 업로드되지 않는다. 상기 내비게이션 디바이스 그 자체 그리고/또는 상기 내비게이션 디바이스가 연결된 컴퓨터는, 소재 기록을 그렇게 사용하는 것에 대한 사용자의 동의를 그 사용자에게 요청하도록 구성될 수 있을 것이다.

상기 서버 (150)는 상기 디바이스의 소재의 기록을 수신하고 그리고 프로세싱을 위해서 이것을 상기 대용량 데이터 저장부 (160) 내에 저장하도록 구성된다. 그래서, 시간이 지남에 따라 상기 대용량 데이터 저장부 (160)는 데이터를 업로드했던 내비게이션 디바이스 (200)의 소재의 복수의 기록들을 축적한다.

위에서 설명된 것처럼, 상기 대용량 데이터 저장부 (160)는 지도 데이터를 또한 포함한다. 그런 지도 데이터는 도로 세그먼트들, 관심 대상 포인트들 및 지도 상에서 보통 발견되는 다른 그런 정보의 위치에 관한 정보를 제공한다.

본 발명의 실시예가 도 5 및 도 6을 참조하여 이제 설명될 것이다.

도 5는 본 발명의 일 실시예에 따라 경로를 재구축하는 방법을 구현하기 위해 사용될 수 있을 예시적인 시스템을 도시한다. 상기 시스템은 내비게이션 디바이스 (300)를 포함하며, 이는 PND 또는 통합된 차량-내 디바이스의 모습일 수 있다. 상기 내비게이션 디바이스는 주어진 영역 내 운행 가능 네트워크의 운행 가능한 세그먼트들을 표현하는 복수의 세그먼트들을 구비한 전자 지도 데이터를 저장한다 (지도 데이터베이스 (305)). 상기 내비게이션 디바이스는 경로 계획 기능성을 제공하는 서드 파티 서버인 경로 생성 서버 (310)와 통신한다. 상기 내비게이션 디바이스 (300)는 제1 및 제2 로케이션의 상세한 내용들, 그리고 옵션으로는 다른 관련 정보를 상기 경로 생성 서버 (310)로 전송하며, 이 서버는 지도 데이터베이스 (315)를 이용하는 상기 디바이스 대신에 상기 로케이션들 사이의 경로를 생성한다. 상기 경로 생성 서버 (310)는 본 발명의 방법들을 구현하기 위해 사용되는 애플리케이션 서버 (320)와 통신한다. 상기 애플리케이션 서버 (320)는 상기 경로 생성 서버 (310)에 의해 생성된 상기 경로를 나타내는 데이터를 취할 수 있으며, 그리고 애플리케이션 데이터베이스 (325)를 이용하여 상기 경로를 표현하는 폴리라인을 나타내는 데이터를 생성하며, 이것은 상기 내비게이션 디바이스 (300)로 전송되는 것이 바람직하다. 비록 일반적으로 아래에서 더욱 상세하게 설명되는 본 발명의 방법들이, 포함된 지도 데이터의 품질 및/또는 양의 면의 어느 하나에서, 그리고/또는 상기 지도 데이터가 저장된 포맷의 면에서, 상기 지도 데이터베이스들 (305, 315, 325)의 상이한 실시예들에도 적용될 수 있지만, 디지털 지도 데이터베이스들 (305, 315 및 325) 중의 몇몇 또는 모두는 동일할 수 있을 것이며, 즉, 동일한 지도 포맷으로 저장된 동일한 지도 데이터를 포함할 수 있을 것이다.

본 발명의 실시예에 따른 방법의 단계들은 도 6을 참조하여 이제 설명될 것이다. 동시에, 상기 내비게이션 디바이스 (300)는 상기 전자 지도 데이터 (305)에 의해 표현된 상기 운행 가능 네트워크를 통한 경로를 생성할 것을 필요로 하며, 이는 상기 디바이스에 의해, 예를 들면, 사용자에게 디스플레이되기 위해, 그리고 상기 경로를 따라 상기 사용자를 안내하기 위한 내비게이션 지시들의 세트를 제공하기 위해 사용될 수 있다. 본 발명은 상기 내비게이션 디바이스가 사용자에 의해 특정된 원점과 목적지 사이의 운행 가능 네트워크를 통해 경로를 생성할 필요가 있는 상황을 참조하여 설명될 것이다. 그러나, 본 발명은 제1 및 제2 로케이션들 중 하나 또는 둘 모두가 상기 내비게이션 디바이스 또는 사용자에 의해 결정되는 경우에 어떤 이유에 의해 상기 내비게이션 디바이스에 의해 요청될 수 있을 임의의 제1 및 제2 로케이션들 사이에서 경로를 생성하는데 적용 가능하다.

상기 내비게이션 디바이스 (300)는 상기 요청된 경로의 상기 원점 및 목적지를 나타내는 데이터를 상기 경로 생성 서버 (310)로 전송한다 - 단계 400. 경로 계획에 있어서 사용될 필요가 있는 추가적인 정보가 전송될 수 있을 것이다. 경로 생성 서버 (300)는 그러면 상기 특정된 원점 및 목적지 사이의 추천 경로를 생성한다 - 단계 420. 이 추천 경로는 상기 서버의 전자 지도 데이터 (315)와 관련될 것이다. 이 지도 데이턴느 상기 내비게이션 디바이스의 전자 지도 데이터와 동일하지 않을 수 있다. 상기 경로 생성 서버 (310)는 그러면 상기 추천 경로를 나타내는 데이터 ("경로 데이터")를 상기 애플리케이션 서버 (320)로 전송한다 - 단계 430. 단일의 서버에 의해 제공되도록 하기 위해서, 대신에 상기 경로 생성 서버 (310) 및 상기 애플리케이션 서버 (320)의 기능들이 결합될 수 있을 것이라는 것이 인정될 것이다. 그러나, 이 기능들을 분리함으로써, 서드 파티 경로 생성 서버가 사용될 수 있다. 상기 경로 데이터는 상기 경로 생성 서버 (310)로부터 상기 애플리케이션 서버 (320)로 어떤 적합한 모습으로 전송될 수 있으며, 비록 보통은 상기 지도 데이터베이스들 (315 및 325)가 상이할 것이지만, 상기 경로 데이터는 지도 불가지론적 포맷으로, 예를 들면, OpenLRTM, AGORA-C 및 TPEG-ULR와 같은 시스템을 이용하여 인코딩된 로케이션 참조로서 전송된다. 보통은, 이 동적 로케이션 참조 기술들은 자신들의 지리적인 좌표들에 의해 그 좌표들 사이의 세그먼트들의 특정 속성들과 함께 제1 디지털 지도 (예를 들면, 지도 데이터베이스 (315)) 내 노드들을 참조함으로써 상기 추천 경로를 인코딩한다. 이 정보는 그러면 제2의 상이한 디지털 지도 (예를 들면, 참조번호 325의 지도 데이터베이스) 상에서 디코딩되거나 분해되어, 그 제2 디지털 지도 내의 동등한 로케이션을 결정한다. 물론, 상기 경로 데이터는, 예를 들면, 참조번호 315 및 325의 지도 데이터베이스들이 동일할 때인 환경들에서 세그먼트 또는 노드 식별자들의 정렬된 목록의 모습과 같은 다른 모습들로 전송될 수 있다.

상기 애플리케이션 서버 (320)는 상기 추천 경로를 나타내는 경로 데이터를 수신하고, 그리고 그 경로 데이터를 상기 경로를 표현하는 폴리라인으로 변환한다 - 단계 440. 생성된 상기 폴리라인 데이터는 라인들에 의해 연결된 복수의 포인트들의 모습인 폴리라인을 나타낸다. 예를 들면, 상기 데이터는 상기 폴리라인 내 라인 세그먼트들에 의해 연결된 포인트들을 식별하는 정렬된 목록의 모습일 수 있다. 상기 포인트들은 위도 및 경도 좌표들의 면에서 정의될 수 있을 것이다. 상기 포인트들은 최적의 프로세싱 효율을 위해서 서로 20 미터 및 100 미터 사이에서 이격될 수 있을 것이다. 상기 폴리라인은 일련의 연결된 라인 세그먼트들과 같은 모습을 가질 수 있을 것이며, 또는 시작 로케이션으로부터의 거리들 및 방위 (bearing)들(각 거리 및 방위는 상기 폴리라인의 다음의 라인 세그먼트를 표시함)의 정렬된 목록으로서의 모습을 가질 수 있을 것이다. 상기 폴리라인은 상기 경로를 정확하게 복제할 필요는 없다. 상기 폴리라인은 상기 경로를 일반화한 것일 수 있다. 예를 들면, 상기 폴리라인 내 포인트들의 개수는 상기 폴리라인이 표현하는 경로의 세그먼트들 사이의 포인트들의 개수와 비교하여 줄어들 수 있을 것이며, 그리고/또는 초기 폴리라인 데이터는 상기 포인트들, 예를 들면, 폴리라인이 포함하는 좌표들의 개수를 줄이기 위해 일반화 프로세스로 넘겨질 수 있을 것이다. 그래서 상기 폴리라인은 그 폴리라인이 적어도 상기 경로와 유사하다는 점에서 상기 경로를 표현하며, 그리고 상기 경로에 근사할 수 있을 것이다.

일단 상기 폴리라인이 생성되면, 상기 애플리케이션 서버 (320)는 상기 폴리라인 데이터를 상기 내비게이션 디바이스에게 전송한다 - 단계 450. 그 폴리라인 데이터는 XML 파일로 전송될 수 있을 것이다.

상기 내비게이션 디바이스 (300)는 상기 폴리라인 데이터를 수신하며, 그리고 그 데이터를 이용하여, 자기 자신이 소유한 전자 지도 데이터 (305)에 관련하여 상기 데이터에 의해 표현된 상기 경로를 재구축한다 - 단계 460. 상기 내비게이션 디바이스는 상기 폴리라인 데이터를 고려하여, 상기 원점 및 목적지 사이에서 보통의 경로 생성 프로세스를 수행함으로써 이것을 한다. 이것은 상기 디바이스의 전자 지도 데이터에 의해 표현된 상기 폴리라인에 더욱 근접한 세그먼트들이 그 폴리라인으로부터 더 먼 거리에 있는 세그먼트들보다 경로 생성의 목적들을 위해 더 선호되는 방식으로 행해진다. 이것은 상기 전자 지도의 운행 가능 세그먼트들에게, 경로 생성을 목적들을 위해 상기 운행가능한 세그먼트들의 상기 폴리라인으로부터의 거리를 기초로 하여 벌점 팩터를 적용함으로써 달성될 수 있을 것이다. 상기 폴리라인으로부터 더 멀리에 있는 세그먼트들은 그 폴리라인에 더 가까이에 있는 세그먼트들보다 더 높은 벌점을 부여받는다. 벌점 팩터들은 상기 폴리라인에 대한 세그먼트들의 근접도에 기초하여, 또는 상기 폴리라인으로부터 주어진 거리에 있는, 예를 들면, 상기 폴리라인을 기반으로 하는 영역 외부에 있는 세그먼트들로부터 시작하여 모든 세그먼트들에게 부여될 수 있다.

예를 들면, 잘 잘려진 다익스트라 (Dijkstra)의 알고리즘과 같은 전통적인 그래프 검색 기술들을 이용하여, 상기 전자 지도에 의해 표현된 네트워크를 통해 최소 비용 경로가 생성되지만, 이 경우에 세그먼트들을 통과하는 것과 연관된 비용 값들은 상기 폴리라인에 대한 상기 세그먼트들의 근접도에 종속하여 조절되거나 결정된다. 그러나, 세그먼트를 통과하기 위한 비용은 경로 생성에 있어서 고려될 다른 팩터들, 그 세그먼트에 대한 통과 시간, 세그먼트의 길이, 곡률 등에 기초한 기여분들을 또한 포함할 것이다.

상기 내비게이션 디바이스 (300)는 자신의 전자 지도 상에 상기 폴리라인을 표현하는 단계를 수행할 것이라는 것이 인정될 것이다. 이것은 상기 폴리라인을 정의하는 좌표들을 상기 전자 지도 데이터에 따라 상기 좌표들을 표현하는 로케이션들로 매칭함으로써 달성될 수 있다. 상기 폴리라인의 세그먼트들은 상기 전자 지도의 세그먼트들에 상관하지 않을 수 있다. 그러나, 이것은 상기 폴리라인에 더 가까운 전자 지도의 세그먼트들을 선호하는 방식으로 경로 생성을 수행하기 위해 상기 폴리라인이 사용되는 것을 방해하지 않는다.

이 방식에서, 결과인 상기 생성된 경로는 상기 폴리라인으로 끌어 당겨지는 경향이 있을 것이다. 그러나, 상기 폴리라인은 복제하는 것을 시도하도록 강제되지 않는다. 이것은 다른 경로 계획 선호도들, 또는 "라이브 (live)" 데이터를 고려하는 자유가 있다는 것을 의미하며, 이 라이브 데이터가 상기 폴리라인에 가장 가까운 세그먼트들보다 상기 경로 내 포함을 위해 더욱 적절한 세그먼트들의 결과가 될 것이다. 상기 경로 생성은, 예를 들면, 세그먼트들을 따르는 트래픽, 세그먼트들에 영향을 주는 폐쇄, 우회 (diversion), 도로공사 등에 관련된 라이브 데이터를 유리하게도 고려한다. 이것은 상기 내비게이션 디바이스 (300)에 의해 어떤 적합한 소스, 예를 들면, 트래픽 서버로부터 획득될 수 있을 것이다. 이 방식에서, 생성된 결과인 경로는 상기 경로 생성 서버 (310)에 의해 생성된 상기 추천 경로를 기반으로 하지만, 상기 도로 네트워크 내 현재의 상태들을 고려한다. 상기 경로는 상기 폴리라인에 가까운 또는 그 폴리라인 상에 있는 세그먼트들이 폐쇄되거나, 또는 극심한 교통 혼잡 등이라면, 그런 폴리라인을 포함하도록 강제되지 않는다.

물론, 상기 폴리라인 데이터는 상기 폴리라인에 더 가까운 세그먼트들이 경로 생성에 있어서 선호될 것인 다른 방식들로 사용될 수 있다. 예를 들면, 상기 전자 지도 데이터에 의해 표현된 상기 폴리라인 주위에 영역이 정의되고, 그 영역 내 운행 가능한 세그먼트들만을 고려한 경로 생성 프로세스가 있을 수 있다. 그 영역 외부의 세그먼트들에게 고정된 벌점 팩터가 적용될 수 있을 것이며, 또는 세그먼트들이 상기 폴리라인으로부터 더 멀리 있으면 더 높은 벌점을 할당받도록 변하는 벌점 팩터가 적용될 수 있다.

일단 상기 내비게이션 디바이스가 자신이 소유한 전자 지도 데이터에 관련하혀 상기 경로를 재구축하면, 그것은 상기 경로를 어떤 적합한 방식으로 사용할 수 있을 것이며, 그리고 그 경로를 따라서 사용자를 안내하기 위해 상기 경로를 디스플레이하고 그리고/또는 내비게이션 지시들의 세트를 생성할 수 있을 것이다.

위에서 설명된 바람직한 실시예에서, 본 발명은 서버 측 경로 생성 및 클라이언트 측 경로 재구축이 분리된, 개선된 하이브리드 경로 설정 시스템을 제공한다는 것을 알 수 있을 것이다.

본 발명이 내비게이션 디바이스에 의한 요청에 응답하여 서버가 상기 경로를 생성하는 시스템에 관련하여 설명되었지만, 상기 폴리라인 데이터를 획득하기 위해 사용된 상기 경로 데이터가 이 방식으로 획득된다는 것이 반드시 필요한 것은 아니다. 경로를 표현하는 폴리라인이 획득될 수 있으며, 그리고 경로를 나타내는 데이터를 기초로 하여 상기 경로의 재구축을 위해 내비게이션 디바이스로 제공될 수 있으며, 이는 다양한 소스들로부터 획득될 수 있을 것이다. 예를 들면, 상기 경로는 사용자가 경로 계획 웹사이트와의 상호작용에 의해 생성된 경로일 수 있을 것이다. 이 방식으로 경로가 계획될 수 있을 것이며, 그리고 출발 이전의 어느 때엔가 폴리라인이 결정되며, 그 후에 출발 직전에 라이브 데이터를 고려하면서, 상기 경로를 재구축하기 위해 상기 폴리라인은 상기 내비게이션 디바이스에 의해 사용된다.

서버가 경로 데이터를 이용하여 상기 폴리라인 데이터를 결정하는 실시예에 관련하여 본 발명이 설명되었지만, 이 단계는 상기 내비게이션 디바이스에 의해 수행될 수 있을 것이라는 것이 예견된다. 예를 들면, 사용자는 적합한 경로 데이터를 상기 내비게이션 디바이스로의 입력으로 제공할 수 있으며, 또는 상기 내비게이션 디바이스는 그런 데이터를, 예를 들면, 경로 생성 서버 또는 다른 시스템으로부터 수신할 수 있다. 상기 내비게이션 디바이스는 그러면, 상기 애플리케이션 서버 (320)가 그런 단계를 수행하는 실시예들과 관련하여 상기에서 설명된 경로를 나타내는 폴리라인 데이터를 획득하기 위해 상기 경로 데이터를 사용하도록 구성될 수 있을 것이다.

위에서 설명된 실시예들에서, 상기 내비게이션 디바이스는 상기 경로 생성 프로세스를 개시하기 이전에 자기 자신의 전자 지도 데이터를 저장하며, 이 데이터는 경로 재구축에서 그 후에 사용된다. 다른 실시예들에서, 상기 내비게이션 디바이스가 주어진 영역에 대한 완전한 전자 지도 데이터를 저장하지 않을 수 있다는 것이 예견된다. 대신에, 상기 내비게이션 디바이스는 필요한대로 서버로부터 관련된 전자 지도 데이터를 수신할 수 있을 것이다. 상기 디바이스의 현재 위치 주변의 구역에 관련된 전자 지도 데이터는 간헐적으로 서버에 의해 상기 디바이스로 전송될 수 있을 것이며, 그래서 상기 디바이스가 머지 않은 미래에 필요할 것 같은 전자 지도 데이터를 항상 가지도록 한다. 상기 내비게이션 디바이스는 현재 위치를 서버에게 표시하는 "맥박" 유형 신호를 제공할 수 있을 것이며, 이것은 상기 디바이스의 현재 위치를 기반으로 하는 관련된 전자 지도 데이터를 제공할 수 있다. 대안으로 또는 추가로, 상기 내비게이션 디바이스가 경로 생성 프로세스를 개시하는 경우, 상기 경로 설정 프로세스에 관련된 전자 지도 데이터는 서버로부터 상기 디바이스로 자동적으로 또는 상기 내비게이션 디바이스에 의한 요청에 응답하여 전송될 수 있을 것이다.

예를 들면, 상기 내비게이션 디바이스가 경로가 생성될 것을 요청하면, 그 내비게이션 디바이스는 현재의 위치일 수 있는 원점, 그리고 그 경로를 위한 목적지를 전송할 수 있다. 상기 방법은 그러면 도 5의 라인을 따른 방식으로 진행될 수 있을 것이며, 서버는 경로를 생성하고, 그리고 폴리라인 데이터를 획득하기 위해 경로 데이터가 사용된다. 그러나, 폴리라인 데이터를 상기 내비게이션 디바이스로 전송하는 것에 추가로, 경로 재구축을 위해 상기 내비게이션 디바이스에 의해 요청된 전자 지도 데이터로, 현재 위치 및/또는 생성된 경로에 기초하여 선택된, 즉, 경로 회랑 (corridor)에 관한 전자 지도 데이터는 추가적으로 이용 가능하게 되며, 예를 들면, 상기 내비게이션 디바이스로 전송된다. 상기 내비게이션 디바이스는 그러면 위에서 설명된 획득된 전자 지도 데이터에 관련하여 상기 경로를 재구축할 수 있다. 그러나, 상기 전자 지도 데이터는 상기 내비게이션 디바이스에 의해 상기 경로 생성 프로세스의 일부로서 수신되고 저장될 데이터이며, 그리고 그 데이터는 경로를 요청하기 이전에 상기 디바이스에 의해 보유되었던 전체 전자 지도가 아니라 경로 설정 회랑에 대응하는 영역에 관련된다.

본 발명의 모습들 중 어느 하나에서 본 발명에 따라 폴리라인 데이터에 기초하한 경로 재구축은 상기 내비게이션 디바이스에 의해 수행될 수 있고 수행되지 않을 수 있다는 것이 예견된다. 대신에, 위에서 설명된 상기 실시예들에서 내비게이션 디바이스 (300)에 의해 수행된 상기 기능들은, 소프트웨어 또는 하드웨어로 구현된 것에 관계없이, 내비게이션 기능성을 추가적으로 제공하거나 또는 제공하지 않는가에 관계없이, 전자 지도 데이터에 액세스하며, 그리고 경로 생성 능력을 가지는, 서버를 포함하는 임의 디바이스에 의해 수행될 수 있을 것이다.

전자 지도 상의 폴리라인의 표현에 더 가까운 전자 지도의 세그먼트가 본 발명의 특정 실시예들에 따른 경로 재구축에 있어서 선호되는 방식이 이제 설명될 것이다.

경로 (또는 그래프) 검색 알고리즘에서 고려된 세그먼트들에게, 상기 폴리라인으로부터의 그 세그먼트들의 거리에 종속하여 벌점 팩터가 적용된다. 세그먼트와 상기 폴리라인 사이의 거리가 더 클수록, 그 세그먼트에 적용된 벌점 팩터는 더 커진다. 이 벌점 팩터는 원점과 목적지 사이의 네트워크를 통한 최소 비용 경로를 결정할 때에 고려되는 상기 폴리라인으로부터의 상기 세그먼트의 거리에 기인하는 비용을 불러일으키며, 세그먼트에 대한 더 높은 벌점 팩터는 더 높은 비용 기여분의 결과가 된다. 이 방식에서, 경로를 생성할 때에, 그 경로는 상기 폴리라인의 대체적인 모습과 같은 모양이 되는 경향이 있을 것이다. 또한, 상기 재구축된 경로, 즉, 추천 경로로부터 차량이 이탈한다면, 그리고 상기 차량을 상기 추천 경로로 복구하게 하기 위한 경로를 다시 생성하는 것이 필요하다면, 상기 차량이 상기 추천 경로로부터 더 멀리 이동할수록, 상기 폴리라인에 가까운 상기 추천 경로로 차량을 반대로 당기는 "끌어당김"의 레벨은 증가할 것이다

경로 재구축 동안에 전자 지도 상에 표현된 상기 폴리라인으로부터의 상기 전자 지도 상의 세그먼트들의 거리에 종속하여 그 세그먼트들에게 벌점 팩터들이 적용되는 방식의 한 예가 더욱 상세하게 이제 설명될 것이다.

예를 들면, 원점과 목적지 사이의 네트워크를 통해 최소 비용 경로를 제공하기 위한 통상의 경로 생성 프로세스 동안에, 운행 가능한 세그먼트를 통과하는 비용에 대한 기여분에 연관된 벌점 팩터를 결정하기 위해 상기 방법이 사용된다. 상기 벌점 팩터는, 그리고 그로 인한 상기 비용 기여분은 상기 운행 가능 세그먼트 그리고 상기 폴리라인 사이의 거리에 기인한 것이며, 그리고 그 거리에 종속된다. 이것은 사용된 비용 함수에 따라 상기 세그먼트를 통과하는 비용에 대한 기여분을 제공할 것이다. 상기 비용에 대한 다른 기여분들은 고려될 것이 소망되는 어떤 다른 팩터들, 예를 들면, 그 세그먼트를 통과하기 위한 이동 시간, 세그먼트 길이 등에 기초할 수 있을 것이다.

상기 벌점 팩터는 상기 운행 가능 세그먼트의 길이, 또는 그 세그먼트의 근사를 따른 여러 포인트들을 고려함으로써 획득된다. 예를 들면, 프로세싱을 간략하게 하기 위해, 운행 가능 세그먼트는 그 세그먼트의 말단 포인트들을 연결시키는 직선으로 취급될 수 있을 것이며, 그래서 중간의 형상 포인트들은 무시된다. 다른 설비들에서, 중간 형상 포인트들이 고려될 수 있을 것이다. 예를 들면, 상기 폴리라인의 하나보다 많은 정점 (vertex)이 상기 폴리라인의 운행 가능 세그먼트의 제1 말단 및 제2 말단의 투사 사이에 존재하는 경우, 상기 세그먼트의 중간 형상 포인트들이 고려될 수 있을 것이다. 이것은 상기 폴리라인이 바짝 조여진 루프를 형성하는 경우에도 상기 생성된 재구축된 경로가 그 폴리라인을 따르는 경향이 있을 것이라는 것을 보장하도록 도울 수 있다.

다음의 단계들은 고려되는 세그먼트를 따른 또는 그 세그먼트의 근사를 따른 각 포인트에 대해 수행된다. 상기 포인트는 상기 폴리라인 상으로 투사된다. 그 포인트에 대한 벌점 팩터는 상기 포인트와 상기 폴리라인 상의 그 포인트의 투사 사이의 거리에 제곱에 비례하게 유도된다. 물론, 다른 실시예들에서, 벌점 팩터는 상기 포인트와 상기 폴리라인 상의 그 포인트의 투사 사이의 거리에 세제곱에, 또는 소망되는 어떤 다른 멱수에 비례할 수 있다. 상기 세그먼트에 대한 전체적인 벌점 팩터는

상기 세그먼트 또는 그 세그먼트의 근사의 길이를 따른 개별 포인트들과 연관된 벌점 팩터들을 합하여 유도된다. 바람직한 실시예들에서, 이것은 적분에 의해 달성된다. 이 전체적인 벌점 팩터는 그러면 경로 생성에서 사용하기 위한 상기 세그먼트와 상기 폴리라인의 거리를 기초로 하는 비용 기여분을 제공하기 위해 사용된다.

다른 말로 하면, 경로 검색 동안에, 추가의 "마찰 손실 벌점"이 각 호 (arc) 상에서 통상적인 전파 (propagation) 비용에 추가된다 (물체 기능에 종속한 이동 시간, 통로 길이 등). 상기 "마찰 손실"은 상기 호에 대한 "마찰력"의 적분으로서 계산되며, 이 경우에 상기 힘 (마찰력)의 크기는 상기 호 상의 포인트와 상기 규정된 폴리라인 상의 그 포인트의 투사 사이의 거리의 제곱에 비례한다. 당신은 폴리라인을 따라 레일들 상에서 미끄러지는 작은 캐리지 (carriage)에 부착된 고무줄을 생각할 수 있다. 당신이 걷고 있는 레일로부터 더 멀어질수록, 그 고무줄은 더 팽팽해지고 그리고 당신이 걷는 것는 더 힘들어진다.

주어진 포인트에 대해 유도된 벌점 팩터는 추가적인 팩터들을 고려할 수 있을 것이다. 몇몇의 옵션의 설비들에서, 벌점 팩터의 크기는 상기 포인트가 그 위로 투사되는 폴리라인 세그먼트의 길이를 고려할 수 있을 것이다. 예를 들면, 그것은 상기 세그먼트의 유클리드 길이의 2차의 역수일 수 있다. 이것은 상기 폴리라인 세그먼트가 더 길수록, 상기 벌점 팩터는 더 작아지며, 그래서 상기 폴리라인으로부터의 동일한 거리에 대해서, 상기 폴리라인이 상대적으로 작은 세그먼트들을 가지는 경우, 즉, 더 거친 경우에, 그 세그먼트에는 더 작은 등급의 벌점이 부여될 것이다. 이 방식에서, 더 거친 폴리라인으로부터 벗어나는 것은 더 작은 등급으로 벌점이 부여될 수 있을 것이다. 다른 옵션의 설비들에서, 상기 폴리라인의 상이한 세그먼트들에는 상이한 상대적인 가중치들이 적용될 수 있을 것이며, 그래서 한 세그먼트 상에 투사된 포인트들과 연관된 운행 가능한 세그먼트에 대해 유도된 벌점 팩터가, 상이한 세그먼트 상으로 투사된 포인트들과 연관된 운행 가능 세그먼트에 대해 유도된 벌점 팩터와 상이할 수 있도록 한다.

세그먼트를 따라 주어진 포인트의 상기 폴리라인 상으로의 투사를 결정할 때에, 통로 이력이 고려될 수 있을 것이다. 이 방식에서, 투사 포인트는 상기 폴리라인의 원점을 향하여 절대로 거꾸로 돌아가지 않을 것이라는 것이 보장될 수 있을 것이다.

몇몇의 경우들에서, 상기 경로의 원점과 목적지가 폴리라인 상에 놓여있지 않는다면 상기 폴리라인은 경로 재구축을 수행하기 이전에 원점과 목적지로 확장될 수 있을 것이다. 이것은 어떤 방식 포인트들에 관련해서 또한 수행될 수 있을 것이다. 원점과 목적지가 상기 폴리라인 상에 놓여있지 않는다면 그 폴리라인을 그 원점과 목적지로 확장하기 보다는, 상기 원점이나 목적지 포인트로부터 상기 폴리라인의 세그먼트로의 직교 투사가 존재할 것이며, 심지어 벌점 팩터가 상기 원점이나 목적지에 상관되지 않는다고 하더라도, 그러면 그 벌점 팩터는 이 투사에 대하여 간단하게 유도될 수 있을 것이다. 상기 폴리라인의 말단 부분들로 투사되는, 세그먼트들 또는 그 세그먼트들 상의 포인트들에 관하여 결정된 벌점 팩터의 크기는 상기 폴리라인의 중간 부분들 상으로 투사하는 포인트들에 대해 결정된 벌점 포인트에 비해 줄어들 수 있을 것이다. 이것은 상기 원점 및 목적지로의 더 매끄러운 접근들을 허용할 수 있다.

재구축될 경로가 이전에 계획된 경로이며, 여전히 운행될 경로인 경우를 특히 참조하여 본 발명의 실시예들이 설명되었지만, 폴리라인의 사용을 포함한 여기에서 설명된 기술들은, 예를 들면, 내비게이션 디바이스에 의해 이전에 이동했던 경로를 재구축하는데 있어서도 동등하게 유용할 수 있다는 것이 이해된다. 그런 한 실시예가 예로서, 그리고 도 7, 도 8b 및 도 8b를 참조하여 이제 설명될 것이다.

도 7의 단계 600에서, 내비게이션 디바이스는 주어진 시작 포인트 및 종료 포인트 사이에서 만들어진 여정을 나타내는 타임-스탬프 (time-stamped) 위치 데이터를 저장한다. 그 위치 데이터는 GNSS 데이터 또는 유사한 모습, 즉, 상기 디바이스가 그 위치에 있었던 시각을 표시하는 연관된 시간적인 데이터를 구비한 복수의 지리적인 좌표들 (예를 들면, 위도 및 경도)이다. 그래서, 그것은 어떤 특별한 전자 지도에 대한 참조에 의한 것이 아니다. 상기 디바이스는 그 디바이스와 연관된 차량에 의한 상기 경로를 따른 이동 동안에 상기 데이터를 수집할 수 있을 것이다. 도 8a는 포인트 A 및 포인트 B 사이의 여정의 표현인 그런 데이터 (700)를 도시한다.

나중에, 이전에 이동했던 경로를 그 시각에 상기 디바이의 전자 지도 데이터에 관련하여 재구축할 것이 소망될 수 있을 것이다. 예를 들면, 그 경로를 따라 사용자를 안내하기 위해 내비게이션 지시들을 제공하거나, 또는 그 경로를 디스플레이하는 것이 소망될 수 있을 것이다. 이것을 하기 위해서, 상기 디바이스는 상기 타임-스탬프 위치 데이터에 의해 정의된 경로의 폴리라인 표현을 생성한다 - 단계 602. 그 폴리라인은 상기 위치 데이터에 의해 표시된 상기 경로를 대체적으로 따른다. 그 폴리라인 데이터는 이전의 실시예들에서처럼 상기 폴리라인을 제공하기 위해 라인 세그먼트들에 의해 연결된 상기 포인트들을 정의하는 좌표들의 목록의 모습일 수 있다.

단계 604에서, 상기 디바이스는 자신의 전자 지도 데이터 상에 폴리라인을 표현한다. 그러면 상기 디바이스는 A 및 B 사이에서 상기 전자 지도에 의해 표현된 상기 운행 가능 네트워크를 통한 경로를 생성하며, 이것은 가능한 가깝게 상기 폴리라인을 따른다 - 단계 606. 이것은 어떤 적합한 방식으로, 예를 들면, 이전의 실시예들에서 설명된 것처럼 상기 폴리라인으로부터 더 먼 거리에 있는 운행 가능 세그먼트들에게 벌점을 부여함으로써 수행될 수 있을 것이다. 상기 폴리라인을 경로 재구축에서의 안내로서만 사용할 것을 추구한 이전의 실시예와는 대조적으로, 이 추가의 실시예들에서의 목표는 상기 폴리라인과 가능한 가깝게 매치하는 경로를 획득하는 것이다. 그래서, 상기 폴리라인으로부터 먼 경로 설정의 결과가 될 수 있을 전형적인 다른 경로 설정 고려들은 고려되지 않을 것이다. 도 8b는 위치 데이터 (700) 상에 중첩된 세그먼트들 (720)로 만들어진 전자 지도에 의해 표현된 운행 가능 네트워크를 통해 이 방식으로 생성될 수 있을 경로 (710)를 도시한다.

상기 디바이스는 상기 결정된 경로를 만드는 세그먼트 ID들의 목록을 생성한다 - 단계 608. 도 8c는 A 및 B 사이에서 생성된 경로를 형성하는 스트레치 S1을 따른 세그먼트 1 - 세그먼트 7의 목록을 도시하며, 이는 A 및 B 사이의 여정을 표현하는 위치 데이터를 기초로 하는 폴리라인을 따른다. 이 방식에서, 이전에 이동했던 경로를 타임-스탬프 위치 데이터의 모습으로 저장하고, 그리고 폴리라인을 이용하여 전자 지도 데이터에 관련된 경로를 그 후에 재구축하여, 심지어는 그 경로로 처음으로 이동했던 이래로 상기 디바이스의 전자 지도 데이터가 업데이트 되는 경우에도, 상기 경로를 정확하게 재구축하는 것이 가능하다. 이는 처음에 이동했던 경로가, 특별한 전자 지도에 대한 참조에 의해서가 아니라 위치 데이터의 면에서 기록되었기 때문이다

다른 디바이스가 이동했던, 이전에 이동했던 경로를 재구축하기 위해서 물론 이 기술들이 적용될 수 있지만, 상기 경로를 나타내는 적합한 위치 데이터가 재구축을 수행하려고 하는 내비게이션 디바이스에게 제공될 수 있다면, 상기 내비게이션 디바이스가 상기 경로를 재구축하는 것은 필수적인 것은 아니다. 추가로, 상기 재구축은 PND에 의해 수행될 필요는 없으며, 경로 계획을 구비한, 그리고 옵션으로는 내비게이션 기능성을 구비한 어떤 디바이스에 의해서도 수행될 수 있을 것이다.

이 추가의 실시예들에서 사용될 수 있을 이전에 이동했던 경로를 나타내는 데이터의 일 예는 다음과 같다. 상기 타임-스탬프 위치 데이터는 상기 경로의 기본적인 세부 내용들, 즉, 경로 식별자, 이동했던 시간, 원점 포인트 및 목적지 포인트와 함께 데이터베이스에 저장된다. 상기 경로의 기본적인 상세 내용들은 다음과 같을 수 있다:

경로	시각	요일	From	To
R1	10:30	수요일	A	B

경로 상세 내용과 연관된 상기 상세한 타임-스탬프 위치 데이터는 도 8a에 도시된 것 같은, 위치 트레이스 또는 유사한 것을 나타날 수 있을 것이다. 그런 위치 데이터의 한 예는 다음과 같을 것이다:

경로	시퀀스	포인트
R1	1	52.12735,4.89283
R1	2	52.12755,4.89291
R1	3	52.12799,4.89392
R1	4	52.12801,4.92274
R1	5	52.12892,4.93043
R1	6	52.12163,4.94377
R1	기타	기타

이 위치 데이터는 상기 경로 내 각 포인트의 좌표들을 시퀀스로 열거한다. 상기 포인트들을 시간 상 동등하게 이격되며, 알려진 간격을 가진다.

이 방식에서, 이전에 이동했던 경로들의 개수에 관련한 트레이스들을 포함하는 데이터베이스가 구축되고, 그리고, 예를 들면, 내비게이션 디바이스에 의해 저장될 수 있다. 주어진 전자 지도에 관련하여 특별한 경로를 재구축할 것이 소망될 때에, 디바이스는 그 경로를 위한 관련된 GPS 데이터에 간단하게 액세스하고, 그리고 위에서 설명되듯이 폴리라인을 이용하여 상기 경로를 재구축할 수 있다. 이것은 여러 경로들에 대해 반복될 수 있을 것이다. 예를 들면, 이전에 이동했던 경로를 나타내는 GPS 정보의 데이터베이스는 경로들의 데이터베이스로 변환될 수 있을 것이며, 이 시간은 전자 지도에 대한 참조에 의한 것이다.

상기에서 주어진, 그리고 도 8a - 도 8b에서 도시된 예에서, 전자 지도에 관련하여 재구축된 경로 R1을 나타내는 데이터는 다음의 경로 개관 및 경로 내에 포함된 세그먼트 ID들의 상세 내용에 의해 정의될 수 있을 것이다.

경로	시각	요일	From	To	스트레치
R1	10:30	수요일	A	B	S1

스트레치	시퀀스	세그먼트 ID
S1	1	8271346
S1	2	8271347
S1	3	8271352
S1	4	8271392
S1	5	8273343
S1	6	8272167
S1	7	8272735

이 추가의 실시예들에서 이전에 이동했던 경로들은, 예를 들면, 통근 경로들, 또는 이동될 수 있을 다른 경로들일 수 있다.

(임의의 동반 청구항들, 요약 및 도면들을 포함하는) 본원에 개시된 모든 특징들, 그리고/도는 그렇게 개시된 임의 방법 또는 프로세스의 단계들 모두는, 그런 특징들 및/또는 단계들 중 적어도 몇몇이 상호 배타적인 경우의 조합을 제외하면, 어떤 조합으로도 결합될 수 있을 것이다.

(임의의 동반 청구항들, 요약 및 도면들을 포함하는) 본원에 개시된 각 특징은, 명시적으로 다르게 선언되지 않았다면, 동일한, 등가의 또는 유사한 목적에 소용이 되는 대안의 특징들에 의해 교체될 수 있을 것이다. 그래서, 명시적으로 다르게 선언되지 않았다면, 개시된 각 특징은 일반적인 일련의 등가의 또는 유사한 특징들의 한 예일 뿐이다.

본 발명은 어떤 전술한 실시예들의 상세 내용들로도 한정되지 않는다. 본 발명은 (어떤 동반 청구항들, 요약들 및 도면들을 포함하는) 본원에서 개시된 특징들의 어떤 신규한 것, 또는 어떤 신규한 조합, 또는 그렇게 개시된 어떤 방법 또는 프로세스의 단계들의 어떤 신규한 하나 또는 어떤 신규한 조합으로도 확장된다. 청구항들은 전술한 실시예들만이 아니라 본 청구항들의 범위 내에 포함된 임의 실시예도 또한 커버하기 위해 구축되어야 한다.

Claims

전자 지도에 의해 커버된 영역에서 운행 가능한 네트워크를 통해 경로를 재구축하는 방법으로, 상기 전자 지도는 상기 운행 가능한 네트워크의 운행 가능한 세그먼트들을 표현하는 복수의 세그먼트들을 포함하며, 상기 방법은:
상기 운행 가능 네트워크를 통한 경로를 표현하는 폴리라인을 나타내는 데이터를 획득하는 단계로, 상기 경로는 상기 전자 지도에 관련하여 재구축될 것인, 획득 단계; 그리고
상기 전자 지도에 의해 표현된 상기 운행 가능한 네트워크를 통해 경로를 생성하는데 있어서 상기 폴리라인을 표시하는 상기 획득된 데이터를 이용하는 단계를 포함하며,
상기 생성된 경로는 상기 전자 지도와 관련하여 상기 운행 가능 네트워크를 통해 상기 폴리라인에 의해 표현된 상기 경로의 재구축을 제공하며, 그리고
상기 경로를 생성하는 것은 상기 전자 지도 상에 표현된 상기 폴리라인에 아주 더 근접한 상기 생성된 경로 내에 포함되는 것을 위해서 상기 전자 지도의 세그먼트들을 선호하는 것을 포함하는, 방법.
제1항에 있어서,
상기 전자 지도 상에 표시된 폴리라인에 기초한 영역을 한정하는 단계, 그리고 경로 생성의 목적을 위해 상기 영역 내에 있는 것으로 간주되는 상기 전자 지도의 세그먼트들을 선호하는 단계를 포함하며,
옵션으로는 상기 영역은 상기 폴리라인을 따라 확장하는 회랑 (corridor)의 모습인, 방법.
제1항 또는 제2항에 있어서,
경로 생성의 목적을 위해 상기 전자 지도의 세그먼트들에게, 상기 전자 지도 상에 표현된 폴리라인에 대한 각 세그먼트들의 근접함에 종속하는 등급으로 벌점을 부여하는 단계를 포함하며, 상기 폴리라인으로부터 더 멀리 있는 세그먼트들은 그 폴리라인에 더 가깝게 있는 세그먼트들보다 더 큰 등급으로 벌점을 부여받는, 방법.
제3항에 있어서,
세그먼트들은, 상기 폴리라인으로부터의 상기 세그먼트의 거리에 종속한 가변 벌점 팩터를 그 세그먼트들에 적용함으로써 벌점을 부여받는, 방법.
제4항에 있어서,
세그먼트들에 적용된 상기 벌점 팩터는 세그먼트와 상기 폴리라인 사이의 거리의 제곱에 비례하여 변하는, 방법.
제3항 내지 제5항 중 어느 한 항에 있어서,
세그먼트들은 그 세그먼트들에 벌점 팩터를 적용함으로써 벌점을 부여받으며, 상기 벌점 팩터는 경로 생성에 있어서 고려된 세그먼트를 통과하는 것과 연관된 비용 팩터를 제공하기 위해 사용되는, 방법.
전술한 항들 중 어느 한 항에 있어서,
상기 폴리라인에 의해 표현된 상기 경로의 재구축을 제공하기 위해 상기 경로를 생성하는 것은 상기 운행 가능 네트워크를 통해 최소 비용 경로를 생성하는 단계를 포함하는, 방법.
전술한 항들 중 어느 한 항에 있어서,
상기 폴리라인을 나타내는 데이터를 획득하는 단계 그리고 상기 전자 지도에 의해 표현된 상기 운행 가능한 네트워크를 통해 상기 경로를 생성하는데 있어서 상기 획득된 데이터를 이용하는 단계는 내비게이션 디바이스에 의해 수행되며, 그 내비게이션 디바이스는 상기 전자 지도를 나타내는 데이터를 저장하는, 방법.
제8항에 있어서,
재구축될 상기 경로는 상기 내비게이션 디바이스로부터 외부 (off-board)에서 생성된 미리-계획된 경로이며, 옵션으로는 상기 경로는 상기 내비게이션 디바이스에 의한 요청에 응답하여 서버에 의해 계획된 것인, 방법.
전술한 항들 중 어느 한 항에 있어서,
재구축될, 상기 운행 가능 네트워크를 통한 상기 경로를 나타내는 데이터를, 상기 경로를 표현하는 폴리라인을 나타내는 데이터를 생성하기 위해 이용하는 단계를 더 포함하는, 방법.
전술한 항들 중 어느 한 항에 있어서,
재구축될 상기 경로는 제1 로케이션과 제2 로케이션 사이의 미리-계획된 경로이며, 옵션으로는 재구축될 경로를 생성하는 단계는 라이브 데이터 (live data)를 고려하는, 방법.
제1항 내지 제10항 중 어느 한 항에 있어서,
재구축될 상기 경로는 상기 네트워크를 통해 이전에 이동했던 경로인, 방법.
제12항에 있어서,
상기 이동했던 경로를 나타내는 위치 데이터 그리고 타이밍 데이터를 획득하는 단계, 그리고
그 데이터를 이용하여 상기 경로를 표현하는 상기 폴리라인을 나타내는 데이터를 생성하는 단계를 더 포함하는, 방법.
제13항에 있어서, 제8항에 종속될 때에,
상기 내비게이션 디바이스는 상기 위치 데이터 및 연관된 타이밍 데이터를 획득하고, 그리고 그 데이터를 이용하여 폴리라인 데이터를 생성하는 상기 단계들을 추가로 수행하며,
상기 이전에 이동했던 경로는 상기 내비게이션 디바이스가 이동했던 경로인, 방법.
제14항에 있어서, 상기 방법은,
상기 내비게이션 디바이스가,
상기 내비게이션 디바이스의 전자 지도에 의해 커버된 상기 영역에서 상기 운행 가능 네트워크를 통해 상기 디바이스가 이전에 이동했던 복수의 경로들을 나타내는 데이터를 저장하고, 그리고
각 경로에 대해, 상기 경로를 표현하는 폴리라인을 나타내는 정보를 생성하기 위해 상기 이전에 이동했던 경로 데이터를 이용하고,
상기 전자 지도에 의해 표현된 상기 운행 가능 네트워크를 통해 경로를 생성하기 위해 폴리라인을 나타내는 상기 획득된 데이터를 이용하고, 상기 생성된 경로는 상기 폴리라인에 의해 표현된 상기 경로의 재구축을 제공하며, 그리고
상기 재구축된 경로를 나타내는 데이터를 저장하는 것을 포함하는 방법.
제1항 내지 제11항 중 어느 한 항에 있어서,
상기 폴리라인을 나타내는 데이터를 획득하는 상기 단계는 무선 통신 링크를 통해, 옵션으로는 서버로부터, 상기 데이터를 수신하는 단계를 포함하는, 방법.
전술한 항들 중 어느 한 항에 있어서,
상기 수신된 폴리라인 데이터는 재구축에서의 사용을 위해 상기 전자 지도 데이터와 연관되며, 또는 상기 전자 지도 데이터를 인출하기 위해 사용될 수 있는 데이터와 연관되며,
상기 방법은 상기 경로 재구축에서 사용하기 위해 상기 전자 지도 데이터를 수신하여 저장하는 단계를 더 포함하는, 방법.
전술한 항들 중 어느 한 항에 있어서, 상기 방법은,
상기 생성된 경로를 사용자에게 출력하는 단계 및/또는
상기 경로를 따라 사용자를 안내하기 위한 내비게이션 지시들의 세트를 제공하는 단계를 더 포함하는, 방법.
전자 지도에 의해 커버된 영역 내 운행 가능한 네트워크를 통한 경로를 재구축하기 위한 경로 설정 시스템으로, 옵션으로는 내비게이션 디바이스로서, 상기 전자 지도는 상기 운행 가능한 네트워크의 운행 가능한 세그먼트들을 표현하는 복수의 세그먼트들을 포함하며, 상기 시스템은:
상기 운행 가능한 네트워크를 통한 경로를 표현하는 폴리라인을 나타내는 데이터를 획득하기 위한 수단으로, 그 경로는 상기 전자 지도에 관련하여 재구축될 것인, 수단; 그리고
상기 전자 지도에 의해 표현된 상기 운행 가능 네크워크를 통해 경로를 생성하는데 있어서 상기 폴리라인을 나타내는 상기 획득된 데이터를 이용하기 위한 수단을 포함하며,
상기 생성된 경로는 상기 전자 지도와 관련하여 상기 폴리라인에 의해 표현된 상기 경로의 재구축을 제공하며, 그리고
상기 경로를 생성하는 것은 상기 전자 지도 상에 표현된 상기 폴리라인에 아주 더 근접한 상기 생성된 경로 내에 포함되는 것을 위해서 상기 전자 지도의 세그먼트들을 선호하는 것을 포함하는, 시스템.
제19항에 있어서,
폴리라인을 나타내는 데이터를 획득하기 위한 상기 수단은 무선 통신 링크를 통해, 옵션으로는 서버로부터, 그런 데이터를 수신하기 위한 수단을 포함하는, 시스템.
제19항에 있어서,
상기 폴리라인을 나타내는 데이터를 획득하기 위한 상기 수단은 재구축될 상기 경로를 나타내는 데이터를 이용하여 상기 폴리라인을 표시하는 데이터를 생성하기 위한 수단을 포함하는, 시스템.
컴퓨팅 디바이스의 적어도 하나의 프로세서에 의해 실행될 때에 상기 컴퓨팅 디바이스로 하여금 제1항 내지 제18항 중 어느 한 항의 방법에 따라서 동작하도록 하는 지시들을 포함하는 컴퓨터 프로그램 제품.
저장된 제22항의 컴퓨터 프로그램 제품을 구비한 비-일시적 컴퓨터 판독가능 매체.