쿼드트리(Quad tree)

 자료구조 카테고리를 만들까 하다가 알고리즘 카테고리에 작성합니다.

쿼드트리란?

 트리 자료구조중 하나로 부모 노드 아래에 자식 노드를 4개(Quad)씩 가지고 있는 트리입니다. 이미지 용량, 충돌, 컬링 등 다양한 곳에서 최적화 기법으로 사용되고 있습니다.

알고리즘

 오늘은 쿼드트리를 이용해 흑백 이미지를 간단하게 압축해보도록 하겠습니다.

검은색을 0, 흰색을 1로 한다면 왼쪽 이미지는 오른쪽과 같이 나타낼 수 있습니다.

 

00001111

00001111

00000011

00000011

11110001

11111111

11111111

11111110

해당 이미지를 쿼드트리를 이용해 압축을 하면 결과는 이렇게 나옵니다.

(0(1101)1((0011)(0111)1(1110))

 그림으로 보신다면 왼쪽과 같은 형태로 압축하는 것입니다. 알고리즘은 이미지의 구역을 4개로 나눈 후, 같은 숫자로 구성돼 있다면 하나로 묶어버리고 그렇지 않으면 다시 구역을 4개로 나누는 형태로 진행됩니다.

소스코드

#include<stdio.h>
#include<malloc.h>
#include<memory.h>
 
void quadTree(char** data, int beginX, int beginY, int size)
{
 
    // 병합 가능한지 체크---------------------------------
    char beginData = data[beginY][beginX];
    bool isCombinable = true;
    for (int y = beginY; y < beginY + size; ++y) {
        for (int x = beginX; x < beginX + size; ++x) {
            if (beginData != data[y][x])
            {
                isCombinable = false;
                break;
            }
        }
        if (isCombinable == false)
            break;
    }
    //---------------------------------------------------
 
    // 병합이 가능하면------------------------------------
    if (isCombinable)
    {
        printf("%c", beginData);
        return;
    }
 
    // 그게 아니라면 4개로 분할---------------------------
    int halfSize = (int)(size * 0.5f);
    printf("(");
    quadTree(data, beginX, beginY, halfSize);
    quadTree(data, beginX + halfSize, beginY, halfSize);
    quadTree(data, beginX, beginY + halfSize, halfSize);
    quadTree(data, beginX + halfSize, beginY + halfSize, halfSize);
    printf(")");
}
 
void main()
{
    int dataSize = 0;
    printf("데이터의 크기를 입력해주세요(2의 승수):");
    scanf("%d", &dataSize);
 
    // 메모리 할당
    char** data = (char**)malloc(sizeof(char*)*dataSize);
    for (int i = 0; i < dataSize; ++i)
    {
        data[i] = (char*)malloc(sizeof(char)*(dataSize + 1));
        memset(data[i], 0, sizeof(data[i]));
    }
 
    printf("데이터를 입력해주세요.\n");
    for (int i = 0; i < dataSize; ++i)
    {
        scanf("%s", data[i]);
    }
    
    // 분할
    quadTree(data, 0, 0, dataSize);
 
    for (int i = 0; i < dataSize; ++i)
    {
        free(data[i]);
    }
    free(data);
}

응용

 충돌 알고리즘도 이와 같은 방법으로 최적화를 진행하게 됩니다. 왼쪽 이미지와 같이 오브젝트들의 구역을 나눈 후, 인접한 영역의 오브젝트들끼리만 충돌처리 알고리즘을 진행합니다.