Поддержи Openmeetings

вторник, 4 декабря 2012 г.

L-системы

L-системы — компактный способ описания изображений, похожих на деревья и не только. Строго говоря, каждая конкретная L-система может сгенерировать простую строку символов, а уже её по определённым правилам можно превратить в картинку. L-системы придумал венгр Аристид Линденмайер (отсюда и буква L).

Число итераций:
Угол поворота:
Константы:
Аксиома:
Правило 1:
Правило 2:
Правило 3:
Правило 4:
Правило 5:

Нажмите , чтобы начать.

Примеры







Общее описание L-систем и простой пример

Формально L-система представляет собой следующее.

  1. Начальную строку символов, называемую «аксиомой».
  2. Правила замены одних символов на другие.
  3. Правила сопоставления символам некоторых действий на холсте, где рисуется изображение, соответствующее данной L-системе.

Возьмём, например, так называемую кривую дракона, а именно дракона Хартера — Хейтуэя (нажмите соответствующую кнопку, чтобы увидеть его). Аксиома для него имеет вид X, правил два, они указаны в соответствующих полях. Применяя правила к аксиоме (первая итерация), получаем строку X+Y. Применяя правила к этой строке ещё раз (вторая итерация), причём делая это строго одновременно, получаем строку X+Y+X-Y. Эта операция проделывается заданное количество раз. После этого мы объявляем, что буквам X и Y соответствует шаг с рисованием линии, а знакам «плюс» и «минус» — повороты направления рисования направо и налево соответственно. Результатом становится кривая, которую вы видите.

Попробуйте установить общее количество итераций равным 1, 2 и 3, чтобы увидеть, как после первой итерации рисуется уголок, задаваемый строкой X+Y; затем рисуется более длинная кривая, полученная после двукратного применения правил замены, и так далее.

Фракталы

Фрактал — это геометрическая фигура дробной размерности. Обычно работают с самоподобными фракталами: это фигура (часто очень красивая), маленькая часть которой в точности совпадает со всей фигурой или её большей частью. Фракталы придумал французский и американский математик Бенуа Мандельброт. В честь него назван любопытный и красивый фрактал — множество Мандельброта; не забудем также родственные ему множества Жюлиа. Но эти фракталы не имеют прямого отношения к нашей теме.

Однако иные фракталы можно описать именно с помощью L-систем. Взглянем на снежинку Коха (нажмите соответствующую кнопку, чтобы увидеть её). Она строится так: рисуется треугольник, каждая его сторона заменяется на отрезок с зубцом (так что вместо одного отрезка получается ломаная из четырёх отрезков), каждый из этих новых отрезков также заводит себе зубец, и так до бесконечности. Мы можем изобразить результат лишь конечного числа итераций, но понятно, что существует геометрическая фигура, являющаяся результатом бесконечного числа таких преобразований (и это будет весьма интересная линия: ограничивая конечную площадь, она имеет бесконечную длину; строго говоря, это не совсем линия, её размерность больше 1, хоть и меньше 2). И одна сторона такой снежинки — самоподобна в том смысле, что в ней можно выделить фрагмент, являющейся её точной уменьшенной копией.

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

Как пользоваться генератором

Вы можете изучить имеющиеся примеры L-систем (поиграв, например, с количеством итераций), а можете составить собственные L-системы. Поле «аксиома», как и полагается, содержит начальную последовательность. Вы можете задать до пяти правил, по которым на каждой итерации один символ заменяется любой строкой. Правило должно иметь вид: символ, знак равенства, заменяющая строка. Несколько правил замены для одного символа делать бессмысленно, применяется только последнее.

Для рисования используется обычная для L-систем «черепашья графика»: представьте, что по холсту ползает черепаха c привязанным к панцирю карандашом. В каждый момент времени у неё есть определённое положение на холсте и определённое направление, куда она смотрит. С этой точки зрения символы трактуются так:

  • Любой символ, не описанный ниже — сделать шаг вперёд, нарисовав линию. Обычно для этой цели используют заглавные латинские буквы, особенно часто букву F от слова forward.
  • Пробелы и все символы, перечисленные в поле «константы» — игнорируются. (Константы при перечислении можно разделять пробелами или запятыми.) Но константы не игнорируются при замене, поэтому они, конечно, нужны.
  • Буква f — сделать шаг вперёд, не рисуя линии.
  • Плюс и минус — оставаясь на месте, повернуться по часовой стрелке или против часовой стрелки на угол, указанный в соответствующем поле.
  • Левая квадратная скобка — запомнить текущее положение, направление и цвет линии. Соответствующая правая квадратная скобка — вспомнить то состояние и вернуться в него. Скобки могут быть вложенными, но должны быть парными, чтобы получившиеся картинки были корректными L-системами. Именно эта операция нужна для рисования деревьев: запоминаемая точка соответствует месту ответвления от основного ствола.
  • Наконец, латинская буква C с последующей десятичной цифрой означает смену цвета линий (только будущих, но не уже нарисованных, конечно). Большинство цветов более или менее древесно-лиственные. Последний номер 9 вернёт обычный чёрный цвет, а цвет номер 8 — «пустой», это невидимое перо, более универсальный инструмент, чем краткая команда f.

Итоговая картинка масштабируется так, чтобы войти в холст.

Возможные обобщения

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

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

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

Наконец, что будет, если на каждой итерации применять правила не ко всем символам одновременно? Тогда мы придём к так называемой формальной грамматике. Это понятие играет важную роль, например, в лингвистике.

Авторские права

Приведённую здесь реализацию L-систем создал Кевин Рост. Андрей Заболотский осуществил перевод интерфейса на русский язык, внёс некоторые правки и написал сопроводительный текст. Код можно распространять и изменять свободно при условии сохранения ссылки на изначального автора.

Ссылки

7 комментариев :

Alexei комментирует...

Помогите, пожалуйста!
Сам не программист, но решение нужно уже сейчас.
Существует массив данных от 1 до 5 000 000. Представлен в виде цепи.

Существует задача 10 раз разложить цепь так, чтобы соблюдались следующие условия:
- каждый элемент массива может занять одно и то же место в цепи повторно только после прохождения через это место всех остальных 4 999 999 элементов;
- каждый элемент массива должен пройти через все места цепи;
- за десять разложений цепи все элементы обязаны перемешаться равномерно относительно длины цепи (1-5 000 000).
Сколько раз по 10 раз придется разложить цепь.

Alexei комментирует...

Добавлю, элементы массива 0 и 1

Alexei комментирует...

Сергей, откуда задача? Что за массив в виде цепи?

Alexei комментирует...

Такая задача встала в процессе проектирования сайта. Массив данных представлен пятью миллионами участников. Вот сейчас пытаемся понять возможно создание такого алгоритма или нет.

Alexei комментирует...

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


Что означает "массив данных представлен в виде цепи"? Иногда говорят, "массив представлен в виде списка".


Дальше непонятно, что за разложения цепи появляются в следующем абзаце.

Alexei комментирует...

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

Alexei комментирует...

здравствуйте, можете помочь? мне нужно написать программу на delphi чтобы выводилось например как на этом сайте осенне дерево

Отправить комментарий