압축된 쿼드트리
세분화된 셀에 해당하는 모든 노드를 저장할 때 빈 노드를 많이 저장하게 될 수 있습니다. 그러한 희소 트리의 크기를 줄이는 것은 잎에 흥미로운 데이터가 있는 하위 트리(즉, "중요 하위 트리")만 저장함으로써 가능합니다. 다시 실제로 크기를 훨씬 더 줄일 수 있습니다. 중요한 하위 트리만 고려할 때 가지치기 프로세스는 중간 노드가 차수가 2인 트리의 긴 경로(한 부모와 한 자식에 대한 링크)를 피할 수 있습니다. 우리는 이 경로의 시작 부분에 노드 U를 저장하고(삭제된 노드를 나타내기 위해 일부 메타 데이터를 연결하고) U에 끝 부분에 뿌리를 둔 하위 트리를 연결하기만 하면 됩니다. 이러한 압축 트리는 여전히 "잘못된" 입력 포인트가 주어졌을 때 선형 높이.
이 압축을 수행할 때 트리를 많이 잘라냈지만 Z-차수 곡선을 활용하여 대수 시간 삽입, 삭제 및 검색을 달성하는 것이 여전히 가능합니다. Z-차수 곡선은 O(1) 시간의 전체 쿼드트리(및 압축된 쿼드트리)의 각 셀을 1차원 선으로 변환하고(O(1) 시간에도 다시 변환) 전체 순서를 작성합니다. 요소에. 이제 우리는 정렬된 집합에 대한 데이터 구조에 쿼드트리를 저장할 수 있습니다(여기에 트리의 노드가 저장됨). 이제 계속하기 전에 합리적인 가정을 해야 합니다. 이진으로 표시된 두 개의 실수 α,β € [0,1]이 주어지면 O(1) 시간에 계산할 수 있다고 가정합니다. 다르다. 또한 쿼드트리에서 두 점/셀의 가장 작은 공통 조상을 O(1) 시간에 계산하고 상대적인 Z 순서를 설정할 수 있으며 O(1) 시간에 바닥 함수를 계산할 수 있다고 가정합니다. 이러한 가정으로 주어진 점 Q의 점 위치(즉, Q를 포함할 셀 찾기), 삭제 및 삽입 작업은 모두 O(n log n) 시간(즉, 검색을 수행하는 데 걸리는 시간) 내에 수행될 수 있습니다. 기본 순서 집합 데이터 구조).
Q에 대한 포인트 위치 수행(즉, 압축 트리에서 셀 결정)
- 기존 셀은 Z 순서에서 Q 앞에 오는 압축 트리에서 발견됩니다. 이 셀을 V라고 부르세요.
- Q€V가 수행되면 V를 반환합니다.
- 그렇지 않으면 압축되지 않은 쿼드트리에서 점 Q와 셀 V의 가장 작은 공통 조상이 무엇인지 찾으십시오. 이 조상 세포를 U라고 부르십시오.
- Z 순서에서 U 앞에 오는 압축 트리에서 기존 셀을 찾아 반환합니다.
구체적인 내용으로 들어가지 않고 삽입과 삭제를 하기 위해서는 먼저 삽입/삭제하고자 하는 항목에 대한 포인트 위치를 수행한 다음 삽입/삭제합니다. 트리 모양을 적절하게 변경하고 필요에 따라 노드를 만들고 삭제하도록 주의해야 합니다.
옥트리
옥트리는 각 내부 노드가 정확히 8개의 자식과 연결된 트리 데이터 구조로 정의됩니다.
옥트리는 3차원 공간을 8개의 옥탄트로 재귀적으로 세분화하여 분할하기 위해 가장 자주 구현됩니다.
옥트리는 쿼드트리의 3차원 아날로그로 취급됩니다. 이름은 oct + tree로 생성되지만 일반적으로 "t"가 하나만 있는 "octree"로 작성됩니다.
Octree는 종종 3D 그래픽 및 3D 게임 엔진에서 구현됩니다.
공간 표현을 위해
옥트리의 각 노드는 그것이 나타내는 공간을 8개의 옥탄트로 세분화할 책임이 있습니다. 포인트 영역(PR)에서
octree에서 노드는 해당 노드에 대한 세분화의 "중심"인 명시적 3차원 점을 저장합니다. 포인트
8개의 자식 각각에 대해 모서리 중 하나를 지정합니다. 매트릭스 기반(MX) 옥트리의 경우 세분화 지점은 암시적으로 노드가 나타내는 공간의 중심입니다. PR 옥트리의 루트 노드는 무한 공간을 나타낼 수 있습니다. MX 옥트리의 루트 노드는 암시적 중심이 잘 정의되도록 유한 경계 공간을 나타낼 수 있어야 합니다.
일반적인 용도
- 3D 컴퓨터 그래픽의 세부 수준 렌더링
- 공간 인덱싱
- 가장 가까운 이웃 검색
- 3차원의 효율적인 충돌 감지
- 유한요소해석
- 희소 복셀 옥트리
- 상태 추정
- 집합 추정