아래와 같은 하나의 줄기에 두개의 가지만 있는 나무 모양의 프랙탈을 이진 나무(Binary Tree)라 한다. 쉽게 짐작할 수 있듯이 많은 자연의 성장 과정이 위와 유사한 구조로 되어 있다. 나무와 하천의 흐름이 가장 쉽게 찾아 볼 수 있는 예이다.
알고리즘
위의 차수가 3 인 이진 나무를 유심히 관찰하자. 구조가 완벽한 재귀적(순환적) 구조이다. 줄기에서 가지를 쳐 나가는 작업을 0 차 가지(잎)에 도달할 때까지 재귀적으로 반복하면 된다. 기본적인 알고리즘은 잡혔다. 이어서는 어떻게 가지를 쳐 나갈 것인가를 결정한다.
길이가 length 인 a 가지를 그린다.
왼쪽으로 30 도 회전하여 길이가 length*0.8 인 b 가지를 그린다.
오른쪽으로 60 도 회전하여 길이가 length*0.8 인 c 가지를 그린다.
3 번 과정을 마친 후 왼쪽으로 30 도 회전하여 진행 방향을 원래대로 환원시킨다.
예를 들어 차수 n = 3 인 경우 위와 같은 처리를 n 을 1 씩 줄여 나가면서 n = 0 이 될때까지 재귀적으로 반복시키면 위의 오른쪽의 나무가 그려진다. 이 때 주의할 점은 예를 들어 b 가지를 그린 후에는 선을 그리는 시작 위치를 b 가지의 시작점인 CP 로 환원시켜야 한다는 점이다. 그래야 위 알고리즘은 c 가지를 정확히 그린다. 이를 위해서 거북이 그래픽 클래스에 현재 거북이의 위치를 저장하는 스택을 포함하였다. 아래 부분은 거북이 클래스에 새로 추가된 함수의 코드이다.
// Header File
typedef stack<Point3D> pstack;
class Turtle
{
private:
...
pstack PointStack; //위치를 저장할 스택
...
public:
...
void MarkCurrentPoint(void); //현재의 위치에 점을 그린다.
void Push(void); //현재의 위치를 저장한다.
void Pop(void); //저장한 위치로 돌아간다.
};
// Source File
Turtle::Turtle(void)
{
//스택 포인터 모두 제거
while(PointStack.size())
{
PointStack.pop();
}
...
}
void Turtle::SetStartPoint(float x, float y, float z)
{
//스택 포인터 모두 제거
while(PointStack.size())
{
PointStack.pop();
}
...
}
void Turtle::MarkCurrentPoint(void)
{
glPointSize(5.0f);
glBegin(GL_POINTS);
glColor3f(1.0f, 0.0f, 0.0f);
glVertex3f(PointList[PointList.size()-1].x, PointList[PointList.size()-1].y, PointList[PointList.size()-1].z);
glColor3f(1.0f, 1.0f, 1.0f);
glEnd();
}
void Turtle::Push(void)
{
int index = PointList.size()-1;
Point3D pt(PointList[index].x, PointList[index].y, PointList[index].z);
//포인트 리스트에 저장되어 있는 마지막 점을 push 한다.
PointStack.push(pt);
}
void Turtle::Pop(void)
{
if(PointStack.size())
{
Point3D pt(PointStack.top());
PointStack.pop();
PointList.push_back(pt);
}
}
위의 알고리즘을 코드로 표현하면 아래와 같다.
void RenderWindow::BinaryTree(int n, float length)
{
turtle.Forward(length);
if(n>0)
{
turtle.Push(); //CP 저장
turtle.Left(30); BinaryTree(n-1, length*0.8);
turtle.Pop(); //CP 로 이동
turtle.Right(60); BinaryTree(n-1, length*0.8);
turtle.Left(30);
}
}
아래는 이진나무를 표현한 프로그램 결과와 전체 코드이다. 오른쪽 그림은 열매를 맺은 나무이다. n==0 일때 현재의 점을 표시하면 된다.
