V Международный конкурс научно-исследовательских и творческих работ учащихся

Старт в науке

Фрактальная геометрия природы: простые алгоритмы для сложных объектов

• Авторы
• Руководители
• Файлы работы
• Наградные документы

Первушин В.И. 1Пермяков  Е.А. 2

---

1МБОУ "Средняя общеобразовательная школа № 125 с углублённым изучением математики"

2Муниципальное бюджетное общеобразовательное учреждение "Средняя общеобразовательная школа № 125 с углублённым изучением математики" «МБОУ СОШ № 125»

Чеботарёва  Н.А. 1Первушина Н.А. 1

---

1Муниципальное бюджетное общеобразовательное учреждение "Средняя общеобразовательная школа № 125 с углублённым изучением математики" «МБОУ СОШ № 125»

Работа в формате PDF

1.7 MB

Автор работы награжден дипломом победителя II степени

Диплом школьникаСвидетельство руководителяСвидетельство руководителя

Введение

Исследования на тему «Фрактальная геометрия природы: простые алгоритмы для сложных объектов» для нас очень актуальны.

Нам известно, что все природные объекты (живые и неживые) имеют сложное строение и цветовую окраску. В сети Internet находится множество очень красивых цветных изображений с различными завитками, языками пламени, молниями и вихрями, напоминающими природные образования: горы, реки, молнии, перья птиц и др. Такие картинки часто устанавливают на рабочий стол персонального компьютера. Все эти изображения носят одно название – фракталы. Мы выяснили, что фракталы – это математические объекты, т.е. каждый из них строится с помощью математических вычислений по заданному алгоритму. Любой алгоритм имеет последовательность шагов и правила выполнения каждого шага, которые несложные, если есть необходимые знания по математике и информатике. Нам стало интересно, сможем ли мы понять эти алгоритмы и разобраться хотя бы в некоторых из них.

В настоящем исследовательском проекте мы сделали попытку с помощью наших руководителей изучить информацию о таких алгоритмах построения фрактальных объектов как метод временного порога и L-графика. Любому, читающему нашу работу будет интересно небольшое путешествие по завораживающим своей красотой и математической точностью построения геометрическим объектам, которые так точно описывают объекты живой и неживой природы. Мы сделаем свои первые шаги к изучению математических алгоритмов и предложим свои фракталы для описания природных объектов.

Гипотеза проекта: некоторые алгоритмы построения фрактальных объектов являются простыми и могут быть применены для описания сложных природных объектов, а также могут быть разработаны самостоятельно.

Цель проекта – создание своих алгоритмов построения фракталов для моделирования природных объектов.

Задачи проекта:

1) изучить понятие «фрактал» и познакомиться с областями его применения;

2) изучить информацию о таком алгоритме построения фрактальных объектов как метод временного порога, познакомиться с построением множества Мандельброта;

3) познакомиться с построением фракталов с помощью и L-систем, изучить построение снежинки Коха, а также Снежинки с использованием операции ветвления;

4) разработать свои алгоритмы построения фракталов с использованием L-систем для описания природных объектов.

Объект исследования – фракталы.

Предмет исследования: алгоритмы построения фракталов.

Методы исследования: изучение литературы и Интернет-ресурсов, беседа со специалистами, извлечение знаний, систематизация информации и анализ, синтез алгоритмов, моделирование подобных объектов на основе полученных знаний.

Ожидаемые результаты проекта:

получение новых знаний в области математики и информатики;

применение полученных знаний для создания новых объектов;

разработанные алгоритмы.

Выполненная работа позволила нам получить новые знания по математике (отрицательные числа и арифметические действия над ними, построение на плоскости углов от заданного направления в диапазоне от 0 до 360 градусов), применить их на практике и получить результат. В области информатики мы получили новые знания работая в приложении Excel Microsoft Office 2016, а также применили знания по программированию в BASIC256 для оформления результатов проекта.

Источники информации для выполнения исследовательского проекта мы нашли в сети Internet. В них содержится вся необходимые для работы данные: от описания научной деятельности автора и основоположника понятия «фрактал» Бенуа Мандельброта [1, 2], до описания всех известных алгоритмов фрактальной компьютерной графики [3 – 5].

Настоящий учебно-исследовательской проект демонстрирует то, что простые алгоритмы построения фрактальных объектов находят своё применение при описании формы сложных природных объектов, а также то, что подобные алгоритмы могут быть разработаны самостоятельно, так же как сделали мы – авторы проекта.

1 Понятие «фрактал» и области его применения

С середины ХIX века математиками стали изучаться геометрические объекты: линии, поверхности, пространственные тела и др., имеющие «сильно изрезанную форму» и обладающие свойствами однородности и самоподобия – фракталы.

Термин фрактал появился в 1975 году, а само слово происходит от латинского слова fractus – дробный и французского слова frangere – ломать, что означает суть фрактала как «изломанного» множества.

В 1977 году вышла книга Бенуа Мандельброта (см. Приложение А) «Форма, случай, размерность». В ней было показано, что существование фракталов позволяет объяснить, а в некоторых случаях предсказать экспериментальные результаты, полученные в различных областях знаний: биология, география, физика и др. Фракталы с большой точностью описывают многие физические явления и природные образования: горы, облака, корни, ветви и листья деревьев, кровеносные сосуды, что далеко не соответствует простым геометрическим фигурам.

В своей книге Б. Мандельброт написал: «Почему геометрию часто называют холодной и сухой? Одна из причин заключается в её неспособности описать форму облака, горы, дерева или берега моря. Облака – это не сферы, горы – не конусы, линии берега – это не окружности, и кора не является гладкой, и молния не распространяется по прямой. Природа демонстрирует нам не просто более высокую степень, а совсем другой уровень сложности» [1, 2].

В современном мире фракталы создаются на компьютере по математическим алгоритмам. Сами алгоритмы достаточно понятны и просты, хотя создаваемые ими объекты состоят из огромного количества самоподобных частей и очень сложны.

Существует множество математических объектов, называемых фракталами, среди них: множество Мандельброта, треугольник Серпинского, и др.

Фрактальная графика – один из видов компьютерной графики.

Фрактальный рисунок можно построить либо с помощью какого-либо алгоритма, либо путем автоматического создания изображения, которое осуществляется путем вычислений по заданным формулам. Изменение изображения происходит при внесении изменений в структуру алгоритма или смене коэффициентов в формуле [3].

2 Метод временного порога

2.1 Алгоритм метода на примере множества Мандельброта

Фракталы с многоцветными завитушками построены с помощью метода временного порога. Они изображаются точками разного цвета на плоскости. Цвет точки зависит от времени (количества шагов) за которое данная точка «выбегает» за заданную границу [4, 5]. Границей является геометрическая фигура, например, квадрат или круг. Примеры таких фракталов представлены на рисунке Б.1 Приложения Б.

Самый известный в мире фрактал, построенный по методу временного порога, – множество Мандельброта. Точки, изображающие множество Мандельброта, похожи на точки плоскости в методе координат. Граница на плоскости – окружность. На рисунке 2.1 приведен пример изображения множества Мандельброта.

Алгоритм построения множества Мандельброта:

Для каждой точки плоскости выполняются вычисления. Координаты каждой точки подставляются в простые уравнения, по которым определяется новая пара координат. Эти координаты снова подставляются в те же уравнения и получается ещё пара координат и т. д. Повторяя многократно эти вычисления, получается набор координат, определяющий путь точки. Путь точки называется орбитой.

Если орбита точки никогда не «выбегает» за пределы границы окружности, расположенной в начале координат, то эта точка – элемент множества Мандельброта. Она закрашивается чёрным.

Если орбита точки выбегает за границу, то соответствующей точке приписывается цвет, который соответствует «времени убегания». Промежуток времени, необходимый для выбегания точек за границу круга называется временем убегания (escape-time).

Когда эта процедура будет применена к каждой расчётной точке, то будет получено разноцветное изображение множества Мандельброта. Если изменить уравнения для расчёта координат, то получатся другие фракталы с временным порогом.

Рисунок 2.1 – Множество Мандельброта и его фрагменты

Увеличивая области множества Мандельброта, появляются новые детали фрактала той же самой формы. Здесь проявляется свойство самоподобия. Цвета, для окрашивания различных орбит, выбираются по усмотрению разработчика. Изменение цветовой гаммы позволяет по-другому посмотреть на объект.

2.2 Применение метода для построения цветного изображения на плоскости

Изучив метод временного порога и алгоритм построения множества Мандельброта, мы решили сами придумать алгоритм. В качестве границы нами была выбрана окружность с центром в начале координат. Алгоритм пересчёта координат предлагаем такой:

Х_нов = 2∙Х_стар+Y_стар, (2.1)

Y_нов = Y_стар – X_стар, (2.2)

где Х_стар, Y_стар – старые координаты точки плоскости (на текущем шаге),

Х_нов, Y_нов – новые координаты точки плоскости (на следующем шаге).

При переходе алгоритма на следующий шаг «новые» координаты становятся «старыми» и снова выполняются те же вычисления по формулам (2.1) и (2.2).

На листе тетради мы нарисовали границу – окружность радиусом 4 см. Для расчёта по алгоритму мы выбрали точки внутри окружности (45 штук) и на её границе (А, В, С, D). Расположение точек приведено на рисунке 2.2.

До начала работы алгоритма будем считать, что все точки окрашены в чёрный цвет.

1 шаг. Координаты всех отмеченных на схеме рисунка 2.2 точек подставляем в формулы (2.1) и (2.2). Получаем «новые» координаты и «новые» точки. Если «новые» точки оказались за границей окружности, то сами точки (рисунка 2.2) раскрашиваются в красный цвет, а которые остались в кругу – чёрные.

2 шаг. «Новые» координаты всех точек черного цвета (рисунка 2.2), после выполнения шага 1 называем «старыми» и снова подставляем в уравнения (2.1) и (2.2). Если «новые» точки оказались за границей окружности, то сами точки (рисунка 2.2) раскрашиваются в синий цвет, а которые всё ещё остались в кругу – чёрные.

Рисунок 2.2 – Схема расположения границы и расчётных точек

3 шаг. «Новые» координаты всех точек черного цвета (рисунка 2.3), после выполнения шага 2 называем «старыми» и снова подставляем в уравнения (2.1) и (2.2). Если «новые» точки оказались за границей окружности, то сами точки (рисунка 2.2) раскрашиваются в зелёный цвет, а которые всё ещё остались в кругу – чёрные.

Алгоритм заканчивает работу, когда все точки внутри границы раскрашены и дальнейшее выполнение шагов алгоритма не приводит к изменению раскраски точек.

Так как координаты выбранных 49 точек плоскости положительные и отрицательные числа, то чтобы не запутаться с вычислениями и сократить время на ручной счёт, мы воспользовались таблицами офисного приложения Excel Microsoft Office 2016 – таблица В.1 Приложения В. В первом столбце мы указали номер точки (см. рисунок 2.2), во втором столбце – координата Х, в третьем столбце – координата Y. Дальше приведены «новые» координаты после 1-го шага расчёта – Х1 и Y1, после 2-го шага расчёта – Х2 и Y2, после 3-го шага – Х3 и Y3. Выполнение 4-го шага не меняет окраску точек внутри границы, т.к. остаётся одна точка чёрного цвета с координатами Х=0 и Y=0. Если подставить эти значения в уравнения (2.1) и (2.2), то «новые» координаты тоже получатся нулевыми и точка всегда будет внутри круга.

Для иллюстрации работы нашего алгоритма мы сделали рисунки в программе BASIC256, как на уроке информатики. Картинки к каждому шагу нашего алгоритма построения фрактала по методу временного порога показаны на рисунке Г.1 Приложения Г.

2.3 Заключение по разделу

Мы познакомились с методом временного порога для построения фракталов. Изучили алгоритм построения множества Мандельброта. На основе полученных знаний мы предложили свой алгоритм с использованием метода временного порога, чтобы разобраться с каждым шагом и выполнить самостоятельно все вычисления и построения. При выполнении вычислений нам потребовались дополнительные математические знания по работе с отрицательными числами. Мы научились их складывать друг с другом и с положительными числами, а также умножать на число. Правильность своих вычислений мы проверили с помощью программы Excel Microsoft Office 2016, в которой работать мы тоже немного научились. А ещё мы использовали свои знания по программированию на языке BASIC256 для решения поставленной задачи.

3 L-системы и терл-графика

3.1 Основные понятия

Понятие «L-система» было введено венгерским биологом Аристидом Лидермаером в 1968 году при изучении искусственных языков для описания различных алгоритмов [3, 4]. С их помощью оказалось можно строить известные самоподобные фракталы: снежинку Коха, ковёр Серпинского и др.

Терл-графика (от английского turtle – черепашка) является системой вывода графического представления фрактального объекта. Исполнитель данной системы – это «черепашка» (точка), которая перемещается по плоскости дискретными шагами, прочерчивая или не прочерчивая след.

Положение «черепашки» задаётся тремя параметрами:

x, y – координаты «черепашки»,

α – направление следующего шага (угол, отсчитываемый от текущего направления движения).

Последовательность команд, определяющих направление перемещения и действия «черепашки», задаётся кодовым словом. Кодовое слов может включать в себя следующие буквы:

F – переместиться на один шаг вперёд, прорисовывая след;

B – переместиться на один шаг вперёд, не прорисовывая след;

[ – открыть ветвь;

] – закрыть ветвь;

+ – увеличить угол α на величину θ;

– – уменьшить угол α на величину θ;

Х, Y – вспомогательные переменные («черепашка» их не замечает).

Размер шага и величина θ задаются изначально и остаются неизменными для всех перемещений «черепашки».

3.2 Алгоритм метода на примере снежинки Коха

L-система, соответствующая снежинке Коха, задаётся следующим образом:

Аксиома: F++F++F

Порождающее правило: F_нов = F – F + + F – F, где α =0 и θ = 60º.

Если построить фрактал только с помощью аксиомы, то его порядок будет 0-ой. Если один раз вместо каждой буквы F в аксиому подставить F_нов, то порядок фрактала будет 1-ый и т.д.

Построение снежинки Коха 1-го порядка вручную (с помощью транспортира и линейки) приведено на рисунке 3.1.

Фракталы более высокого порядка можно построить с помощью специальных компьютерных программ, которые доступны в сети Internet. Например, такой: LGraphics. На рисунке Д.1 Приложения Д представлен её интерфейс с примером построения снежинки Коха.

Рисунок 3.1 – Построение снежинки Коха 1-го порядка.

3.3 Алгоритм метода на примере построения фрактала Снежинка с использованием операции ветвления

Когда в L-системе встречается символ [ (открыть ветвь), то нужно запомнить координаты точки нахождения «черепашки» и направление её движения, т.е. переменные x, y и α. К сохранённым переменным следует вернуться после обнаружения символа ] (закрыть ветвь). Хранятся координаты точки и её направление друг за другом:

x₁, y₁, α₁

x₂, y₂, α₂

x₃, y₃, α₃

…

В конец этого списка записываются новые данные. При закрытии ветви переменным x, y, α задаются значения из конца списка и удаляются из него.

L-система, соответствующая Снежинке, задаётся следующим образом:

Аксиома: [F]+[F]+[F]+[F]+[F]+[F]

Порождающее правило: F_нов = F[++F][–FF]FF[+F][–F]FF, где α =0 и θ = 60º.

На рисунке 3.2 показано построение Снежинки 0-го порядка (по аксиоме). На рисунке Д.2 Приложения Д показан пример построения Снежинки 1-го порядка в LGraphics.

Рисунок 3.2 – Построение Снежинки 0-го порядка

На рисунке 3.3 представлены два описанных выше фрактала (снежинка Коха и Снежинка) только 4-го порядка, построенные в программе LGraphics. В результате многократной подстановки «правила вывода» вместо каждой из букв F аксиомы получается более детальная картинка фрактала.

Рисунок 3.3 – Снежинка Коха и Снежинка 4-го порядка

3.4 Разработка новых алгоритмов

На базе полученных знаний об L-системах и при помощи программы LGraphics, мы разработали свои алгоритмы для описания природных объектов.

3.4.1 Алгоритм Первушина В. И.

Фрактал «Облака».

Аксиома: F – F+F+F

Порождающее правило: F_нов = F+B – F – FF – F+F+B – F+++FF,

B_нов=BBBB, где α =0 и θ = 90º.

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

Результат работы алгоритма в виде изображения фрактала 4-го порядка приведен на рисунке Е.1 Приложения Е.

3.4.2 Алгоритм Пермякова Е. А.

Фрактал «Ветка полыни».

Аксиома: F[+F][ –F][++F][ – – F]F

Порождающее правило: F_нов = F[+F][+F]F[FF][ – F][ – F], где α =90º и θ = 15º.

Фрактал построен по типу известного фрактала «Цветок» [5]. Начало построения – вертикально вверх α =90º, а далее ветвление с углом θ = 15º или кратным ему.

Результат работы алгоритма в виде изображения фрактала 5-го порядка приведен на рисунке Е.2 Приложения Е.

Заключение

В ходе работы над исследовательским проектом мы выполнили все поставленные задачи, а именно:

изучили понятие «фрактал» и познакомились с областями его применения;

познакомились с некоторыми алгоритмами построения фрактальных объектов – методом временного порога и L-графикой;

изучили построение множества Мандельброта и показали, как работает этот метод на своём примере;

изучили построение Снежинки Коха и Снежинки с использованием операции ветвления, все построения мы выполнили вручную, а также с помощью программного средства LGraphics;

разработали свои алгоритмы построения фракталов на основе L-графики для описания таких природных объектов, как «Облака» и «Ветка полыни».

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

Работая над проектом, мы получили новые знания по математике и информатике, которые необходимо углублять, чтобы иметь возможность использовать фрактальные объекты для решения важных научных проблем и задач, как это делал Бенуа Мандельброт.

Список литературы

1 Бенуа Мандельброт [Электронный ресурс]. URL: http://www.incunabula.ru/blogs/people/2010/10/18/benua-mandel-brot.php (дата обращения: 18.02.18г.)

2 URL: http://nmetau.edu.ua/file/metodichka_io_sinergetiki.pdf (дата обращения: 18.02.18г.)

3 Компьютерная графика что такое? Виды компьютерной графики [Электронный ресурс]. URL: http://fb.ru/article/190005/kompyuternaya-grafika-chto-takoe-vidyi-kompyuternoy-grafiki(дата обращения: 18.02.18г.)

4 Моделирование и анализ пространственных и временных объектов [Электронный ресурс]. URL: http://labfer.ins.urfu.ru/common/pdf/fractal.pdf (дата обращения: 18.02.18г.)

5 Нургалиев А. Фракталы [Электронный ресурс]. URL: http://codemore.ru/2014/01/19/fractals.htm (дата обращения: 18.02.18г.)

Приложение А

(справочное)

Бенуа Мандельброт – французский и американский математик, создатель фрактальной геометрии. Лауреат премии Вольфа по физике (1993)

«Если вы разрежете один из цветков цветной капусты, то вы увидите, что в руках у вас останется та же цветная капуста, только меньшего размера. Вы можете продолжать резать снова и снова, но все, что вы получите – это маленькие копии цветной капусты».

Будущий ученый никак себя не проявлял до совершеннолетия. Но у Бенуа Мандельброта открылся необычный математический дар – великолепное пространственное воображение. Даже алгебраические задачи он решал геометрическим способом. Оригинальность его решений позволила ему поступить в университет Сорбонны в Париже, а затем в Калифорнийский институт технологии США. В середине 1960-х годов он разработал теорию фрактальной геометрии, или геометрии природы. Целью фрактальной геометрии был анализ сломанных, «морщинистых» и нечетких форм. В 1977 и 1982 годах он публикует работы, посвященные «фрактальной геометрии» или «геометрии природы». В них он утверждал, что на первый взгляд случайные математические формы на самом деле следуют образцу, если их разбить на отдельные повторяющиеся формы.

Концепция Мандельброта позволила ученым измерить ранее неизмеримые объекты, в том числе береговую линию Британских островов, облака, легкие человека или цветную капусту. Фрактальная геометрия помогла осуществить новые технологические разработки в области цифровой музыки и сжатия изображений. Открытие Мандельброта также имело далеко идущие последствия для физики, биологии и астрономии. Ученый умер 4 октября 2010 года в Кембридже (Массачусетс, США), в возрасте 85 лет.

Приложение Б

(справочное)

Рисунок Б.1 – Фракталы, построенные по методу временного порога

Приложение В

(обязательное)

Таблица В.1

Приложение Г

(обязательное)

Рисунок Г. 1 – Картинки к каждому шагу алгоритма

Приложение Д

(обязательное)

Рисунок Д.1 – Пример построения снежинки Коха 1-го порядка в LGraphics

Рисунок Д.2 – Пример построения Снежинки 0-го порядка в LGraphics.

Приложение Е

(обязательное)

Рисунок Е.1 – Фрактал «Облака»

Рисунок Е.2 – Фрактал «Ветка полыни»