쿼드 트리

점 데이터가 있는 점 영역 쿼드 트리입니다.버킷 용량 1

이미지의 단계별 쿼드 트리 압축.왼쪽은 트리 경계 상자와 함께 압축된 이미지를 나타내고 오른쪽은 압축된 이미지만 표시합니다.

쿼드 트리는 각 내부 노드에 정확히 4개의 하위 노드가 있는 트리 데이터 구조입니다.4분할은 8분할의 2차원 유사체로 2차원 공간을 4분할 또는 영역으로 재귀적으로 분할하여 분할하는 데 가장 많이 사용됩니다.잎 세포와 관련된 데이터는 용도에 따라 다르지만 잎 세포는 "흥미로운 공간 정보 단위"를 나타낸다.

분할된 영역은 정사각형 또는 직사각형일 수도 있고 임의 모양을 가질 수도 있습니다.이 데이터 구조는 1974년 ^[1]라파엘 핑켈과 J.L. 벤틀리에 의해 쿼드 트리라고 명명되었습니다.유사한 파티셔닝은 Q 트리라고도 합니다.모든 형태의 쿼드리는 몇 가지 공통적인 기능을 가지고 있습니다.

그들은 공간을 적응 가능한 세포로 분해한다.
각 셀(또는 버킷)에는 최대 용량이 있습니다.최대 용량에 도달하면 버킷이 분할됩니다.
트리 디렉토리는 쿼드트리의 공간적 분해를 따릅니다.

트리 피라미드(T-pyramid)는 "완전한" 트리입니다. T-피라미드의 모든 노드는 리프 노드를 제외한 4개의 하위 노드를 가집니다. 모든 잎은 이미지 내의 개별 픽셀에 해당하는 동일한 레벨에 있습니다.트리 피라미드의 데이터는 완전한 이진 트리를 어레이에 ^[2]콤팩트하게 저장하는 방법과 유사한 암묵적인 데이터 구조로서 어레이에 콤팩트하게 저장할 수 있습니다.

종류들

사각형 트리는 영역, 점, 선 및 곡선을 포함하여 나타내는 데이터 유형에 따라 분류할 수 있습니다.4각 트리는 트리 모양이 데이터가 처리되는 순서와 무관한지 여부에 따라 분류될 수도 있습니다.다음은 일반적인 쿼드트리 유형입니다.

지역 쿼드트리

영역 쿼드 트리는 영역을 4개의 동일한 사분원, 하위 사분원 등으로 분해하여 2차원 공간의 파티션을 나타냅니다.각 리프 노드는 특정 서브 영역에 대응하는 데이터를 포함합니다.트리의 각 노드에는 정확히 4개의 하위 노드가 있거나 하위 노드(리프 노드)가 없습니다.이 분해 전략을 따르는 사분목의 높이(즉, 더 정교함이 필요한 서브사분원에 흥미로운 데이터가 있는 한 서브사분할)는 분해되는 공간의 관심 영역의 공간 분포에 민감하고 이에 따라 달라진다.지역 쿼드 트리는 트라이의 일종입니다.

깊이 n의 영역 쿼드 트리를 사용하여 2 × 2ⁿ 화소로 이루어진ⁿ 화상을 나타낼 수 있으며, 여기서 각 화소 값은 0 또는 1이다.루트 노드는 이미지 영역 전체를 나타냅니다.영역의 픽셀이 완전히 0 또는 1이 아닌 경우 분할됩니다.이 응용 프로그램에서 각 리프 노드는 모두 0 또는 모두 1인 픽셀 블록을 나타냅니다.이러한 트리를 이미지 저장에 사용할 경우 공간 측면에서 절약될 수 있다는 점에 유의하십시오. 이미지에는 많은 경우 전체적으로 동일한 색 값을 갖는 상당한 크기의 영역이 있습니다.쿼드 트리는 이미지 내의 모든 픽셀의 큰 2D 어레이를 저장하는 것이 아니라 픽셀 해상도 크기의 셀보다 더 높은 분할 수준일 수 있는 동일한 정보를 캡처할 수 있습니다.트리 해상도와 전체 크기는 픽셀 및 이미지 크기에 따라 제한됩니다.

영역 쿼드 트리는 데이터 필드의 가변 분해능 표현으로도 사용할 수 있다.예를 들어, 각 리프 노드는 자신이 나타내는 서브 영역의 평균 온도를 저장하는 쿼드 트리로 저장할 수 있습니다.

지역 쿼드 트리가 점 데이터 집합(예: 도시 집합의 위도 및 경도)을 나타내는 데 사용되는 경우 각 잎에 최대 단일 점이 포함될 때까지 영역이 세분됩니다.

포인트 쿼드트리

점^[3] 쿼드 트리는 2차원 점 데이터를 나타내는 데 사용되는 이진 트리를 개조한 것입니다.모든 사분면 트리의 특징을 공유하지만 하위 분할의 중심이 항상 한 점에 있기 때문에 진정한 트리입니다.보통 O(log n) 시간으로 동작하는 2차원 순서 데이터 포인트를 비교하는 데 매우 효율적입니다.점 사분목은 완전성에 대해 언급할 가치가 있지만, 일반화된 이진 검색을 ^[4]위한 도구로서 k-d 트리에 의해 능가되고 있다.

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

평면 분할은 점 삽입 순서에 따라 결정되므로 트리의 높이는 삽입 순서에 따라 달라집니다."잘못된" 순서로 삽입하면 입력 포인트 수에서 높이의 트리가 선형으로 표시될 수 있습니다(이 트리는 링크 리스트가 됩니다).점 세트가 정적인 경우 전처리를 수행하여 균형 잡힌 높이의 트리를 작성할 수 있습니다.

점 쿼드트리의 노드 구조

포인트 쿼드트리의 노드는 바이너리 트리의 노드와 유사하며, 주요 차이점은 일반적인 바이너리 트리에서와 같이 2개의 포인터("왼쪽"과 "오른쪽") 대신 4개의 포인터(각 사분면에 1개)를 가지고 있다는 것입니다.또한 키는 보통 x좌표와 y좌표를 참조하여 두 부분으로 분해됩니다.따라서 노드에는 다음 정보가 포함됩니다.

4 포인터: quad[']NW', 쿼드[']NE', 쿼드[']SW'), 쿼드[']SE’]
포인트:
- 키: 보통 x, y 좌표로 표현됩니다.
- 값(이름 등)

포인트 영역(PR) 쿼드트리

포인트 영역(PR) 쿼드리는^[5]^[6] 영역 쿼드리와 매우 유사합니다.차이점은 셀에 대해 저장된 정보의 유형입니다.영역 쿼드트리에는 리프 셀 영역 전체에 적용되는 균일한 값이 기억된다.그러나 PR 쿼드트리의 셀에는 리프 셀 내에 존재하는 점 목록이 저장됩니다.앞서 언급했듯이, 이 분해 전략을 따르는 나무의 경우 높이는 점의 공간 분포에 따라 달라진다.포인트 쿼드 트리와 마찬가지로 PR 쿼드 트리도 "불량" 세트가 지정되면 선형 높이를 가질 수 있습니다.

엣지 쿼드트리

모서리 사분목^[7]^[8](PM 사분목과 거의 유사)은 점이 아닌 선을 저장하는 데 사용됩니다.곡선은 셀을 매우 미세한 분해능으로 세분함으로써 근사치를 구합니다. 특히 셀당 단일 선분이 있을 때까지 그러합니다.모서리/수직 근처에서 가장자리 사분원 트리는 최대 분해 수준에 도달할 때까지 계속 분할됩니다.이로 인해 극도로 불균형한 트리가 발생하여 인덱싱의 목적을 저하시킬 수 있습니다.

폴리곤 맵(PM) 쿼드트리

폴리곤 맵 쿼드트리(또는 PM 쿼드트리)는 퇴화(분리된 정점 또는 ^[9]가장자리가 있음을 의미)되는 폴리곤 집합을 저장하는 데 사용되는 쿼드트리의 변형입니다.^[10] PM 쿼드리와 가장자리 쿼드리의 큰 차이점은 셀의 정점에서 세그먼트가 만나는 경우 고려 중인 셀이 세분되지 않는다는 것입니다.

PM 쿼드트리에는 크게 세 가지 클래스가 있으며 각 검은색 노드에 저장되는 정보에 따라 달라집니다.PM3 쿼드리는 교차하지 않는 에지의 양, 최대 한 점을 저장할 수 있습니다.PM2 쿼드리는 모든 가장자리가 동일한 엔드 포인트를 공유해야 한다는 점을 제외하고 PM3 쿼드리와 동일합니다.마지막으로 PM1 쿼드리는 PM2와 비슷하지만 검은색 노드는 점과 그 가장자리 또는 점을 공유하는 가장자리 세트를 포함할 수 있지만 점을 포함하지 않는 점과 가장자리 세트를 가질 수 없습니다.

압축된 사분할

이 섹션은 Sariel Har-Peled의 ^[11]책의 하위 섹션을 요약합니다.

분할된 셀에 대응하는 모든 노드를 저장하면 빈 노드가 많이 저장될 수 있습니다.잎에 흥미로운 데이터가 있는 하위 트리(예: "중요 하위 트리")만 저장하면 이러한 희박한 나무의 크기를 줄일 수 있습니다.실제로 크기를 더 줄일 수 있습니다.중요한 서브트리만 보관하고 있는 경우, 플루닝 프로세스로 인해 중간 노드의 레벨이2(1개의 부모 및1개의 자녀에 대한 링크)가 있는 트리에 긴 패스가 남을 수 있습니다.이 경로의 선두에 $노드$ u({ $displaystyle$ u $u$ })를 저장하고(및 삭제된 노드를 나타내기 위해 메타데이터와 관련지어) 그 끝에 있는 서브트리를u({ $displaystyle$ u $u$ 에 연결하기만 하면 됩니다.이러한 압축 트리는 "불량" 입력 포인트에서 선형 높이를 가질 수 있습니다.ts를 클릭합니다.

이 압축을 수행할 때 트리를 많이 잘라내지만 Z 순서 곡선을 이용하여 로그 시간 검색, 삽입 및 삭제를 수행할 수 있습니다.Z순서 곡선은 풀 쿼드트리(및 압축 쿼드트리)의 각 셀을 $O(1)$ O( $)(\displaystyle$ O( $1))$ 시간으로 $O(1)$ 1차원 라인에 매핑하고(또한 $O(1)$ O(1 $)(\displaystyle$ O( $1))$ $O(1)$ 으로 $O(1)$ $O(1)$ 요소에 대한 전체 순서를 작성합니다.따라서 쿼드 트리를 순서 있는 세트(트리의 노드를 저장)의 데이터 구조에 저장할 수 있습니다.

계속 진행하기 전에 합리적인 가정을 설명해야 합니다. 2개의 $\alpha ,\beta \in [0,1)$ β $\alpha ,\beta \in [0,1)$ δ [ $\alpha ,\beta \in [0,1)$ 0 , $\alpha ,\beta \in [0,1)$ $O(1)$ ] { $displaystyle$ \alpha $,$ $\beta \in$ [ $0$ , 1 } 이 $\alpha ,\beta \in [0,1)$ 2진수로 표현되면 O $O(1)$ ( $O(1)$ ) $O(1)$ { $displaystyle$ O( $1)}$ 시간 $O(1)$ $O(1)$ 로 계산될 수 있다고 가정합니다.또한 쿼드트리 내 2개의 포인트/셀의 $가장$ 낮은 공통 조상을 $O(1)$ O( $1$ $)$ $시간$ 으로 $O(1)$ 계산하여 상대적인 Z순서를 확립하고 O(1) $시간$ $O(1)$ 에 플로어 함수를 계산할 수 있다고 가정합니다 $.$

이러한 전제조건에서는 소정의 $포인트$ q{ $displaystyle$ q}( $q$ $즉,$ q{ $displaystyle$ q} $q$ 를 $O(\log {n})$ 포함하는 셀 결정), 삽입 및 삭제 조작은 $O(\log {n})$ O $($ n $) 시간($ 즉, 순서부 dat에서 검색을 수행하는 데 걸리는 시간) 내에 $O(\log {n})$ 할 수 있습니다.구조물)

q $\displaystyle$ q의 $q$ 점 $위치$ (압축 트리에서 셀 찾기)를 수행하려면:

Z 순서로 q $\displaystyle$ q보다 앞에 $q$ $있는$ 압축 트리에서 기존 셀을 찾습니다.이 $v$ 을 v $\displaystyle$ v라고 부릅니다.
q $q\in v$ v \ $displaystyle$ q \ $in$ v \ $displaystyle$ v를 $v$
그렇지 않으면 비압축 쿼드 트리에서 $q$ (\ $displaystyle$ q)와 $q$ 셀 $v$ (\ $displaystyle$ v $)$ 의 $v$ 가장 낮은 공통 조상을 찾습니다. $이것$ 을 조상 $u$ 라고 부릅니다 $u$
$Z$ 순서로 사용자앞에 $u$ $있는$ 압축 트리에서 기존 셀을 찾아 반환합니다.

자세한 내용을 설명하지 않고 삽입 및 삭제를 수행하기 위해 먼저 삽입/삭제할 항목의 포인트 위치를 지정한 후 삽입/삭제합니다.필요에 따라 노드를 생성 및 제거하면서 트리를 적절히 재구성할 수 있도록 주의해야 합니다.

쿼드 트리의 일반적인 사용

이미지 표현
이미지 처리
메쉬 생성
공간 인덱싱, 점 위치 쿼리 및 범위 쿼리
2차원에서의 효율적인 충돌 검출
지형 데이터의 답답한 도태 보기
스프레드시트^[12] 또는 일부 매트릭스^{[citation needed]} 계산에 대한 형식 정보 등 희박한 데이터 저장
다차원장해법(컴퓨터 유체역학, 전자기학)
Conway의 Game of ^[13]Life 시뮬레이션 프로그램입니다.
상태 추정^[14]
4중 트리는 프랙탈 이미지 분석 영역에도 사용됩니다.
최대 분리 집합

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

쿼드트리, 특히 지역 쿼드트리는 이미지 처리 애플리케이션에 적합합니다.여기서 설명하는 것은 바이너리 이미지 데이터로 한정합니다만, 영역 4 트리 및 이 4 트리에서의 화상 처리 조작은 컬러 ^[4]^[15]이미지에 적합합니다.

이미지 결합/교차

이미지 조작에 쿼드리를 사용하는 것의 장점 중 하나는 조합과 교차점의 설정 조작을 간단하고 ^[4]^[16]^[17]^[18]빠르게 할 수 있다는 것입니다.^[19] 2개의 바이너리 화상이 주어졌을 때, 입력 화상 중 하나가 같은 위치에 검은 픽셀을 가지는 경우, 화상 연합(오버레이라고도 불린다)은 픽셀이 검은 이미지를 생성합니다.즉, 출력 이미지의 픽셀은 두 입력 이미지의 해당 픽셀이 흰색일 때만 흰색이고, 그렇지 않을 경우 출력 픽셀은 검은색입니다.픽셀 단위로 조작하는 것이 아니라 쿼드 트리의 기능을 활용하여 단일 노드에서 여러 픽셀을 표현하는 것으로 결합을 보다 효율적으로 계산할 수 있습니다.아래 설명의 목적상, 서브트리에 흑백의 픽셀이 모두 포함되어 있는 경우는, 그 서브트리의 루트는 회색입니다.

이 알고리즘은 출력 $쿼드트리$ T $(\$ $displaystyle$ T $T$ 를 구축하면서 2개의 입력 쿼드트리( $T_{2}$ \ $displaystyle T_$ $T_{2}$ $T2\displaystyle T_$ 2})를 통과하는 것으로 동작합니다.비공식적으로 알고리즘은 다음과 같습니다.이미지 내의 같은 영역에 대응하는 $v_{1}\in T_{1}$ 1 $v_{1}\in T_{1}$ $v_{1}\in T_{1}$ 1 \ $displaystyle v$ _ { $1$ \ $in$ T _ { $1$ } $v_{2}\in T_{2}$ v $v_{2}\in T_{2}$ 2 \ $display$ v _ { 2 \ in $T$ _ { $2$ v v v노드 v1 \ display tyle $v_$ { $2$ \ { $v_{2}\in T_{2}$ 2 }로 $v_{2}\in T_{2}$ 간주합니다.

$v_{1}$ 1 $({$ $v_{2}$ $v_{2}$ 2({ $displaystyle v_{2})$ 가 $v_{2}$ 검은색이면 $v_{1}$ 노드가 T $({displaystyle$ T $})$ 로 $T$ 생성되어 검은색으로 표시됩니다.둘 중 하나만 검은색이고 다른 하나는 회색인 경우 회색 노드는 아래에 하위 트리를 포함합니다.이 서브트리는 통과할 필요가 없습니다.
$($ $v_{2}$ { $displaystyle v_{1$ $})$ 이 $v_{2}$ 이면 $($ $각각$ $v_{1}$ { $displaystyle$ $v_{2$ 와 그 아래의 서브트리(존재하는 경우)가T {{ $displaystyle$ T $}$ 에 복사됩니다.
$({$ 과 $v_{1}$ $({$ 가 $v_{2}$ 모두 회색일 경우 $v_{1}$ ({ $displaystyle v_1})$ 과 $v_{1}$ $v_{2}$ v2({ $displaystyle$ v_ ${2$ }})의 $v_{2}$ $v_{1}$ 하는 자녀가 고려됩니다.

이 알고리즘은 동작하지만 그 자체로는 최소 크기의 쿼드트리를 보증하지 않습니다.예를 들어 크기가 $2^{k}\times 2^{k}$ × $(\$ 2 $^{k}\times$ 2 $^{k})$ 인 $2^{k}\times 2^{k}$ 체커보드(각 타일이 픽셀)를 그 보완체와 결합시킨 결과를 생각해 봅시다.그 결과 검은색의 거대한 정사각형이 됩니다.이 사각형은 루트 노드(검은색)만을 가진 쿼드 트리로 표현되어야 하지만 알고리즘에 $의해$ 깊이 k(\ $style$ k $k$ 의 완전한 4각형 트리가 생성됩니다.이를 수정하기 위해 결과 쿼드 트리의 상향 트래버스를 실행하여 4개의 자식 노드의 색상이 동일한지 여부를 확인합니다.같은 ^[4]색깔의 잎으로 부모를 대신할 수 있습니다

두 영상의 교차점은 거의 동일한 알고리즘입니다.두 이미지의 교차점에 대해 생각할 수 있는 한 가지 방법은 흰색 픽셀에 대해 합성을 하는 것입니다.이와 같이 교차를 수행하기 위해 합집합 알고리즘에서 검은색과 흰색의 언급을 바꿉니다.

연결된 컴포넌트 라벨

바이너리 이미지에서 두 개의 인접한 검은색 픽셀을 고려합니다.경계 수평 또는 수직 가장자리를 공유하는 경우 인접해 있습니다.일반적으로 인접한 화소로만 이동함으로써 한쪽이 다른 쪽으로부터 도달할 수 있는 경우에는 2개의 검은 화소가 접속된다(즉, 각각의 연속된 쌍이 인접한 곳에 검은 화소의 경로가 있다).연결된 검은색 픽셀의 최대 집합은 연결된 구성 요소입니다.이미지의^[20] 쿼드트리 표현을 사용하여 Samet은 쿼드트리 ^[4]^[21]크기에 비례하여 이들 연결된 컴포넌트를 시간 내에 찾아 라벨을 붙이는 방법을 보여 주었습니다.이 알고리즘은 폴리곤 컬러링에도 사용할 수 있습니다.

알고리즘은 다음 3단계로 동작합니다.

흑색 픽셀간의 인접 관계를 확립하다
첫 번째 단계부터 동등성 관계를 처리하여 연결된 각 구성요소에 대해 하나의 고유한 레이블을 얻습니다.
연결된 구성요소와 연관된 레이블로 검은색 픽셀 레이블 지정

설명을 간단히 하기 위해 쿼드 트리 내 노드의 자녀가 Z 순서(SW, NW, SE, NE)를 따른다고 가정합니다.이 구조에 의존할 수 있기 때문에 쿼드 트리를 탐색하여 계층의 다른 레벨에 있는 인접 셀을 찾는 방법을 알고 있습니다.

스텝 1은 쿼드트리의 사후 트래버스에 의해 실행됩니다.각 검은 $잎$ v $\displaystyle$ v $\$ displaystyle $v$ v\displaystyle v $\$ displaystyle v\displaystyle v $\$ displaystyle의 가장자리를 공유하는 $북쪽$ 및 $동쪽$ 셀을 $나타내는$ 노드를 살펴봅니다.나무는 Z순으로 구성되어 있기 때문에, 우리는 남부와 서부의 이웃들이 이미 돌보고 설명해온 불변성을 가지고 있습니다.현재 고려 중인 북쪽 또는 동쪽 $u$ 을u $displaystyle$ 로 합니다. 만약 $u\displaystyle$ u가 $u$ 검은색 픽셀을 $나타낸다면$ :

사용자 $(\displaystyle$ u) $v$ v $(\displaystyle$ v $)$ 중 $v$ $u$ 에 라벨이 있는 경우 해당 라벨을 다른 셀에 할당합니다.
둘 다 라벨이 없는 경우 라벨을 생성하여 둘 다에 할당합니다.
$사용자(\displaystyle$ u)와 $u$ v $(\displaystyle$ v $)$ 의 $v$ 라벨이 다를 $경우$ 이 라벨의 동등성을 기록하고 다음으로 넘어갑니다.

스텝 2는 union-find 데이터 ^[22]구조를 사용하여 실행할 수 있습니다.우선 각각의 고유 라벨부터 개별 세트로 합니다.첫 번째 단계에서 언급된 모든 동등성 관계에 대해, 우리는 대응하는 집합을 결합한다.그런 다음 나머지 각 세트는 이미지에서 서로 다른 연결된 구성 요소와 연결됩니다.

순서 3에서는, 다른 순서 후의 트래버설을 실행합니다.이번에는 검은색 $노드$ v {\ $displaystyle$ v $}$ 마다 $v$ Union-find의 찾기작업( $이전$ $레이블$ v {\ $displaystyle$ v $v$ 을 사용하여v {\ $displaystyle$ v $}$ 에 $v$ 새 레이블( $v$ {\ $displaystyle$ v $v$ }이 $v$ 된 연결된 구성 요소와 관련됨)을 찾아 할당합니다.

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

이 섹션은 Har-Peled와 de Berg ^[23]^[24]등의 책의 한 장을 요약한다.

메시 생성은 기본적으로 추가 처리를 수행할 수 있는 점 세트의 삼각 측량입니다.따라서 결과 삼각측량은 더 빠르고 오류 발생률이 낮은 특정 특성(비균일성, 너무 얇지 않은 삼각형, 희박한 영역의 큰 삼각형, 고밀도 영역의 작은 삼각형 등)을 갖는 것이 바람직하다.점 세트에 작성된 사분면 트리를 사용하여 이러한 원하는 특성과의 메시를 작성할 수 있습니다.

균형 잡힌 잎은 한 변에 많아야 한 귀퉁이가 있다.

쿼드트리의 리프 및 $v$ 하는 셀 v $\displaystyle$ v $v$ 셀의 양쪽에 인접한 셀의 코너 포인트가 1개씩 교차하는 경우 v $\displaystyle$ v는 $v$ (메쉬 생성용) 밸런스라고 $합니다$ .즉, v ${displaystyle$ v $}$ 에 $v$ $v$ 한 잎의 쿼드트리 레벨은v{ $displaystyle$ v $v$ 의 레벨과 최대 1개 차이가 납니다.이것이 모든 잎에 해당되면 쿼드트리 전체가 (메쉬 생성을 위해) 균형을 이루고 있다고 합니다.

$셀$ v(\ $displaystyle$ v $)$ 와 $v$ v $(\displaystyle$ v $v$ 를 중심으로 하는 $5\times 5$ 크기의 셀의 5 $(\displaystyle$ 5 $\times$ 5) 근방을 $5\times 5$ 확장 클러스터라고 부릅니다.쿼드 트리가 균형 잡힌 경우 쿼드 트리는 균형 잡힌 상태이며, 포인트 세트를 포함하는 모든 $리프$ u(\ $displaystyle$ u)에 $u$ 대해 확장 클러스터도 쿼드 트리에 포함되며 확장 클러스터에는 포인트 세트의 다른 포인트가 포함되지 않습니다.

메쉬의 작성은 다음과 같이 이루어집니다.

입력점에 쿼드 트리를 만듭니다.
Diagnostree의 밸런스를 확인합니다.잎마다 너무 큰 이웃이 있으면 이웃을 세분화한다.트리가 균형을 잡을 때까지 이 과정을 반복합니다.또한 포인트가 있는 리프에서는 각 리프 확장 클러스터의 노드가 트리에 있는지 확인합니다.
점을 포함하는 리프 $노드$ v {\ $displaystyle$ v $}$ 마다 $v$ 확장 클러스터가 다른 점을 포함하는 경우 트리를 더욱 세분화하고 필요에 따라 재조정합니다.세분화가 필요한 경우v의각 $하위$ $u$ 에 대해 $u$ $u$ 의 $u$ 확장 클러스터 $u$ 가 트리에 있는지 확인합니다(필요에 따라 재조정).
트리의 균형이 잘 잡힐 때까지 이전 단계를 반복합니다.
쿼드 트리를 삼각형으로 변환합니다.

트리 셀의 모서리 점을 삼각측량에서 꼭지점으로 간주합니다.변환 단계를 시작하기 전에 몇 개의 포인트가 들어 있는 여러 개의 상자가 있습니다.변환 단계는 다음과 같은 방법으로 수행됩니다. 각 점에 대해 셀의 가장 가까운 모서리를 접고 결과 4개의 사각형을 삼각 측량하여 "나이스" 삼각형을 만듭니다(관심 있는 독자는 "나이스" 삼각형을 만드는 것에 대한 자세한 내용은 Har-Peled의^[23] 12장을 참조하십시오).

나머지 정사각형은 몇 가지 간단한 규칙에 따라 삼각형으로 나뉩니다.각 일반 정사각형(내부 및 변에 점이 없음)에 대해 대각선을 도입합니다.균형 잡힌 특성으로 점을 분리한 방법 때문에 변과 교차하는 모서리가 있는 정사각형은 뒤틀린 것이 아닙니다.이와 같이 교차하는 모서리가 있는 정사각형을 다음과 같이 삼각 측량할 수 있습니다.교차하는 변이 하나 있는 경우 교차점과 반대쪽 모서리를 연결하는 긴 대각선을 더하면 정사각형은 세 개의 삼각형이 됩니다.교차하는 변이 4개인 경우 4개의 교차점 중 2개의 교차점 사이에 모서리를 추가하여 정사각형을 반으로 나눈 다음 이 두 개의 끝점을 나머지 2개의 교차점에 연결합니다.다른 사각형의 경우 가운데 점을 도입하여 각 교차점뿐만 아니라 사각형의 네 모서리 모두에 연결합니다.

마지막에는 쿼드 트리로 만든 멋진 삼각형 메쉬 포인트 세트가 있습니다.

유사 코드

다음 의사 코드는 포인트만 처리하는 쿼드트리를 구현하는 방법을 보여 줍니다.다른 접근방식을 사용할 수 있습니다.

전제 조건

이러한 구조물이 사용되는 것으로 가정한다.

// 점 및 벡터 구조 XY {float x; float y; function __construct(float _x, float _y) {...} // 반차원 및 중심 구조 AABB { XY 중심; float halfDimension; function __construct(XY 중심, float halfloat half dimension) {i} 컨텐션}을 나타내는 단순 좌표 객체nsPoint(XY 포인트) {...} 함수가 교차합니다.AABB(AABB 기타) {...} }

쿼드 트리 클래스

이 클래스는 1개의 쿼드 트리와 그 루트가 되는 노드를 모두 나타냅니다.

클래스 QuadTree {// 이 쿼드 트리 노드 상수 QT_NODE_CAPACITY = 4; // 이 쿼드 트리 AABB 경계의 경계를 나타내는 축 정렬 경계 상자에 저장할 수 있는 요소 수를 나타내는 임의 상수입니다. // 이 쿼드 트리 노드 배열의 XY [size_Q_node]의 점APACH] 포인트, // 하위 QuadTree* 노스웨스트, QuadTree* 노스이스트, QuadTree* 사우스웨스트, QuadTree* 사우스웨스트, // 메서드 함수 __constructure(AAB_boundary) {...} 함수 삽입(XY p) {...} 함수 서브사이드({...}) {...} // 4개의 하위 쿼드로 완전히 분할되는 4개의 하위 함수가 생성됩니다.nge(AAABB 범위) {...} }

삽입

다음 방법에서는 쿼드트리의 적절한 쿼드에 포인트를 삽입하고 필요에 따라 분할합니다.

클래스 QuadTree { ... // QuadTree 함수 삽입(XY p) {// (!boundary.containsPoint(p)가 false를 반환하면 이 쿼드 트리에 속하지 않는 개체 무시, // 개체를 추가할 수 없음 // 이 쿼드 트리에 공간이 있고 분할이 없는 경우 여기에 개체를 추가합니다.E<>QT_NODE_CAPACITY&&,northWest== null){points.append(p)대가 진정한;}// 그렇지 않으면, subdivide을 추가해서 중요한 것은 중 노든다는 것을 받아들이면(northWest null==)subdivide(), //We다에 넣points/data 포함된로 이 쿼드 배열에 n.ew게 한다면만약(northEast->, 삽입(p)) 돌아오면 true(southEast->, 삽입(p))대가 진정한 우리는 오직;만약(southWest->, 삽입(p))대가 진정한; 그렇지 않으면 //은 알려지지 않은 이유(이것이 절대로 일어나지 않아야 한다)retu을 삽입할 수 없//the 마지막 노드 만약(northWest->, 삽입(p))반환한 데이터를 보관하고 싶다.rn 거짓.} }

쿼리 범위

다음 방법에서는 범위 내에 포함된 모든 점을 찾습니다.

클래스 QuadTree { ... // 범위 함수 queryRange(AABB 범위) {// 결과 배열 준비 XY 포인트 배열InRange;/ 범위가 이 쿼드와 교차하지 않으면 자동으로 중단됩니다(! 경계.교차).AABB(범위))대가 pointsInRange;만약(northWest null==)물에 담그다가 없으면 아이들(intp)0;p<, points.size, p++){만약(range.containsPoint(points[p]))pointsInRange.append(points[p]).}을 끓여 이 쿼드 수준에서 // 빈 목록//체크 개체,을 해지할 수 있다.항아리PointsInRange, // 그렇지 않으면, 그 아이들 pointsInRange.appendArray(northWest->, queryRange(범위)의 포인트를 더하면;pointsInRange.appendArray(northEast->, queryRange(범위). pointsInRange.appendArray(southWest->, queryRange(범위). pointsInRange.appendArray(southEast->, queryRange(범위)..    return pointsInRange; } }

「」를 참조해 주세요.

레퍼런스

Aluru와 Samet에^[21]^[15] 의한^[4] 조사는 4개의 트리의 좋은 개요를 제공합니다.

메모들

^ Finkel, R. A.; Bentley, J. L. (1974). "Quad trees a data structure for retrieval on composite keys". Acta Informatica. 4 (1): 1–9. doi:10.1007/BF00288933. S2CID 33019699. Retrieved 6 November 2019.
^ 밀란 송카, 바츨라프 할락, 로저 보일"이미지 처리, 분석 및 기계 비전", 2014. 페이지 108-109.
^ Finkel, R. A.; Bentley, J. L. (1974). "Quad Trees A Data Structure for Retrieval on Composite Keys". Acta Informatica. Springer-Verlag. 4: 1–9. doi:10.1007/bf00288933. S2CID 33019699.
^ ^a ^b ^c ^d ^e ^f Aluru, S. (2004). "Quadtrees and octrees". In D. Mehta and S. Sahni (ed.). Handbook of Data Structures and Applications. Chapman and Hall/CRC. pp. 19-1 -- 19-26. ISBN 9781584884354.
^ Orenstein, J. A. (1982). "Multidimensional tries used for associative searching". Information Processing Letters. Elsevier. 14 (4): 150–157. doi:10.1016/0020-0190(82)90027-8.
^ Samet, H. (1984). "The quadtree and related hierarchical data structures" (PDF). ACM Computing Surveys. ACM. 16 (2): 187–260. doi:10.1145/356924.356930. S2CID 10319214.
^ Warnock, J. E. (1969). "A hidden surface algorithm for computer generated halftone pictures". Computer Science Department, University of Utah. TR 4-15.
^ Schneier, M. (1981). "Two hierarchical linear feature representations: edge pyramids and edge quadtrees". Computer Graphics and Image Processing. Elsevier. 17 (3): 211–224. doi:10.1016/0146-664X(81)90002-2.
^ 해난 새밋과 로버트 웨버입니다"4각 트리를 사용한 폴리곤 컬렉션 저장"ACM 그래픽스 거래 1985년7월 : 182-222.InfoLAB.Web. 2012년 3월 23일
^ Nelson, R. C.; Samet, H. (1986). "A consistent hierarchical representation for vector data". ACM SIGGRAPH Computer Graphics. 20 (4): 197–206. doi:10.1145/15886.15908.
^ Har-Peled, S. (2011). "Quadtrees - Hierarchical Grids". Geometric approximation algorithms. Mathematical Surveys and Monographs Vol. 173, American mathematical society.
^ Sestoft, Peter (2014). Spreadsheet Implementation Technology: Basics and Extensions. The MIT Press. pp. 60–63. ISBN 9780262526647.
^ Tomas G. Rokicki (2006-04-01). "An Algorithm for Compressing Space and Time". Retrieved 2009-05-20.
^ 헤닝 에버하르트, 베사 클룸프, 유웨 DHanebeck, 효율적인 비선형 상태 추정을 위한 밀도 나무, 제13회 정보 융합 국제 회의 진행, 2010년 7월.
^ ^a ^b Samet, H. (1989). "Hierarchical spatial data structures". Symposium on Large Spatial Databases: 191–212.
^ Hunter, G. M. (1978). Efficient Computation and Data Structures for Graphics. Ph.D. dissertation, Department of Electrical Engineering and Computer Science, Princeton University.
^ Hunter, G. M.; Steiglitz, K. (1979). "Operations on images using quad trees". IEEE Transactions on Pattern Analysis and Machine Intelligence. 2 (2): 145–153. doi:10.1109/tpami.1979.4766900. PMID 21868843. S2CID 2544535.
^ Schneier, M. (1981). "Calculations of geometric properties using quadtrees". Computer Graphics and Image Processing. 16 (3): 296–302. doi:10.1016/0146-664X(81)90042-3.
^ Mehta, Dinesh (2007). Handbook of Data Structures and Applications. Chapman and Hall/CRC Press. p. 397.
^ Samet, H. (1981). "Connected component labeling using quadtrees". Journal of the ACM. 28 (3): 487–501. CiteSeerX 10.1.1.77.2573. doi:10.1145/322261.322267. S2CID 17485118.
^ ^a ^b Samet, H. (1988). "An overview of quadtrees, octrees, and related hierarchical data structures". In Earnshaw, R. A. (ed.). Theoretical Foundations of Computer Graphics and CAD. Springer-Verlag. pp. 51–68.
^ Tarjan, R. E. (1975). "Efficiency of a good but not linear set union algorithm" (PDF). Journal of the ACM. 22 (2): 215–225. doi:10.1145/321879.321884. hdl:1813/5942. S2CID 11105749.
^ ^a ^b Har-Peled, S. (2011). "Good Triangulations and Meshing". Geometric approximation algorithms. Mathematical Surveys and Monographs Vol. 173, American mathematical society.
^ de Berg, M.; Cheong, O.; van Kreveld, M.; Overmars, M. H. (2008). "Quadtrees Non-Uniform Mesh Generation". Computational Geometry Algorithms and Applications (3rd ed.). Springer-Verlag.

일반 참고 자료

Raphael Finkel and J.L. Bentley (1974). "Quad Trees: A Data Structure for Retrieval on Composite Keys". Acta Informatica. 4 (1): 1–9. doi:10.1007/BF00288933. S2CID 33019699.
Mark de Berg, Marc van Kreveld, Mark Overmars, and Otfried Schwarzkopf (2000). Computational Geometry (2nd revised ed.). Springer-Verlag. ISBN 3-540-65620-0.{{cite book}}: CS1 유지: 여러 이름: 작성자 목록(링크) 제14장: 쿼드 트리: 페이지 291–306.
Samet, Hanan; Webber, Robert (July 1985). "Storing a Collection of Polygons Using Quadtrees" (PDF). Retrieved 23 March 2012.

[1] Finkel, R. A.; Bentley, J. L. (1974). "Quad trees a data structure for retrieval on composite keys". Acta Informatica. 4 (1): 1–9. doi:10.1007/BF00288933. S2CID 33019699. Retrieved 6 November 2019.

[2] 밀란 송카, 바츨라프 할락, 로저 보일"이미지 처리, 분석 및 기계 비전", 2014. 페이지 108-109.

[3] Finkel, R. A.; Bentley, J. L. (1974). "Quad Trees A Data Structure for Retrieval on Composite Keys". Acta Informatica. Springer-Verlag. 4: 1–9. doi:10.1007/bf00288933. S2CID 33019699.

[Aluru2004-4] ^ ^a ^b ^c ^d ^e ^f Aluru, S. (2004). "Quadtrees and octrees". In D. Mehta and S. Sahni (ed.). Handbook of Data Structures and Applications. Chapman and Hall/CRC. pp. 19-1 -- 19-26. ISBN 9781584884354.

[5] Orenstein, J. A. (1982). "Multidimensional tries used for associative searching". Information Processing Letters. Elsevier. 14 (4): 150–157. doi:10.1016/0020-0190(82)90027-8.

[6] Samet, H. (1984). "The quadtree and related hierarchical data structures" (PDF). ACM Computing Surveys. ACM. 16 (2): 187–260. doi:10.1145/356924.356930. S2CID 10319214.

[7] Warnock, J. E. (1969). "A hidden surface algorithm for computer generated halftone pictures". Computer Science Department, University of Utah. TR 4-15.

[8] Schneier, M. (1981). "Two hierarchical linear feature representations: edge pyramids and edge quadtrees". Computer Graphics and Image Processing. Elsevier. 17 (3): 211–224. doi:10.1016/0146-664X(81)90002-2.

[9] 해난 새밋과 로버트 웨버입니다"4각 트리를 사용한 폴리곤 컬렉션 저장"ACM 그래픽스 거래 1985년7월 : 182-222.InfoLAB.Web. 2012년 3월 23일

[10] Nelson, R. C.; Samet, H. (1986). "A consistent hierarchical representation for vector data". ACM SIGGRAPH Computer Graphics. 20 (4): 197–206. doi:10.1145/15886.15908.

[11] Har-Peled, S. (2011). "Quadtrees - Hierarchical Grids". Geometric approximation algorithms. Mathematical Surveys and Monographs Vol. 173, American mathematical society.

[12] Sestoft, Peter (2014). Spreadsheet Implementation Technology: Basics and Extensions. The MIT Press. pp. 60–63. ISBN 9780262526647.

[13] Tomas G. Rokicki (2006-04-01). "An Algorithm for Compressing Space and Time". Retrieved 2009-05-20.

[14] 헤닝 에버하르트, 베사 클룸프, 유웨 DHanebeck, 효율적인 비선형 상태 추정을 위한 밀도 나무, 제13회 정보 융합 국제 회의 진행, 2010년 7월.

[:0-15] Samet, H. (1989). "Hierarchical spatial data structures". Symposium on Large Spatial Databases: 191–212.

[16] Hunter, G. M. (1978). Efficient Computation and Data Structures for Graphics. Ph.D. dissertation, Department of Electrical Engineering and Computer Science, Princeton University.

[17] Hunter, G. M.; Steiglitz, K. (1979). "Operations on images using quad trees". IEEE Transactions on Pattern Analysis and Machine Intelligence. 2 (2): 145–153. doi:10.1109/tpami.1979.4766900. PMID 21868843. S2CID 2544535.

[18] Schneier, M. (1981). "Calculations of geometric properties using quadtrees". Computer Graphics and Image Processing. 16 (3): 296–302. doi:10.1016/0146-664X(81)90042-3.

[19] Mehta, Dinesh (2007). Handbook of Data Structures and Applications. Chapman and Hall/CRC Press. p. 397.

[20] Samet, H. (1981). "Connected component labeling using quadtrees". Journal of the ACM. 28 (3): 487–501. CiteSeerX 10.1.1.77.2573. doi:10.1145/322261.322267. S2CID 17485118.

[:1-21] Samet, H. (1988). "An overview of quadtrees, octrees, and related hierarchical data structures". In Earnshaw, R. A. (ed.). Theoretical Foundations of Computer Graphics and CAD. Springer-Verlag. pp. 51–68.

[22] Tarjan, R. E. (1975). "Efficiency of a good but not linear set union algorithm" (PDF). Journal of the ACM. 22 (2): 215–225. doi:10.1145/321879.321884. hdl:1813/5942. S2CID 11105749.

[:2-23] Har-Peled, S. (2011). "Good Triangulations and Meshing". Geometric approximation algorithms. Mathematical Surveys and Monographs Vol. 173, American mathematical society.

[24] Berg, M.; Cheong, O.; van Kreveld, M.; Overmars, M. H. (2008). "Quadtrees Non-Uniform Mesh Generation". Computational Geometry Algorithms and Applications (3rd ed.). Springer-Verlag.

[1]

[2]

[3]

[4]

[5]

[6]

[7]

[8]

[9]

[10]

[11]

[12]

[13]

[14]

[15]

[16]

[17]

[18]

[19]

[20]

[21]

[22]

[23]

[24]

v t 트리 데이터 구조
트리 검색 (다이나믹 세트/어소시에이션 어레이)	2–3 2–3–4 AA (a, b) AVL B B+ B* B^x. (최적) 바이너리 검색 춤추다 HTree 간격 주문통계 (좌향) 레드-블랙 희생양 스플라이 T 나무 UB 무게 밸런스
수북이	바이너리 이항 브로달 피보나치 좌파 페어링 스큐 판 엠데 보아스 약한
시도하다	Ctrie C-trie(압축 ADT) 해시 기수 서픽스 삼진수 검색 X-Fast 고속
공간 데이터 파티션 트리	공 BK BSP 데카르트어 힐베르트 R k-d(표준 k-d) M 미터법 MVP 옥트리 PH 우선 순위 R 쿼드 R R+ R* 부분 부사장 X
기타 트리	덮다 지수 펜윅 손가락. 프랙탈 트리 인덱스 퓨전 해시 캘린더 i디스턴스 K-ary 좌측자녀 우측자매 링크/컷 로그 구조화 결합 머클 p q. 범위 SPQR 정상

Search

쿼드 트리

네임스페이스

더

목차

종류들

지역 쿼드트리

포인트 쿼드트리

점 쿼드트리의 노드 구조

포인트 영역(PR) 쿼드트리

엣지 쿼드트리

폴리곤 맵(PM) 쿼드트리

압축된 사분할

쿼드 트리의 일반적인 사용

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

이미지 결합/교차

연결된 컴포넌트 라벨

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

유사 코드

전제 조건

쿼드 트리 클래스

삽입

쿼리 범위

「」를 참조해 주세요.

레퍼런스

메모들

일반 참고 자료

Search

쿼드 트리

종류들

지역 쿼드트리

포인트 쿼드트리

점 쿼드트리의 노드 구조

포인트 영역(PR) 쿼드트리

엣지 쿼드트리

폴리곤 맵(PM) 쿼드트리

압축된 사분할

쿼드 트리의 일반적인 사용

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

이미지 결합/교차

연결된 컴포넌트 라벨

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

유사 코드

전제 조건

쿼드 트리 클래스

삽입

쿼리 범위

「 」를 참조해 주세요.

레퍼런스

메모들

일반 참고 자료

「」를 참조해 주세요.