» » »

3.Двумерные алгоритмы Понятие о рекурсии. Понятие о фракталах. Сглаживание кривых

3.Двумерные алгоритмы Понятие о рекурсии. Понятие о фракталах. Сглаживание кривых.

Рекурсия

В программировании рекурсия — вызов функции (процедуры) из неё же самой, непосредственно (простая рекурсия) или через другие функции (сложная рекурсия), например, функция A вызывает функцию B, а функция B — функцию A. Количество вложенных вызовов функции или процедуры называется глубиной рекурсии.

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

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

Впрочем, имеется специальный тип рекурсии, называемый «хвостовой рекурсией». Интерпретаторы и компиляторы функциональных языков программирования, поддерживающие оптимизацию кода (исходного и/или исполняемого), автоматически преобразуют хвостовую рекурсию к итерации, благодаря чему обеспечивается выполнение алгоритмов с хвостовой рекурсией в ограниченном объёме памяти. Такие рекурсивные вычисления, даже если они формально бесконечны (например, когда с помощью рекурсии организуется работа командного интерпретатора, принимающего команды пользователя), никогда не приводят к исчерпанию памяти. Однако, далеко не всегда стандарты языков программирования чётко определяют, каким именно условиям должна удовлетворять рекурсивная функция, чтобы транслятор гарантированно преобразовал её в итерацию. Одно из редких исключений — язык Scheme (диалект языка Lisp), описание которого содержит все необходимые сведения.

Любую рекурсивную функцию можно заменить циклом и стеком.

§  См. также примеры реализации функции факториал

Данные

Описание типа данных может содержать ссылку на саму себя. Подобные структуры используются при описании списков и графов. Пример описания списка (C++):

 class element_of_list

 {

   element_of_list *next; /* ссылка на следующий элемент того же типа */

   int data; /* некие данные */

 };

Рекурсивная структура данных зачастую обуславливает применение рекурсии для обработки этих данных.

 

Фрактал (лат. fractus — дробленый, сломанный, разбитый) — сложная геометрическая фигура, обладающая свойством самоподобия, то есть составленная из нескольких частей, каждая из которых подобна всей фигуре целиком. В более широком смысле под фракталами понимают множества точек вевклидовом пространстве, имеющие дробную метрическую размерность (в смысле Минковского или Хаусдорфа), либо метрическую размерность, строго большую топологической.

Фрактал — это бесконечно самоподобная геометрическая фигура, каждый фрагмент которой повторяется при уменьшении масштаба.

Фрактал — самоподобное множество нецелой размерности.

Сжатие изображений

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

Компьютерная графика

Фракталы широко применяются в компьютерной графике для построения изображений природных объектов, таких, как деревья, кусты, горные ландшафты, поверхности морей и так далее. Существует множество программ, служащих для генерации фрактальных изображений, см. Генератор фракталов (программа).

 

СГЛАЖИВАНИЕ КРИВЫХ

   В автоматизированном проектировании и управлении станками часто требуется построить гладкую кривую по набору заданных точек. Ограничимся пока анализом плоских кривых.

Из нескольких возможных способов построения гладких кривых выберем форму В-сплайна. Из заданной последовательности точек выбираются две соседние точки и между ними строится кривая кубического полинома на основе позиций четырех точек – двух уже упомянутых и двух соседних с ними точек. В-сплайн обеспечивает получение более гладких кривых, чем другие способы сглаживания за счет того, что получаемые кривые не проходят точно через заданные точки. Математическая гладкость кривых выражается в терминах непрерывности параметрических представлений  x(t) и y(t)  и их производных. К типа В-сплайна обладают свойством непрерывности даже вторых производных  x’’(t) и y’’(t) в точке стыковки двух соседних сегментов кривой. На рисунке показано, как выглядят кривые , если нулевая, первая или вторая производная не непрерывны в некоторой точке .

Последняя кривая может считаться гладкой, но она не удовлетворяет строгим требованиям, которые выполняются в способе В-сплайна.

  Рассмотрим этот метод в работе. Будем использовать параметрическое представление кривых. Любая точка части кривой между двумя заданными последовательными точками P и Q будет иметь координаты x(t) и y(t), где t увеличивается от 0 до 1, если отслеживается часть кривой от точки P до точки Q. Можно считать, что t – это время. Если имеются заданные точки

 P0 (x0, y0)

P1(x1 y1)

  ...

Pn(xn yn),

То часть кривой В-сплайна между двумя последовательными точками Pi  и Pi+1 получается путем вычисления значений функций x(t) и y(t) для изменения t  от 0 до 1

    x(t) = {(a3t + a2) t + a1}t +a0

     y(t) = {(b3t + b2) t + b1}t +b0

Эти уравнения содержат следующие коэффициенты:

a3 = (- xi-1 + 3 xi – 3 xi+1 + xi+2)/6

a2 = (xi-1 – 2 xi+ xi+1)/2

a1 = (- xi-1 + xi+1)/2

a0 = (xi-1 + 4 xi + xi+1)/ 6,

  а коэффициенты b1, b2, b3, b4 вычисляются по значениям yi-1, yi, yi+1/ yi+2 аналогичным образом..

 


Друзья! Приглашаем вас к обсуждению. Если у вас есть своё мнение, напишите нам в комментарии.

Поделиться

Оплаченная реклама

Дисциплины