경로 탐색과 좌표영역분할

경로 탐색 서비스는 특정 위치의 정보를 제공함으로써 길안내와 같은 여러 가지 실시간 서비스를 제공하는데 이러한 정보를 제공하기 위해서 해당하는 위치의 좌표를 내려 받는다. 이때, 내려 받은 좌표를 가지고 해당 지역을 검색 하기 위해서는 해당하는 지역을 찾아야 한다.

하지만, 일정 범위가 아닌 전 세계를 범위로 잡고 해당 지역을 검색한다면 어떻게 될까? 만약 그렇게 된다면 많은 시간과 비용이 소비됨에 따라서 제대로 된 서비스를 제공받지 못하게 된다. 특히 길안내 서비스에서 시작 위치를 제공 할 때, 길안내 할 수 있는 모든 범위에서 시작 위치를 찾는다고 가정하면, 아마도 시작 위치 지점을 찾는데 엄청난 시간일 걸릴 것이다.

이번 S프로젝트에서 위와 같은 문제에 부딪쳤다. 국내 경로탐색 에서는 각 링크마다 링크가 포함되어 있는 영역에 대한 정보가 주어졌다. 따라서 출발지점을 찾을 때 이 영역과 인접 영역들을 구해서 선택 지점을 찾을 수 있었다. 하지만 글로벌 경로탐색에서는 처음에는 특정한 영역 정보를 지정하지 않은 상태에서 프로젝트를 진행했는데, 링크에 영역 정보가 존재하지 않아 어떠한 지점을 찾을 때 모든 영역을 탐색해서 해당하는 지점을 찾다 보니 경로를 탐색하는데 엄청난 시간이 소비되는 것을 알 수 있었다.

글로벌 경로탐색에서 사용된 영역 분할방법은 글로벌 영역을 동일한 크기의 영역으로 나눠서 실제 경로탐색을 할 수 있는 영역(인도네시아)의 좌표정보를 하나의 집합체로 만들어서, 출발지점을 찾을 때 근접한 영역에서 찾도록 하는 것이었다.

int globalMbrs[][] = new int[360][360];
    
int shareMaxX; //해당 영역을 찾기 위한 최대X좌표 값(좌표의 정수 값)
int shareMaxY; //해당 영역을 찾기 위한 최대Y좌표 값(좌표의 정수 값)
int shareMinX; //해당 영역을 찾기 위한 최소X좌표 값(좌표의 정수 값)
int shareMinY; //해당 영역을 찾기 위한 최소Y좌표 값(좌표의 정수 값)
    
int remainderMaxX; //해당 영역의 구분을 위한 최대X좌표 값(좌표의 나머지 값)
int remainderMaxY; //해당 영역의 구분을 위한 최대Y좌표 값(좌표의 나머지 값)
int remainderMinX; //해당 영역의 구분을 위한 최소X좌표 값(좌표의 나머지 값)
int remainderMinY; //해당 영역의 구분을 위한 최소Y좌표 값(좌표의 나머지 값)

우선 전체 영역을 전 세계로 잡고 위도, 경도를 1도 기준(360X360)으로 나누었다. 지구가 원형(타원형)이므로 극점이 연결되므로 0,1,2,3......358, 359, 0, 1, 2…… 이런 식으로 0~359 사이의 범위 내에서 영역을 구분 지었다.

아래 소스 코드는 현재 주어진 좌표 영역의 이전 영역을 구하기 위한 계산 로직으로, 현재 좌표영역이 0 일 때 359를 반환한다.

public static int rotatePos(int position) {

    return (position -1) == -1 ? 359 : (position -1);
}

이렇게 나누어진 영역을 바탕으로 링크의 좌표정보를 토대로 각 영역에 링크정보가 포함되도록 했는데 링크의 최대, 최소 좌표 값을 가지고 어떤 영역에 걸치는지를 판단 할 수 있다.

위의 그림에서처럼 좌표가 교차점에 존재 할 때(1, 2, 3, 4), 최대, 최소 좌표가 각각 다른 영역에 존재 할 때(5), 최대, 최소 좌표 중에 하나가 경계에 존재하고 최대, 최소 좌표가 다른 영역에 존재 할 때(6, 7, 8, 9)에는 4개의 영역에 포함된다.

// makeGlobalMbr : 해당 링크 정보를 저장하는 메소드라고 가정함
// 4사분면 모두 걸쳐있을 때
if (remainderMaxX == 0 && remainderMaxY == 0){
	globalMbrs[shareMaxX][shareMaxY] = makeGlobalMbr(link); 
	globalMbrs[shareMaxX][rotatePos(shareMaxY)] = makeGlobalMbr(link);          
	globalMbrs[rotatePos(shareMaxX)][rotatePos(shareMaxY)] = makeGlobalMbr(link);
	globalMbrs[rotatePos(shareMaxX)][shareMaxY] = makeGlobalMbr(link);
}

if (remainderMaxX == 0 && remainderMinY == 0){
	globalMbrs[shareMaxX][shareMinY] = makeGlobalMbr(link);
	globalMbrs[shareMaxX][rotatePos(shareMinY)] = makeGlobalMbr(link);
	globalMbrs[rotatePos(shareMaxX)][rotatePos(shareMinY)] = makeGlobalMbr(link);
	globalMbrs[rotatePos(shareMaxX)][shareMinY] = makeGlobalMbr(link);
}
   
if (remainderMinX == 0 && remainderMinY == 0){	
    globalMbrs[shareMinX][shareMinY] = makeGlobalMbr(link);
    globalMbrs[shareMinX][rotatePos(shareMinY)] = makeGlobalMbr(link);
    globalMbrs[rotatePos(shareMinX)][rotatePos(shareMinY)] = makeGlobalMbr(link);
    globalMbrs[rotatePos(shareMinX)][shareMinY] = makeGlobalMbr(link);
}

if (remainderMinX == 0 && remainderMaxY == 0){

    globalMbrs[shareMinX][shareMaxY] = makeGlobalMbr(link);
    globalMbrs[shareMinX][rotatePos(shareMaxY)] = makeGlobalMbr(link);
    globalMbrs[rotatePos(shareMinX)][rotatePos(shareMaxY)] = makeGlobalMbr(link);
    globalMbrs[rotatePos(shareMinX)][shareMaxY] = makeGlobalMbr(link);
}
    
if(remainderMaxY == 0 && shareMinY != shareMaxY) 
	|| remainderMinX == 0 && shareMinY != shareMaxY) 
	|| remainderMinY == 0 && shareMinX != shareMaxX)
    || remainderMinX == 0 && shareMinY != shareMaxY)) {

    globalMbrs[shareMaxX][shareMaxY] = makeGlobalMbr(link);
    globalMbrs[shareMaxX][rotatePos(shareMaxY)] = makeGlobalMbr(link);
    globalMbrs[rotatePos(shareMaxX)][rotatePos(shareMaxY)] = makeGlobalMbr(link);
    globalMbrs[rotatePos(shareMaxX)][shareMaxY] = makeGlobalMbr(link);
}

또한 최대, 최소 좌표가 경계에 존재하고 최대, 최소 좌표가 같은 영역에 존재 할 때(1, 2, 3, 4), 최대, 최소 좌표가 경계에 존재하지 않고 최대, 최소 좌표가 각각 다른 영역에 존재 할 때(5, 6)에는 2개의 영역에 포함된다.

if (remainderMinX == 0 && shareMinY == shareMaxY) {

     globalMbrs[shareMinX][shareMinY] = makeGlobalMbr(link);
     globalMbrs[rotatePos(shareMinX)][shareMinY] = makeGlobalMbr(link);
} 

if (remainderMinY == 0 && shareMinX == shareMaxX) {

     globalMbrs[shareMinX][shareMinY] = makeGlobalMbr(link);
     globalMbrs[shareMinX][rotatePos(shareMinY)] = makeGlobalMbr(link);
}

마지막으로 최대, 최소 좌표가 같은 영역에 존재 할 때에는 한 개의 영역에 포함되도록 하였다.

//좌표가 교차 지점에 존재 하지 않을 때
//해당 링크의 x, y 좌표로 매칭되는 경도, 위도 정보를 추출해서 set
globalMbrs[shareMinX][shareMinY] = makeGlobalMbr(link);

if (shareMaxX != shareMinX) {

    globalMbrs[shareMaxX][shareMinY] = makeGlobalMbr(link);
}

if (shareMaxX != shareMinY) {

    globalMbrs[shareMinX][shareMaxY] = makeGlobalMbr(link);
}

if (shareMaxX != shareMinX && shareMaxY != shareMinY) {

    globalMbrs[shareMaxX][shareMaxY] = makeGlobalMbr(link);

[클래스 다이어그램]

이렇게 3가지 방법으로 영역을 나누어서 경로 탐색을 수행했다. 영역을 나누지 않고 경로탐색을 수행했을 때에는 전 범위 내에서 모든 좌표를 찾아가면서 선택한 지점의 좌표를 찾았어야만 했는데, 영역을 나누고 난 다음부터는 최대 4개의 영역에서만 좌표를 찾을 수 있어 경로 탐색하는 시간이 줄어드는 것을 볼 수 있었다.

위와 같은 방법으로 글로벌 경로탐색 프로젝트를 진행하였고, 큰 문제 없이 프로젝트를 마칠 수 있었다. 하지만 분명히 더 보완해야 할 점이 존재한다. 실제 글로벌 경로탐색 프로젝트는 인도네시아 전역에서만 경로탐색이 가능하다고 가정하에 진행되었으므로, 영역을 나눌 때 전세계 기준으로 영역을 나누지 않고, 인도네시아 영역만 범위를 나눴으면 시간이 좀 더 단축 될 수 있었을 것이다. 또한, 정확한 링크의 위치를 알기 위해서는 링크의 각 vertex(링크를 연결하는 점) 지점을 계산해서 링크를 그려야 하지만, 실제로 위도, 경도를 1도 단위로 잘랐으므로 영역의 범위가 넓기 때문에 세부적인 계산은 하지 않았기 때문에 정확성이 떨어진다는 문제도 있었다. 만약, 다른 글로벌 영역에서 경로탐색을 할 때, 위와 같은 범위와 정확성 문제를 보완한다면 좀 더 효율적인 경로탐색을 수행 할 수 있을 것이라고 생각한다.