|
Разработка программы для построения кривых Серпинского i-го порядка
Формализация задачи Оригинальный узор на рисунке 1
состоит из суперпозиции четырех кривых. Эти кривые соответствуют некоторому
регулярному образу. Алгоритм для построения этих кривых на экране монитора или
на графопостроителе под управлением вычислительной машины описан в
[1]. – реализовать этот алгоритм в виде
программы на функциональном языке программирования Lisp. Анализируя рисунок 1, можно
обнаружить, что он получен путем наложения друг на друга нескольких кривых.
Первые две из них показаны на рисунке 2. Кривая S -го порядка. Необходимо выяснить,
какова рекурсивная схема этих кривых. Главная особенность кривой
Серпинского состоит в том, что она замкнута и в ней нет пересечений. Это
означает, что основная рекурсивная схема должна давать разомкнутую кривую
линию, четыре части которой соединяются линиями, не принадлежащими самому
рекурсивному образу. И действительно, эти замыкающие линии представляют собой
отрезки прямых в четырех внешних углах, на рисунке 2 они выделены жирными
линиями. Можно считать, что они принадлежат к непустой начальной кривой S –
квадрату, "стоящему" на одном углу. Теперь достаточно легко составить
рекурсивную схему. , а процедуры, рисующие
соединительные прямые, будем обозначать стрелками, указывающими соответствующем
направлении. Надо отметить, что четыре рекурсивных образа по существу идентичны,
но лишь повертываются на 90 S: A D а рекурсивные составляющие (горизонтальные и вертикальные отрезки –
двойной длины): æ A ß A Предположим, что для построения части прямой в нашем распоряжении есть
процедура , передвигающая перо в заданном направлении на
заданное расстояние, причем направление задается целочисленным параметром
градусов. Если единичную прямую обозначить через
и к самой ( cond ( ( > k 0 ) ( D ( - k 1 )
) ( Line 7 h ) Эта процедура
инициируется главной программой по одному разу для каждой кривой Серпинского,
образующих приведенный рисунок. Употребление явного параметра для уровня
гарантирует окончание работы, так как глубина рекурсии не может быть больше
. Ее
задача - установить начальную точку кривой, т.е. исходные координаты пера
( . Квадрат, где рисуется кривая, помещается в середине
экрана, заданной ширины и высоты. По сравнению с
таким рекурсивным построением эквивалентные программы, где избегали употребления
рекурсии, выглядят крайне сложными и запутанными. Рисунок 3 Схема алгоритма главной процедуры SIERPINS.LSP для XLISP версии
2.1 Переменная
*VMode* управляет установкой видео режима, ;; Эта установка соответствует
режиму 640x480 Color, ;; с установкой этого режима необходимо
выбрать ;;
*MaxX* 640 ) ;Максимальная ширина экрана по умолчанию *SquareSize* 256 ) ;Размер области для
построения ;; *MaxX* *MaxY* *SquareSize* в соответствии с
выбранным режимом ( 4
;320x200 Color ( 16
;640x350 Color ( 18
;640x480 Color 106 106 800 600 ) Unsupported graphics mode: *VMode* ) ) defun
( get-internal-run-time ) ) ) ) ( return-from pause
) ) ) ) round ;; Параметры:
<Direction> - направление рисования (0-7) ( ( 3 ( setq x ( + x Size ) y ( + y Size ) )
) ;; Функции A, B, C, D - рекурсивные функции
рисования ( A ( - k 1 ) ) ( Line 1 h ) ( A ( - k 1 ) ) ( B
( - k 1 ) ) ( Line 3 h ) ( B ( - k 1 )
) ( C ( - k 1 ) ) ( Line 5 h ) ( C ( - k 1 ) ) ( D
( - k 1 ) ) ( Line 7 h ) ( D ( - k 1 )
) ;; ( x0 ( div *MaxX* 2 ) ) ;Вычисление
начальной точки ( ;Основной цикл i ( + Count 1 ) ) 'Done ) ;Условие завершения h ( div h 2 ) ) ;точки для рисования и Px x0 Py y0 ) ;Установка пера
( A i ) ( Line 1 h ) ;Рисование ( i ( + i 1 )) ;Инкримент счетчика Try (SierpinskiCurve 4) )
;Подсказка x86 персональный компьютер (386 минимум; 486, Pentium,
или Pentium Pro рекомендуется) Microsoft Windows 3.1, Microsoft Windows for Workgroups, Microsoft Windows
95, Microsoft Windows NT 3.51 или 4.0 Установленный интерпретатор
XLisp версии 2.1 или выше Загрузить
интерпретатор XLisp c параметром "Sierpins.lsp": В
ответ на приглашение XLisp ввести: (SierpinskiCurve 4) Тест проводился
на рабочей станции со следующей конфигурацией: Windows 95 Программа тестировалась при значениях параметра
Рисунок 5 Рисунок 8 "XLisp-Plus 2.1
Programmers Manual", David Michael Betz
| |
