쿼드트리

쿼드트리
종류	트리
발명일	1974
발명자	라파엘 핀켈과 J.L. 벤틀리
점근표기법으로 된 시간복잡도
알고리즘 평균 최악의 경우

점 데이터를 포함하는 점-영역 쿼드트리. 버킷 용량 1.

단계별 이미지 쿼드트리 압축. 왼쪽은 트리 경계 상자와 함께 압축된 이미지를 보여주고, 오른쪽은 압축된 이미지만을 보여준다.

쿼드트리(Quadtree)는 각 내부 노드가 정확히 네 개의 자식을 갖는 트리 자료 구조이다. 쿼드트리는 팔진트리의 2차원 아날로그이며, 2차원 공간을 네 개의 사분면 또는 영역으로 재귀적으로 분할하여 공간을 분할하는 데 가장 자주 사용된다. 리프 셀과 관련된 데이터는 응용 프로그램에 따라 다르지만, 리프 셀은 "흥미로운 공간 정보의 단위"를 나타낸다.

분할된 영역은 정사각형 또는 직사각형일 수 있으며, 임의의 모양을 가질 수도 있다. 이 자료 구조는 1974년 라파엘 핀켈과 J.L. 벤틀리에 의해 쿼드트리라고 명명되었다. 유사한 분할은 Q-트리라고도 알려져 있다.

모든 형태의 쿼드트리는 몇 가지 공통적인 특징을 공유한다.

• 공간을 적응 가능한 셀로 분해한다.
• 각 셀(또는 버킷)은 최대 용량을 가진다. 최대 용량에 도달하면 버킷이 분할된다.
• 트리 디렉터리는 쿼드트리의 공간 분해를 따른다.

트리-피라미드(T-피라미드)는 "완전한" 트리이다. T-피라미드의 모든 노드는 리프 노드를 제외하고 4개의 자식 노드를 가진다. 모든 리프는 동일한 레벨에 있으며, 이미지의 개별 픽셀에 해당하는 레벨이다. 트리-피라미드의 데이터는 이진 힙이 완전 이진 트리를 배열에 압축적으로 저장하는 방식과 유사하게 암묵적 자료 구조로 배열에 압축적으로 저장될 수 있다.

유형

2D 인덱스에 대한 재귀적 이진 공간 분할법 쿼드트리의 예시.

쿼드트리는 영역, 점, 선 및 곡선을 포함하여 나타내는 데이터 유형에 따라 분류될 수 있다. 쿼드트리는 또한 트리의 모양이 데이터 처리 순서에 독립적인지 여부에 따라 분류될 수도 있다. 다음은 쿼드트리의 일반적인 유형이다.

영역 쿼드트리

영역 쿼드트리는 2차원 공간의 분할을 나타내며, 영역을 네 개의 동일한 사분면, 하위 사분면 등으로 분해하고, 각 리프 노드는 특정 하위 영역에 해당하는 데이터를 포함한다. 트리의 각 노드는 정확히 네 개의 자식을 갖거나 자식이 없다(리프 노드). 이 분해 전략을 따르는 쿼드트리(즉, 더 많은 정제가 필요한 흥미로운 데이터가 하위 사분면에 있는 한 하위 사분면을 세분화하는)의 높이는 분해되는 공간 내 흥미로운 영역의 공간 분포에 민감하며 의존적이다. 영역 쿼드트리는 트라이 (컴퓨팅)의 한 유형이다.

깊이가 n인 영역 쿼드트리는 2ⁿ × 2ⁿ 픽셀로 구성된 이미지를 나타내는 데 사용될 수 있으며, 각 픽셀 값은 0 또는 1이다. 루트 노드는 전체 이미지 영역을 나타낸다. 어떤 영역의 픽셀이 완전히 0 또는 1이 아니면, 해당 영역은 세분화된다. 이 응용 프로그램에서 각 리프 노드는 모두 0 또는 모두 1인 픽셀 블록을 나타낸다. 이러한 트리가 이미지를 저장하는 데 사용될 때 공간 절약 가능성에 주목하라. 이미지는 종종 전체적으로 동일한 색상 값을 가진 상당한 크기의 많은 영역을 포함한다. 이미지의 모든 픽셀을 큰 2차원 배열로 저장하는 대신, 쿼드트리는 픽셀 해상도 크기의 셀보다 훨씬 높은 수준에서 동일한 정보를 캡처할 수 있다. 트리 해상도와 전체 크기는 픽셀 및 이미지 크기에 의해 제한된다.

영역 쿼드트리는 데이터 필드의 가변 해상도 표현으로도 사용될 수 있다. 예를 들어, 영역의 온도는 쿼드트리로 저장될 수 있으며, 각 리프 노드는 자신이 나타내는 하위 영역의 평균 온도를 저장한다.

점 쿼드트리

점 쿼드트리는 2차원 점 데이터를 표현하는 데 사용되는 이진 트리의 변형이다. 모든 쿼드트리의 특징을 공유하지만, 분할의 중심이 항상 점 위에 있으므로 진정한 트리이다. 일반적으로 O(log n) 시간에 작동하며 2차원, 순서가 있는 데이터 점을 비교하는 데 매우 효율적이다. 점 쿼드트리는 완전성을 위해 언급할 가치가 있지만, 일반화된 이진 탐색 도구로서 K-d 트리에 의해 능가되었다. 무작위 삽입을 가진 점 쿼드트리는 가중 평면 확률 격자라는 이름으로 연구되었다.

점 쿼드트리는 다음과 같이 구성된다. 삽입할 다음 점이 주어지면, 해당 점이 있는 셀을 찾아 트리에 추가한다. 새 점은 해당 점을 통과하는 수직선과 수평선에 의해 셀이 사분면으로 분할되도록 추가된다. 결과적으로 셀은 직사각형이지만 반드시 정사각형일 필요는 없다. 이 트리에서 각 노드는 입력 점 중 하나를 포함한다.

평면의 분할은 점 삽입 순서에 따라 결정되므로, 트리의 높이는 삽입 순서에 민감하며 의존적이다. "나쁜" 순서로 삽입하면 입력 점 수에 선형적인 높이의 트리(이 경우 연결 리스트가 됨)가 될 수 있다. 점 집합이 정적인 경우, 균형 잡힌 높이의 트리를 만들기 위한 사전 처리가 수행될 수 있다.

점 쿼드트리의 노드 구조

점 쿼드트리의 노드는 이진 트리의 노드와 유사하며, 주요 차이점은 일반적인 이진 트리처럼 두 개("왼쪽"과 "오른쪽") 대신 네 개의 포인터(각 사분면에 하나씩)를 갖는다는 것이다. 또한 키는 일반적으로 x, y 좌표를 참조하는 두 부분으로 분해된다. 따라서 노드에는 다음 정보가 포함된다.

• 네 개의 포인터: quad[‘NW’], quad[‘NE’], quad[‘SW’], quad[‘SE’]
• 점; 여기에는 다음이 포함된다:
  • 키; 일반적으로 x, y 좌표로 표현됨
  • 값; 예를 들어 이름

점-영역(PR) 쿼드트리

점-영역(PR) 쿼드트리는 영역 쿼드트리와 매우 유사하다. 차이점은 셀에 저장되는 정보 유형이다. 영역 쿼드트리에서는 리프 셀의 전체 영역에 적용되는 균일한 값이 저장된다. 그러나 PR 쿼드트리의 셀은 리프 셀 내에 존재하는 점들의 목록을 저장한다. 앞에서 언급했듯이, 이 분해 전략을 따르는 트리의 높이는 점들의 공간 분포에 따라 달라진다. 점 쿼드트리처럼 PR 쿼드트리도 "나쁜" 점 집합이 주어지면 선형적인 높이를 가질 수 있다.

가장자리 쿼드트리

가장자리 쿼드트리(PM 쿼드트리와 매우 유사하게)는 점 대신 선을 저장하는 데 사용된다. 곡선은 셀당 하나의 선분만 남을 때까지 매우 세밀하게 셀을 세분화하여 근사화된다. 모서리/정점 근처에서 가장자리 쿼드트리는 최대 분해 수준에 도달할 때까지 계속 분할한다. 이로 인해 극도로 불균형한 트리가 생성되어 인덱싱 목적을 상실할 수 있다.

다각형 맵(PM) 쿼드트리

다각형 맵 쿼드트리(또는 PM 쿼드트리)는 퇴화될 수 있는 (즉, 고립된 정점이나 가장자리를 가질 수 있는) 다각형 컬렉션을 저장하는 데 사용되는 쿼드트리의 변형이다. PM 쿼드트리와 가장자리 쿼드트리 사이의 큰 차이점은 고려 중인 셀이 셀 내의 정점에서 세그먼트가 만나는 경우에도 세분화되지 않는다는 것이다.

PM 쿼드트리에는 세 가지 주요 클래스가 있으며, 각 검은색 노드에 저장하는 정보에 따라 달라진다. PM3 쿼드트리는 임의의 수의 교차하지 않는 가장자리와 최대 하나의 점을 저장할 수 있다. PM2 쿼드트리는 PM3 쿼드트리와 동일하지만, 모든 가장자리가 동일한 끝점을 공유해야 한다는 점이 다르다. 마지막으로 PM1 쿼드트리는 PM2와 유사하지만, 검은색 노드에는 점과 해당 가장자리가 포함되거나 점을 공유하는 가장자리 집합만 포함될 수 있으며, 점과 점을 포함하지 않는 가장자리 집합을 동시에 가질 수는 없다.

압축된 쿼드트리

이 섹션은 사리엘 하르-펠레드의 책에 있는 하위 섹션을 요약한 것이다.

세분화된 셀에 해당하는 모든 노드를 저장하면 많은 빈 노드를 저장하게 될 수 있다. 리프에 흥미로운 데이터가 있는 서브트리(즉, "중요한 서브트리")만 저장하여 이러한 희소 트리의 크기를 줄일 수 있다. 실제로 크기를 더 줄일 수도 있다. 중요한 서브트리만 유지하면 가지치기 과정에서 중간 노드의 차수가 2인 긴 경로(하나의 부모와 하나의 자식에 대한 링크)가 남을 수 있다. 이 경로의 시작 부분에 있는 노드 $u$만 저장하고 (제거된 노드를 나타내기 위해 일부 메타데이터를 연결하여) 끝에 있는 서브트리를 $u$에 연결하면 된다. "나쁜" 입력 점이 주어지면 이러한 압축된 트리도 여전히 선형 높이를 가질 수 있다.

이 압축을 수행할 때 트리의 많은 부분을 잘라내지만, Z-차순 곡선을 활용하면 여전히 로그 시간 탐색, 삽입 및 삭제를 달성할 수 있다. Z-차순 곡선은 전체 쿼드트리(및 압축된 쿼드트리)의 각 셀을 $O(1)$ 시간 안에 1차원 선으로 매핑하여(그리고 $O(1)$ 시간 안에 다시 매핑하여) 요소에 대한 전체 순서를 생성한다. 따라서 정렬된 집합의 자료 구조(트리의 노드를 저장하는)에 쿼드트리를 저장할 수 있다.

계속하기 전에 합리적인 가정을 언급해야 한다. 이진수로 표현된 두 실수 $\alpha ,\beta \in [0,1)$가 주어졌을 때, 이들이 다른 첫 번째 비트의 인덱스를 $O(1)$ 시간에 계산할 수 있다고 가정한다. 또한 쿼드트리에서 두 점/셀의 최저 공통 조상을 $O(1)$ 시간에 계산하고 상대적인 Z-순서를 설정할 수 있으며, 바닥 함수를 $O(1)$ 시간에 계산할 수 있다고 가정한다.

이러한 가정을 통해 주어진 점 $q$의 점 위치(즉, $q$를 포함할 셀 결정), 삽입 및 삭제 작업은 모두 $O(\log {n})$ 시간에 수행될 수 있다(즉, 기본 정렬된 집합 자료 구조에서 검색을 수행하는 데 걸리는 시간).

$q$에 대한 점 위치를 수행하려면(즉, 압축된 트리에서 해당 셀을 찾으려면):

1. Z-순서에서 $q$보다 먼저 오는 압축된 트리의 기존 셀을 찾는다. 이 셀을 $v$라고 한다.
2. 만약 $q\in v$이면, $v$를 반환한다.
3. 그렇지 않으면, 압축되지 않은 쿼드트리에서 점 $q$와 셀 $v$의 최저 공통 조상이 되었을 셀을 찾는다. 이 조상 셀을 $u$라고 한다.
4. Z-순서에서 $u$보다 먼저 오는 압축된 트리의 기존 셀을 찾아 반환한다.

구체적인 내용은 생략하고, 삽입 및 삭제를 수행하려면 먼저 삽입/삭제할 대상의 점 위치를 찾은 다음 삽입/삭제한다. 필요에 따라 노드를 생성하고 제거하면서 트리를 적절하게 재구성해야 한다.

쿼드트리의 일반적인 사용

비트맵과 압축된 쿼드트리 표현

• 이미지 표현
• 이미지 처리
• 메시 생성
• 공간 인덱스팅, 점 위치 쿼리, 범위 쿼리
• 2차원에서의 효율적인 충돌 감지
• 지형 데이터의 뷰 프러스텀 컬링
• 스프레드시트의 서식 정보나 일부 행렬 계산을 위한 희소 데이터 저장
• 다차원 장의 해법 (전산 유체 역학, 전자기학)
• 라이프 게임 시뮬레이션 프로그램.
• 상태 추정
• 쿼드트리는 프랙탈 이미지 분석 분야에서도 사용된다.
• 최대 서로소 집합

쿼드트리를 이용한 이미지 처리

쿼드트리, 특히 영역 쿼드트리는 이미지 처리 응용 분야에 잘 적용되었다. 이진 이미지 데이터에 대한 논의에 국한하겠지만, 영역 쿼드트리와 그 위에서 수행되는 이미지 처리 작업은 컬러 이미지에도 마찬가지로 적합하다.

이미지 합집합/교집합

이미지 조작에 쿼드트리를 사용하는 장점 중 하나는 합집합 및 교집합의 집합 연산을 간단하고 빠르게 수행할 수 있다는 것이다. 두 개의 이진 이미지가 주어졌을 때, 이미지 합집합(오버레이라고도 함)은 입력 이미지 중 하나라도 동일한 위치에 검은색 픽셀이 있으면 픽셀이 검은색인 이미지를 생성한다. 즉, 출력 이미지의 픽셀은 두 입력 이미지 모두의 해당 픽셀이 흰색일 때만 흰색이고, 그렇지 않으면 출력 픽셀은 검은색이다. 픽셀별로 연산을 수행하는 대신, 쿼드트리의 단일 노드로 여러 픽셀을 표현하는 능력을 활용하여 합집합을 더 효율적으로 계산할 수 있다. 아래 논의를 위해, 서브트리가 검은색과 흰색 픽셀을 모두 포함하면 해당 서브트리의 루트는 회색으로 칠해진다고 말한다.

이 알고리즘은 두 입력 쿼드트리($T_{1}$ 및 $T_{2}$)를 순회하면서 출력 쿼드트리 $T$를 구축하는 방식으로 작동한다. 비공식적으로 알고리즘은 다음과 같다. 이미지의 동일한 영역에 해당하는 노드 $v_{1}\in T_{1}$ 및 $v_{2}\in T_{2}$를 고려한다.

• 만약 $v_{1}$ 또는 $v_{2}$가 검은색이면, $T$에 해당 노드가 생성되고 검은색으로 칠해진다. 만약 둘 중 하나만 검은색이고 다른 하나가 회색이면, 회색 노드 아래에 서브트리가 포함된다. 이 서브트리는 순회할 필요가 없다.
• 만약 $v_{1}$ (각각 $v_{2}$)가 흰색이면, $v_{2}$ (각각 $v_{1}$)와 그 아래의 서브트리(있는 경우)가 $T$로 복사된다.
• 만약 $v_{1}$과 $v_{2}$ 모두 회색이면, $v_{1}$과 $v_{2}$의 해당 자식이 고려된다.

이 알고리즘은 작동하지만, 그 자체로 최소 크기의 쿼드트리를 보장하지는 않는다. 예를 들어, $2^{k}\times 2^{k}$ 크기의 바둑판(모든 타일이 픽셀인)과 그 보수를 합집합하는 결과를 고려해 보자. 결과는 루트 노드(검은색으로 칠해진)만 있는 쿼드트리로 표현되어야 할 거대한 검은색 사각형이지만, 대신 알고리즘은 깊이 $k$의 완전 4진 트리를 생성한다. 이를 해결하기 위해, 결과 쿼드트리의 상향식 순회를 수행하여 네 자식 노드가 동일한 색상인지 확인하고, 이 경우 부모 노드를 동일한 색상의 리프로 대체한다.

두 이미지의 교집합은 거의 동일한 알고리즘이다. 두 이미지의 교집합을 생각하는 한 가지 방법은 흰색 픽셀에 대한 합집합을 수행하는 것이다. 따라서 교집합을 수행하려면 합집합 알고리즘에서 검은색과 흰색의 언급을 바꾼다.

연결 성분 레이블링

이진 이미지에서 인접한 두 검은색 픽셀을 고려해 보자. 이들은 경계 수평 또는 수직 가장자리를 공유하면 인접한다. 일반적으로 두 검은색 픽셀은 인접한 픽셀로만 이동하여 다른 픽셀에서 도달할 수 있으면 연결된다(즉, 각 연속 쌍이 인접한 검은색 픽셀 경로가 존재한다). 연결된 검은색 픽셀의 각 최대 집합은 연결 성분이다. 이미지의 쿼드트리 표현을 사용하여 사메트는 쿼드트리 크기에 비례하는 시간으로 이러한 연결 성분을 찾고 레이블을 지정하는 방법을 보여주었다. 이 알고리즘은 다각형 색칠에도 사용될 수 있다.

알고리즘은 세 단계로 작동한다.

1. 검은색 픽셀 간의 인접 관계를 설정한다.
2. 첫 번째 단계의 동등 관계를 처리하여 각 연결 성분에 대해 고유한 레이블을 얻는다.
3. 검은색 픽셀에 해당 연결 성분과 연결된 레이블을 지정한다.

논의를 단순화하기 위해 쿼드트리 노드의 자식이 Z-차순 (SW, NW, SE, NE)을 따른다고 가정하자. 이 구조를 믿을 수 있기 때문에, 어떤 셀에 대해서도 계층 구조의 다른 수준에서 인접한 셀을 찾기 위해 쿼드트리를 탐색하는 방법을 안다.

1단계는 쿼드트리의 후위 순회로 수행된다. 각 검은색 리프 $v$에 대해 북쪽 이웃 및 동쪽 이웃(즉, $v$의 셀과 가장자리를 공유하는 북쪽 및 동쪽 셀)을 나타내는 노드를 살펴본다. 트리가 Z-순서로 구성되어 있으므로 남쪽 및 서쪽 이웃은 이미 처리되고 고려되었다는 불변성을 가진다. 현재 고려 중인 북쪽 또는 동쪽 이웃을 $u$라고 하자. 만약 $u$가 검은색 픽셀을 나타내면:

• 만약 $u$ 또는 $v$ 중 하나만 레이블을 가지고 있다면, 그 레이블을 다른 셀에 할당한다.
• 만약 둘 다 레이블을 가지고 있지 않다면, 하나를 생성하여 둘 다에 할당한다.
• 만약 $u$와 $v$가 다른 레이블을 가지고 있다면, 이 레이블 동등성을 기록하고 다음으로 넘어간다.

2단계는 합집합-찾기 자료 구조를 사용하여 수행할 수 있다. 각 고유 레이블을 별도의 집합으로 시작한다. 첫 번째 단계에서 기록된 모든 동등 관계에 대해 해당 집합을 합집합한다. 그 후, 남아있는 각 고유 집합은 이미지의 고유한 연결 성분과 연결된다.

3단계는 또 다른 후위 순회를 수행한다. 이번에는 각 검은색 노드 $v$에 대해 합집합-찾기의 find 연산( $v$의 이전 레이블과 함께)을 사용하여 $v$의 새 레이블을 찾고 할당한다( $v$가 속한 연결 성분과 연결된).

쿼드트리를 이용한 메시 생성

이 섹션은 하르-펠레드와 데 베르그 등의 책에서 발췌한 장을 요약한 것이다.

메시 생성은 본질적으로 추가 처리가 수행될 수 있는 점 집합의 삼각측량이다. 따라서 결과 삼각측량이 특정 속성(예: 비균일성, "너무 가늘지 않은" 삼각형, 희소 영역의 큰 삼각형, 밀집 영역의 작은 삼각형 등)을 갖는 것이 바람직하며, 이는 추가 처리를 더 빠르고 오류가 적게 만든다. 점 집합에 구축된 쿼드트리는 이러한 원하는 속성을 가진 메시를 생성하는 데 사용될 수 있다.

균형 잡힌 리프는 한 변에 최대 하나의 모서리를 갖는다.

쿼드트리의 리프와 해당 셀 $v$를 고려해 보자. 셀의 각 변이 인접 셀의 모서리 점에 의해 각 변에서 최대 한 번만 교차되면 $v$는 (메시 생성을 위해) 균형 잡혔다고 말한다. 이는 $v$에 인접한 리프의 쿼드트리 수준이 $v$의 수준과 최대 1만큼 차이 난다는 것을 의미한다. 모든 리프에 대해 이것이 참이면 전체 쿼드트리가 (메시 생성을 위해) 균형 잡혔다고 말한다.

셀 $v$와 $v$를 중심으로 하는 동일한 크기의 셀로 구성된 $5\times 5$ 이웃을 고려해 보자. 이 이웃을 확장 클러스터라고 부른다. 쿼드트리가 균형 잡혀 있고, 점 집합의 점을 포함하는 모든 리프 $u$에 대해 해당 확장 클러스터도 쿼드트리에 있으며 확장 클러스터에 점 집합의 다른 점이 포함되어 있지 않으면 쿼드트리는 잘 균형 잡혔다고 말한다.

메시 생성은 다음과 같이 수행된다.

1. 입력 점에 대해 쿼드트리를 구축한다.
2. 쿼드트리가 균형 잡혀 있는지 확인한다. 모든 리프에 대해 너무 큰 이웃이 있으면 해당 이웃을 세분화한다. 트리가 균형 잡힐 때까지 이 과정을 반복한다. 또한 점이 있는 리프의 경우 각 리프의 확장 클러스터에 대한 노드가 트리에 있는지 확인한다(필요에 따라 다시 균형을 맞춘다).
3. 점을 포함하는 모든 리프 노드 $v$에 대해, 확장 클러스터가 다른 점을 포함하면 트리를 추가로 세분화하고 필요에 따라 다시 균형을 맞춘다. 만약 세분화해야 했다면, $v$의 각 자식 $u$에 대해 $u$의 확장 클러스터 노드가 트리에 있는지 확인한다(필요에 따라 다시 균형을 맞춘다).
4. 트리가 잘 균형 잡힐 때까지 이전 단계를 반복한다.
5. 쿼드트리를 삼각측량으로 변환한다.

트리 셀의 모서리 점을 삼각측량의 정점으로 간주한다. 변환 단계 전에 우리는 일부에 점이 있는 상자들을 가지고 있다. 변환 단계는 다음 방식으로 수행된다. 각 점에 대해 셀의 가장 가까운 모서리를 점에 맞게 변형하고, 결과로 생성되는 네 개의 사각형을 "좋은" 삼각형으로 삼각측량한다(관심 있는 독자는 "좋은" 삼각형을 만드는 것에 대한 자세한 내용은 Har-Peled의 12장을 참조한다.).

남은 정사각형은 몇 가지 간단한 규칙에 따라 삼각측량된다. 각 정규 정사각형(내부에 점이 없고 변에 모서리 점이 없는)에 대해 대각선을 도입한다. 우리가 점들을 잘 균형 잡는 속성으로 분리하는 방식 때문에, 변을 교차하는 모서리를 가진 정사각형은 변형된 정사각형이 아니다. 따라서 교차하는 모서리를 가진 정사각형은 다음과 같이 삼각측량할 수 있다. 교차하는 변이 하나인 경우, 사각형은 교차점과 반대쪽 모서리를 연결하는 긴 대각선을 추가하여 세 개의 삼각형이 된다. 교차하는 변이 네 개인 경우, 네 교차점 중 두 개 사이에 모서리를 추가하여 사각형을 절반으로 분할한 다음, 이 두 끝점을 나머지 두 교차점에 연결한다. 다른 정사각형의 경우, 중앙에 점을 도입하고 사각형의 네 모서리와 각 교차점에 연결한다.

결국, 쿼드트리에서 구축된 점 집합의 잘 삼각측량된 메시를 얻게 된다.

의사 코드

다음 의사 코드는 점만 처리하는 쿼드트리를 구현하는 한 가지 방법을 보여준다. 다른 접근 방식도 사용할 수 있다.

선행 조건

이러한 구조가 사용된다고 가정한다.

 // 점과 벡터를 나타내는 간단한 좌표 객체
 struct XY
 {
     float x;
     float y;

     function __construct(float _x, float _y) {...}
 }

 // 반차원과 중심을 가진 축 정렬 경계 상자
 struct AABB
 {
     XY center;
     float halfDimension;

     function __construct(XY _center, float _halfDimension) {...}
     function containsPoint(XY point) {...}
     function intersectsAABB(AABB other) {...}
 }

QuadTree 클래스

이 클래스는 하나의 쿼드트리와 그것이 뿌리내린 노드를 모두 나타낸다.

 class QuadTree
 {
     // 이 쿼드트리 노드에 저장할 수 있는 요소의 수를 나타내는 임의의 상수
     constant int QT_NODE_CAPACITY = 4;

     // 이 쿼드트리의 경계를 나타내기 위해 반차원과 중심을 가진 축 정렬 경계 상자
     AABB boundary;

     // 이 쿼드트리 노드의 점들
     Array of XY [size = QT_NODE_CAPACITY] points;

     // 자식들
     QuadTree* northWest;
     QuadTree* northEast;
     QuadTree* southWest;
     QuadTree* southEast;

     // 메서드
     function __construct(AABB _boundary) {...}
     function insert(XY p) {...}
     function subdivide() {...} // 이 쿼드를 4개의 동일한 영역의 쿼드로 완전히 분할하는 4개의 자식을 생성한다.
     function queryRange(AABB range) {...}
 }

삽입

다음 메서드는 필요에 따라 분할하여 점을 쿼드트리의 적절한 쿼드에 삽입한다.

 class QuadTree
 {
     ...

     // 쿼드트리에 점 삽입
     function insert(XY p)
     {
         // 이 쿼드트리에 속하지 않는 객체 무시
         if (!boundary.containsPoint(p))
             return false; // 객체를 추가할 수 없음

         // 이 쿼드트리에 공간이 있고 세분화가 없다면 여기에 객체 추가
         if (points.size < QT_NODE_CAPACITY && northWest == null)
         {
             points.append(p);
             return true;
         }

         // 그렇지 않다면, 세분화한 다음 어떤 노드든 받아들일 점을 추가
         if (northWest == null)
             subdivide();
         // 마지막 노드만 데이터를 포함하기를 원한다면 이 쿼드 배열에 포함된 점/데이터를 새 쿼드에 추가해야 한다.

         if (northWest->insert(p)) return true;
         if (northEast->insert(p)) return true;
         if (southWest->insert(p)) return true;
         if (southEast->insert(p)) return true;

         // 그렇지 않다면, 알 수 없는 이유로 점을 삽입할 수 없다 (이런 일은 절대 일어나서는 안 됨)
         return false;
     }
 }

범위 쿼리

다음 메서드는 범위 내에 포함된 모든 점을 찾는다.

 class QuadTree
 {
     ...

     // 범위 내에 나타나는 모든 점 찾기
     function queryRange(AABB range)
     {
         // 결과 배열 준비
         Array of XY pointsInRange;

         // 범위가 이 쿼드와 교차하지 않으면 자동으로 중단
         if (!boundary.intersectsAABB(range))
             return pointsInRange; // 빈 목록

         // 이 쿼드 레벨에서 객체 확인
         for (int p = 0; p < points.size; p++)
         {
             if (range.containsPoint(points[p]))
                 pointsInRange.append(points[p]);
         }

         // 자식이 없으면 여기서 종료
         if (northWest == null)
             return pointsInRange;

         // 그렇지 않으면 자식의 점들을 추가
         pointsInRange.appendArray(northWest->queryRange(range));
         pointsInRange.appendArray(northEast->queryRange(range));
         pointsInRange.appendArray(southWest->queryRange(range));
         pointsInRange.appendArray(southEast->queryRange(range));

         return pointsInRange;
     }
 }

같이 보기

• 적응형 메시 세분화
• 이진 공간 분할법
• 이진 타일링
• K-d 트리
• 팔진트리
• R-트리
• UB-트리
• 공간 데이터베이스
• 서브페이빙
• Z-차순 곡선

각주

Aluru와 Samet의 조사는 쿼드트리에 대한 좋은 개요를 제공한다.

일반 참조

1. 라파엘 핀켈과 J.L. 벤틀리 (1974). 《Quad Trees: A Data Structure for Retrieval on Composite Keys》. 《Acta Informatica》 4. 1–9쪽. doi:10.1007/BF00288933. S2CID 33019699. 
2. 마크 데 베르그, 마크 반 크레벨트, 마르크 오버르마르스, 오트프리드 슈바르츠코프 (2000). 《Computational Geometry》 2 revis판. 스프링거-페를라크. ISBN 3-540-65620-0.  CS1 관리 - 여러 이름 (링크) Chapter 14: Quadtrees: pp. 291–306.
3. Samet, Hanan; Webber, Robert (July 1985). “Storing a Collection of Polygons Using Quadtrees” (PDF). 2012년 6월 17일에 원본 문서 (PDF)에서 보존된 문서. 2012년 3월 23일에 확인함.