L-systemとは - わかりやすく解説 Weblio辞書 (original) (raw)

L-system（エルシステム、Lindenmayer system）は形式文法の一種で、植物の成長プロセスを初めとした様々な自然物の構造を記述・表現できるアルゴリズムである。自然物の他にも、反復関数系（Iterated Function System、 IFS）のようないわゆる自己相似図形やフラクタル図形を生成する場合にも用いられる。L-System は1968年、ハンガリーユトレヒト大学の理論生物学者にして植物学者であったアリステッド・リンデンマイヤー（Aristid Lindenmayer）により提唱され、発展した。

起源

L-system により生成された3次元の樹木モデル。

生物学者としてリンデンマイヤーは、酵母や糸状菌、そして藍藻類の Anabaena catenula のような藻類など、様々な生物の成長パターンを研究していた。もともと L-system は、そのような単細胞生物もしくは体制の単純な多細胞生物の成長様式や、植物細胞における近隣の細胞の相互関係を記述するために開発されたものであった。後に L-system はより高等な植物の形態や、複雑な分岐構造を記述する為のツールとして発展を遂げるのである。

L-system の構造

L-system の基本は再帰性で、自己相似図形やフラクタル図形のような形状を簡単に記述する事ができる。植物やその他の見た目が自然な生物構造も同様に簡単に定義でき、再帰呼出の回数を増やす事であたかも構造が「成長」し、複雑化していくように見える。L-system は人工生命の生成にもよく用いられる。

L-system の文法は en:Unrestricted grammar のものに似ている（→ チョムスキー階層）。現在では、以下のような四ツ組によって定義されることが多い。

G = {V, S, ω, P},

各要素は、

置換規則 P において、置換対象が単独の文字のみである場合、L-system は文脈自由言語である。一方、置換規則が近隣の文字との相互関係まで考慮するものである場合、L-system は文脈依存言語である。また、置換規則Pが各文字に対して毎回確実に適用される時、L-system は「決定論的」であると言われ、D0L-system（deterministic context-free L-system ）などと呼ばれる。逆に、置換規則の適用が確率に左右される場合には「確率論的」L-system と呼ばれる。

L-system をグラフィックスに応用する場合、L-system が生成する文字列を、何らかの形で画面上の図形に変換しなければならない。例えば FractInt というプログラム（文末の外部リンク参照）では、LOGOのようなタートルを利用してグラフィックスを生成する。つまりプログラムが L-system の文字列をタートルの制御命令に翻訳し、図形を描画させている。

L-systems の実例

例1：藻類

L-system 誕生の契機となった、藻類の成長を記述する例。

V ： A, B

S ： なし

ω： A

P ： (A → AB), (B → A)

順次計算してゆくと、文字列は以下のように成長する。

n = 0 ： A

n = 1 ： AB

n = 2 ： ABA

n = 3 ： ABAAB

n = 4 ： ABAABABA

この例では、置換規則 P において、_(A → AB)_ は不均等な細胞分裂により通常の細胞Aと未熟な細胞Bが生じる事を表し、_(B → A)_ は未熟な細胞Bが成長して分裂可能な細胞 A へと成熟する事を表している。この文字列を図形化（例えば A を分枝型の細胞、B を小型の細胞の図などにそれぞれ置き換える）する事で、あたかも寒天培地上に展開した藻類のコロニーのような絵を得る事ができる。

例2：フィボナッチ数列

V ： A, B

S ： なし

ω： A

P ： (A → B), (B → AB)

計算を進めると、以下のような文字列となる。

n = 0 ： A

n = 1 ： B

n = 2 ： AB

n = 3 ： BAB

n = 4 ： ABBAB

n = 5 ： BABABBAB

n = 6 ： ABBABBABABBAB

n = 7 ： BABABBABABBABBABABBAB

この文字列の各文字数を _n_=0 から順に数えると、フィボナッチ数列（1 1 2 3 5 8 13 21 34 55 89 …）となっている。この例では文字列の内容は問わず長さだけに注目しているので、例えば置換規則の (B → AB) を (B → BA) で置き換えても同様の数列を得る事ができる。

例3：カントール集合

V ： A, B

S ： なし

ω： A

P ： (A → ABA), (B → BBB)

計算を進めると、以下のような文字列となる。

n = 0 ： A

n = 1 ： ABA

n = 2 ： ABABBBABA

n = 3 ： ABABBBABABBBBBBBBBABABBBABA

この文字列の A を線分、B を抜き取られた部分に置き換えると下のような図が得られる。置換規則の (A → ABA) は線分（閉区間）を3等分して中央を抜き取る操作に相当する。_(B → BBB)_ は一度取り除かれた区間が戻らない事を意味する。詳しくはカントール集合（Cantor set）を参照

例4：コッホ曲線

直角で構成されるコッホ曲線の描画例。

V ： F

S ： +, -;

ω： F

P ： (F → F+F-F-F+F)

上記において、F はタートルによる直線の描画、_+_ はタートルを左へ90°回転、同じく_-_ は右へ90°回転する事を意味する。これを順次計算すると、以下のような図形が得られる。

n = 0 ：

F

n = 1 ：

F+F-F-F+F

n = 2 ：

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

n = 3 ：

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+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

例5：ペンローズ・タイル

L-system を利用して、下図のような平面充填模様を生成する事もできる。詳しくはペンローズ・タイル及びロジャー・ペンローズを参照。

例6：シェルピンスキーの三角形

L-system でシェルピンスキーの三角形を作図する例。

V ： A, B

S ： +, -

ω： A

P ： (A → B−A−B), (B → A+B+A)

上記において、A 及び B はタートルによる直線の描画、_+_ はタートルを左へ60°回転、同じく_-_ は右へ60°回転する事を意味する。同様の図形を描く置換規則は他にもあるが、この規則の場合、タートルは三角形の左下から描き始める事になる。

n = 2, n = 4, n = 6, n = 8 の時にそれぞれ描画される図形。n → ∞ の時、シェルピンスキーの三角形に等しくなる。

例7：コッホ曲線の変形

通常のコッホ曲線に、周期的な角度の変更を加えながら描画したフラクタル図形の一種。

その他の L-system を利用したグラフィックス

既知の問題

L-system に関する問題は数多く存在するが、その最たるものは L-system を逆に辿る事が困難であるというものである。具体的には、ある構造が示された時に、その構造を生成するパラメータや置換規則を見つける事が難しい。これは自然物のような複雑な（反復回数の多い）過程を経て形成された図形に顕著である。

L-system の種類

実数列における L-system：

平面における L-system：

空間における L-system：

確率的L-system

確率的 (Stochastic) L-systemは、L-systemを拡張して確率的に分岐できるようにしたものである。確率的L-systemには標準が無いため、ソフトウェアによって文法が異なる。

以下は確率的な分岐を行うL-systemの実装毎の例である。

Tong Linの実装(1996) Houdini(L-system SOP) Cinema 4D(MoSplineのTurtle)
A=(0.5)FA A=(0.25)+F-A A=(0.25)-F+A A=FA:0.5 A=+F-A:0.25 A=-F+A:0.25 A:(rnd(1)<0.5)=FA A:(rnd(1)<0.75)=+F-A A:(rnd(1)>0.75)=-F+A

文脈依存L-system

文脈依存 (Context-sensitive) L-systemは、L-systemを拡張したものであり、パターンマッチングによって文脈に依存した分岐が可能となっている。文脈依存L-systemを実装したものとしては、Tong Linの実装などが存在する。

関連項目

参考文献

外部リンク

表 話 編 歴 フラクタル
特徴 フラクタル次元 Assouad（英語版） Box-counting（英語版） Correlation（英語版） ハウスドルフ Packing（英語版） 位相 再帰（英語版） 自己相似 自己相似過程 スケール不変性
反復関数系 バーンズリーのシダ カントール集合 ドラゴン曲線 レヴィC曲線 コッホ雪片 メンガーのスポンジ シェルピンスキーのカーペット シェルピンスキーの三角形 空間充填曲線 T-square（英語版）
ストレンジアトラクター 多重フラクタル系（英語版）
L-system 空間充填曲線
Escape-time fractals バーニングシップ・フラクタル ジュリア集合 充填 リアプノフ・フラクタル マンデルブロ集合 ニュートン・フラクタル（英語版）
確率的フラクタル ブラウン運動 非整数ブラウン運動 ブラウンの木（英語版） 拡散律速凝集 フラクタル地形 Lévy flight（英語版） パーコレーション理論（英語版） Self-avoiding walk（英語版）
人物 ゲオルク・カントール フェリックス・ハウスドルフ ガストン・ジュリア ヘルゲ・フォン・コッホ ポール・レヴィ アレクサンドル・リャプノフ ブノワ・マンデルブロ ルイス・フライ・リチャードソン ヴァツワフ・シェルピニスキ
その他 "How Long Is the Coast of Britain?（英語版）" 海岸線のパラドックス List of fractals by Hausdorff dimension（英語版） The Beauty of Fractals（英語版） (1986 book)