쿼드트리

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

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

모든 형태의 쿼드트리는 몇 가지 공통적인 특징을 공유한다.
 공간을 적응 가능한 셀로 분해한다.
 각 셀(또는 버킷)은 최대 용량을 가진다. 최대 용량에 도달하면 버킷이 분할된다.
 트리 디렉터리는 쿼드트리의 공간 분해를 따른다.

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

유형
섬네일|2D 인덱스에 대한 재귀적 이진 공간 분할법 쿼드트리의 예시.
쿼드트리는 영역, 점, 선 및 곡선을 포함하여 나타내는 데이터 유형에 따라 분류될 수 있다. 쿼드트리는 또한 트리의 모양이 데이터 처리 순서에 독립적인지 여부에 따라 분류될 수도 있다. 다음은 쿼드트리의 일반적인 유형이다.

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

깊이가 n인 영역 쿼드트리는 2n × 2n 픽셀로 구성된 이미지를 나타내는 데 사용될 수 있으며, 각 픽셀 값은 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 쿼드트리)는 퇴화될 수 있는 (즉, 고립된 정점이나 가장자리를 가질 수 있는) 다각형 컬렉션을 저장하는 데 사용되는 쿼드트리의 변형이다.하난 사메트 and Robert Webber. "Storing a Collection of Polygons Using
Quadtrees". ACM Transactions on Graphics July 1985: 182-222. InfoLAB. Web. 23 March 2012
 PM 쿼드트리와 가장자리 쿼드트리 사이의 큰 차이점은 고려 중인 셀이 셀 내의 정점에서 세그먼트가 만나는 경우에도 세분화되지 않는다는 것이다.

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

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

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

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

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

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

에 대한 점 위치를 수행하려면(즉, 압축된 트리에서 해당 셀을 찾으려면):
 Z-순서에서 보다 먼저 오는 압축된 트리의 기존 셀을 찾는다. 이 셀을 라고 한다.
 만약 이면, 를 반환한다.
 그렇지 않으면, 압축되지 않은 쿼드트리에서 점 와 셀 의 최저 공통 조상이 되었을 셀을 찾는다. 이 조상 셀을 라고 한다.
 Z-순서에서 보다 먼저 오는 압축된 트리의 기존 셀을 찾아 반환한다.
구체적인 내용은 생략하고, 삽입 및 삭제를 수행하려면 먼저 삽입/삭제할 대상의 점 위치를 찾은 다음 삽입/삭제한다. 필요에 따라 노드를 생성하고 제거하면서 트리를 적절하게 재구성해야 한다.

쿼드트리의 일반적인 사용
섬네일|upright=1.7|비트맵과 압축된 쿼드트리 표현
 이미지 표현
 이미지 처리
 메시 생성
 공간 인덱스팅, 점 위치 쿼리, 범위 쿼리
 2차원에서의 효율적인 충돌 감지
 지형 데이터의 뷰 프러스텀 컬링
 스프레드시트의 서식 정보나 일부 행렬 계산을 위한 희소 데이터 저장
 다차원 장의 해법 (전산 유체 역학, 전자기학)
 라이프 게임 시뮬레이션 프로그램.
 상태 추정Henning Eberhardt, Vesa Klumpp, Uwe D. Hanebeck, Density Trees for Efficient Nonlinear State Estimation, Proceedings of the 13th International Conference on Information Fusion, Edinburgh, United Kingdom, July, 2010.
 쿼드트리는 프랙탈 이미지 분석 분야에서도 사용된다.
 최대 서로소 집합

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

이미지 합집합/교집합
이미지 조작에 쿼드트리를 사용하는 장점 중 하나는 합집합 및 교집합의 집합 연산을 간단하고 빠르게 수행할 수 있다는 것이다.

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

이 알고리즘은 두 입력 쿼드트리( 및 )를 순회하면서 출력 쿼드트리 를 구축하는 방식으로 작동한다. 비공식적으로 알고리즘은 다음과 같다. 이미지의 동일한 영역에 해당하는 노드  및 를 고려한다.
 만약  또는 가 검은색이면, 에 해당 노드가 생성되고 검은색으로 칠해진다. 만약 둘 중 하나만 검은색이고 다른 하나가 회색이면, 회색 노드 아래에 서브트리가 포함된다. 이 서브트리는 순회할 필요가 없다.
 만약  (각각 )가 흰색이면,  (각각 )와 그 아래의 서브트리(있는 경우)가 로 복사된다.
 만약 과  모두 회색이면, 과 의 해당 자식이 고려된다.

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

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

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

알고리즘은 세 단계로 작동한다.
 검은색 픽셀 간의 인접 관계를 설정한다.
 첫 번째 단계의 동등 관계를 처리하여 각 연결 성분에 대해 고유한 레이블을 얻는다.
 검은색 픽셀에 해당 연결 성분과 연결된 레이블을 지정한다.
논의를 단순화하기 위해 쿼드트리 노드의 자식이 Z-차순 (SW, NW, SE, NE)을 따른다고 가정하자. 이 구조를 믿을 수 있기 때문에, 어떤 셀에 대해서도 계층 구조의 다른 수준에서 인접한 셀을 찾기 위해 쿼드트리를 탐색하는 방법을 안다.

1단계는 쿼드트리의 후위 순회로 수행된다. 각 검은색 리프 에 대해 북쪽 이웃 및 동쪽 이웃(즉, 의 셀과 가장자리를 공유하는 북쪽 및 동쪽 셀)을 나타내는 노드를 살펴본다. 트리가 Z-순서로 구성되어 있으므로 남쪽 및 서쪽 이웃은 이미 처리되고 고려되었다는 불변성을 가진다. 현재 고려 중인 북쪽 또는 동쪽 이웃을 라고 하자. 만약 가 검은색 픽셀을 나타내면:
 만약  또는  중 하나만 레이블을 가지고 있다면, 그 레이블을 다른 셀에 할당한다.
 만약 둘 다 레이블을 가지고 있지 않다면, 하나를 생성하여 둘 다에 할당한다.
 만약 와 가 다른 레이블을 가지고 있다면, 이 레이블 동등성을 기록하고 다음으로 넘어간다.
2단계는 합집합-찾기 자료 구조를 사용하여 수행할 수 있다. 각 고유 레이블을 별도의 집합으로 시작한다. 첫 번째 단계에서 기록된 모든 동등 관계에 대해 해당 집합을 합집합한다. 그 후, 남아있는 각 고유 집합은 이미지의 고유한 연결 성분과 연결된다.

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

쿼드트리를 이용한 메시 생성
이 섹션은 하르-펠레드와 데 베르그 등의 책에서 발췌한 장을 요약한 것이다.

메시 생성은 본질적으로 추가 처리가 수행될 수 있는 점 집합의 삼각측량이다. 따라서 결과 삼각측량이 특정 속성(예: 비균일성, "너무 가늘지 않은" 삼각형, 희소 영역의 큰 삼각형, 밀집 영역의 작은 삼각형 등)을 갖는 것이 바람직하며, 이는 추가 처리를 더 빠르고 오류가 적게 만든다. 점 집합에 구축된 쿼드트리는 이러한 원하는 속성을 가진 메시를 생성하는 데 사용될 수 있다.
섬네일|균형 잡힌 리프는 한 변에 최대 하나의 모서리를 갖는다.
쿼드트리의 리프와 해당 셀 를 고려해 보자. 셀의 각 변이 인접 셀의 모서리 점에 의해 각 변에서 최대 한 번만 교차되면 는 (메시 생성을 위해) 균형 잡혔다고 말한다. 이는 에 인접한 리프의 쿼드트리 수준이 의 수준과 최대 1만큼 차이 난다는 것을 의미한다. 모든 리프에 대해 이것이 참이면 전체 쿼드트리가 (메시 생성을 위해) 균형 잡혔다고 말한다.

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

메시 생성은 다음과 같이 수행된다.
 입력 점에 대해 쿼드트리를 구축한다.
 쿼드트리가 균형 잡혀 있는지 확인한다. 모든 리프에 대해 너무 큰 이웃이 있으면 해당 이웃을 세분화한다. 트리가 균형 잡힐 때까지 이 과정을 반복한다. 또한 점이 있는 리프의 경우 각 리프의 확장 클러스터에 대한 노드가 트리에 있는지 확인한다(필요에 따라 다시 균형을 맞춘다).
 점을 포함하는 모든 리프 노드 에 대해, 확장 클러스터가 다른 점을 포함하면 트리를 추가로 세분화하고 필요에 따라 다시 균형을 맞춘다. 만약 세분화해야 했다면, 의 각 자식 에 대해 의 확장 클러스터 노드가 트리에 있는지 확인한다(필요에 따라 다시 균형을 맞춘다).
 트리가 잘 균형 잡힐 때까지 이전 단계를 반복한다.
 쿼드트리를 삼각측량으로 변환한다.
트리 셀의 모서리 점을 삼각측량의 정점으로 간주한다. 변환 단계 전에 우리는 일부에 점이 있는 상자들을 가지고 있다. 변환 단계는 다음 방식으로 수행된다. 각 점에 대해 셀의 가장 가까운 모서리를 점에 맞게 변형하고, 결과로 생성되는 네 개의 사각형을 "좋은" 삼각형으로 삼각측량한다(관심 있는 독자는 "좋은" 삼각형을 만드는 것에 대한 자세한 내용은 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의 조사는 쿼드트리에 대한 좋은 개요를 제공한다.

내용주

일반 참조

  Chapter 14: Quadtrees: pp. 291–306.


분류:기하 자료 구조
분류:트리 구조