Построить фрактал драконова ломанная. Реализовать метод, заключающийся в генерации последовательности поворотов. Кривая дракона (драконова ломаная) – фрактал, построение которого можно объяснить следующим образом. Берём отрезок, сгибаем его пополам. Затем многократно повторяем итерацию. Если после этого снова разогнуть получившуюся (сложенную) линию так, чтобы все углы были равны 90°, мы получим драконову ломаную. Этот же фрактал, Дракон Хартера, также известный как дракон Хартера — Хейтуэя, был впервые исследован физиками NASA — John Heighway, Bruce Banks, и William Harter. Он был описан в 1967 году Мартином Гарднером (Martin Gardner) в колонке «Математические игры» журнала «Scientific American». Многие свойства фрактала были описаны Chandler Davis и Дональдом Кнутом. В своей программе я реализовала метод, заключающийся в генерации последовательности поворотов (т.е. предварительно рассчитала, под какими углами надо рисовать новые отрезки), а потом построила массив точек, задающий ломаную с заданными параметрами. (Существует ряд других алгоритмов построения этого фрактала.) Источник здесь: В программе за описанную последовательность отвечает функция 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 я оставляю без комментариев, т.к. они не имеют отношения к алгоритму построения этого фрактала.
Ключевые слова:
фрактал, драконова ломанная, кривая дракона, дракон Хартера — Хейтуэя
|
|||||||