| 1 |
1
최단 경로로 도달할 수 있는 목적지들의 지점들로 이루어진 도형 내에서 불필요한 지점의 개수를 확인하는 단계;
상기 불필요한 지점의 개수에 기초하여 상기 도형 내 영역을 유효 영역과 무효 영역으로 분할하는 경계선을 생성하는 단계;
경로 탐색 시작 지점의 모든 이웃 지점에 대하여 목적지가 상기 경계선에 의해 분할된 유효 영역에 있는지를 확인하여 최단 경로를 탐색하는 단계
를 포함하되,
상기 유효 영역에는 무효 지점이 포함될 수 있으나, 상기 무효 영역에는 유효한 지점이 포함될 수 없는 것을 특징으로 하는 최단 경로 탐색 방법
|
| 2 |
2
제 1항에 있어서,
상기 도형은 최소 경계 직사각형(Minimum Bounding Rectangle)인 것을 특징으로 하는 최단 경로 탐색 방법
|
| 3 |
3
제 2항에 있어서,
상기 최소 경계 직사각형 내에서 최단 경로를 이루는 유효한 지점만으로 컨벡스 헐(convex hull)을 구성하는 단계
를 더 포함하되,
상기 최소 경계 직사각형 내 영역은 상기 컨벡스 헐의 각 변을 연장한 경계선에 의해 분할되는 것을 특징으로 하는 최단 경로 탐색 방법
|
| 4 |
4
제 1항에 있어서,
분할된 무효 영역들 중, 가장 많은 불필요한 지점을 포함하는 무효 영역을 분할한 경계선을 제 1 경계선으로 설정하는 단계
를 더 포함하는 것을 특징으로 최단 경로 탐색 방법
|
| 5 |
5
제 4항에 있어서,
상기 무효 영역 내의 불필요한 지점 개수의 1/2 값을 임계값으로 설정하는 단계와
상기 분할된 무효 영역들 중 불필요한 지점의 개수가 상기 임계값보다 큰 무효 영역의 경우, 상기 무효 영역을 분할한 경계선을 제 n 경계선으로 설정하는 단계
를 더 포함하되,
상기 설정된 n개의 경계선들을 이용하여 최단 경로를 탐색하는 것을 특징으로 하는 최단 경로 탐색 방법
|
| 6 |
6
제 1항에 있어서,
상기 유효 영역과 상기 무효 영역을 구별하는 플래그 정보를 설정하는 단계를 더 포함하되,
상기 플래그 정보에 기초하여 상기 도형 내 영역을 유효 영역과 무효 영역으로 분할하는 것을 특징으로 하는 최단 경로 탐색 방법
|
| 7 |
7
제 1항에 있어서,
상기 유효 영역은 불필요한 지점을 포함할 수 있는 것을 특징으로 하는 최단 경로 탐색 방법
|
| 8 |
8
제 1항에 있어서,
상기 무효 영역은 유효한 지점을 포함할 수 없는 것을 특징으로 하는 최단 경로 탐색 방법
|
| 9 |
9
경로 탐색의 시작 지점의 이웃에 위치하는 지점들의 최소 경계 직사각형(Minimum Bounding Rectangle)을 설정하는 단계;
상기 최소 경계 직사각형 내에 목적지가 포함되어 있다면, 상기 이웃 지점의 최소 경계 직사각형을 유효 영역과 무효 영역으로 분할하는 단계;
상기 목적지가 상기 유효 영역 내에 포함되어 있는 경우, 상기 이웃 지점을 큐(queue)에 저장하는 단계
를 포함하되,
상기 유효 영역에는 무효 지점이 포함될 수 있으나, 상기 무효 영역에는 유효한 지점이 포함될 수 없는 것을 특징으로 하는 최단 경로 탐색 방법
|
