| 1 |
1
전자 장치가 지도 상에서 경로를 제공하는 방법에 있어서,복수의 노드들 및 상기 복수의 노드들 사이를 연결하는 간선을 포함하는 상기 지도를 획득하는 단계;상기 지도상 상기 경로의 출발지 좌표 및 목적지 좌표를 획득하는 단계;상기 출발지 좌표에 위치하는 시작 노드에 인접하는 노드들을 식별하는 단계;상기 식별된 노드들을 제1 노드 리스트에 추가하는 단계;상기 제1 노드 리스트에 추가된 노드들의 경로 점수에 기초하여 상기 제1 노드 리스트 내 가장 낮은 경로 점수를 가지는 노드를 제2 노드 리스트에 추가하는 단계; 및상기 제2 노드 리스트에 추가된 노드에 인접하는 노드들을 식별하는 단계; 를 포함하는, 방법
|
| 2 |
2
제1항에 있어서, 상기 방법은상기 제2 노드 리스트에 추가된 노드에 인접하는 노드들을 상기 제1 노드 리스트에 추가함으로써, 상기 제1 노드 리스트를 갱신하는 단계; 및상기 갱신된 제1 노드 리스트 내 가장 낮은 경로 점수를 가지는 노드를 상기 제2 노드 리스트에 추가함으로써 상기 제2 노드 리스트를 갱신하는 단계; 를 더 포함하는, 방법
|
| 3 |
3
제2항에 있어서, 상기 제2 노드 리스트에 추가된 노드는상기 제2 노드 리스트에 추가된 노드가 상기 제2 노드 리스트에 추가되기 직전, 상기 제2 노드 리스트에 추가된 노드의 식별 정보를, 노드 부모 정보로써 포함하는 것을 특징으로 하는, 방법
|
| 4 |
4
제2항에 있어서, 상기 방법은상기 제1 노드 리스트 내 가장 낮은 경로 점수를 가지는 노드가 상기 제2 노드 리스트로 추가되면, 상기 제2 노드 리스트에 추가된 노드를 상기 제1 노드 리스트에서 삭제하는 단계; 를 더 포함하는, 방법
|
| 5 |
5
제4항에 있어서, 상기 방법은상기 제2 노드 리스트에 추가된 노드가 지형 지물 또는 장애물에 대응되는 장애 노드인지 여부를 식별하는 단계; 및상기 제2 노드 리스트에 추가된 노드가 상기 장애 노드로 식별되면, 상기 제2 노드 리스트에 추가된 노드가 삭제된 상기 제1 노드 리스트에서, 가장 낮은 경로 점수를 가지는 노드를 상기 제2 노드 리스트에 추가함으로써 상기 제2 노드 리스트를 갱신하는 단계; 를 더 포함하는, 방법
|
| 6 |
6
제2항에 있어서, 상기 방법은상기 제2 노드 리스트에 추가된 노드가 지형 지물 또는 장애물에 대응되는 장애 노드인지 여부를 식별하는 단계; 및상기 제2 노드 리스트에 추가된 노드가 상기 장애 노드로 식별되는 경우, 상기 장애 노드가 상기 제2 노드 리스트에 추가되기 전, 상기 갱신된 제1 노드 리스트 내 두번째로 낮은 경로 점수를 가지는 노드를 상기 제2 노드 리스트에 추가함으로써, 상기 제2 노드 리스트를 갱신하는 단계; 를 포함하는, 방법
|
| 7 |
7
제3항에 있어서, 상기 방법은상기 제2 노드 리스트에 추가된 노드가 상기 목적지 좌표에 위치하는 목적지 노드인지 여부를 식별하는 단계;상기 제2 노드 리스트에 추가된 노드가 상기 목적지 노드로 식별되는 경우, 상기 제2 노드 리스트에 추가된 노드들에 포함된 노드 부모 정보에 기초하여 상기 시작 노드로부터 상기 목적지 노드까지의 경로를 결정하는 단계; 및상기 결정된 경로를 제공하는 단계; 를 포함하는, 방법
|
| 8 |
8
제7항에 있어서, 상기 경로를 결정하는 단계는상기 제2 노드 리스트에 추가된 노드가 상기 목적지 노드로 식별되면, 상기 제2 노드 리스트에 추가된 노드들의 노드 부모 정보를 추적하는 단계; 및상기 추적된 노드 부모 정보에 기초하여 상기 경로를 결정하는 단계; 를 포함하는, 방법
|
| 9 |
9
제8항에 있어서, 상기 추적하는 단계는상기 추적된 노드 부모 정보가 상기 시작 노드의 노드 식별 정보를 나타낼 때까지, 상기 목적지 노드로 식별된 상기 제2 노드 리스트에 추가된 노드로부터 상기 시작 노드를 향하는 방향으로, 상기 제2 노드 리스트에 추가된 노드들의 노드 부모 정보를 추적하는 단계; 를 포함하는, 방법
|
| 10 |
10
제7항에 있어서, 상기 제1 노드 리스트 내 노드들의 경로 점수는상기 시작 노드로부터 상기 제1 노드 리스트 내 노드까지 이동하는데 소요되는 거리 및 상기 제1 노드 리스트 내 노드로부터 상기 목적지 노드까지 이동하는데 소요되는 거리에 기초하여 결정되는 것을 특징으로 하는, 방법
|
| 11 |
11
제10항에 있어서, 상기 시작 노드로부터 상기 제1 노드 리스트 내 노드까지 이동하는데 소요되는 거리 및 상기 제1 노드 리스트 내 노드로부터 상기 목적지 노드까지 이동하는데 소요되는 거리는 하버사인 함수에 기초하여 결정되는 것을 특징으로 하는, 방법
|
| 12 |
12
제1항에 있어서, 상기 출발지 좌표 및 목적이지 좌표를 획득하는 단계는상기 출발지 좌표에 대응되는 위도 정보 및 경도 정보를 획득하는 단계; 및상기 목적지 좌표에 대응되는 위도 정보 및 경도 정보를 획득하는 단계; 를 포함하는, 방법
|
| 13 |
13
제7항에 있어서, 상기 결정된 경로 정보를 제공하는 단계는상기 지도에 대한 지도 이미지를 결정하는 단계; 및상기 지도 이미지상에 상기 추적된 노드에 대한 식별 정보를 표시함으로써 상기 경로에 대한 경로 이미지 정보를 제공하는 단계; 를 포함하는, 방법
|
| 14 |
14
지도 상에서 경로를 제공하는 전자 장치에 있어서,네트워크 인터페이스;하나 이상의 인스트럭션을 저장하는 메모리; 및상기 하나 이상의 인스트럭션을 실행하는 적어도 하나의 프로세서; 를 포함하고,상기 적어도 하나의 프로세서는 상기 하나 이상의 인스트럭션을 실행함으로써, 복수의 노드들 및 상기 복수의 노드들 사이를 연결하는 간선을 포함하는 상기 지도를 획득하고,상기 지도상 상기 경로의 출발지 좌표 및 목적이지 좌표를 획득하고,상기 출발지 좌표에 위치하는 시작 노드에 인접하는 노드들을 식별하고,상기 식별된 노드들을 제1 노드 리스트에 추가하고,상기 제1 노드 리스트에 추가된 노드들의 경로 점수에 기초하여 상기 제1 노드 리스트 내 가장 낮은 경로 점수를 가지는 노드를 제2 노드 리스트에 추가하고,상기 제2 노드 리스트에 추가된 노드에 인접하는 노드들을 식별하는, 전자 장치
|
| 15 |
15
제14항에 있어서, 상기 적어도 하나의 프로세서는상기 제2 노드 리스트에 추가된 노드에 인접하는 노드들을 상기 제1 노드 리스트에 추가함으로써, 상기 제1 노드 리스트를 갱신하고,상기 갱신된 제1 노드 리스트 내 가장 낮은 경로 점수를 가지는 노드를 상기 제2 노드 리스트에 추가함으로써 상기 제2 노드 리스트를 갱신하는, 전자 장치
|
| 16 |
16
제15항에 있어서, 상기 제2 노드 리스트에 추가된 노드는상기 제2 노드 리스트에 추가된 노드가 상기 제2 노드 리스트에 추가되기 직전, 상기 제2 노드 리스트에 추가된 노드의 식별 정보를, 노드 부모 정보로써 포함하는 것을 특징으로 하는, 전자 장치
|
| 17 |
17
제15항에 있어서, 상기 적어도 하나의 프로세서는상기 제1 노드 리스트 내 가장 낮은 경로 점수를 가지는 노드가 상기 제2 노드 리스트로 추가되면, 상기 제2 노드 리스트에 추가된 노드를 상기 제1 노드 리스트에서 삭제하는, 전자 장치
|
| 18 |
18
제17항에 있어서, 상기 적어도 하나의 프로세서는상기 제2 노드 리스트에 추가된 노드가 지형 지물 또는 장애물에 대응되는 장애 노드인지 여부를 식별하고,상기 제2 노드 리스트에 추가된 노드가 상기 장애 노드로 식별되면, 상기 제2 노드 리스트에 추가된 노드가 삭제된 상기 제1 노드 리스트에서, 가장 낮은 경로 점수를 가지는 노드를 상기 제2 노드 리스트에 추가함으로써 상기 제2 노드 리스트를 갱신하는, 전자 장치
|
| 19 |
19
제15항에 있어서, 상기 적어도 하나의 프로세서는상기 제2 노드 리스트에 추가된 노드가 지형 지물 또는 장애물에 대응되는 장애 노드인지 여부를 식별하고,상기 제2 노드 리스트에 추가된 노드가 상기 장애 노드로 식별되는 경우, 상기 장애 노드가 상기 제2 노드 리스트에 추가되기 전, 상기 갱신된 제1 노드 리스트 내 두번째로 낮은 경로 점수를 가지는 노드를 상기 제2 노드 리스트에 추가함으로써, 상기 제2 노드 리스트를 갱신하는, 전자 장치
|
| 20 |
20
전자 장치가 지도 상에서 경로를 제공하는 방법에 있어서,복수의 노드들 및 상기 복수의 노드들 사이를 연결하는 간선을 포함하는 상기 지도를 획득하는 단계;상기 지도상 상기 경로의 출발지 좌표 및 목적이지 좌표를 획득하는 단계;상기 출발지 좌표에 위치하는 시작 노드에 인접하는 노드들을 식별하는 단계;상기 식별된 노드들을 제1 노드 리스트에 추가하는 단계;상기 제1 노드 리스트에 추가된 노드들의 경로 점수에 기초하여 상기 제1 노드 리스트 내 가장 낮은 경로 점수를 가지는 노드를 제2 노드 리스트에 추가하는 단계; 및상기 제2 노드 리스트에 추가된 노드에 인접하는 노드들을 식별하는 단계; 를 포함하는, 방법을 수행하도록 하는 프로그램이 저장된 컴퓨터로 읽을 수 있는 기록 매체
|
