QuadTree

지도, Deep Zoom 등 2차원 솔루션에서, 정보의 구축과 검색을 원활히 하기 위해서,
QuadTree 형식의 자료 구조가 구현되는 것이 바람직합니다.

예를들면 방대한 영역에 존재하는 데이터 중,
보이는 화면영역에 해당하는 데이터만 빨리빨리 찾아와야 할 때 유용합니다.

QuadTree는 4개의 자식을 갖는 트리구조입니다.
평면을 계속 4분할해 나가면서 트리가 구성됩니다.

1개의 Cell은 maximum capacity를 가지고 있어서, 그 값이 넘게 자식이 존재해야할
필요성이 있을 때 또 분할됩니다.

수직선, 수평선이란 자식까지 정의하여 총 6개의 자식을 갖도록 설계하는 경우도 있습니다.
(CAD/CAM 프로그래밍 할 때 그렇게 했었음.)

한번 이렇게 구성된(Build) QuadTree는 영역에 대한 검색을 실시 할 때,
유용하게 사용됩니다.

5년동안 MFC로 CAD/CAM 프로그래밍하는 동안 매일 만지작거려왔는데,
이제는 실버라이트에서도 사용하기 위해서 QuadTree를 C#으로 포팅할 때가 된 것 같습니다.

그전에 혹시 쓸만한 좋은 소스가 있는지 코드플렉스를 뒤져봤습니다.
XNA 관련된 소스만 찾을 수 있었습니다.

XNA에서는 QuadTree가 어떻게 활용되고 있는지
Youtube에 올라와 있는 데모 동영상을 보시죠.

사실 이 동영상에는 쿼드트리 이상의 것이 들어있어서 요점을 흐릴 수 있습니다만,
쿼드 트리가 없으면 퍼포먼스가 엄청 떨어지는 데모입니다.