쿼드트리 공간 분할 계산기

사각 구역에 점을 담다가 정해진 개수를 넘으면 사분면 넷으로 쪼개고, 쪼갠 칸이 또 넘치면 또 쪼개는 자료구조입니다. 그래서 점이 촘촘한 곳은 깊고 텅 빈 곳은 얕은, 분포에 맞춘 울퉁불퉁한 격자가 만들어집니다. 지도·게임 충돌 검사·이미지 압축에 널리 쓰입니다.

빈 칸을 만들지 않습니다. 같은 해상도를 균등 격자로 내려면 가장 깊은 곳에 맞춰 전체를 쪼개야 해서 깊이 d일 때 칸이 4^d개 필요하고, 그 대부분이 텅 빕니다. 쿼드트리는 점이 있는 곳만 쪼개므로 칸 수가 점 개수에 비례합니다. 이 계산기가 「점이 든 칸」과 「같은 해상도의 균등 격자였다면」을 나란히 보여 주니 차이를 바로 볼 수 있습니다.

두 가지 지름길이 있습니다. 노드의 구역이 찾는 사각형과 아예 겹치지 않으면 그 아래를 통째로 건너뛰고(가지치기), 반대로 구역이 사각형에 통째로 들어가면 그 아래 점을 하나도 검사하지 않고 전부 담습니다(싹쓸이). 부분적으로 걸치는 노드만 내려가 점 하나하나를 봅니다. 둘 중 하나만 있으면 이득이 절반입니다.

같은 자리에 점이 여럿이면 아무리 쪼개도 갈라지지 않기 때문입니다. 사분면 중 한 칸에 전부 몰리고 그 칸을 또 쪼개도 마찬가지라 무한 재귀에 빠집니다. 깊이가 한계에 닿으면 용량을 넘겨도 더 쪼개지 않고 그냥 담아야 합니다. 편의를 위한 장치가 아니라 정확성을 위해 반드시 있어야 하는 장치입니다. 예제의 「같은 자리에 겹친 점」으로 확인할 수 있습니다.

가르는 방식이 다릅니다. k-d 트리는 점 하나를 골라 그 점을 지나는 선으로 한 번에 둘로 나누고 축을 번갈아 씁니다. 쿼드트리는 구역 한가운데를 기준으로 한 번에 넷으로 나눕니다. k-d 트리는 중앙값으로 갈라 균형이 잡히지만 점을 넣고 빼면 균형이 깨지고, 쿼드트리는 칸의 위치가 좌표만으로 정해져 삽입·삭제가 쉽습니다.

작게 잡으면 칸이 잘게 갈려 질의에서 걸러 내는 힘이 세지지만 노드가 많아져 메모리와 순회 비용이 늘고, 크게 잡으면 반대입니다. 실무에서는 4~16 사이를 흔히 씁니다. 이 계산기에서 용량을 바꿔 가며 노드 수와 검사한 점 수가 어떻게 맞바뀌는지 직접 볼 수 있습니다.

전송되지 않습니다. 트리를 쌓고 질의하는 일이 모두 브라우저 안에서 이뤄지고, 입력값은 이 기기에만 남습니다.