(GIS)지도 데이터 시각화, R-tree 알고리즘

(격식체 = gpt)

GIS 데이터 시각화

GIS 데이터를 다루면서 시각화 렌더링시에, 위도/경도가 어느 지역에 속하는지 분류하는데 예를 들면 다음과 같다.

지역1: (127.123, 36.231), (127.154, 36.271), (127.203, 36.181)
지역2: (127.423, 36.531), (127.454, 36.571), (127.503, 36.581)

 

(경도, 위도) 가 특정 지역에 적중하는지 판단하는 알고리즘은 d3.geoContains 같은 게 있다.

d3.getContains는 내부적으로 어떤 알고리즘을 사용할까? 이름만 들어보자.

 

Ray-Casting: 다각형 내 포함 여부를 판단하기 위해 주로 Ray-Casting 알고리즘을 사용합니다. 이는 주어진 점에서 임의의 방향으로 반직선을 그렸을 때, 다각형의 경계를 통과하는 횟수를 계산하여 홀수이면 내부에, 짝수이면 외부에 있는 것으로 간주하는 방식입니다.

 

대륙별 경계 고려: 지구의 곡률과 큰 면적을 고려하여, 좌표계의 차이와 지구 표면의 비정형성을 처리하기 위한 좌표 변환을 수행합니다. 이 과정에서 경도가 180도 이상인 경우 경계가 반대로 이어지는 문제를 방지합니다.

 

GIS 특성을 고려하고 Ray-Casting 등 기하 알고리즘을 사용하는 듯하다.

---

아무튼, geoContains(object, point) 이런 식으로 지역과 포인트를 넣어서 포인트가 히트하는지 true/false를 반환한다.

예시로 지역이 300개, 위치 데이터가 10,000개라면 1개 데이터는 적중하는 지역이 나올 때까지 지역 300개를 순회한다.

그래서 300 * 10,000 = 3백만이다. 렌더링마다 수행되기는 과분한 횟수이다.

 

O(n^2) 시간복잡도를 줄여야겠다. 포인터에서 가까운 지역을 먼저 추리고 그 안에서 geoContains를 확인하려면?

 

R-tree

R-tree

MBR : Minimum Bounding Rectangle, 최소 경계 직사각형

Internal Node: 리프 노드로 향하는 포인터를 포함하는 노드, MBR을 통해 자식 노드들의 범위를 나타냄

Leaf Node : 실제 데이터를 포함하는 노드

 

위 그림에서 마지막 계층(파란색)이 Leaf Node이고 그전에는 Internal Node이다.

검색 (Search)

검색은 범위 쿼리와 근접성 쿼리가 될 수 있다.

Range Query: 특정한 영역(사각형, 원 등)을 주고, 이 영역과 겹치는 모든 데이터 항목을 찾는다.

Nearest Neighbor Query: 특정 좌표를 기준으로 가장 가까운 데이터 항목을 찾는다.

검색 과정(Nearest Neighbor Query)

1. 루트 노드에서 시작:
   • 루트 노드의 모든 자식 노드(MBR)와 기준점 사이의 최소 거리를 계산합니다.
   • 거리 기준으로 노드를 정렬한 후, 가장 가까운 노드부터 탐색을 시작합니다.
2. 내부 노드 탐색:
   • 내부 노드의 자식 노드들 중 최소 거리 후보를 기준으로 탐색합니다.
   • 기준점과 멀리 떨어진 노드는 탐색에서 제외합니다.
3. 리프 노드 탐색:
   • 리프 노드에 도달하면, 데이터 항목과 기준점 사이의 거리를 계산합니다.
   • 현재까지 발견된 데이터 중 가장 가까운 항목(들)을 업데이트합니다.
4. 가지치기:
   • 탐색 도중, 더 가까운 항목이 발견되면 멀리 있는 노드들을 배제합니다.
   • 이로 인해 검색 범위가 점점 줄어들어 효율성이 증가합니다.

분할 (Split):

• 노드가 꽉 차면, 그 노드를 분할하여 두 개의 새로운 노드를 생성합니다. 분할 시, 겹침이 최소화되도록 데이터를 분배합니다.
• 이 과정에서 각 노드는 다시 MBR을 계산하여 트리의 균형을 유지합니다.

 

R-tree, 이중 순회 시간 비교

겹침 조건 = not (겹치지 않는 조건) 이다.

!(box.minX > searchArea.maxX ||
    box.maxX < searchArea.minX ||
    box.minY > searchArea.maxY ||
    box.maxY < searchArea.minY)

하나라도 true면 겹치지 않는다.

 

위치 데이터 백만 개, 지역 데이터 1,000개라고 생각하고 R-tree 시간을 측정해 보자. (npm rbush 라이브러리 사용)

이중 순회

// 랜덤 지역 데이터 생성 함수
const generateRandomData = (count) => {
    const data = [];
    for (let i = 0; i < count; i++) {
        const x = Math.random() * 1000;
        const y = Math.random() * 1000;
        const width = Math.random() * 10;
        const height = Math.random() * 10;
        data.push({
            minX: x,
            minY: y,
            maxX: x + width,
            maxY: y + height,
        });
    }
    return data;
};

// 검색 함수 (이중 순회)
const searchBoxes = (data, searchArea) => {
    const results = [];
    for (const box of data) {
        // 겹침 조건 확인
        if (
            !(box.minX > searchArea.maxX ||
                box.maxX < searchArea.minX ||
                box.minY > searchArea.maxY ||
                box.maxY < searchArea.minY)
        ) {
            results.push(box);
        }
    }
    return results;
};

console.time("Total Time");
// 지역 데이터 생성
const dataCount = 1_000;
const data = generateRandomData(dataCount);

// 검색 및 시간 측정
const searchCount = 1_000_000;
console.time('Search Time');
for (let i = 0; i < searchCount; i++) {
    const x = Math.random() * 1000;
    const y = Math.random() * 1000;
    const searchArea = {
        minX: x,
        minY: y,
        maxX: x + 50,
        maxY: y + 50,
    };
    const results = searchBoxes(data, searchArea);
}
console.timeEnd('Search Time');
console.timeEnd("Total Time");

Search Time: 3.302s

R-tree

const RBush = require('rbush');

const tree = new RBush();

// 랜덤 지역 데이터 생성 함수
const generateRandomData = (count) => {
    const data = [];
    for (let i = 0; i < count; i++) {
        const x = Math.random() * 1000;
        const y = Math.random() * 1000;
        const width = Math.random() * 10;
        const height = Math.random() * 10;
        data.push({
            minX: x,
            minY: y,
            maxX: x + width,
            maxY: y + height,
        });
    }
    return data;
};

console.time("Total Time");
// 지역 데이터 생성
const dataCount = 1_000;
const data = generateRandomData(dataCount);
// R-tree 데이터 삽입 및 시간 측정
console.time('Insertion Time');
tree.load(data);
console.timeEnd('Insertion Time');

// 검색 작업 수행 및 시간 측정
const searchCount = 1_000_000;
console.time('Search Time');
for (let i = 0; i < searchCount; i++) {
    const x = Math.random() * 1000;
    const y = Math.random() * 1000;
    const searchArea = {
        minX: x,
        minY: y,
        maxX: x + 50,
        maxY: y + 50,
    };
    const a = tree.search(searchArea);
    // console.log(a.length);
}
console.timeEnd('Search Time');
console.timeEnd("Total Time");

Insertion Time: 2.125ms
Search Time: 293.518ms
Total Time: 301.968ms

 

결론

GIS가 아니어도 데이터 시각화를 하다 보면, 비교적 복잡한 상태와 데이터 로직을 만들게 되는 것 같다.

알고리즘을 만들 때, O(n^2) 복잡도를 주의하고, 데이터 특성을 고려하여 O(N or logN)으로 풀어내자.