R-트리 공간 색인 계산기

그 둘은 «점»을 다루는 공간 자료구조입니다. R-트리는 점이 아니라 «사각형(최소경계상자, MBR)»을 다룹니다. 지도 위의 건물·도로·행정구역처럼 그 자체로 면적이 있는 객체를 색인할 때 씁니다.

뿌리에서부터, 자식들 중 새 사각형을 더했을 때 넓이가 가장 적게 늘어나는 자식을 골라 내려갑니다(동점이면 원래 넓이가 더 작은 쪽). 검색할 때 형제 노드끼리 겹치는 영역이 적을수록 가지치기가 잘 되므로, 삽입 단계부터 겹침을 줄이려는 것입니다.

Guttman(1984)의 2차 분할(quadratic split)을 씁니다. 먼저 두 항목을 짝지었을 때 «낭비»(합친 넓이 − 각자 넓이의 합)가 가장 큰 쌍을 두 그룹의 씨앗으로 삼고, 남은 항목마다 두 그룹에 넣었을 때 늘어나는 넓이 차이가 가장 큰 것부터 그 차이가 작은 쪽 그룹에 넣습니다.

질의 사각형과 겹치는 사각형을 모두 찾는 검색입니다. 트리를 타고 내려가다 질의와 아예 겹치지 않는 노드의 MBR을 만나면 그 아래를 통째로 건너뛰어(가지치기), 모든 사각형을 하나씩 비교하는 전수 검사보다 빠릅니다.

이 계산기는 트리로 찾은 결과와, 가지치기 없이 모든 사각형을 하나씩 겹침 판정하는 전수 검사 결과를 나란히 비교해 항상 같은 목록이 나오는지 확인합니다. 가지치기가 답을 놓치지 않는지가 검증 포인트입니다.