🌲Quad Tree & Loose Quad Tree& Octree

Quad Tree

Binary Tree가 Node가 두 개인 트리구조인 것처럼

 

Quad Tree는 Node가 네 개인 트리구조를 말한다.

 

사용처

1. 대량의 좌표 데이터를 압축 저장
2. 보통 흑백 이미지 표현에 많이 사용
3. 게임에서는 지형정보를 저장하기 위해 많이 사용한다.
   • 거대한 지형을 탐색할 때, 필요 없는 정보를 버릴 수 있다
   • Procedural Grneration에서 QuadTree를 이용해 생성

   • 

4. Collision Check 시에 사용 

 

  어느 Box에 Collision이 생겼는지 탐색하는 경우에 사용할 수 있을 듯하다.

 

  무작정 탐색보다 어느 사분면에 맞았는지를 따라가는 편이 정확한 충돌위치 판별에 도움이 될 것

 

 

 

 

Loose Quad Tree

Loose Quad Tree 알고리즘은 기존 Quad Tree 알고리즘의 문제점을 보완하기 위해 탄생

 

Quad Tree 알고리즘의 문제점?

• Quad Tree는 크기를 엄격하게 4개로 분할한다.
• 이렇다 보니 한 개의 영역 Data가 몰리는 경우에 비효율적
  • 불필요하게 많은 Node를 생성하고 메모리를 낭비할 수 있음
• 그러니 검색속도가 느려질 수 있다.

⇒ 그래서 Loose Quad Tree는 각 영역을 Loose하게 분할한다.

 

https://community.cesium.com/t/announcing-cesium-osm-buildings/9757

이런 형식으로 엄격하게 분할하지 않는 QuadTree를 말한다.

 

Octree

Wiki-Octree https://www.google.com/url?sa=i&url=https%3A%2F%2Fen.wikipedia.org%2Fwiki%2FOctree&psig=AOvVaw1o7-kigjRb314zK7vxN40w&ust=1707576077731000&source=images&cd=vfe&opi=89978449&ved=0CBQQjhxqFwoTCJD1n9--noQDFQAAAAAdAAAAABAD'

 

Octree는 QuadTree의 3차원 형태로 생각하면 쉽다.

 

8개의 자식노드를 가지는 트리구조이다.