| 摘要 |
도로망 내에서 연속 경로를 인코딩하기 위한 효율적 방법이 개시된다. 이상적으로는 인코딩될 경로는 디지털 맵 내에서 완전하게 표시될 수 있으며 디지털 맵 내에 존재하며 연속적으로 정렬되는 경로선 및/또는 세그먼트들의 경로 목록으로서 표시가능하다. 이 방법은, (i) 루트 검색 목록 내에 시작 포지션을 저장하는 단계로서, 시작 포지션은: (a) 경로 목록 내에 최초로 나타나는 경로선 또는 세그먼트이거나, 제1 경로선 또는 세그먼트의 시작 노드가 인위적일 경우에는 디지털 맵 내에 나타나는 제1 경로선 또는 세그먼트로서, 선택적으로 다른 인위적 노드(artificial node)를 통하여 제1 경로선 또는 세그먼트로 직접적으로 인도하는 실제 시작 노드(real start node)를 가지는 제1 경로선 또는 세그먼트, 또는 (b) 경로 목록 내에 역시 나타나는 가장 최근에 식별된 이탈(deviation) 경로선 또는 세그먼트 중 하나인 단계; (ii) 시작 포지션의 시작 노드로부터 출발하여 시작 포지션을 포함하며, 디지털 맵 내의 경로 목록 내의 최후 경로선 또는 세그먼트의 종료 노드(end node)까지의 경로를 선택하는 단계로서, 경로는 소정의 알고리즘에 의하여 결정되는 경로 결정 단계; (iii) 알고리즘에 의하여 결정된 최단 경로를 일치 여부에 대하여 경로 목록과 비교하는 단계로서, 일치성(identity)이 없는 경우에는, 경로 목록의 일부이며 디지털 맵 내의 교차로(intersection)를 표시하는 시작 노드를 가지지만 경로 목록 내에 최초로 나타나는 경로선 또는 세그먼트가 아닌 적어도 하나의 이탈 경로선 또는 세그먼트를 식별하되, 이러한 이탈 경로선 또는 세그먼트가 경로 목록 내에 나타나는 최후 경로선 또는 세그먼트의 종료 노드에서 종결되지 않으면, 이러한 이탈 경로선 또는 세그먼트를 이용하여 (i) 단계를 반복하는 단계; 및 (iv) 이미 저장되지 않았다면 경로 목록 내의 최후 경로선 또는 세그먼트를 루트 검색 목록 내에 저장하는 단계를 포함한다. 가장 바람직하게는, 이용되는 알고리즘은 최단 경로 알고리즘이다. |
