Кривая - гильберт
Cтраница 1
 |
Время выполнения программы по вычислению чисел Фибоначчи. [1] |
Кривые Гильберта ( Hilbert curves) - это самоподобные кривые, которые обычно определяются рекурсивно. На рис. 5.2 изображены кривые Гильберта 1 -го, 2-го, и 3-го порядка. [2]
 |
Кривые Гильберта, составленные из меньших кривых. [3] |
Например, кривая Гильберта 2-го порядка состоит из четырех кривых Гильберта 1-го порядка. Точно так же кривая Гильберта 3-го порядка составлена из четырех кривых Гильберта 2-го порядка, каждая из которых включает четыре кривых Гильберта 1 -го порядка. На рис. 5.3 изображены кривые Гильберта 2-го и 3-го порядка. Меньшие кривые, из которых построены кривые большего размера, выделены жирными линиями. [4]
Для рисования кривых Гильберта с помощью этого рекурсивного алгоритма предназначена программа Hilbl, показанная нарис. При запуске этой программы не задавайте слишком большую глубину рекурсии ( больше 6) до тех пор, пока вы не определите, насколько быстро она работает на вашем компьютере. [5]
 |
Окно программы Sierpl. [6] |
Каки алгоритм построения кривых Гильберта, этот алгоритм выполняется в течение времени О ( 4), но это не означает, что он не эффективен. [7]
Сдругой стороны, нерекурсивные версии алгоритмов рисования кривых Гильберта и Серпинского достаточно сложны. [8]
Следующий код иллюстрирует нерекурсивную версию процедуры рисования кривых Гильберта. [9]
Например, кривая Гильберта 2-го порядка состоит из четырех кривых Гильберта 1-го порядка. Точно так же кривая Гильберта 3-го порядка составлена из четырех кривых Гильберта 2-го порядка, каждая из которых включает четыре кривых Гильберта 1 -го порядка. На рис. 5.3 изображены кривые Гильберта 2-го и 3-го порядка. Меньшие кривые, из которых построены кривые большего размера, выделены жирными линиями. [10]
Второй факт, которыйдоказываетдостоинства описанного алгоритма, заключается в следующем: кривая Гильберта порядка 9 содержит так много линий, что большинство компьютерных мониторов становятся полностью закрашенными. Это не удивительно, поскольку кривая содержит 262 143 сегментов линий. Поэтому вам, вероятно, никогда не понадобится выводить на экран кривые Гильберта 9-го или более высоких порядков. [11]
Эта процедура инициируется главной программой по одному разу для каждой из кривых Гильберта, образующих приведенный рисунок. [12]
Если использовать те же примитивы рисования, что и в случае кривых Гильберта, то приведенные рекурсивные схемы без труда трансформируются в ( прямо или косвенно) рекурсивный алгоритм. [13]
Еще один пример рекурсии - программа, которая вычерчивает в диалоговом окне кривую Гильберта. На рис. 12.7 приведены кривые Гильберта первого, второго и третьего порядков. [14]
Затем в главе рассматривается несколько примеров, в которых применение рекурсии более уместно. Алгоритмы построения кривых Гильберта и Серпинско-го используют рекурсию должным образом и очень эффективно. [15]
Страницы: 1 2