칸토어 먼지

프랙탈의 본성은 '축소하여 자기자신을 복제' 하는 것으로 앞 장의 예제들도 이를 만족하고 있다. 흔히들 프랙탈은 1970년대 만델브로트에 의해 창시되었다고 하나 그 이전에도 여러 수학자들에 의해 프랙탈이 연구되었다.

칸토어 먼지(Georg Cantor. 1872), 코호 곡선(Helge von Koch, 1904), 시어핀스키 양탄자(Waclaw Sierpinski. 1910년대 후반) 등이 대표적인 예이다. 이들을 고전적 프랙탈(Classical Fractal)이라 한다.

이 장에서는 고전적 프랙탈 중 칸토어 먼지를 재귀 호출 함수를 사용하여 구현하는 방법을 설명한다.

칸토어 먼지와 칸토어 집합

고전적 프랙탈 가운데 가장 오래된 것중의 하나가 칸토어 먼지로 1872년에 독일의 수학자 칸토어에 의해 발표되었다.

위의 그림은 칸토어 먼지의 그림이다. 길이가 1인 직선을 준비한 후 가운데 1/3 을 지운다. 이 결과 좌우에 두 직선이 생기는데 이 두 직선에 대해서도 가운데 1/3 을 지운다. 이러한 작업을 무한히 반복한 결과 남아 있는 것들의 모임을 칸토어 먼지라고 부른다. 칸토어 먼지를 칸토어 집합(Contor Set)이라고도 한다. 칸토어 집합은 물리, 수학, 통계 등 여러 분야에서 널리 활용되고 있다.

알고리즘 분석

위 그림의 칸토어 먼지는 완벽한 순환적 구조이다. 이와 같은 순환적 구조의 경우에는 재귀 호출 함수를 사용하여 프로그램을 작성하는데, 앨고리즘을 분석할 때에는 재귀호출이 한번 수행된 후 얻어진 그림을 가지고 분석한다. -> 방향으로 칸토어 먼지를 그리는 것으로 하고 이 그림을 그리는 함수를 Cantor()라 하자.

코드 작성

이 상의 내용을 코드로 작성해 보자. 우선 사각형을 그려주는 함수 DrawRectangle() 를 살펴보자.

void DrawRectangle(GLfloat x, GLfloat y, GLfloat length)
{
    glPushMatrix();
        glTranslatef(x, y, 0.0f); //지정 위치로 이동
        glScalef(1.0f, length, 1.0f); //Y축으로 length 만큼 확대 
        //넓이 1*length 의 사각형
        glBegin(GL_QUADS); 
            glColor3f(1.0f, 0.5f, 1.0f);
            glVertex3f(-1.0f, 0.0f, 0.0f);
            glVertex3f( 0.0f, 0.0f, 0.0f);
            glVertex3f( 0.0f, 1.0f, 0.0f);
            glVertex3f(-1.0f, 1.0f, 0.0f);
        glEnd();
    glPopMatrix(); 
}

너비가 1 인 사각형을 그리되, glScalef() 함수를 이용해서 Y 축으로 length 길이만큼 확대하므로 결과적으로 1*length 의 너비를 갖는 사각형을 그리게 된다. 다음은 칸토어 먼지를 그려주는 Cantor() 함수를 살펴보자.

void Cantor(GLfloat x, GLfloat y, GLfloat length)
{
    if(length > 0.1f) //0.1f 보다 큰 사각형들을 그린다.
    {
        DrawRectangle(x, y, length); //A 를 그린다.
        //각 사각형의 간격은 1.5
        Cantor(x+1.5f, y, length/3.0f); //B 를 그린다.
        Cantor(x+1.5f, y+length*(2.0f/3.0f), length/3.0f); //C 를 그린다.
    }
}

B 를 그릴 때 A length 의 1/3 크기의 사각형을 그린다. 그리고 C 를 그릴 때 Y 축에서 2/3 만큼 아래로 이동한 좌표에 A length 의 1/3 크기의 사각형을 그린다. length 가 0.1 보다 작아질 때까지 이를 계속해서 반복한다. 다음은 투영영역을 설정하는 OnSize() 의 함수다.

void RenderWindow::OnSize(WPARAM wParam, LPARAM lParam)
{
    width = LOWORD(lParam);
    height = HIWORD(lParam);

    if (height == 0)
        height = 1; 

    glViewport( 0, 0, width, height ); 

    glMatrixMode(GL_PROJECTION); 
    glLoadIdentity(); 

    width /= 5; //X축 5배 확대
    height /= 5; //Y축 5배 확대

    // {left, top}~{right,bottom} => {0,0}~{width/5, height/5}
    glOrtho(0, width, height, 0, 1.0f, -1.0f);

    glMatrixMode(GL_MODELVIEW); 
    glLoadIdentity(); 
}

윈도우에서 사용하는 좌표계와 동일한 좌표계를 만들고 있다. 칸토어 먼지는 이러한 좌표계를 사용하는 것이 구현하기 더 쉽기 때문에 그렇게 했다. 다음은 이를 좋합한 전체적인 코드와 결과 프로그램의 화면을 보자.

#include <windows.h>
#include "lib\egl.h"

using namespace egl;

void DrawRectangle(GLfloat x, GLfloat y, GLfloat length)
{
    glPushMatrix();
        //지정 위치로 이동
        glTranslatef(x, y, 0.0f);
        //Y축으로 length 만큼 확대
        glScalef(1.0f, length, 1.0f);
        //넓이 1*length 의 사각형
        glBegin(GL_QUADS); 
            glColor3f(0.0f, 1.0f, 0.0f);
            glVertex3f(-1.0f, 0.0f, 0.0f);
            glVertex3f( 0.0f, 0.0f, 0.0f);
            glVertex3f( 0.0f, 1.0f, 0.0f);
            glVertex3f(-1.0f, 1.0f, 0.0f);
        glEnd();
    glPopMatrix(); 
}

void Cantor(GLfloat x, GLfloat y, GLfloat length)
{
    if(length > 0.1f)
    {
        DrawRectangle(x, y, length); //A

        //각 사각형의 간격은 1.5
        Cantor(x+1.5f, y, length/3.0f); //B
        Cantor(x+1.5f, y+length*(2.0f/3.0f), length/3.0f); //C
    }
}

class RenderWindow : public Window
{
private:
    GLsizei width, height;
public:
    virtual void RenderGLScene(void);
    virtual void OnSize(WPARAM wParam, LPARAM lParam);
};

void RenderWindow::OnSize(WPARAM wParam, LPARAM lParam)
{
    width = LOWORD(lParam);
    height = HIWORD(lParam);

    if (height == 0)
        height = 1; 

    glViewport( 0, 0, width, height ); 

    glMatrixMode(GL_PROJECTION); 
    glLoadIdentity(); 

    width /= 5; //X축 5배 확대
    height /= 5; //Y축 5배 확대

    // {left, top}~{right,bottom} => {0,0}~{width, height}
    glOrtho(0, width, height, 0, 1.0f, -1.0f);

    glMatrixMode(GL_MODELVIEW); 
    glLoadIdentity(); 
}

void RenderWindow::RenderGLScene(void)
{
    static float length=60.0f;
    static float OriginX =0.0f; 
    static float OriginY =0.0f; 

    OriginX = (float)(width/2); //칸토어 먼지가 그려질 X축 원점은 윈도우 너비의 1/2
    OriginY = (float)(height/2)-(length*0.5); //칸토어 먼지가 그려질 Y축 원점은 윈도우 높이의 1/2 - 막대기 길이의 1/2 

    Window::RenderGLScene();
    Cantor(OriginX, OriginY, length);
}

int APIENTRY WinMain(HINSTANCE hInstance, HINSTANCE hPrevInstance, LPSTR lpCmdLine, int nShowCmd)
{
    RenderWindow app;
    if(!app.Create(FALSE,"Fractal Graphics - Cantor Set"))
        return EXIT_FAILURE;
    return app.Run();
}