ドラゴン曲線

再帰的なアルゴリズム

---

以前の投稿に続き，L-systemのようなシミュレーションを行ってみたい．今回はドラゴン曲線（Dragon curve）というものを描く．

条件は下記である．

• 公理： "FX"
• 置換規則：
• X → X+YF+
• Y → -FX-Y
• F → F （Fはそのまま）
• 回転角： 90°
• 各世代ごとに線分の長さを縮小（scale_factor = 0.5）して描画
  

import math
import matplotlib.pyplot as plt
import imageio
import io
import numpy as np

# 文字列の次世代を生成する関数
def generate_next_string(current, rules):
    next_string = ""
    for ch in current:
        if ch in rules:
            next_string += rules[ch]
        else:
            next_string += ch
    return next_string

# タートル解釈を行い、線分のリストを返す関数
def interpret_lsystem(instructions, angle_deg, line_length):
    # 初期状態：位置 (0,0)、初期角度 0°（右向き）
    x, y = 0, 0
    angle = 0
    segments = []
    stack = []
    for cmd in instructions:
        if cmd == 'F':
            new_x = x + line_length * math.cos(math.radians(angle))
            new_y = y + line_length * math.sin(math.radians(angle))
            segments.append(((x, y), (new_x, new_y)))
            x, y = new_x, new_y
        elif cmd == '+':
            angle += angle_deg
        elif cmd == '-':
            angle -= angle_deg
        elif cmd == '[':
            stack.append((x, y, angle))
        elif cmd == ']':
            x, y, angle = stack.pop()
        # その他の文字（X, Y など）は描画には使わないので無視
    return segments

# 得られた線分を描画し、画像（numpy配列）として返す関数
def plot_segments(segments, margin=10):
    if not segments:
        fig, ax = plt.subplots(figsize=(6,6))
        ax.set_aspect('equal')
        ax.axis('off')
        ax.set_xlim(-margin, margin)
        ax.set_ylim(-margin, margin)
        buf = io.BytesIO()
        plt.savefig(buf, format='png', bbox_inches='tight', pad_inches=0)
        buf.seek(0)
        img = imageio.v2.imread(buf)
        plt.close(fig)
        return img
    
    xs, ys = [], []
    for seg in segments:
        (x1, y1), (x2, y2) = seg
        xs.extend([x1, x2])
        ys.extend([y1, y2])
    xmin, xmax = min(xs), max(xs)
    ymin, ymax = min(ys), max(ys)
    
    fig, ax = plt.subplots(figsize=(6,6))
    for seg in segments:
        (x1, y1), (x2, y2) = seg
        ax.plot([x1, x2], [y1, y2], color='black', linewidth=1)
    ax.set_aspect('equal')
    ax.axis('off')
    ax.set_xlim(xmin - margin, xmax + margin)
    ax.set_ylim(ymin - margin, ymax + margin)
    
    buf = io.BytesIO()
    plt.savefig(buf, format='png', bbox_inches='tight', pad_inches=0)
    buf.seek(0)
    img = imageio.v2.imread(buf)
    plt.close(fig)
    return img

# 各フレームのサイズを統一するためのパディング処理
def pad_frames(frames):
    max_h = max(frame.shape[0] for frame in frames)
    max_w = max(frame.shape[1] for frame in frames)
    padded_frames = []
    for frame in frames:
        h, w = frame.shape[:2]
        pad_bottom = max_h - h
        pad_right = max_w - w
        padded = np.pad(frame, ((0, pad_bottom), (0, pad_right), (0, 0)),
                        mode='constant', constant_values=255)
        padded_frames.append(padded)
    return padded_frames

# L-systemの各世代の描画を行い、GIFを出力する関数
def lsystem_to_gif(axiom, rules, angle_deg, initial_length, iterations, scale_factor, gif_filename):
    frames = []
    current_string = axiom
    line_length = initial_length
    for i in range(iterations + 1):
        print(f"Iteration {i}, string length: {len(current_string)}")
        segments = interpret_lsystem(current_string, angle_deg, line_length)
        img = plot_segments(segments)
        frames.append(img)
        current_string = generate_next_string(current_string, rules)
        line_length *= scale_factor  # 線分長さの縮小
    frames = pad_frames(frames)
    imageio.mimsave(gif_filename, frames, duration=0.5)
    print("GIF saved as", gif_filename)

# メイン処理：ドラゴン曲線
if __name__ == "__main__":
    # L-systemパラメータ（ドラゴン曲線）
    axiom = "FX"
    rules = {
        "X": "X+YF+",
        "Y": "-FX-Y",
        "F": "F"  # Fはそのまま
    }
    angle_deg = 90
    initial_length = 400    # 初期の線分長さ
    iterations = 15         # 反復回数
    scale_factor = 0.5      # 各世代ごとに線分長さを縮小
    gif_filename = "dragon_curve.gif"
    
    lsystem_to_gif(axiom, rules, angle_deg, initial_length, iterations, scale_factor, gif_filename)

参考文献

• Chang, A., & Zhang, T. (Year). The fractal geometry of the boundary of dragon curves. Institution or Publisher.