KR100339763B1

KR100339763B1 - 지도 데이터베이스 장치

Info

Publication number: KR100339763B1
Application number: KR1019997005340A
Authority: KR
Inventors: 노무라다카시
Original assignee: 하기와라 가즈토시; 가부시키가이샤 자나비 인포메틱스
Priority date: 1996-12-16
Filing date: 1997-12-16
Publication date: 2002-06-05
Also published as: EP0953954A4; DE69733151T2; EP0953954B1; KR20000057581A; JP3905136B2; WO1998027534A1; DE69733151D1; EP0953954A1; US6023655A

Abstract

본 발명은 지도 데이터베이스 장치에 관한 것으로서, 시단과 종단에 노드를 갖는 링크에 관한 데이터를 복수개 이용하여 도로를 나타냄과 동시에 축척률이 다른 지도마다 따로 설치된 복수의 링크에 관한 데이터가 축척률이 가장 작은 상위레벨에서 축척률이 가장 큰 하위레벨의 도로 지도데이터로서 각각 저장되고, 상위 레벨의 하나의 지도 영역을 복수로 분할한 M개의 소영역내의 상세 정보의 각각이 하위 레벨의 하나의 지도 영역의 도로 지도 데이터로서 M개 기억되는 지도 데이터베이스 장치에 있어서, 축척률이 작은 상위레벨의 도로지도데이터와 축척률이 큰 하위 레벨의 도로 지도데이터와의 대응관계를 나타내는 레벨간 대응 데이터로서 상위 레벨에서 하위 레벨을 본 경우의 각 레벨의 노드의 대응 정보가 설치되어 있는 것을 특징으로 한다.

Description

지도 데이터베이스 장치{MAP DATABASE DEVICE}

차량 위치 주변의 도로지도를 표시하는 기능과 맵매칭을 실시하여 차량 위치를 정확하게 검출하는 기능 및 출발지에서 목적지까지의 추장 루트를 연산하는 기능 등을 겸비한 차량용 네비게이션 장치가 알려져 있다. 이 종래의 차량용 네비게이션 장치에서는 기존의 소프트웨어와의 호환성을 유지하면서 또 처리 속도를 올리기 위하여 도로지도 표시용 데이터, 맵매칭용 데이터 및 루트 탐색용 데이터를 1장의 CD-ROM에 각각 따로 저장하고 있다.

도로 지도 표시용 데이터는 축척률이 가장 작고 넓은 지역을 표시하기 위한 최고 넓은 지도 데이터와, 축척률이 가장 크고 좁은 지역을 상세하게 표시하는 최고 상세 지도 데이터와, 최고 넓은 지역 지도 데이터와 최고 상세 지도 데이터의 사이의 다른 축척률의 복수의 지도 데이터를 구비하고 있다. 예를들면 최고 넓은 지역 지도 데이터를 레벨 4의 데이터, 최고 상세 지도 데이터를 레벨 1의 데이터, 레벨 4와 레벨 1 사이의 데이터를 각각 레벨 3 및 레벨 2의 데이터라고 한다.

도 23은 상기 레벨 4, 레벨 3 및 레벨 2로서 기억하는 도로 지도 표시용 데이터의 도로 지도를 설명하는 도면이며, CD-ROM에는 레벨 4의 도로 지도 표시용 데이터와 레벨 3의 도로 지도 표시용 데이터 및 레벨 2의 도로 지도 표시용 데이터가 각각 기억된다. 도 23은 레벨 4의 1개의 메시(M4)의 도로 지도를 나타내며, 이 메시(M4)에는 1개의 도로(D1)와 도로(D1)의 교차점(n3)에 접속되는 도로(D2)와 도로(D1)의 양 단의 교차점(n1, n2)에 접속되는 2개의 도로(D3, D4)가 존재해 있다. 레벨 4의 1개의 메시(M4)를 16등분한 해칭으로 나타낸 소영역(m3)이 레벨 3의 1개의 메시(M3)가 되고, 도 23에 나타내는 바와 같이 메시(M3)에는 도로(D1, D2)의 일부분이 존재한다. 레벨 3의 1개의 메시(M3)를 16등분한 해칭으로 나타내는 소영역(m2)이 레벨(2)의 1개의 메시(M2)가 되고, 도 23에 나타내는 바와 같이 메시(M2)에는 도로(D1, D2)의 일부분과 도로(D1)에 접속되어 있는 도로(D5, D6) 등이 존재한다.

추장 경로 탐색 기능을 갖는 네비게이션 장치에서는 상기한 도로 지도 데이터와는 따로 루트 탐색용 데이터를 구비하고 있다. 루트 탐색에는 도로 형상은 필요가 없기 때문에 루트 탐색용 데이터는 어떤 노드(본 명세서에서는 자노드라고 함)와 그것에 접속되어 있는 노드(본 명세서에서는 인접노드라고 함)의 데이터를 갖는다. 노드 데이터에는 노드의 위치 좌표가 포함된다.

예를 들면, 도로 지도 데이터의 레벨 4와 레벨 2에 대응하는 2개의 루트 탐색용 데이터를 구비하고, 루트 탐색을 할 때는 출발지 근방과 목적지 근방을 레벨 2로 탐색하고, 그 이외의 영역을 레벨 4에서 탐색하도록 하여 루트 탐색 시간을 단축화하고 있다.

이와같은 종래기술에서는 상위 레벨과 하위 레벨 사이의 노드의 대응을 작은 기억 용량으로 효율적으로 실시함과 동시에 높은 신뢰성을 실시하는 것이 요구되고 있다.

본 발명은 바람직하게는 차량용 네비게이션 장치 등에 탑재되어 도로 지도 표시, 맵매칭 및 추장 루트의 연산 등에 사용되는 지도 데이터베이스 장치에 관한 것이다.

도 1은 본 발명에 의한 지도 데이터베이스 장치를 사용한 차량용 네비게이션 장치의 한 실시형태의 블록도,

도 2는 메시 영역내에서 2개의 도로가 교차하는 예를 나타내는 도면,

도 3은 링크열 데이터를 설명하는 도면,

도 4는 도로 지도 표시용 데이터의 구성을 나타내는 도면,

도 5는 복수의 노드 및 보간점을 갖는 도로 지도의 예를 나타내는 도면,

도 6은 도 6의 굵은 선 도로의 링크열 데이터를 나타내는 도면,

도 7은 링크열 데이터에 부가되기 직전의 데이터를 판독하기 위한 오프셋 정보를 나타내는 도면,

도 8은 링크열 데이터를 최후미에서 판독하는 경우의 판독 방법을 나타내는 도면,

도 9A∼도 9D는 노드 정보나 보간점 정보의 데이터 길이의 종류를 나타내는 도면,

도 10A, 도 10B는 속성1+X좌표 데이터의 한 예를 나타내는 도면,

도 11A, 도 11B는 속성2+Y좌표 데이터의 한 예를 나타내는 도면,

도 12는 루트 탐색용 데이터의 데이터 구성을 나타내는 도면,

도 13은 경로 탐색용 레벨간 대응 데이터의 데이터 구성을 설명하는 도면,

도 14A, 도 14B는 자노드 대응 정보와 인접 노드 대응 정보를 설명하는 도면,

도 15는 각 레벨의 분할 테두리(메시)수와 그 메시를 특정하는 코드를 설명하는 도면,

도 16은 레벨 4와 레벨 2의 자노드와 인접 노드를 설명하는 도면,

도 17은 도 16에서의 레벨간 대응 데이터의 한 예를 나타내는 도면,

도 18은 추장 루트 데이터의 데이터 구성의 개요를 나타내는 도면,

도 19의 (A), (B)는 추장 루트 데이터의 노드정보와 링크정보의 데이터 구성의 상세도,

도 20은 레벨 4와 레벨 2의 데이터에 의한 경로 탐색을 설명하는 도면,

도 21은 제어회로가 실시하는 메인 처리의 개요를 나타내는 플로우차트,

도 22는 도 21에 계속되는 플로우차트,

도 23은 레벨 4, 레벨 3, 레벨 2의 도로를 설명하는 도면,

도 24는 링크 데이터와 노드 데이터의 종래예를 나타내는 도면,

도 25는 교차점을 경계로 하여 각 도로를 각각 다른 링크로 하는 종래예를 설명하는 도면,

도 26은 네비게이션 장치를 컴퓨터에 의해 실현한 경우의 도면, 및

도 27은 메시 코드의 취급 방법에 대해서 설명하는 도면이다.

본 발명의 목적은 각 레벨간에서의 동일 도로에 관한 데이터의 대응을 작은 기억 용량으로, 또 높은 신뢰성으로 실시하도록 한 지도 데이터베이스 장치를 제공하는데 있다.

상기 목적을 달성하기 위해 시단과 종단에 노드를 갖는 링크에 관한 데이터를 복수개 사용하여 도로를 나타냄과 동시에 축척률이 다른 지도마다 따로 설치된 복수의 링크에 관한 데이터가 축척률이 가장 작은 상위 레벨에서 축척률이 가장 큰 하위 레벨의 도로 지도 데이터로서 각각 저장되며, 상위 레벨의 하나의 지도 영역을 복수로 분할한 M개의 소영역내의 상세정보의 각각이 하위 레벨의 하나의 지도 영역의 도로 지도 데이터로서 M개 기억되는 지도 데이터베이스 장치에 있어서, 축척률이 작은 상위레벨의 도로 지도 데이터와 축척률이 큰 하위레벨의 도로 지도 데이터와의 대응 관계를 나타내는 레벨간 대응 데이터로서, 상위레벨에서 하위 레벨을 본 경우의 각 레벨의 노드의 대응 정보가 설치된다.

또한, 다른 태양에서 레벨간 대응 데이터는 경로 탐색용 데이터이며, 그 경로 탐색용 데이터는 상위 레벨의 자노드에 인접하는 상위 인접 노드의 번호와 그 상위 자노드에 대응하는 하위 레벨의 자노드에 인접하는 하위 인접 노드의 번호를대응하여 설치되어 있다.

도 1은 본 발명의 지도 데이터베이스 장치를 내부에 갖는 차량용 네비게이션장치의 한 실시형태의 블록도이다. 도 1에서 도면부호 “1”은 차량의 현재 지점을 검출하는 현재 지점 검출장치로서, 예를 들면 차량의 진행방위를 검출하는 방위센서나 차속을 검출하는 차속센서 및 GPS(Global Positioning System) 위성으로부터의 GPS신호를 검출하는 GPS센서 등으로 이루어진다.

도면부호 “2”는 장치 전체를 제어하는 제어회로이며, 마이크로프로세서 및 그 주변회로로 이루어진다. 도면부호 “3”은 차량의 목적지 등을 입력하는 입력장치, 도면부호 “4”는 현재 지점 검출장치(1)에 의해 검출된 차량위치정보 등을 저장하는 DRAM, 도면부호 “5”는 표시장치(6)에 표시하기 위한 화상 데이터를 저장하는 화상메모리이며, 화상메모리(5)에 저장된 화상데이터는 적절하게 판독되어 표시장치(6)에 표시된다. 도면부호“7”은 제어회로(2)가 연산한 추장 루트상의 노드 정보나 링크정보 등을 저장하는 SRAM이다.

도면부호 “8”은 도로 지도 표시, 경로 탐색(루트 탐색) 및 맵매칭 등을 실시하기 위한 여러가지 데이터를 저장하는 지도 데이터베이스 장치로서, 예를 들면 CD-ROM장치나 자기 기록 장치 등으로 구성된다. 도면부호 “9”는 이 지도 데이터베이스 장치에 장전되는 상기 데이터가 기록된 기록 매체이며, 예를 들면 CD-ROM이다. 단순히 지도 데이터베이스 장치라는 경우는 이 기록매체도 포함하는 것이다. 지도 데이터베이스 장치(8)에는 도로 형상이나 도로 종별에 관한 정보 등으로 이루어진 지도 표시용 데이터와 도로 형상과는 직접 관계없는 분기점 정보나 교차점 정보 등으로 이루어진 루트 탐색용 데이터가 저장되어 있다. 지도 표시용 데이터는 주로 표시장치(6)에 도로 지도를 표시할 때 사용되며, 루트 탐색용 데이터는 추장경로(추장루트)를 연산할 때 사용된다.

다음으로, 지도 데이터베이스 장치(8)에 저장되어 있는 지도 표시용 데이터와 루트 탐색용 데이터의 데이터 구성에 대해서 설명한다.

[1]지도표시용 데이터

(1) 링크열 데이터의 개요

본 실시형태의 지도표시용 데이터는 도로지도를 소정 범위마다 구분한 메시영역마다 데이터를 관리하고 있으며, 메시영역내에 존재하는 각 도로를 각각 다른 링크열로 한다. 예를 들면, 도 2에 나타내는 바와 같이 1개의 메시영역내에서 2개의 도로(D1, D2)가 교차하는 경우에는 각 도로를 각각 다른 링크열 1, 2로 나타내는 것으로 하고, 링크열 1은 링크 11, 12로 구성되며, 링크열 2는 링크 21∼23으로 구성되는 것으로 한다. 이 경우, 링크열 1의 각 링크, 링크열 2의 각 링크는 동일 종별의 도로이다. 링크는 도로를 나타내는 최소단위이며, 도 2에서는 교차점 사이를 한개의 링크 단위로 하여 각 링크에 고유 번호(이하, 링크번호라고 함)을 붙여 구별한다. 도 2의 교차점, 즉 각 링크의 접속점을 노드(N0∼N4)로 나타내고 있다. 노드는 각 링크의 시점과 종점이 있으며, 후술하는 바와 같이 노드간을 자세하게 구분하는 보간점(補間点)을 설치하는 경우도 있다.

또한, 본 실시형태에서는 다리나 터널 등과 같이 도로상에 특징적인 구조물이 있는 경우에는 그 전후의 도로를 다른 링크열 데이터로 한다. 예를 들면, 도 3에 나타내는 바와 같이, 국도 246호상에 다리 및 터널이 있는 경우에는 다리 및 터널의 앞, 다리 및 터널 구간, 다리 및 터널 끝을 각각 다른 링크열로 한다. 도 3에서는 이것들을 링크열 101∼105로 나타내고 있다. 이와같이, 도로상의 특징적인구조물을 경계로 하여 그 전후를 다른 링크열로 하여 도로지도상의 다리나 터널 등을 용이하게 검색할 수 있게 된다.

지도 표시용 데이터는 축척률이 다른 복수의 데이터를 갖는다. 본 실시형태에서는 각 축척률의 데이터를 레벨 n(n은 예를 들면 1∼4)의 데이터라고 한다. 레벨 1이 가장 상세한 도로지도이며, 레벨이 올라갈수록 소축척률로 넓은 영역의 도로 지도가 된다.

(2) 링크열 데이터의 데이터 구성

도 2의 도로에 대해서 설명하면 지도 표시용 데이터는 도 4에 나타내는 바와 같이, 링크열 1, 2∼n에 관한 각종 정보를 기술한 링크열 데이터를 링크열마다 설치하여 구성되며, 각 링크열의 데이터는 링크열 정보와 노드링크 정보를 갖고, 링크열 정보는 도 4에도 나타내는 바와 같이 다음과 같은 데이터로 구성된다.

①링크열 크기

②요소점수

③링크속성

④도로 명칭 오프셋

⑤노선번호

또한, 노드 링크 정보는 도 4에도 나타내는 바와 같이 다음 데이터로 구성된다.

①속성1+X좌표

②속성2+Y좌표

③동일 노드 오프셋

④유도 오프셋

⑤링크번호

⑥높이 정보

(3) 링크열 정보에 대해서

도 4에서, 링크열 크기는 링크열의 데이터 길이를 나타내는 데이터이다. 요소점수는 노드점수와 보간점수의 합계를 나타내는 데이터, 링크속성은 국도, 지방도로, 고속도로 등의 도로의 종류를 나타내는 데이터, 노선번호는 국도나 지방도로의 번호이다. 도로 명칭 오프셋은 이 실시형태에서는 관계가 없기 때문에 설명을 생략한다. 보간점은 후술한다.

(4) 노드 링크 정보에 대해서

도 5는 도 2에 나타내는 링크열 1 및 링크열 2를 상세하게 나타낸다. 예를 들면, 도 5의 굵은 선으로 나타낸 링크열 2의 노드 링크 정보는 도 6과 같이 된다. 도시한 바와 같이, 링크열 2의 데이터는 링크열상의 노드(N1, N2, N3)(도 5의 흑색 동그라미)에 관한 노드 정보와 보간점(도 5의 백색 동그라미)에 관한 보간점 정보를 포함한다. 노드 정보는 노드의 위치 좌표(X, Y)와 노드에 접속되는 링크의 속성과 링크번호를 갖고, 보간점 정보는 보간점의 위치 좌표(X, Y)를 갖는다. 이 위치좌표가 후술하는 추장 루트 표시용의 형상 데이터 또는 맵매칭용 형상 데이터로 이용된다. 도 5의 굵은 선의 링크열 2는 노드 N1와 NO2 사이의 링크번호 21의 링크와 노드 N02와 N3사이의 링크번호 22의 링크 및 노드(N3)에 접속된 링크번호 23의 링크를 갖는다. 도 6에서도 알 수 있는 바와 같이, 노드(NO2)의 노드 정보는 링크번호 21의 링크와 링크번호 22의 링크를 공유하고 있다. 이 노드 정보 및 보간점 정보는 링크의 접속순으로 데이터가 배치되어 있다. 이때문에, 링크열 데이터를 선두 어드레스에서 차례로 판독하여 링크열 전체의 도로 형상이나 도로종별 등을 검출할 수 있다.

이와같이, 본 실시형태에서는 1개의 메시영역내에서 링크열을 단위로 하여 데이터를 관리하여 인접하는 링크간의 노드는 서로 공유하기 때문에 도 24에 나타낸 종래예와 같이 링크를 단위로 데이터를 관리하는 경우에 비해 데이터의 총 용량을 줄인다. 도 24에서 링크(L0∼L3)는 각각 시점과 종점에 노드(N0b, N1a, N1b……N3a)를 갖고, 각 노드에는 접속 정보로서 동일 노드인 것을 나타내는 동일 노드 정보(C01……C10)가 설치되어 있다.

(5) 동일 노드를 나타내는 오프셋

도 5에서, 링크열 1과 링크열 2가 교차하는 지점의 노드의 부호를 링크열 1의 노드를 N01로 하고, 링크열 2의 노드를 N02로 하고, 또 링크열 3의 노드를 N03으로 한다. 이 경우, 이 교차점(NO1∼N03)의 노드 정보는 각각 동일 노드 오프셋이라는 데이터 항목을 갖고 있다.

도 7에 의해 동일 노드 오프셋을 상세하게 설명한다. 예를 들면 링크열 2의 노드(N02)의 동일 노드 오프셋으로는 링크열 1의 노드(N01)의 노드 정보가 기억된 어드레스값이 저장되며, 마찬가지로 링크열 1의 노드(NO1)의 동일 노드 오프셋으로는 링크열 3의 노드정보가 기억된 어드레스값이 저장되며, 링크열 3의 노드(N03)의동일 노드 오프셋으로는 링크열 2의 노드(N02)의 노드 정보가 기억된 어드레스값이 저장된다.

한편, 도 5의 교차점(N01∼N03)으로 나타내어진 교차점 이외의 노드는 다른 도로와 교차하고 있지 않기 때문에 이 노드의 노드정보의 동일 노드 오프셋 기억 영역에는 동일 노드에 관한 다른 노드가 존재하지 않는 것을 나타내는 특정 값, 예를 들면 FFFFh가 저장된다.

이와같이, 동일 노드 오프셋을 설치하여 교차점과 같이 동일 노드에 대해 복수의 노드 정보가 존재하는 경우에도 각 노드 정보의 대응 관계를 용이하게 파악할 수 있게 된다. 또한, 종래의 장치에서는 도 25에 나타내는 바와 같이 3개의 도로가 교차하는 교차점에 대응하는 노드를 5개(N0a∼N0d) 필요로 한 것에 비해 본 실시형태에서는 도 5에 나타내는 바와 같이 3개(N01∼N03)로 충분하기 때문에 데이터량을 삭감할 수 있다.

(6) 속성 1

노드의 X좌표와 함께 저장되는 속성 1은 링크열 데이터를 역방향으로 판독하기 위한 오프셋 정보이다. 상기한 바와 같이, 링크열 데이터에는 실제로 접속되어 있는 순서에 따라서 노드정보나 보간점 정보 등이 데이터 배치되어 있다. 이때문에, 링크열 데이터를 기억부의 선두어드레스에서 차례로 판독하면 선두위치로부터의 도로 형상을 정확하게 파악할 수 있다.

한편, 경우에 따라서는 링크열 데이터를 최후미부터 판독하여 최후미부터의 도로 형상을 파악할 필요가 생기는 경우도 있다. 이 경우, 최후미의 노드 정보나보간점 정보를 판독한 후에, 그 직전에 데이터가 배치되어 있는 노드 정보 등의 헤더 위치를 검출할 필요가 있다. 예를 들면 도 5의 굵은 선으로 나타내는 링크의 링크열 데이터(도 6)를 최후미부터 판독하는 경우를 생각하면 도 8에 화살표로 나타내는 바와 같이, 노드(N3)의 노드 정보를 판독한 후에 그 직전에 데이터가 배치되어 있는 보간점 정보의 헤더 위치를 검출하여 이 헤더위치에서 보간점 정보를 판독할 필요가 있다. 하지만,노드 정보나 보간점 정보의 데이터량은 이하에 설명하는 바와 같이 노드나 보간점에 따라서 달라 노드정보나 보간점 정보의 헤더 위치를 일률적으로 정할 수 없다.

도 9A∼도 9D는 노드 정보나 보간점 정보의 데이터량이 다른 경우를 설명하는 도면이며, 도 9A는 노드 정보 등이 X, Y 위치 좌표의 2워드로 구성되는 경우, 도 9B는 도 9A에 동일 노드 오프셋을 더한 3워드로 구성되는 경우, 도 9C는 도 9B에 유도 오프셋 정보를 더한 4워드로 구성되는 경우, 도 9D는 도 9C에 링크 번호를 더한 5워드로 구성되는 경우를 각각 나타낸다.

도 9A∼도 9D에 나타내는 바와 같이, 노드정보나 보간점 정보의 데이터량은 각 링크에 따라서 다르기 때문에 본 실시형태에서는 노드정보나 보간점 정보의 헤더위치를 나타내는 정보를 속성 1의 데이터로서 미리 링크열 데이터에 부가하고 있다. 이 실시형태에서는 각 노드나 보간점의 X위치 좌표와 함께 부가하고 있다.

예를 들면 도 10A는 속성1+X좌표 데이터를 구성하는 2바이트 데이터의 하위 11비트에 X위치 좌표를 저장하고, 상위 2비트에 각 노드 정보 등의 헤더 위치를 나타내는 정보를 저장하는 예를 나타내는 도면이다. 이 상위 2비트에는 각 노드정보등의 헤더위치까지 어떤 워드인지를 나타내는 정보가 저장된다.

이와 같이, 본 실시형태에서는 직전의 노드 정보 등의 헤더 위치를 나타내는 정보를 링크열 데이터에 부가하기 때문에 링크열 데이터를 역방향으로 판독하는 경우라도 모든 노드 정보 등을 누락하지 않고 판독할 수 있다.

(7) 속성 2

노드의 Y좌표와 함께 저장되는 속성 2는 교통규제 정보, 도로폭 정보, 차선수정보를 포함한다. 링크열 데이터를 구성하는 노드 링크 정보의 각 데이터의 데이터 길이는 16비트(2바이트=1워드)이다. 속성2+Y좌표를 나타내는 데이터의 하위 11비트에는 도 11A에 나타내는 바와 같이, 하위 11비트에 Y위치 좌표를 저장하고, 상위 5비트에 교통규제정보, 도로폭 정보 및 차선수 정보가 저장된다. 상위 5비트의 비트의 조합에 의해서 도 11B의 ①∼⑧중 어떤 하나의 정보가 선택된다.

이와 같이, 노드의 위치 좌표 등을 저장하기 위한 2바이트 데이터의 빈 비트를 이용하여 도로폭 정보와 교통 규제 정보 및 차선수 정보를 저장하도록 했기 때문에 데이터량을 늘리지 않고 도로폭 정보나 교통 규제 정보 등을 링크열 데이터에 부가할 수 있다.

(8) 높이 정보

도로 지도를 3차원으로 표시할 경우에는 도로 지도상의 복수의 지점에 대해서 표고차에 관한 데이터가 필요하게 된다. 따라서, 본 실시형태에서는 링크열을 구성하는 각 링크의 높이 정보를 정리하여 링크열 데이터의 최후미에 부가하고 있다. 또한, 높이 정보를 갖는 링크열 데이터와 높이 정보를 갖지 않는 링크열 데이터가 혼재하기 때문에 높이 정보는 복수의 노드 및 복수의 보간점에 각각 부가할 수 있다.

링크열 데이터에 높이 정보를 부가하여 도로 지도를 입체적으로 표시할 수 있게 된다. 또한, 높이 정보를 링크열 데이터의 최후미에 정리하여 부가하기 때문에 필요할 때만 높이 정보를 판독하면 좋고, 예를 들면 통상의 평면지도를 표시하는 경우와 같이 높이 정보가 불필요한 경우에는 높이 정보 직전까지의 데이터를 판독하면 좋다.

[2]루트 탐색용 데이터

루트 탐색용 데이터는 축척률이 다른 복수의 도로지도표시용 데이터에 대응하는 복수의 데이터를 갖고, 각 축척률의 데이터를 레벨 m(m은 예를 들면 2, 4)의 데이터라고 한다.

도 12는 루트 탐색용 데이터의 데이터 구성을 나타내는 도면이다. 루트 탐색용 데이터에는 도시한 바와 같이, 도로를 표현하는 최소 단위인 링크의 접속점(노드)마다 다른 노드와의 접속 관계를 나타내는 노드 정보가 저장되어 있다. 각 노드 정보는 각각 자노드 정보와 인접 노드 정보로 이루어지며, 자노드 정보중에는 노드의 위치 좌표가 저장되어 있다. 한편, 인접 노드 정보에는 도시한 바와 같이, 인접 노드번호와 자노드에서 인접 노드에 이르기까지의 링크의 링크번호와 그 링크의 링크 비용 및 그 링크의 교통규제정보가 저장되어 있다. 또한, 각 노드 정보는링크의 접속순으로 저장되어 있으며, 저장되는 순번에 의해 자노드의 노드번호를 파악할 수 있도록 되어 있다. 이때문에, 자노드정보로서 자노드의 노드번호를 저장하지 않아도 자노드의 노드번호를 파악할 수 있어 메모리 용량을 삭감할 수 있다.

[3] 루트 탐색용 레벨간 대응 데이터

도 13은 루트 탐색용 레벨간 대응 데이터의 데이터 구성을 나타내는 도면이다. 루트 탐색용 레벨간 대응 데이터는 각 레벨의 메시(예를 들어 도 23의 메시(M4, M3, M2))마다 설치되어 있다. 도 13은 1개의 메시에서의 레벨간 대응 데이터를 나타내는 것으로 대응 정보(l∼i)는 그 메시에 존재하는 노드의 수만큼 설치된다. 노드가 10이면 i=10이다. 또한, 메시 코드는 메시 코드란에 저장된다.

대응 정보(l∼i)의 각각에는 도시한 바와 같이 자노드 대응정보와 인접노드(#1∼#n) 정보를 기억하는 영역이 설치되어 있다. 자노드 대응 정보는 인접하는 노드 수, 해당 자레벨의 자노드에 관한 자레벨 정보 및 하위 레벨 정보를 포함하는 정보이다. 자레벨 정도는 해당하는 레벨의 노드(자노드라고 함)의 번호를 포함한다. 하위 레벨 정보는 대응하는 하위 레벨의 노드의 번호와 자노드가 존재하는 상위 레벨상의 소영역을 나타내는 분할 영역 번호를 포함하는 정보이다. 인접 노드(#1∼#n) 정보는 각각 자레벨 인접정보와 하위레벨 인접 정보를 포함하는 정보이다. 자레벨 인접 정보는 자레벨에서의 자노드에 인접하는 노드의 번호를 포함하며, 하위 레벨 인접 정보는 그 인접 노드에 대응하는 하위 레벨의 노드의 노드 번호와 자노드가 존재하는 상위 레벨상의 소영역을 나타내는 분할 소영역 번호를 포함하는 정보이다.

또한, 도 15는 이 분할 소영역 번호를 정했을 때 사용되는 방향 코드를 나타내는 도면이다. 최상위 레벨(n+4)은 분할 소영역이 1개, 즉 자기 자신을 나타내고 있다. 레벨(n+3)에서는 분할 소영역이 16(4×4)개, 레벨(n+2)에서는 분할 소영역이 256(16×16)개, 레벨(n+1)에서는 분할 소영역이 4096(64×64)개, 최하위 레벨(n)에서는 분할 소영역이 65536(256×256)개일 때의 적용 경도 방향 코드와 적용 위도 방향 코드가 도시되어 있다. 분할 소영역 번호는 이 적용 경도 방향 코드 2행과 적용 위도 방향 코드 2행으로 나타내어지고, 2바이트 필요해진다.

상기 분할 소영역 번호에 대해서 더욱 자세히 설명하기 전에 메시 코드에 대해 이하 설명한다. 메시라는 것은 상술한 바와 같이 도로 지도를 소정 범위마다 구분한 하나의 범위이다. 이 메시 각각에 소정 기준에 기초하여 메시 코드가 부여되어 있다. 도 27은 이 메시 코드의 취급방식에 대해서 설명하는 도면이다. 도 27은 위도 방향 40분, 경도 방향 1도의 크기를 1차 메시라고 하고, 이 1차 메시가 4장 모인 레벨 4의 하나의 메시(M40)를 나타내고 있다. 도 27은 또 레벨 4의 하나의 메시(M40)를 16분할한 레벨 3의 메시(M30), 그것을 더 16분할한 레벨 2의 하나의 메시(20)에 대해서도 나타내고 있다.

메시코드는 메시의 좌측 하부 모서리(남서방향의 모서리) 점의 위도 경도에 기초한 값으로 나타낸다. 1차메시의 메시코드는 위도에 3/2를 더한 값을 상 2행으로 하고, 경도에서 마이너스 100한 값을 하 2행으로 하여 합계 4행으로 나타낸다. 레벨 4의 메시는 1차 메시의 메시코드와 동일한 계산으로 4행으로 나타낸다. 따라서, 도 27의 레벨 4의 메시(M40)의 메시 코드는 35도 20분×(3/2)=53과 139도-100도=39에 의해 5339로 나타낸다. 또 레벨 4인 것을 나타내는 코드를 부가하여5339F4의 6행으로 나타낸다. 코드는 모두 1행 4비트로 나타내기 때문에 상기 6행의 경우는 3바이트 필요해진다.

레벨 3의 메시는 1차 메시가 4분할된 것이기 때문에, 그 4분할을 00, 01, 10, 11로 나타내고, 이 값을 1차 메시 코드에 부가하여 나타낸다. 예를 들면 도 27의 레벨 3의 메시(M31)의 메시 코드는 5339F311의 8행으로 나타낸다. F3은 레벨 3을 나타내고 있다. 도 27에서, 2차 메시는 1차 메시를 세로 8분할, 가로 8분할의 64분할한 것이다. 따라서, 2차 메시코드는 1차 메시코드에 00∼77의 코드를 부가하여 나타낸다. 예를 들면, 레벨 2의 메시(M20)는 533900으로 나타내고, 또 레벨 2인 것을 나타내는 코드가 부가되어 533900F2의 8행으로 나타낸다. 메시M21는 543977F2로 나타낸다.

분할 소영역 번호의 설명으로 되돌린다. 루트 탐색용 레벨간 대응 데이터는 상위 레벨이 있는 메시가 있는 노드가 하위 레벨의 어떤 메시의 어떤 노드에 대응하는지를 대응하기 위한 데이터이다. 따라서, 하위 레벨의 영역을 나타내는데는 상술한 각 레벨의 메시 코드를 직접 사용하는 것이 가장 알기 쉽다. 그러나, 메시코드를 나타내는데는 상술한 바와 같이 레벨 4에서는 6행, 레벨 3, 레벨 2에서는 8행 필요해지고, 또 하위 레벨로 가면 행수가 증가한다. 따라서, 루트 탐색용 레벨간 대응 데이터의 용량을 크게 할 필요가 있다. 따라서, 본 실시형태에서는 하위 레벨의 분할 소영역을 나타내기 위해 도 15에 도시한 방향 코드를 사용한 분할 소영역 번호로 하위 레벨의 영역을 나타내고 있다.

분할 소영역은 도 15에 도시한 바와 같이, 하위 방향으로 1레벨 내려갈 때마다 16분할하고, 최하층의 레벨에서는 256×256=65536으로 분할되어 5개의 레벨간에서 대응할 수 있다. 이 분할 소영역 번호는 기준이 되는 메시에 대해 상대적인 분할을 나타내는 것이다. 예를 들면 레벨(4)의 어떤 메시에 대해 2개 아래의 레벨(2)의 분할 소영역을 나타내는데는 도 15의 레벨(n+2)의 코드를 사용하고, 레벨(2)이 있는 메시에 대해 1개 아래의 레벨(1)의 분할 소영역을 나타내는데는 레벨(n+3)의 코드를 사용한다.

도 27의 레벨(4)의 메시(M40)에 노드(n100)가 있다고 한 경우, 이 레벨(4)의 메시(M40)에 대해 노드(n100)가 존재하는 하위 레벨의 소영역 번호는 레벨 3에서는 도 15의 레벨(n+3)의 코드를 사용하여 8040이고, 레벨 2에서는 도 15의 레벨(n+4)의 코드를 사용하여 A060이다.

이상과 같이 하여 분할 소영역 번호가 부여되기 때문에 기준이 되는 메시의 메시 코드와 이 분할 소영역 번호에 의해 하위 레벨의 해당하는 메시 코드를 계산할 수 있다. 예를 들면 도 27의 상술한 레벨 4의 메시 코드 5339의 메시(M40)의 노드(n100)에 대응하는 레벨 3의 메시(M32)의 메시 코드는 5439F301이고, 레벨 2의 메시(M22)의 메시 코드는 543926F2로서 도 15 및 도 27의 관계를 나타내는 일정한 계산식으로 계산할 수 있다.

인접노드(#1∼#n) 정보는 해당 레벨의 자노드가 포함되는 소영역의 번호순, 또 동일한 소영역에 포함되는 노드의 번호순으로 소트되어 미리 기억되어 있다. 도 14는 이 소트의 상태를 나타내는 도면이다. 도 14A와 같이 레벨 4의 1개의 메시(M4)를 예를 들면 4×4의 16의 소영역으로 분할하고, 각 소영역을 특정하는 코드를 하단행을 좌측에서 차례로 (00, 00), (00, 40), (00, 80), (00, C0)로 하고, 그 위의 행을 (40, 00), (40, 40)……, 최상단행의 가장 우측 영역을 (C0, C0)로 나타낸다. 그리고, 소영역(00, 00)에는 2개의 노드번호(0, 1)가 존재하고, 소영역(00, 40)에는 3개의 노드번호(0, 1, 2)가 존재하고, 소영역(00, 80)에는 4개의 노드 번호(0, 1, 2, 3)가 존재한다. 또한, 소영역은 하위 레벨(3)의 메시(M3)(도 23)와 일치한다.

이와같은 경우, 도 14B에 나타내는 바와 같이 자노드 대응 정보는 소영역의 번호순으로, 또 동일한 소영역의 노드 번호순으로 소트되어 기억된다. 이와같이 하는 것에 의해, 테이블내의 데이터를 검색하는 시간을 단축할 수 있다.

도 16 및 도 17에 의해 자노드 대응정보와 인접노드(#1∼#n) 정보를 상세히 설명한다. 예를 들면 레벨 4의 자노드번호(1000)에 인접하는 3개의 노드의 인접 노드 번호를 1100, 1200, 1300으로 한다. 자노드 대응 정보의 자레벨 노드 번호로서 1000이, 이 노드에 대응하는 레벨 2의 노드번호가 하위 레벨 노드 번호 230으로서 각각 기억된다. 또한, 레벨 2의 노드 230이 도 27에 예시한 노드(n100)와 같다고 생각되면 저장되는 분할 소영역 번호로서 A060이 기억된다.

또한, 인접노드(#1) 정보로는 레벨 4의 노드(1000)에 인접하는 노드 번호 1100이 자레벨 노드번호로서 기억됨과 동시에, 노드 1000과 1100 사이의 링크(LB)에 대응하는 레벨 2의 링크를 Lb로 하면 링크 Lb상의 복수의 노드중 노드 230에 가장 가까운 인접하는 노드의 번호가 하위 레벨 노드번호 231로서 기억된다. 또한, 레벨 2의 인접노드번호 231의 노드가 저장되는 분할 소영역 번호로서 A060이 기억된다.

또, 인접노드(#3) 정보로는 레벨 4의 노드(1000)에 인접하는 노드 번호 1300이 자레벨 노드번호로서 기억됨과 동시에, 노드 1000과 1300 사이의 링크(LA)에 대응하는 레벨 2의 링크를 La로 하면 링크(La)상의 복수의 노드중 노드 230에 가장 가까운 인접하는 노드의 번호가 하위 레벨 노드 번호 354로서 기억된다. 또, 레벨 2의 인접 노드 번호 354의 노드가 저장되는 분할 소영역 번호로서 A060이 기억된다.

[4]추장 루트 데이터

도 18은 경로 탐색 데이터에 기초하여 탐색된 출발지에서 목적지까지의 추장 루트를 나타내는 추장 루트 데이터의 데이터 구성의 개요를 나타내는 도면이다. 추장 루트 데이터에는 추장 루트상의 노드정보와 링크정보가 메시 영역 단위로 분류되어 저장되어 있다.

도 18에 나타내는 바와 같이, 추장 루트 데이터는 메시코드, 노드수, 노드정보, 링크종별수, 링크정보, 페리정보 및 터널정보로 구성된다. 이 중에 메시코드의 기억 영역에는 메시영역을 식별하는 번호가 저장되며, 노드수의 기억영역에는 메시영역내에 존재하는 노드수가 저장되고, 노드정보의 기억영역에는 도19의 (A)에 상세하게 나타낸 바와 같이, 메시 영역내의 각 노드의 노드번호, 위치좌표, 거리비용 등이 저장된다. 또한, 링크 종별수의 기억 영역에는 메시영역내에 존재하는 링크의 종별수가 저장되며, 링크정보의 기억 영역에는 도 19의 (B)에 상세하게 나타낸 바와 같이, 메시영역내의 각 링크의 링크종별, 링크수, 링크번호 등이 저장된다. 도 19의 (A), (B)는 동일 메시코드로 나타낸 영역내에 2개의 링크열(1, 2)이 있는 경우를 나타낸다.

이하, 플로우차트를 참조하여 본 실시형태의 동작을 설명한다. 이 실시형태에서는 다음과 같이 하여 추장 루트를 구해 표시장치(6)에 표시한다. 레벨 2와 레벨 4의 도로 지도 데이터를 사용한 루트 탐색은 다음과 같이 하여 실시된다.

루트 탐색 처리를 도 20을 참조하여 상세히 설명한다.

①레벨 2의 출발지 근방의 소정 영역(R1)(예를 들면 50Km사방)을 설정한다.

②그 소정 영역내에서 출발지(ST)(현재 지점)를 시점으로 하여 목적지에 접속되어 있다고 생각되는 도로를 추출하여 소정 영역내에서의 종점의 노드(ST1∼ST3)를 결정한다. 또, 이 종점의 노드중에서 소정 영역을 결정하는 4변중 목적지를 향하는 2변(H1, H2)에 인접하는 노드(ST2, ST3)를 상위 대응 종점 노드로 선택한다.

③레벨 2의 목적지 근방의 소정 영역(R2)(예를 들면 50Km사방)을 설정한다.

④그 소정영역내에서 목적지(DP)를 시점으로 하여 출발지에 접속되어 있다고 생각되는 도로를 추출하여 소정 영역내에서의 종점의 노드(DP1∼DP3)를 결정한다. 또한, 이 종점의 노드 중에서 소정 영역을 결정하는 4변중 출발지를 향하는 2변(H3, H4)에 인접하는 노드(DP2, DP3)를 상위 대응 종점 노드로 선택한다.

⑤레벨 4에서 출발지와 목적지를 포함하는 소정 영역(R3)을 경로 탐색 영역으로 설정한다.

⑥출발지 근방의 소정 영역내에서 선택된 복수의 상위 대응 종점 노드(ST2,ST3)에 대응하는 레벨 4의 노드(ST2’, ST3’)를 레벨 4의 시점 노드로서 검출함과 동시에 목적지 근방의 소정 영역내에서 선택된 복수의 상위 대응 종점 노드(DP2, DP3)에 대응하는 레벨 4의 노드(DP2’, DP3’)을 레벨 4의 종점 노드로 검출한다.

⑦레벨 4의 복수의 시점 노드(ST2’, ST3’)와 복수의 종점 노드(DP2’, DP3’)사이를 접속하는 도로를 탐색한다.

⑧레벨 2의 출발지(ST)와 선택된 상위 대응 종점 노드(ST2, ST3)간의 거리, 레벨 4의 시점 노드(ST2’, ST3’)와 종점 노드(DP2’, DP3’)간의 거리 및 레벨 2의 목적지(DP)와 선택된 상위 대응 종점 노드(DP2, DP3)간의 거리를 각각 가산하여 예를 들면 가장 짧은 것을 추장 루트로 결정한다.

도 21, 도 22는 제어회로(2)가 실시하는 메인 처리의 개요를 나타내는 플로우차트이다. 도 21의 단계(S1)에서는 현재 지점 검출장치(1)를 이용하여 차량 위치를 검출한다. 단계(S2)에서는 입력장치(3)에 의해 입력된 목적지를 판독한다. 단계(S3)에서는 지도 데이터베이스 장치(8)에 저장되어 있는 지도 표시용 데이터에 기초하여 경로 탐색이 가능한 도로상에 경로 탐색의 개시점 및 종료점을 설정한다. 예를 들면 차량의 개시점은 차량의 현재 위치(차량위치), 종료점이 목적지이다.

단계(S4)에서는 레벨 2의 루트 탐색용 데이터를 이용하여 경로 탐색의 개시점 부근의 경로 탐색을 실시한다. 그리고, 개시점 부근에서의 추장 루트의 후보를 복수 선택한다. 단계(S5)에서는 레벨 2의 루트 탐색용 데이터를 이용하여 경로 탐색의 종료점 부근의 경로 탐색을 실시한다. 그리고, 종료점 부근에서의 추장 루트의 후보를 복수로 선택한다.

단계(S6)에서는 단계(S4, S5)에서 선택한 추장 루트의 후보간의 경로에 대해서 레벨 4의 루트 탐색용 데이터를 이용하여 경로 탐색을 실시하여 개시점에서 종료점까지의 추장 루트를 연산한다.

이와 같이, 개시점 및 종료점 부근과 개시점 및 종료점의 중간 부근에서 다른 레벨의 루트 탐색용 데이터를 이용하는 이유는 모든 경로에 대해서 레벨 2의 루트 탐색용 데이터를 이용하여 경로 탐색을 실시하면 데이터량이 팽대해지기 때문에 경로 탐색에 필요한 연산시간이 길어지기 때문이다. 단계(S7)에서는 단계(S6)에서 연산한 추장 루트에 관한 정보를 추장 루트 데이터로서 SRAM(7)에 기억한다.

도 21의 단계(S7)의 처리가 종료되면 도 22의 단계(S8)로 진행하여 배경 지도 묘사 처리를 실시하여 표시장치(6)에 표시하기 위한 추장 루트 주변의 도로 지도에 관한 데이터를 화상 메모리(5)에 묘사(저장)한다. 계속해서 단계(S9)로 진행하여 단계(S3)에서 연산한 추장 루트를 표시하는데 필요한 데이터를 화상메모리(5)에 겹쳐 묘사(저장)한다. 단계(S10)에서는 화상메모리(5)에 저장되어 있는 데이터를 판독하여 표시장치(6)에 추장루트 및 그 주변의 도로지도를 표시한다.

도 12에 나타내는 바와 같이, 본 실시형태의 루트 탐색용 데이터 및 추장 루트 데이터는 링크의 접속 정보만을 유지하고 있으며, 도로 형상에 관한 정보는 유지되어 있지 않다. 따라서, 모니터상의 도로 지도에 추장 루트를 겹쳐 묘사하는데는 추장 루트 데이터에 기초하여 도로 지도 데이터에서 형상 데이터를 추출한다.

본 실시형태에서는 루트 탐색용 데이터와 루트 탐색용 레벨간 대응 데이터를 이용하여 루트 탐색을 실시하도록 하였다. 여기서, 루트 탐색용 데이터는 각 레벨의 각 노드마다 자노드에 관한 자노드 정보와 이 자노드에 인접하는 인접 노드에 관한 인접 정보를 포함한다. 루트 탐색용 레벨간 대응 데이터는 그 레벨의 자노드에 관한 자레벨 정보와, 그 자노드에 대응하는 하위 레벨의 노드에 관한 하위 레벨 정보를 한셋트로 하는 자노드 대응 정보 및 자노드에 인접하는 인접 노드에 관한 자레벨 인접 정보와 그 자노드에 대응하는 하위 레벨의 노드에 인접하는 인접 노드에 관한 하위 레벨 인접 정보를 한셋트로 하는 인접 노드 정보를 포함한다. 그리고, 레벨간 대응 데이터에는 하위 레벨에서 상위 레벨을 직접 특정하는 정보를 기억하지 않고, 상위 레벨에서 하위 레벨을 직접 특정하는 정보만을 기억하도록 했기 때문에 데이터 용량을 작게 할 수 있고, 또 최하위 레벨의 대응 데이터가 불필요하게 되어 그만큼 데이터 용량도 저감할 수 있다.

또한, 하위 레벨에서 상위레벨로의 노드의 대응은 하위 레벨의 메시 코드에서 그 노드가 존재하는 상위 레벨의 메시의 메시 코드를 계산에 의해 구하고, 또 그 상위의 메시에서의 자기 노드가 존재하는 분할 소영역 번호를 계산에 의해 구한다. 자기의 노드번호와 계산에 의해 구한 분할 소영역 번호로 계산에 의해 구한 상위 레벨의 메시 코드에 해당하는 메시의 루트 탐색용 레벨간 대응 데이터내를 검색하여 상위레벨의 메시의 노드번호와 대응시킬 수 있다. 예를 들면 도 16의 예로 레벨 2의 노드 230에서 상위의 대응하는 레벨 4의 노드 1000을 발견한 경우를 설명한다. 우선, 레벨 2의 메시코드가 도 27의 예로 메시(M22)의 543926F2라고 하면 메시코드의 상 4행에서 레벨 4의 대응하는 메시의 메시코드는 5339F4인 것이 계산에 의해 구해진다. 즉, 메시(M40)이다. 또한, 이 메시(M40)내에서 레벨 2의 메시코드 543926F2에 대응하는 분할 소영역 번호는 A060인 것은 계산에 의해 구해진다. 계산에 의해 구해진 상위 레벨의 메시 코드 5339F4의 메시 M40가 갖는 루트 탐색용 레벨간 대응 데이터중(즉, 도 17 또는 도 13)을 자기의 노드 번호 230과 계산에 의해 구한 분할 소영역 번호(A060)를 키로 검색하면 대응하는 노드로서 노드 1000을 발견할 수 있다.

기억용량의 저감에 대해서 더욱 상세히 설명한다.

도 23에서, 예를 들면 레벨 2의 메시(M2)의 노드(n3”)를 레벨 2에서 선택된 상위 대응 종점 노드로 하면, 레벨 4의 경로 탐색 데이터중에서 노드(n3”)와 대응하는 노드를 검출하기 위해서는, 즉 하위 레벨에서 상위 레벨의 대응 노드를 검색하기 위해서는 레벨 2의 노드(n3”)에 대응하는 레벨 4의 노드(n3)의 노드 번호를 레벨 2의 노드(n3”)의 노드 번호에 부수하여 기억하면 좋다. 또한, 반대로 상위 레벨에서 하위 레벨의 대응 노드를 검색하기 위해서는, 즉 레벨 2의 경로 탐색용 데이터중에서 노드(n3)에 대응하는 레벨 2의 노드(n3”)를 검출하기 위해서는 레벨 4의 노드(n3)에 대응하는 레벨 2의 노드(n3”)의 노드번호를 레벨 4의 노드(n3)의 노드 번호에 부수하여 기억하면 좋다.

그러나, 상위 레벨에서 하위 레벨의 노드를 대응하는 경우, 다음과 같은 문제가 있다. 도 23에서, 레벨 4의 메시(M4)는 16개이 소영역으로 분할되고, 16개의 소영역에 각각 대응하여 레벨 3의 데이터가 필요하며, 레벨 4의 메시(M4)와 같은 지역의 데이터를 레벨 3은 16개의 메시의 데이터로 기억한다. 이것을 메시(M3-1∼M3-16)로 하면 메시(M3-1∼M3-16)의 각각에 존재하는 복수의 노드에는각각 l∼Q까지의 노드 번호가 할당되어 있다. 즉, 메시(M3-1∼M3-16)중에서 동일한 번호가 중복되어 노드번호로 사용되고 있다. 레벨 3과 레벨 2 사이에서도 마찬가지이며, 레벨 3의 16개의 메시(M3-1∼M3-16)의 각각에는 각각 또는 16개의 메시가 대응되어 있다. 메시(M3-1)에 대해서는 메시(M2-1-1∼M2-1-6)가, 메시(M3-2∼M3-16)에 대해서는 메시(M2-2-1∼M2-16-16)가 존재한다. 즉, 메시(M2-1-1∼M2-16-16)중에서는 동일한 노드번호가 중복되어 사용되고 있다. 따라서, 상위 레벨에서 하위 레벨을 보고 레벨 4의 노드(n3)에 대응하는 레벨 2의 노드(n3”)을 설정하는 경우, 노드번호만으로 설정할 수 없다.

더욱 구체적으로 설명하면 레벨 4의 소영역(m4)의 노드번호 1에 대응하는 레벨 2의 노드번호를 17로 한 경우, 레벨 4의 다른 15개의 소영역에 대응하는 레벨 2의 각 메시중에도 노드번호 17의 노드가 존재할 가능성이 있어, 노드번호 17만으로 하위 레벨 2의 노드를 특정할 수 없다. 모든 레벨을 통해 노드번호를 계속하여 노드번호로 하면 노드번호만으로 특정할 수 있지만 그 경우 일본 전국에서는 수백만개의 노드수가 되어 기억용량이 팽대해져 버린다.

이 점이 본 실시형태에 의한 지도 데이터베이스 장치에서는 상기한 바와 같은 루트 탐색용 레벨간 대응 데이터를 이용하고 있기 때문에 상위 레벨에서 하위 레벨을 특정하는 대응만으로 상위 레벨에서 하위 레벨 및 하위레벨에서 상위레벨이 대응을 할 수 있고 기억용량을 저감할 수 있다.

또한, 본 실시형태에서는 레벨간 대응 데이터중의 자레벨 인접 데이터와 대응시켜 하위 레벨 인접 데이터를 기억시키고 있기 때문에 경로 탐색 연산시의 레벨간의 인접 데이터의 대응에 의해 신뢰성이 높은 루트 탐색을 실시할 수 있다. 예를 들면 레벨 2에서 출발지 부근을 탐색하고, 어느 노드 이후는 레벨 4에서 루트 탐색을 실시할 경우, 상술한 루트 탐색용 레벨간 대응 데이터에 의해 레벨 4의 대응하는 노드를 발견하고, 그 노드에서 레벨 4의 데이터로 루트 탐색을 실시한다. 이때, 하위 레벨로 이미 그 노드에 도달하기까지의 루트가 탐색 완료라는 것을 알 수 있으면 상위 레벨로 이 노드로부터 탐색을 개시할 때, 이 루트는 다른 루트와 완전히 동일한 조건으로 루트 탐색 후보를 예로 들어 탐색할 필요가 없다. 완전히 동일한 조건으로 탐색을 하게 되면, 탐색 시간이 낭비가 되고, 또 U턴해서 반대로 되돌아가는 탐색 결과를 얻는 경우도 있다. 어떤 노드에 도달하기까지의 루트가 탐색 완료라는 것을 알기 위해서는 해당하는 루트의 가장 인접한 노드의 대응 관계를 알 수 있으면 그 루트를 알 수 있다. 여기서, 가장 인접한 노드의 정보를 갖게 한 것은 레벨간에 의해 노드사이에 포함되는 정보량이 다르기 때문이다. 상위 레벨의 어떤 노드에 인접하는 노드간에 있어서, 하위 레벨에서는 더 새로운 노드가 포함되기 때문이다. 또, 인접 노드 정보 대신에 접속되는 링크 번호등의 링크 정보로 해도 좋다.

또한, 상기 실시형태에서는 루트 탐색용 레벨간 대응 데이터에 있어서 하위 레벨의 분할 소영역을 나타내기 위해 분할 소영역 번호로 나타냈지만, 상기에도 설명한 바와 같이, 각 레벨의 메시 코드를 직접 사용해도 좋다. 데이터 용량은 많이 필요해지지만, 계산을 하지 않아도 좋아져 프로그램이 간단해진다.

또한, 상기 실시형태에서는 도 1에 도시한 구성의 차량용 지도 네비게이션 장치의 예를 나타냈지만, 이 실시형태에 한정할 필요는 없다. 예를 들면, 도 26에 도시한 바와 같이 퍼스널컴퓨터와 같은 컴퓨터(101)에 네비게이션 시스템의 제어 프로그램이 탑재된 기록 매체로부터 제어 프로그램을 판독하여 이것을 실행하는 것에 의해 본 실시형태의 차량용 지도 네비게이션 장치와 동등한 시스템을 구축할 수 있다. 이 경우, 상기 실시형태에 나타낸 지도 데이터베이스도 기록매체(103)로부터 판독한다. 또, 현재 지점 검출 장치(104) 등 네비게이션 시스템을 구성하는데 필요한 장치도 컴퓨터(101)의 외부 폰트에 접속한다.

Claims

시단과 종단에 노드를 갖는 링크에 관한 데이터를 복수개 이용하여 도로를 나타냄과 동시에 축척률이 다른 지도마다 따로 설치된 복수의 링크에 관한 데이터가 축척률이 가장 작은 상위 레벨에서 축척률이 가장 큰 하위 레벨의 도로 지도 데이터로서 각각 저장되고, 상위 레벨의 하나의 지도 영역을 복수로 분할한 M개의 소영역내의 상세 정보의 각각이 하위 레벨의 하나의 지도영역의 도로 지도 데이터로서 M개 기억되는 지도 데이터베이스 장치에 있어서,

축척률이 작은 상위 레벨의 도로 지도 데이터와 축척률이 큰 하위 레벨의 도로 지도 데이토와의 대응 관계를 나타내는 레벨간 대응 데이터로서, 상기 상위레벨에서 하위 레벨을 본 경우의 각 레벨의 노드의 대응 정보가 설치되어 있는 것을 특징으로 하는 지도 데이터베이스 장치.
제 1 항에 있어서,

상기 레벨간 대응 데이터는,

(1) 상기 상위 레벨의 상위 노드를 나타내는 번호와, (2) 상기 상위노드에 대응하는 하위 레벨의 하위 노드를 나타내는 번호와, (3) 상기 하위 노드가 존재하는 상기 하위 레벨의 상기 소영역의 번호가 각각 서로 대응된 정보이며, 최하위 레벨을 제외한 각 레벨마다 설치되어 있는 것을 특징으로 하는 지도 데이터베이스 장치.
제 1 항에 있어서,

상기 각 레벨의 레벨간 대응 데이터는 상기 상위 레벨의 노드가 포함되는 상기 소영역의 번호순, 또 동일한 소영역에 포함되는 노드의 번호순으로 소트되어 있는 것을 특징으로 하는 지도 데이터베이스 장치.
제 1 항에 있어서,

상기 레벨간 대응 데이터는 경로 탐색용 데이터이며, 그 경로 탐색용 데이터는 상위 레벨의 자노드에 인접하는 상위 인접 노드의 번호와 그 상위 자노드에 대응하는 하위 레벨의 자노드에 인접하는 하위 인접 노드의 번호를 대응하여 설치되어 있는 것을 특징으로 하는 지도 데이터베이스 장치.
제 1 항에 있어서,

상기 레벨간 대응 데이터는,

(1) 상기 상위 레벨의 상위 노드를 나타내는 식별부호와, (2) 상기 상위 노드에 대응하는 하위 레벨의 하위 노드를 나타내는 식별부호와, (3) 상기 하위 노드가 존재하는 상기 하위 레벨의 상기 소영역의 식별 부호가 각각 서로 대응된 정보이며, 최하위 레벨을 제외한 각 레벨마다 설치되어 있는 것을 특징으로 하는 지도 데이터베이스 장치,
제 2 항에 있어서,

상기 소영역의 번호는 상기 상위 레벨의 하나의 지도영역을 기준으로 하여 부여되는 상대적인 소영역의 번호인 것을 특징으로 하는 지도 데이터베이스 장치.
제 2 항에 있어서,

상기 하위 레벨의 소영역의 번호 체계는 상기 소영역의 번호에서 상기 상위 레벨의 하나의 지도 영역의 번호가 특정되는 번호체계인 것을 특징으로 하는 지도 데이터베이스 장치.
제 5 항에 있어서,

상기 하위 레벨의 소영역의 식별부호체계는 상기 소영역의 식별부호에서 상기 상위 레벨의 하나의 지도 영역의 식별부호가 특정되는 것을 특징으로 하는 지도 데이터베이스 장치.
시단과 종단에 노드를 갖는 링크에 관한 데이터를 복수개 이용하여 도로를 나타냄과 동시에 축척률이 다른 지도마다 따로 설치된 복수의 링크에 관한 데이터가 축척률이 가장 작은 상위 레벨에서 축척률이 가장 큰 하위 레벨의 도로 지도 데이터로서 각각 저장되며, 상위 레벨의 하나의 지도 영역을 복수로 분할한 M개의 소영역내의 상세 정보의 각각이 하위 레벨의 하나의 지도 영역의 도로 지도 데이터로서 M개 기억되는 지도 데이터베이스 장치에 있어서,

축척률이 작은 상위 레벨의 도로 지도 데이터와 축척률이 큰 하위 레벨의 도로 지도데이터와의 대응 관계를 나타내는 레벨간 대응 데이터로서,

(1)상기 상위 레벨의 상위 자노드를 나타내는 번호와 상기 상위 자노드에 대응하는 하위 레벨의 하위 자노드를 나타내는 번호가 대응되고,

(2) 상기 상위 자노드에 접속된 상위 인접 노드를 나타내는 번호와 상기 하위 자노드에 접속된 하위 인접 노드를 나타내는 번호가 대응되며, 최하위 레벨을 제외한 레벨마다 설치되어 있는 것을 특징으로 하는 지도 데이터베이스 장치.
제 5 항에 있어서,

상기 각 레벨의 레벨간 대응 데이터는 상기 자노드가 포함되는 상기 소영역의 번호순, 또 동일한 소영역에 포함되는 노드의 번호순으로 소트되어 있는 것을 특징으로 하는 지도 데이터베이스 장치.
시단과 종단에 노드를 갖는 링크에 관한 데이터를 복수개 이용하여 도로를 나타냄과 동시에 축척률이 다른 지도마다 따로 설치된 복수의 링크에 관한 데이터가 축척률이 가장 작은 상위 레벨에서 축척률이 가장 큰 하위 레벨의 도로 지도데이터로서 각각 저장되고, 상위레벨의 하나의 지도 영역을 복수로 분할한 M개의 소영역내의 상세 정보의 각각이 하위 레벨의 하나의 지도영역의 도로 지도데이터로서 M개 기억되는 지도 데이터베이스가 기억되는 기록매체에 있어서,

축척률이 작은 상위 레벨의 도로 지도 데이터와 축척률이 큰 하위 레벨의 도로 지도데이터와의 대응 관계를 나타내는 레벨간 대응 데이터로서, 상기 상위 레벨에서 하위 레벨을 본 경우의 각 레벨의 노드의 대응 정보가 설치되어 있는 것을 특징으로 하는 기록매체.
시단과 종단에 노드를 갖는 링크에 관한 데이터를 복수개 이용하여 도로를 나타냄과 동시에 축척률이 다른 지도마다 따로 설치된 복수의 링크에 관한 데이터가 축척률이 가장 작은 상위 레벨에서 축척률이 가장 큰 하위 레벨의 도로 지도데이터로서 각각 저장되고, 상위레벨의 하나의 지도 영역을 복수로 분할한 M개의 소영역내의 상세 정보의 각각이 하위 레벨의 하나의 지도영역의 도로 지도데이터로서 M개 기억되는 지도 데이터베이스 장치와,

상기 지도 데이터베이스 장치의 데이터베이스를 사용하여 경로 탐색 및 모니터에 도로 지도 및 경로 탐색 결과의 표시를 실시하는 제어장치를 구비하는 네비게이션 장치에 있어서,

상기 지도 데이터베이스 장치에는 축척률이 작은 상위 레벨의 도로 지도데이터와 축척률이 큰 하위 레벨의 도로 지도데이터와의 대응 관계를 나타내는 레벨간 대응 데이터로서, 상기 상위레벨에서 하위레벨을 본 경우의 각 레벨의 노드의 대응 정보가 설치되어 있는 것을 특징으로 하는 네비게이션장치.