Фрактал драконова ломаная

dragon.JPG

Построить фрактал драконова ломанная. Реализовать метод, заключающийся в генерации последовательности поворотов.

Кривая дракона (драконова ломаная) – фрактал, построение которого можно объяснить следующим образом.

Берём отрезок, сгибаем его пополам. Затем многократно повторяем итерацию. Если после этого снова разогнуть получившуюся (сложенную) линию так, чтобы все углы были равны 90°, мы получим драконову ломаную.

Этот же фрактал, Дракон Хартера, также известный как дракон Хартера — Хейтуэя, был впервые исследован физиками NASA — John Heighway, Bruce Banks, и William Harter. Он был описан в 1967 году Мартином Гарднером (Martin Gardner) в колонке «Математические игры» журнала «Scientific American». Многие свойства фрактала были описаны Chandler Davis и Дональдом Кнутом.

В своей программе я реализовала метод, заключающийся в генерации последовательности поворотов (т.е. предварительно рассчитала, под какими углами надо рисовать новые отрезки), а потом построила массив точек, задающий ломаную с заданными параметрами. (Существует ряд других алгоритмов построения этого фрактала.)

Источник здесь:
http://en.wikipedia.org/wiki/Dragon_curve , раздел [Un]Folding the Dragon.

В программе за описанную последовательность отвечает функция

void precalc(int level, bool par) {
	s = "R";
	for (int i = 0; i < level - 1; i++) {
		int len = (int)s.size();
		s += 'R';
		for (int j = len - 1; j >= 0; j--) {
			if(s[j] == 'R') s += 'L';
			else s += 'R';
		}
	}
 
	Point p1(0, 0), p2(p1.x, p1.y + lgth), p3;
	if(par) {p2.x = p1.x + lgth; p2.y =  p1.y;}
 
	//p2.x = p1.x; p2.y = p1.y + lgth;
	coords[0] = p1; coords[1] = p2;
 
	int i, len;
	len = (int)s.size();
	for (i = 0; i < len; i++)  {
		if(s[i] == 'L') {
			p3.x = p2.x + p2.y - p1.y;
			p3.y = p2.y + p1.x - p2.x;
		}
		else {
			p3.x = p2.x + p1.y - p2.y;
			p3.y = p2.y + p2.x - p1.x;
		}
		p1.x = p2.x; p1.y = p2.y;
		p2.x = p3.x; p2.y = p3.y;
		coords[i + 2] = p2;
	}
}

Она работает с глобальными переменными
string s; 
Point coords[COORDS_SIZE + 1];

Направление первого отрезка задаётся вручную. Поскольку кривые некоторых порядков располагаются «вертикально», что нерационально с точки зрения их размещения на экране, в этой функции вводится вспомогательный параметр par, который позволяет изменять направление начального отрезка, если это необходимо.

Также для рационализации положения кривой используется функция

void Shift(int dx, int dy, int level) {
	int size = 1 << level;
	for (int i = 0; i <= size; i++) {coords[i].x += dx; coords[i].y += dy;}
}

Следующая функция вычисляет, насколько надо сдвинуть кривую, чтобы она расположилась в центре экрана, и, если есть необходимость, выполняет поворот на 90 градусов, вызывая функцию precalc с изменённым параметром.

void toCenter (int level, HWND hWnd) {
	GetClientRect(hWnd, &ClientRect);
	int right = coords[0].x, left = coords[0].x, top = coords[0].y, bottom = coords[0].y;
	int size = 1 << level;
	for (int i = 1; i <= size; i++) {
		if (coords[i].x < left) left = coords[i].x;
		if(coords[i].x > right) right = coords[i].x;
		if(coords[i].y < top) top = coords[i].y;
		if(coords[i].y > bottom) bottom = coords[i].y;
	}
	if(right - left < bottom - top) {
		precalc(level, true);
		right = coords[0].x, left = coords[0].x, top = coords[0].y, bottom = coords[0].y;
		for (int i = 1; i <= size; i++) {
			if (coords[i].x < left) left = coords[i].x;
			if(coords[i].x > right) right = coords[i].x;
			if(coords[i].y < top) top = coords[i].y;
			if(coords[i].y > bottom) bottom = coords[i].y;
		}
	}
	int c = (ClientRect.bottom - bottom + top - ClientRect.top) >> 1;
	c = - bottom + ClientRect.bottom - c;
	int d = (ClientRect.right - right + left - ClientRect.left) >> 1;
	d = - right + ClientRect.right - d;
	Shift(d, c, level);
	return;
}

Наконец, функция рисования. Кроме уже упомянутого глобального массива coords она использует массив BYTE col[19][3]; в который занесены значения цветов для раскраски участков фрактала.

void Draw(HWND hWnd, HDC hdc, int level) {
 
	toCenter (level, hWnd);
 
	RECT rect;
    HBITMAP frame;
    HDC mem;
    GetClientRect(hWnd, &rect);
    mem=CreateCompatibleDC(hdc);
    frame=CreateCompatibleBitmap(hdc, rect.right-rect.left, rect.bottom-rect.top);
    SelectObject(mem, frame);
 
	/*background*/
	HBRUSH hBrush = CreateSolidBrush(RGB(0,0,0));
	HBRUSH hOldBrush = (HBRUSH)SelectObject(mem, (HGDIOBJ)hBrush);
	GetClientRect(hWnd, &ClientRect);
	Rectangle(mem,ClientRect.left, ClientRect.top, ClientRect.right, ClientRect.bottom);
	SelectObject(mem, hOldBrush);
	DeleteObject(hBrush);
	/*----------------------------------curve----------------------------------*/
 
	int size = 1 << level, lvl = 2, step = 2, j = 0, i = 1;
	int add = MAX_LEVEL - level;
	for (step = 0; lvl <= size; lvl += step) {
 
		HPEN hPen = CreatePen(PS_SOLID, 1, RGB(col[j + add][0],col[j + add][1], col[j + add][2]));
		HPEN hOldPen = (HPEN)SelectObject(mem, (HGDIOBJ)hPen);
		MoveToEx(mem, coords[i - 1].x, coords[i - 1].y, NULL);
		for (; i <= lvl; i++) LineTo(mem, coords[i].x, coords[i].y);
		j++;
		step = (1 << j);
		SelectObject(mem, hOldPen);
		DeleteObject(hPen);
		if(j == 19) break;
	}
	/*------------------------------------------------------------------------------*/
	BitBlt(hdc, 0, 0, rect.right-rect.left, rect.bottom-rect.top, mem, 0, 0, SRCCOPY);
    DeleteDC(mem);
    DeleteObject(frame);
}

Программа позволяет менять длину отрезка ломаной и порядок самой кривой через соответствующее диалоговое окно. Стандартные функции, типы данных и объекты WinAPI я оставляю без комментариев, т.к. они не имеют отношения к алгоритму построения этого фрактала.

Ключевые слова: 
фрактал, драконова ломанная, кривая дракона, дракон Хартера — Хейтуэя
ВложениеРазмер
Кривая дракона (исходники)2.27 Мб