Используя рекурсивную процедуру построить фигуру дерево пифагора. Open Library - открытая библиотека учебной информации. Функция построения дерева Пифагора на языке С
Следующим примером может быть известное "Пифагорово дерево". Оно часто изображается так, как показано на рис. 3.2. Каждый из прямоугольных треугольников в этом дереве имеет внутренний угол, равный 45°.
Опять воспользуемся генератором случайных чисел для создания более общей программы, которая может сформировать не только рис. 3.2, но также генерировать и менее регулярные деревья. Углы, задаваемые равными 45° для рис. 3.2, в общем случае будут задаваться случайным образом в пределах между (45 - delta) ° и (45 + delta) °, где значение delta задается в качестве входного параметра вместе с параметром n, определяющим глубину рекурсии. Регулярная версия, изображенная на рис. 3.2, получается при задании delta = 0 и n = 7. На рисунке параметр п определяет количество треугольников на пути от корня до листьев дерева. Сердцевиной программы будет рекурсивная функция square_and_triangle ("квадрат и треугольник") с параметром n, определяющим глубину рекурсии, в качестве первого аргумента. В случае если значение параметра n больше нуля, то задачей функции square_and_triangle, как это определяется названием, будет вычертить квадрат и над ним треугольник, а затем еще дважды обратиться к самой себе с соответствующими новыми аргументами, первый из которых задается равным n-1. Размер и положение квадрата полностью определяются четырьмя параметрами: X0,Y0, а и j (см. рис. 3.3). Для вычерчивания треугольника крайне важно знать угол a. Этот угол, выраженный в градусах, равен 45+deviation , где deviation равно одному из целых чисел ряда -delta, -delta+I, ... , delta, выбираемому случайным образом. На рис. 3.3 необходимые точки пронумерованы последовательными числами 0,1,2,3,4. Координаты X0 , Y0 точки О задаются в обращении к функции. Для вычисления остальных точек вначале рассмотрим более простую ситуацию при j = 0 , то есть когда сторона 0 1 квадрата занимает горизонтальное положение.
 |
/* PYTH_TREE: Вариант дерева Пифагора */
#include "math.h"
#include "stdlib.h"
#include "time.h"
#define pi 3.1415927
#include "stdio.h"
struct {float xx; float yy; int ii;} s;
void pfopen(){ fp=fopen("scratch", "wb"); }
void pmove(float x,float y)
{ s.xx=x; s.yy=y; s.ii=0; /* 0 = pen up */ /* 0 = перо поднято */
fwrite(&s, sizeof s, 1, fp);
void pdraw(float x,float y)
{ s.xx=x; s.yy=y; s.ii=1; /* 1 = pen down */ /* 1 = перо опущено */
fwrite(&s, sizeof s, 1, fp);
void pfclose(){ fclose(fp); }
void square_and_triangle(int n,float x0,float y0, float a, float phi)
{ float x, y, xx, yy, cphi, sphi, c1, c2, b, c,
alpha, calpha, salpha;
int i, deviation; /* phi and alpha in radians */
/* delta in degrees */
if(n==0) return; /* углы phi и alpha в радианах */
/* угол delta в градусах */
deviation=rand()%(2*delta+1)-delta;
alpha=(45+deviation)*pi/180.0;
x=x=x0; x=x=x0+a;
y=y=y0; y=y=y0+a;
calpha=cos(alpha); salpha=sin(alpha);
c=a*calpha; b=a*salpha;
/* Rotation about (x0, y0) through angle phi ; */
/* Поворот вокруг точки (x0, y0) на угол phi;*/
cphi=cos(phi); sphi=sin(phi);
c1=x0-x0*cphi+y0*sphi;
c2=y0-x0*sphi-y0*cphi;
for (i=0; i<5; i++)
{ xx[i]=x[i]*cphi-y[i]*sphi+c1;
yy[i]=x[i]*sphi+y[i]*cphi+c2;
for (i=0; i<5; i++) pdraw(xx[i],yy[i]);
square_and_triangle(n-1, xx, yy, c, phi+alpha);
square_and_triangle(n-1, xx, yy, b, phi+alpha-0.5*pi);
pfopen(); time(&seed); srand((int)seed);
printf (" Задайте угол delta в градусах (0 < delta < 45) ");
scanf("%d", &delta);
printf(" Задайте глубину рекурсии n "); scanf("%d", &n);
square_and_triangle(n, 0.0, 0.0, 1.0, 0.0);
Эта программа формирует файл SCRATCH, который должен быть обработан программой GENPLOT из лекции 2. Графический результат работы программы для delta = 30 и п = 7 показан на рис. 3.4.
Привет, друзья, интересующиеся фракталами и не только. Начиная с этого момента, я запускаю серию постов, в которых буду объяснять принципы построения простейших фракталов. Изучать всегда интересно и я помогу вам в этом: отныне мы будем знать многие и многие фракталы. Аттрактор Лоренца в статье про хаос был тому примером. А сегодня я расскажу вам про дерево Пифагора.
Итак, что это такое? Дерево Пифагора – это простейший фрактал, который можно начертить на бумаге. Но почему этот фрактал называется деревом Пифагора? Дело в том, что здесь есть связь с теоремой Пифагора – одной из основ евклидовой геометрии. Помните ее? Я напомню: а2 + b2 = c2 (сумма квадратов длин катетов равна квадрату длины гипотенузы). Эта теорема известна с древности, доказательств теоремы в настоящее время насчитывают более 400, и только Пифагор впервые доказал ее геометрически. Он построил такую фигуру: взял прямоугольный треугольник и на его сторонах нарисовал квадраты. Такая фигура еще называется «Пифагоровы штаны»:
Если продолжить данную конструкцию рекурсивно, то мы получаем в итоге дерево Пифагора:
1 итерация (в нашем дереве Пифагора угол равен 45 градусам):
Вторая итерация:
Третья итерация:
Десятая итерация:
Важное свойство дерева Пифагора: если площадь первого квадрата равна единице, то на каждом уровне сумма площадей квадратов тоже будет равна единице.
Если угол изменить с 45 градусов, то можно построить и другие типы дерева Пифагора.
Вот, к примеру, так называемое «обдуваемое ветром дерево Пифагора»:
В некоторых генераторах фрактальной графики реализована формула построения фрактала на основе дерева Пифагора. Эта реализация очень напоминает IFS – системы, особенно если заменить квадраты на прямоугольники или вытянутые фигуры.
На сегодня всё, до следующих встреч, в которых будет много других интересных фракталов)
Особенности
Одним из свойств дерева Пифагора является то, что если площадь первого квадрата равна единице, то на каждом уровне сумма площадей квадратов тоже будет равна единице.
Если в классическом дереве Пифагора угол равен 45 градусам, то также можно построить и обобщённое дерево Пифагора при использовании других углов. Такое дерево часто называют обдуваемое ветром дерево Пифагора . Если изображать только отрезки, соединяющие каким-либо образом выбранные «центры» треугольников, то получается обнаженное дерево Пифагора .
Примеры
Pythagoras tree 1.gif
Классическое дерево Пифагора
Pythagoras tree 2.gif
Обдуваемое ветром дерево Пифагора
Pythagoras tree 3.gif
Обнаженное дерево Пифагора
Pythagoras tree 4.gif
Обнаженное обдуваемое ветром дерево Пифагора
См. также
Напишите отзыв о статье "Дерево Пифагора"
Отрывок, характеризующий Дерево Пифагора
В то время как Россия была до половины завоевана, и жители Москвы бежали в дальние губернии, и ополченье за ополченьем поднималось на защиту отечества, невольно представляется нам, не жившим в то время, что все русские люди от мала до велика были заняты только тем, чтобы жертвовать собою, спасать отечество или плакать над его погибелью. Рассказы, описания того времени все без исключения говорят только о самопожертвовании, любви к отечеству, отчаянье, горе и геройстве русских. В действительности же это так не было. Нам кажется это так только потому, что мы видим из прошедшего один общий исторический интерес того времени и не видим всех тех личных, человеческих интересов, которые были у людей того времени. А между тем в действительности те личные интересы настоящего до такой степени значительнее общих интересов, что из за них никогда не чувствуется (вовсе не заметен даже) интерес общий. Большая часть людей того времени не обращали никакого внимания на общий ход дел, а руководились только личными интересами настоящего. И эти то люди были самыми полезными деятелями того времени.Те же, которые пытались понять общий ход дел и с самопожертвованием и геройством хотели участвовать в нем, были самые бесполезные члены общества; они видели все навыворот, и все, что они делали для пользы, оказывалось бесполезным вздором, как полки Пьера, Мамонова, грабившие русские деревни, как корпия, щипанная барынями и никогда не доходившая до раненых, и т. п. Даже те, которые, любя поумничать и выразить свои чувства, толковали о настоящем положении России, невольно носили в речах своих отпечаток или притворства и лжи, или бесполезного осуждения и злобы на людей, обвиняемых за то, в чем никто не мог быть виноват. В исторических событиях очевиднее всего запрещение вкушения плода древа познания. Только одна бессознательная деятельность приносит плоды, и человек, играющий роль в историческом событии, никогда не понимает его значения. Ежели он пытается понять его, он поражается бесплодностью.
Занимаясь изучением алгоритмов обнаружения событий электрокардиограммы для исследовательской части дипломной работы, я обнаружил, что длительность R-R интервала кардиограммы, вычисленная даже с точностью до второго знака после запятой, достаточно точно характеризует сердечнососудистую систему конкретного человека. Поскольку я уже довольно давно увлекаюсь фрактальной геометрией, в моей голове моментально родилась мысль, как можно придать «личных» качеств какому-нибудь простейшему фрактальному объекту.
Так появилось «Электрокардиографическое дерево Пифагора».
Теоретическая часть – 1. Об электрокардиограмме
Графическая запись разности потенциалов, создающихся между различными участками сердечной мышцы в процессе ее возбуждения, называется электрокардиограммой (ЭКГ). Ориентация и величина этих потенциалов сердца на электрокардиограмме выражаются в амплитуде зубцов и их направленности (полярности) по отношению к изоэлектрической линии. И охватывают диапазон 0,15…300 Гц при уровне сигналов 0,3…3 мВ.Нормальная ЭКГ состоит из зубцов и горизонтально расположенных между ними отрезков (сегментов) линий (Рисунок 1).
Рисунок 1 – Схематическое изображение нормальной электрокардиограммы.
В клинической практике применяются отведения от различных участков поверхности тела. Эти отведения называются поверхностными. При регистрации ЭКГ обычно используется 12 общепринятых отведений, шесть от конечностей и шесть грудных. Первые три стандартных отведения были предложены Эйнтховеном. Частота сокращений сердца (ЧСС) определяется по продолжительности одного сердечного цикла, т.е. по продолжительности интервала R – R.
Стандартным и наиболее удобным для определения ЧСС является II-отведение по Эйнтховену, т.к. в нем наибольшую амплитуду имеет именно зубец R.
Практическая часть – 1
Для расчетов будем использовать реальную ЭКГ здорового человека во II-отведении по Эйнтховену, полученную из базы данных физиологических сигналов .Параметры ЭКГ:
Разрешение АЦП 12 бит;
Частота семплирования 100 Гц;
Длительность 10 секунд;
Рисунок 2 – Изображение нормальной ЭКГ из БД.
Далее определим QRS-комплекс, чтобы потом из него выделить зубец R. Для этого воспользуемся алгоритмом, основанном на взвешенном и возведенном в квадрат операторе первой производной и на фильтре скользящего среднего .
Звучит сложнее, чем выглядит:
Где x(n) - сигнал ЭКГ, N -ширина окна, в пределах которого разность первого порядка вычисляется, возводится в квадрат и взвешивается с использованием, коэффициента (N-i+1) .
Взвешивающий коэффициент линейно спадает, начиная от текущей разности, до разности вычисленной на N отсчетов ранее по времени, что обеспечивает сглаживающий эффект.
Дальнейшее сглаживание выполняется с использованием фильтра скользящего среднего по M точкам:
При частоте дискретизации 100Гц ширина окна фильтра устанавливается как M=N=8 . Данный алгоритм дает единственный пик для каждого QRS-комплекса и подавляет зубцы P и Т. В результате обработки, получаем следующий вид ЭКГ (Рисунок 3).
Рисунок 3 – Изображение ЭКГ после фильтрации.
Поиск зубца R в обработанном сигнале может быть выполнен с помощью простого алгоритма поиска пиков:
1. Сканирование фрагмента сигнала g(n)
, на котором ожидается наличие пика, и определение максимальной величины gmax
.
2. Определение порога, как некоторой доли от максимума, Th=0.8gmax
.
3. Для всех g(n)>Th выбираются те отсчеты, для которых соответствующие величины g(n)
больше, чем определенное заданное число M
предыдущих или последующих отсчетов g(n)
.
Определенный таким образом набор {p}
содержит индексы всех найденных в сигнале g(n)
пиков.
Пики, вызванные артефактами, можно отбраковать дополнительными условиями, например - минимальный интервал между двумя соседними пиками.
Рисунок 4 – Изображение ЭКГ с отмеченными R-зубцами.
Далее стоит сама простая задача - определение средней длины R-R интервала данной ЭКГ. И в этом случае она равна 733мс. «По фану» рассчитаем ЧСС: 60/0.733=81.85 ударов/мин. Теперь у нас есть величина, характеризующая работу сердца конкретного человека.
Небольшое пояснение:
Сердце – не метроном, оно не может выстукивать такт с равными временными промежутками между ударами. R-R интервал для здорового человека колеблется в небольших пределах. Если колебания интервала будут значительными – это свидетельствует о наличии аритмий и других нарушений. Механизм колебаний является очень сложным комплексом процессов, связанным с электрической проводимостью конкретного сердца.
Используя величину среднего R-R интервала в качестве параметра при построении дерева Пифагора можно придать ему «неповторимые» («личные») черты.
Теоретическая часть – 2. О фракталах
Фракталами называются геометрические объекты: линии, поверхности, пространственные тела, имеющие сильно изрезанную форму и обладающие свойством самоподобия. Основоположник теории фракталов франко-американский математик Бенуа Мандельброт образовал термин фрактал от латинского причастия fractus. Соответствующий глагол frangere переводится, как ломать, разламывать, т.е. создавать фрагменты неправильной формы. Самоподобие, предопределяет масштабную инвариантность (скейлинг) основных геометрических особенностей фрактального объекта, их неизменность при изменении масштаба. Повторяемость изрезанности линий фрактальных объектов может быть полной (в этом случае говорят о регулярных фракталах), либо может наблюдаться некоторый элемент случайности (такие фракталы называют случайными). Структура случайных фракталов на малых масштабах не является точно идентичной всему объекту, но их статистические характеристики совпадают.Дерево Пифагора - разновидность геометрического регулярного фрактала, основанная на фигуре, известной как «Пифагоровы штаны» .
Принцип построения геометрического фрактала - рекурсия.
Практическая часть – 2
Алгоритм построения дерева Пифагора:1) Строим вертикальный отрезок;
2) Из верхнего конца этого отрезка рекурсивно строим еще 2 отрезка меньшей длины под углом 90° друг к другу;
3) Вызываем функцию построения двух последующих отрезков для каждой ветви дерева;
Функция построения дерева Пифагора на языке С.
Void Draw(double x, double y, double L, double a) {
if(L > max) {
L*=0.7;
moveto(x,y);
lineto((int)(x+L*cos(a)),(int)(y-L*sin(a)));
x=x+L*cos(a);
y=y-L*sin(a);
Draw(x,y,L,a+Pi/n);
Draw(x,y,L,a-Pi/m);
}
}
Рисунок 5 – дерево Пифагора для ЭКГ при R-R: 733ms.
Единственное, что осталось изменить - это в качестве переменной L использовать в программе вычисленную длину среднего R-R интервала ЭКГ.
Таким образом можно получить «личное» дерево Пифагора, которое будет «дышать», в зависимости от физической нагрузки, а длина ветвей и их закрученность - «максимально точно описывать» вашу личность.
Список литературы
1. Исследовательский ресурс сложных физиологических сигналов:Если самая большая площадь имеет размеры L × L, все дерево Пифагора плотно помещается в коробку размером 6L × 4L. Тонкости дерева напоминают кривую Леви .
Построение
Построение дерева Пифагора начинается с квадрата. По этой площади построены два квадрата, каждый уменьшен линейным коэффициентом ½ √ 2, так что углы квадратов совпадают попарно. Такая же процедура применяется рекурсивно , то к двум - еще меньшие квадраты, до бесконечности. На рисунке ниже показаны первые несколько итераций в процессе строительства.
Площадь
N - итерация в строительстве добавляет 2n квадраты размером (½ √ 2) N, в общей площади 1. Таким образом, может показаться, в этой части дерево растет неограниченно в пределе N → ∞. Тем не менее, некоторые из площадей перекрываются, начиная с порядка 5 итерации , и дерево на самом деле имеет конечную площадь, поскольку она соответствует размерам в 6 × 4. Это нетрудно доказать, что площадь А дерева Пифагора должна быть в диапазоне от 5 <А <18, которая может быть сужена в дальнейшем дополнительными усилиями.
Изменение угла
Интересный набор вариаций может быть построен путем поддержания равнобедренного треугольника, но изменения базового угла (90 градусов для стандартного дерева Пифагора). В частности, когда базовый половинный угол составляет 30 ° = арксинус (0.5), легко видеть, что размер клеток остается постоянным. Первое перекрытие происходит на четвертой итерации. Общая схема является по сути, ромббитригексагональной плиткой, где массив из шестиугольников граничит с конструкцией квадратов.
В пределе , когда половинный угол составляет 90 градусов, то, очевидно, не перекрываются, и общая площадь в два раза превышает площадь основания квадрата. Было бы интересно узнать, есть ли связь между алгоритмическим значением базового половинного угла и итерации, на которой квадраты накладываются друг на друга.
Измененное и модифицированное дерево Пифагора (фрактал) для применения в антенной технике.
Использование оригинального фрактального дерева Пифагора (UPTF ) изобретено голландским математиком, Альберт E.Босманом в 1942 году. Дерево Пифагора является 2D фракталом построенным из квадратов. Как уже описывалось ранее, начиная с пятой итерации некоторые из площадей перекрываются, и дерево - фрактал фактически имеет конечную площадь, поскольку она помещается в размер 6 × 4 - коробки. По этой причине необходимо задержать перекрытие пальцами левой и правой руки UPTF в 4-й итерации, таким образом, мы проектируем MPT - фрактал путем устранения первых итераций большой площади и изменим равнобедренный прямоугольный треугольник равнобедренным треугольником с крутыми углами (α = 10 град), чтобы уменьшить высоту фрактала и спроектировать компактные антенны. Наша цель в проектировании ЛПУ является использование этого фрактала для управления пропускной способностью и сопротивлением резонансов. На основе результатов моделирования изменения дерева Пифагора замечена очень хорошая возможность миниатюризации из-за его свойства самоподобия, без значительного снижения пропускной способности и эффективности антенны.
Фламандский художник Jos de Mey создал много работ с деревом Пифагора в качестве основного мотива. Ниже вы можете увидеть его работы.
http://demonstrations.wolfram.com/PythagorasTree/ - Фрактальная конструкция, основанная на теореме Пифагора. Это асимметричный вариант; симметричный вариант также возможен.
http://demonstrations.wolfram.com/download-cdf-player.html - скачать плеер для просмотра
Источник : http://en.wikipedia.org/wiki/Pythagoras_tree_(fractal)
Перевод: Дмитрий Шахов