코딩맥스

10,000개의 점에서 86개만 비교하고도 범위를 찾을 수 있을까

코딩맥스읽는 데 45분쿼드트리자료구조알고리즘공간 분할
목차

화면 위에 점이 수천 개 흩어져 있는데, 특정 사각형 안에 들어온 점만 골라내야 할 때가 있습니다. 2D 게임의 충돌 검사나 지도 앱의 화면 영역 불러오기가 그렇죠.

이럴 때 자주 꺼내 쓰는 자료구조가 쿼드트리(Quad Tree)입니다. 공간을 네 칸으로 나누고 점이 많이 몰린 칸만 다시 네 칸으로 쪼개 두는 방식입니다.

오래된 아이디어인데도 지금 우리가 쓰는 웹 시각화 도구와 지도 서비스, 비디오 코덱 안에서 여전히 돌아가고 있습니다. 고작 '꽉 찬 칸만 네 개로 나눈다'는 규칙 하나가 어떻게 전체를 다 뒤지는 수고를 덜어 주고 실제 코드에서는 어떤 순서로 움직이는 걸까요?

유닛끼리 부딪혔는지 모든 쌍을 다 비교해야 할까

게임에서 유닛끼리 부딪혔는지 확인하려면 처음엔 모든 쌍을 하나씩 비교하게 되는데, 같은 쌍을 두 번 비교하지 않도록 고쳐도 계산량은 여전히 O(n2)O(n^2)에 머뭅니다. 쿼드트리는 가로세로 길이가 같은 사각형(예를 들어 [0,100)×[0,100))을 북서(NW)·북동(NE)·남서(SW)·남동(SE) 네 칸으로 나누어 자식이 넷인 트리에 1대1로 대응시키고, 각 칸은 중심점(center)과 절반 길이(halfDimension)로 정의된 AABB(Axis-Aligned Bounding Box, 축 정렬 경계 상자)로 표현합니다.

FIG 1 · DIAGRAM
root [0,100)×[0,100)NWNESWSE[0,50)×[0,50)[50,100)×[0,50)[0,50)×[50,100)[50,100)×[50,100)center (50,50)halfDimension = 50root(50,50)h 50NWNESWSE(25,25)(75,25)(25,75)(75,75)h 25h 25h 25h 25(x,y) = center, 칸의 중심점h = halfDimension, 절반 길이
그림 1. 가로세로 100인 사각형이 네 자식 노드를 가진 트리로 대응하고 루트의 절반 길이는 50, 각 자식의 절반 길이는 25다

이렇게 위치를 기준으로 객체를 정리해 두는 구조를 공간 분할(spatial partition)이라고 부릅니다. 지도 앱을 확대할 때마다 큰 사각형 하나가 네 칸으로 갈라지는 모습을 떠올리면 이해가 빠르죠. 비슷한 분할 아이디어는 1934년 Whitney covering lemma에도 나왔지만, 'quadtree'라는 이름은 1974년 라파엘 핀켈(Raphael Finkel)과 존 벤틀리(J. L. Bentley)가 (x, y) 같은 복합 키(composite keys)를 검색하는 논문에서 붙였습니다.

노드가 가리키는 영역이 AABB로 정해져 있으니 코드가 묻는 질문도 단순해집니다. Wikipedia의 쿼드트리 의사코드는 점이 칸 안에 있는지 확인하는 containsPoint와, 두 사각형이 겹치는지 확인하는 intersectsAABB 두 함수에 기대어 동작합니다.

점 하나를 넣으면 insert는 어느 칸을 거쳐 갈까

용량(QT_NODE_CAPACITY)이 1인 트리에 (10,10), (80,20), (30,70), (20,30), (40,40)을 차례로 넣으면, 칸이 찰 때마다 root가 네 칸으로 나뉘고 다시 root.NW가 나뉘면서 각 점의 자리가 정해집니다.

FIG 2 · STEP
1 / 10
root [0,100)×[0,100)용량 1insert 실행 기록 · 들여쓰기는 호출 깊이NWNESWSE(10,10)(80,20)(30,70)(20,30)(40,40)지금 보는 칸거부된 칸넣는 점넣는 순서insert (10, 10)root: stored (10, 10)insert (80, 20)subdivide rootinsert (80, 20)subdivide rootroot.NW: not in -> falseinsert (80, 20)subdivide rootroot.NW: not in -> falseroot.NE: stored (80, 20)insert (30, 70)root.NW: not in -> falseroot.NE: not in -> falseinsert (30, 70)root.NW: not in -> falseroot.NE: not in -> falseroot.SW: stored (30, 70)insert (20, 30)root.NW: stored (20, 30)insert (40, 40)subdivide root.NWinsert (40, 40)subdivide root.NWroot.NW.NW: not in -> falseroot.NW.NE: not in -> falseroot.NW.SW: not in -> falseinsert (40, 40)subdivide root.NWroot.NW.NW: not in -> falseroot.NW.NE: not in -> falseroot.NW.SW: not in -> falseroot.NW.SE: stored (40, 40)(10,10)(80,20)(30,70)(20,30)(40,40)

(10,10)을 넣는다. root가 비어 있으니 root에 그대로 저장한다.

모든 단계 보기
  1. (10,10)을 넣는다. root가 비어 있으니 root에 그대로 저장한다.
  2. (80,20)을 넣는다. 용량 1인 root가 이미 차 있어서 subdivide()로 네 칸을 만든다.
  3. 자식 중 NW에 먼저 묻는다. (80,20)은 NW [0,50)×[0,50) 밖이라 false가 돌아온다.
  4. 다음으로 물은 NE가 (80,20)을 받아 저장한다.
  5. (30,70)을 넣는다. root는 이미 나뉘어 있어서 NW와 NE에 차례로 묻지만 둘 다 거부한다.
  6. 세 번째로 물은 SW가 (30,70)을 저장한다.
  7. (20,30)을 넣는다. 비어 있던 root.NW가 바로 받아서 저장한다.
  8. (40,40)을 넣는다. root.NW로 내려가지만 이미 (20,30)으로 차 있어서 root.NW를 다시 네 칸으로 나눈다.
  9. root.NW 안의 NW, NE, SW는 (40,40)을 담지 못해 차례로 false를 돌려준다.
  10. root.NW.SE가 (40,40)을 저장한다. 먼저 들어온 (10,10)은 root에, (20,30)은 root.NW에 그대로 남는다.
그림 2. 용량 1인 트리에 점 5개를 넣으면 root가 한 번 나뉜 뒤 NW가 한 번 더 나뉘며 차례로 자리가 정해진다

실제 삽입 과정을 따라가려면 Wikipedia의 insert 의사코드부터 봐야 합니다.

C++
function insert(XY p)
{
    // Ignore objects that do not belong in this quad tree
    if (!boundary.containsPoint(p))
        return false; // object cannot be added
 
    // If there is space in this quad tree and if it doesn't have subdivisions, add the object here
    if (points.size < QT_NODE_CAPACITY && northWest == null)
    {
        points.append(p);
        return true;
    }
 
    // Otherwise, subdivide and then add the point to whichever node will accept it
    if (northWest == null)
        subdivide();
    // We have to add the points/data contained in this quad array to the new quads if we only want
    // the last node to hold the data
 
    if (northWest->insert(p)) return true;
    if (northEast->insert(p)) return true;
    if (southWest->insert(p)) return true;
    if (southEast->insert(p)) return true;
 
    // Otherwise, the point cannot be inserted for some unknown reason (this should never happen)
    return false;
}

이 의사코드는 containsPoint의 세부 구현을 {...}로 비워 두었기 때문에, 경계를 반열린 구간 [min, max)로 잡고 y가 아래로 커진다고 가정해 Python 3으로 옮겨 실행해 보았습니다.

Text
insert (10, 10)
root: stored (10, 10)
insert (80, 20)
  subdivide root [0,100)x[0,100)
  root.NW: (80, 20) not in [0,50)x[0,50) -> false
  root.NE: stored (80, 20)
insert (30, 70)
  root.NW: not in -> false
  root.NE: not in -> false
  root.SW: stored (30, 70)
insert (20, 30)
  root.NW: stored (20, 30)
insert (40, 40)
  subdivide root.NW [0,50)x[0,50)
    root.NW.NW / NE / SW: not in -> false
    root.NW.SE: stored (40, 40)

(10,10)은 root가 비어 있어서 바로 들어갑니다. 두 번째 점 (80,20)이 들어올 때는 root의 용량이 꽉 찼고 아직 나뉘지 않았으므로 subdivide()가 실행되어 크기가 같은 네 자식을 만듭니다. 그런 다음 NW부터 순서대로 insert를 호출하는데, NW가 false를 돌려주면 그다음 NE가 받아 저장하고 즉시 true를 반환하죠.

세 번째 (30,70)은 NW와 NE에서 모두 거부된 뒤 SW에 들어가고, 네 번째 (20,30)은 빈 NW에 들어갑니다. 마지막 (40,40)을 넣을 때는 NW가 이미 찼기 때문에 root.NW가 한 번 더 나뉘고 NW.SE에 저장됩니다. 그런데 여기서 이상한 점이 하나 눈에 띕니다. 맨 처음 넣은 (10,10)은 (20,30)이나 (40,40)과 같은 왼쪽 위 영역인데도 root.NW 아래로 내려가지 않고 끝까지 root에 남아 있거든요.

(10,10)은 왜 끝까지 root에 남아 있을까

이유는 insert 코드가 subdivide()를 호출한 뒤 새로 들어온 점 p만 자식에게 넘기고, 이미 points에 담겨 있던 점은 옮기지 않기 때문입니다. 같은 다섯 점으로 만든 트리라도 Wikipedia 의사코드처럼 기존 점을 부모에 남기는 구현과, 로버트 나이스트롬(Robert Nystrom)의 Game Programming Patterns처럼 칸이 나뉠 때 기존 점을 자식으로 내려보내는 구현은 트리 모양이 달라집니다.

FIG 3 · DIAGRAM
Wikipedia 의사코드: 기존 점이 부모에 남는다Game Programming Patterns: 기존 점을 자식으로 내려보낸다rootNWNESWSENWNESWSErootNWNESWSENWNESWSE(10,10)(20,30)(80,20)(30,70)(40,40)(80,20)(30,70)(10,10)(20,30)(40,40)비어 있음비어 있음비어 있음비어 있음비어 있음비어 있음비어 있음비어 있음(10,10)이 root에 그대로 남는다root.NW도 (20,30)을 들고 있다(10,10)이 root.NW.NW까지 내려간다점은 모두 맨 아래 칸에만 있다
그림 3. 같은 점 5개를 넣어도 기존 점을 부모에 남기는 구현과 자식으로 내려보내는 구현은 트리 모양이 다르다

실제로 Wikipedia 코드 안의 주석도 마지막 노드만 데이터를 갖게 하려면 기존 점들을 새 자식으로 옮겨야 한다고 적어 두었습니다. 반대로 기존 점을 자식으로 재분배하는 방식에서는 새로 만든 자식도 용량을 넘을 수 있어서 한 번의 삽입으로 여러 단계가 연쇄 분할될 수 있습니다. 분할 횟수와 재분배 비용은 점 사이 거리와 트리 깊이에도 영향을 받습니다.

웹 시각화 라이브러리 D3의 d3-quadtree는 아예 내부 노드와 리프 노드의 구조 자체를 갈라놓았습니다. 내부 노드는 좌상(0)·우상(1)·좌하(2)·우하(3) 순서의 희소 4원소 배열이고, 리프만 data와 next를 가진 객체여서 length가 4인지 undefined인지로 둘을 구분합니다. 게다가 좌표가 같은 점들은 연결 리스트(next)로 묶어 두어 무한정 쪼개지는 일을 막죠. 이렇게 트리에 점을 쌓아 두었으니, 이제 특정 사각형 안의 점만 꺼내 올 때 queryRange가 어떤 칸을 건너뛰는지 따라가 볼 차례입니다.

범위 질의는 어떤 칸을 아예 보지 않을까

(40,40)을 넣기 직전의 트리에서 중심 (20,20), 각 축의 절반 길이가 15인 정사각형([5,35)×[5,35))으로 queryRange를 실행하면 root와 네 자식 모두 경계 겹침(intersectsAABB)은 검사하지만, 실제로 점 목록을 확인하는 곳은 범위와 겹치는 root와 NW 두 곳뿐입니다. NE, SW, SE는 경계 검사가 거짓이라 점 목록과 후손 탐색을 생략하고, 최종 결과로 [(10,10), (20,30)]이 쌓입니다.

FIG 4 · STEP
1 / 8
NWNESWSE건너뜀건너뜀건너뜀10,1020,3080,2030,70질의 범위 [5,35)×[5,35)건너뛴 칸root(10,10)NW(20,30)NE(80,20)SW(30,70)SE점 없음겹침검사 전검사 전검사 전검사 전root(10,10)1개 담음NW(20,30)겹침NW(20,30)1개 담음NE(80,20)안 겹침SW(30,70)안 겹침SE점 없음안 겹침경계 검사 1개 노드 · 점 목록 확인 0곳경계 검사 1개 노드 · 점 목록 확인 1곳경계 검사 2개 노드 · 점 목록 확인 1곳경계 검사 2개 노드 · 점 목록 확인 2곳경계 검사 3개 노드 · 점 목록 확인 2곳경계 검사 4개 노드 · 점 목록 확인 2곳경계 검사 5개 노드 · 점 목록 확인 2곳결과(10,10)(20,30)2개 반환queryRange(range)현재 노드 root현재 노드 root현재 노드 root.NW현재 노드 root.NW현재 노드 root.NE현재 노드 root.SW현재 노드 root.SE현재 노드 root 반환1if (!boundary.intersectsAABB(range)) return [];2for (p in points) if (range.containsPoint(p)) append(p);3if (northWest == null) return pointsInRange;4for (child in NW, NE, SW, SE) append(child->queryRange(range));

root에서 queryRange를 시작한다. root의 경계 [0,100)×[0,100)이 질의 범위 [5,35)×[5,35)와 겹치므로 계속 진행한다.

모든 단계 보기
  1. root에서 queryRange를 시작한다. root의 경계 [0,100)×[0,100)이 질의 범위 [5,35)×[5,35)와 겹치므로 계속 진행한다.
  2. root의 점 목록을 확인한다. (10,10)이 범위 안에 있어 결과에 담는다.
  3. root에 자식이 있으므로 NW부터 호출한다. NW의 경계 [0,50)×[0,50)이 범위와 겹친다.
  4. NW의 점 목록을 확인해 (20,30)을 결과에 담는다. NW는 자식이 없어 여기서 돌아간다.
  5. NE의 경계 [50,100)×[0,50)은 범위와 겹치지 않는다. 점 목록과 후손을 보지 않고 빈 목록을 돌려준다.
  6. SW의 경계 [0,50)×[50,100)도 겹치지 않는다. 안에 있는 (30,70)은 확인하지 않고 건너뛴다.
  7. SE의 경계 [50,100)×[50,100)도 겹치지 않아 건너뛴다. 이로써 경계 검사는 5개 노드에서 끝났다.
  8. root가 결과 [(10,10), (20,30)]을 돌려준다. 경계는 5개 노드에서 검사했고, 점 목록은 root와 NW 두 곳에서만 확인했다.
그림 4. 경계 겹침은 5개 노드에서 검사하지만 점 목록은 root와 NW 두 곳에서만 확인한다

Wikipedia의 queryRange 의사코드를 보면 첫 줄에서 바로 승부가 갈립니다.

C++
function queryRange(AABB range)
{
    // Prepare an array of results
    Array of XY pointsInRange;
 
    // Automatically abort if the range does not intersect this quad
    if (!boundary.intersectsAABB(range))
        return pointsInRange; // empty list
 
    // Check objects at this quad level
    for (int p = 0; p < points.size; p++)
    {
        if (range.containsPoint(points[p]))
            pointsInRange.append(points[p]);
    }
 
    // Terminate here, if there are no children
    if (northWest == null)
        return pointsInRange;
 
    // Otherwise, add the points from the children
    pointsInRange.appendArray(northWest->queryRange(range));
    pointsInRange.appendArray(northEast->queryRange(range));
    pointsInRange.appendArray(southWest->queryRange(range));
    pointsInRange.appendArray(southEast->queryRange(range));
 
    return pointsInRange;
}

root는 질의 범위와 겹치므로 자신이 들고 있던 (10,10)이 범위 안에 있는지 확인해 결과에 담고 네 자식을 호출합니다. NW 역시 경계가 겹쳐서 (20,30)을 담은 뒤 자식이 없으므로 돌아옵니다. 반면 NE, SW, SE는 첫 if 문에서 intersectsAABB가 거짓으로 나오자마자 빈 목록을 돌려주고 끝납니다. 만약 그 아래에 수천 개의 자손 노드가 매달려 있었더라도 통째로 건너뛰는 셈이죠. 점이 몇 개 안 될 때는 세 칸을 덜 보는 수준이지만, 점이 아주 많아지면 차이가 어떻게 달라질까요?

점이 아주 많아지면 얼마나 덜 비교할까

1000×1000 영역에 균등 난수로 점을 뿌리고(용량 4, seed 1) 20×20 범위를 질의한 단 한 번의 실행(난수 생성기와 질의 좌표·집계 코드 미기재, 실행 시간 미측정, 독립 벤치마크 아님)에서 전수 비교와 쿼드트리가 각각 몇 개의 점을 비교했는지 정리했습니다.

방식비교한 점 수찾은 점 수
전수 비교10,000개6개
쿼드트리 (용량 4)86개6개

찾은 점의 개수는 똑같은데 비교한 점의 수는 백 배 넘게 벌어졌습니다. 고전적인 점 쿼드트리의 점 삽입과 정확한 점 검색은 무작위 삽입 조건에서 평균 로그 비용으로 설명됩니다. 다만 여기서 다룬 고정 중점 구현의 범위 질의 비용은 방문한 노드와 검사·반환한 점의 수에 따라 달라지며, 일반적으로 O(log⁡n)O(\log n)이라고 단정할 수 없습니다. 한편 천체 N체 시뮬레이션의 Barnes–Hut 알고리즘(1986년 Nature) 역시 공간을 계층적으로 나누어 힘 계산량을 N2N^2에서 Nlog⁡NN \log N으로 낮췄습니다. D3의 many-body force도 쿼드트리와 이 근사를 써서 한 번 적용할 때 O(nlog⁡n)O(n \log n)에 계산합니다(셀 너비 w와 질량중심까지의 거리 l의 비 w/l이 기본값 theta = 0.9보다 작으면 그 셀 안의 노드를 하나로 취급). 그런데 쿼드트리는 이렇게 범위 안의 점을 빠르게 찾는 데서 끝나지 않고, 매일 보는 지도 서비스의 타일 주소 체계에도 그대로 쓰입니다.

지도 타일 주소는 왜 4진수 숫자일까

Bing Maps의 타일 시스템에서는 레벨 3의 타일 (3, 5)를 예로 들 때 X=011과 Y=101의 대응하는 비트를 한 쌍씩 결합해 2, 1, 3을 만들고, 이 숫자들이 루트에서 사분면을 차례로 고른 경로 "213"이 됩니다.

FIG 5 · DIAGRAM
레벨 1레벨 2레벨 3X = 3Y = 5X + 2Yquadkey0111012130+21+01+22130123사분면 번호: 왼쪽 위부터 0, 1, 2, 3Y는 아래로 커진다213X=3Y=5레벨 3 · 8 × 8 타일 중 (3, 5)루트 → 2 → 21 → 213
그림 5. 타일 좌표 (3, 5)의 X·Y 비트를 한 쌍씩 섞으면 루트에서 내려가는 4진수 경로 213이 나온다

Bing Maps 타일은 256 × 256 픽셀 크기이고, 레벨별 지도 너비는 2^level 타일입니다. 레벨마다 X 비트가 1이면 1, Y 비트가 1이면 2를 더해 0에서 3 사이 숫자 하나를 만들고 이를 이어 붙여 quadkey를 만드는 C# 코드입니다.

csharp
public static string TileXYToQuadKey(int tileX, int tileY, int levelOfDetail)
{
    StringBuilder quadKey = new StringBuilder();
    for (int i = levelOfDetail; i > 0; i--)
    {
        char digit = '0';
        int mask = 1 << (i - 1);
        if ((tileX & mask) != 0)
        {
            digit++;
        }
        if ((tileY & mask) != 0)
        {
            digit++;
            digit++;
        }
        quadKey.Append(digit);
    }
    return quadKey.ToString();
}

이 방식 덕분에 quadkey의 길이가 곧 줌 레벨이 되고, 어떤 타일의 주소는 항상 부모 타일의 quadkey로 시작합니다. 비슷한 트리 분할은 비디오 코덱에서도 쓰이는데, HEVC 개요 논문(2012년)은 부호화 트리 블록(CTB)을 쿼드트리 형태의 신호로 더 작은 블록으로 쪼갠다고 설명합니다. 그렇다고 모든 공간 문제에서 쿼드트리가 정답이 되지는 않습니다.

쿼드트리 대신 다른 구조를 고를 때는 언제일까

빈 공간이 넓고 데이터가 한쪽에 몰려 있는 2차원 정적 공간이라면 쿼드트리가 잘 맞습니다. 반대로 점이 한곳에 극단적으로 몰리거나 삽입 순서가 나쁘면 점 쿼드트리의 높이가 점 개수에 비례해 연결 리스트처럼 선형으로 무너질 수 있고(PR 쿼드트리와 압축 쿼드트리도 나쁜 입력에서는 선형이 될 수 있음) 같은 좌표 처리가 없는 구현에서는 동일 좌표를 반복해서 넣을 때 분할이 멈추지 않을 여지도 있습니다.

객체가 계속 움직이는 게임에서도 고민이 필요합니다. 위치가 바뀔 때마다 트리를 다시 정리해야 해서 CPU를 쓰기 때문이죠. D3 문서도 트리에 들어 있는 동안에는 점의 x, y 좌표를 직접 바꾸지 말고 remove한 뒤 다시 add하라고 권하며, 많은 점이 움직였다면 트리를 새로 만드는 편이 나을 수 있다고 봅니다. Finkel·Bentley의 원 논문 요약에서도 점 쿼드트리의 삭제와 병합은 본질적으로 어려워 보인다고 짚었습니다. 빈 공간이 많은지, 객체가 자주 움직이는지, 몇 차원인지에 따라 네 가지 자료구조의 쓰임새가 갈립니다.

자료구조잘 맞는 상황약점 또는 참고할 점
고정 격자(flat grid)객체가 자주 움직이고 구조가 단순하며 셀을 배열로 미리 할당해 격자 구조의 메모리를 고정하고 싶을 때계층형 쿼드트리와 달리 빈 공간이 많을 때 유리하지 않음
쿼드트리빈 공간이 많은 2차원 공간에서 범위 질의·충돌 검사를 할 때불균형 시 높이가 선형이 되고, 객체 이동 시 재정리 비용이 듦
k-d tree다차원 점 데이터의 범위 검색·최근접 이웃 검색점 쿼드트리와 달리 2차원 공간을 네 사분면으로 고정 분할하지 않음
옥트리(octree)3차원 공간을 정육면체 여덟 개로 나누어 다룰 때쿼드트리와 같은 계층 분할이라 객체가 움직이면 갱신 비용이 듦

쿼드트리는 어떤 데이터 모양에 잘 맞는지가 분명한 도구입니다.

꽉 찬 칸만 쪼갠다는 한 문장이 결국 무엇을 바꿨나

모든 유닛 쌍을 대조해야 했던 O(n2)O(n^2) 비교가, 공간을 네 칸씩 쪼개어 점 분포와 질의 위치에 따라 범위와 겹치지 않는 가지의 점 검사와 후손 탐색을 생략할 수 있는 작업으로 바뀝니다. insert와 queryRange 두 재귀 함수가 하는 일도 '내 칸 안에 있는가'와 '이 칸이 범위와 겹치는가'를 묻는 것뿐이죠.

물론 Finkel·Bentley 논문 본문이나 Samet의 1984년 서베이 전체를 확인하지 못한 한계는 있고, Wikipedia 문서 상단에는 인용 형식이 불명확하다는 경고가 붙어 있으며 의사코드 역시 경계선 위 점의 처리가 빠져 있습니다. 그런데도 반세기가 지난 지금까지 게임 엔진과 D3, 지도 타일이 같은 원리를 쓰는 이유는 구조가 화려해서가 아니라, 빈 공간을 통째로 건너뛰는 가장 단순한 규칙이 여전히 유효하기 때문입니다.