L-системы

Реализация L-системы состоит из двух частей. Сначала мы по заданным правилам генерируем строку символов, а потом интерпретируем символы этой строки как команды черепашьей графики.

Рассмотрим получение строки. Задаётся начальная строка, называемая также аксиомой или инициатором, и набор правил, задающих на что заменять символы строки. Например, для снежинки Коха начальная строка имеет вид F++F++F, а правило имеет вид F → F-F++F-F.

Далее на каждом шаге одновременно заменются все символы строки согласно правилам. Для снежинки Коха имеем: F++F++F → F-F++F-F++F-F++F-F++F-F++F-F. На следующем шаге получим: F-F++F-F-F-F++F-F++F-F++F-F-F-F++F-F++F-F++F-F-F-F++F-F++F-F++F-F-F+F++F-F++F-F++F-F-F-F++F-F++F-F++F-F-F-F++F-F.

Продолжаем данный процесс заданное число шагов.

package ru.xaoc.fractalworld.lsystems;

import java.util.HashMap;
import java.util.Map;

public class LSystem {
    private String first;
    private Map rules;

    public LSystem(String first, Map rules) {
        this.first = first;
        this.rules = rules;
    }

    public LSystem(String first, String[][] rules) {
        this.first = first;
        this.rules = new HashMap();
        for (int i = 0; i < rules.length; ++i) {
           this.rules.put(rules[i][0].charAt(0), rules[i][1]);
        }
    }

    private String apply(String string) {
        StringBuilder result = new StringBuilder();
        for (int i = 0; i < string.length(); ++i) {
            if (rules.containsKey(string.charAt(i))) {
                result.append(rules.get(string.charAt(i)));
            } else {
                result.append(string.charAt(i));
            }
        }
        return result.toString();
    }

    public String getResult(int depth) {
        String result = first;
        for (int i = 0; i < depth; ++i) {
            result = this.apply(result);
        }
        return result;
    }
}

Состояние черепашки будем описывать тремя параметрами . Символы строки будем интерпретировать следующим образом:
F — переместиться вперёд на один шаг, прорисовывая след,
b — переместиться вперёд на один шаг, не оставляя следа, иногда вместо b используют G,
+ — уменьшить угол на заданную величину ,
- — увеличить угол на заданную величину ,
[ — запомнить состояние черепашки в стеке,
] — взять в качестве состояния черепашки последний элемент стека, и вытолкнуть этот элемент из стека.

package ru.xaoc.fractalworld.lsystems;

import java.util.Stack;

public class Turtle {

    private final Canvas canvas;
    private State state;
    private Stack memory = new Stack();
    private final double stepLength;
    private final double deltaAngle;

    public Turtle(Canvas canvas, double stepLength, double deltaAngle) {
        this.canvas = canvas;
        this.stepLength = stepLength;
        this.deltaAngle = deltaAngle;
    }

    public void draw(String string, State first) {
        state = first;
        for (int i = 0; i < string.length(); ++i) {
            switch (string.charAt(i)) {
                case 'F':
                    drawStep();
                    break;
                case 'b':
                    moveStep();
                    break;
                case '+':
                    rotateRight();
                    break;
                case '-':
                    rotateLeft();
                    break;
                case '[':
                    pushState();
                    break;
                case ']':
                    popState();
                    break;
                default:
                    break;
            }
        }
    }

    private void drawStep() {
        double oldX = state.getX();
        double oldY = state.getY();
        double angle = state.getAngle();
        double newX = oldX + Math.cos(angle) * stepLength;
        double newY = oldY - Math.sin(angle) * stepLength;
        canvas.drawLine(oldX, oldY, newX, newY);
        state = new State(newX, newY, angle);
    }

    private void moveStep() {
        double oldX = state.getX();
        double oldY = state.getY();
        double angle = state.getAngle();
        double newX = oldX + Math.cos(angle) * stepLength;
        double newY = oldY - Math.sin(angle) * stepLength;
        state = new State(newX, newY, angle);
    }

    private void rotateRight() {
        double x = state.getX();
        double y = state.getY();
        double oldAngle = state.getAngle();
        double newAngle = oldAngle - deltaAngle;
        state = new State(x, y, newAngle);
    }

    private void rotateLeft() {
        double x = state.getX();
        double y = state.getY();
        double oldAngle = state.getAngle();
        double newAngle = oldAngle + deltaAngle;
        state = new State(x, y, newAngle);
    }

    private void pushState() {
        memory.push(state);
    }

    private void popState() {
        state = memory.lastElement();
        memory.pop();
    }
}

package ru.xaoc.fractalworld.lsystems;

public class State {
    private double x;
    private double y;
    private double angle;

    public State(double x, double y, double angle) {
        this.x = x;
        this.y = y;
        this.angle = angle;
    }

    public double getX() {
        return x;
    }

    public double getY() {
        return y;
    }

    public double getAngle() {
        return angle;
    }
}

Скачайте весь исходный код.

Смотрите также:

• Коллекция L-систем.

Ссылки:

• Статья на хабре L-Systems — математическая красота растений ,
• 2D фракталы на основе L-систем ,
• Fractint L-Systems Tutorial .