L-system

１．L-systemについて

Blender には、3DのL-system（LParser）のプラグインがあり、木などの作図に使われている。
おそらく、作図ツールでは一般的な機能。
進む方向を指定して線分を引くことを繰り返す。
今回の例では、+,-で左右の方向を示し、Fで一単位の線分を引くことを示す。
例えば、F+F+F+F と言う文字列は正方形を描く。
L-system は、文字列をインタプリットして描画するシステム。
この前提は、左右の方向が直角を単位とすること、線分の長さは常に一定であること。
L-system では、初期状態と置換規則を使う。
初期状態、置換規則の式は１つとは限らないが、ここではFを置き換える１つの規則のみ。
初期状態をF、置換規則を F->F+F-F-F+F とすると、コッホ曲線を描く。
０次は、F の1単位の線分を表す。
１次は、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 が描かれる。
この規則だけを使うと、連続した一本の線が描かれる。これに、位置と方向の組のスタックを追加すると木のような分岐した線が描ける。
ここでは、[、] の文字で Push/Pop を示す。

２．Silverlightのサンプルプログラムの実行

左図をクリックすると実行します。
式は、+,-,[,],F の５種類の文字を並べた文字列。
初期状態と置換規則を、この式で与えます。
指定回数、置換を行って生成される文字列を先頭からインタプリットして描画します。
線分の方向を示す角度の１単位は、設定できます。
角度や線分の長さを１単位より大きくするには、+.-,F の文字を連続すれば実現できます。

３．例

WikipediaのL-systemにあるコッホ曲線の例

Wikipediaのコッホ曲線の項の図

初期状態を F-F-F-F-F-F に（コッホ雪片）

スタックを使った式の例

４．XAMLのPath

数式やアルゴリズムで模様や自然物の形状を作り出す方法がありますが、XAML の Path を対応させれば便利そうだと思いました。
XAML文を生成してブラウザで解釈させるのも、ビハインドコードでPathオブジェクトを生成するのも、それぞれに利用価値があります。
ここで作成したサンプルはビハインドコードでPathオブジェクトを生成しています。

Path は、単純な座標列ではなく、XAMLで記述する場合とビハインドコードで生成する場合では差異もあります。少し、整理しておこうともいます。

４．１．パスマークアップ構文

ジオメトリックパスを XAML で記述するためのミニ言語があり、Path オブジェクトを作れます。
これは、XAML のコンパイラの機能であり、現状はビハインドコードでミニ言語をGeometry オブジェクトに変換する方法はないようです。

PathMarkup.xaml

<Canvas>
<Path Stroke="Black"
Data=
"
M 0,0
L 20,100
H 100
V 150
C 100,200 200,-200 300,150
Q 100,100 300,300
S 100,100 200,300
T 150,200 100,300
A 10,10 90 0 0 50,300
Z
"
/>
</Canvas>

	1.M 0,0 (移動)
	2.L 20,100 (線分)
	3.H 100 (水平線)
	4.V 150 (垂直線)
	5.C 100,200 200,-200 300,150 (3次ベジエ曲線)
	6.Q 100,100 300,300 (2次ベジエ曲線)
	7.S 100,100 200,300 (平滑3次ベジエ曲線)
	8.T 150,200 100,300 (平滑2次ベジエ曲線)
	9.A 10,10 90 0 0 50,300 (楕円の円弧)
	10.Z (視点と結んで閉じる)

４．２．セグメントの種類

前述の線分やベジェ曲線などの描画要素はセグメントと言うようです。XAMLでもビハインドコードでも共通に使えるセグメントは以下の表ようになっています。

左図を描画する、XAMLとビハインドコードを載せておきます。
XAMLはIEで直接開くことができます。
ビハインドコードの例は、Silverlightアプリケーション・プロジェクトや、WPFアプリケーション・プロジェクトを作成し、ひな形のXAMLの<Grid>にLoadedイベント処理を追加して記述してください。

この例では、Pathオブジェクトを構成するクラスの構造もわかります。
・Pathは、PathGeometry 型のDataプロパティにジオメトリを保持します。
・PathGeometry クラスの Figures プロパティは PathFigure オブジェクトのコレクションです。
・PathFigure クラスの Segments プロパティは、各種セグメントのコレクションです。

１つの Path オブジェクトは、複数の PathFigure オブジェクトを持つことができ、各 PathFigure オブジェクトは一連の線画を保持できます。

	クラス名	機能
1	ArcSegment	楕円の円弧
2	BezierSegment	3次ベジエ曲線
3	LineSegment	線分
4	QuadraticBezierSegment	2次ベジエ曲線
5	PolyBezierSegment	連続した3次ベジエ曲線
6	PolyLineSegment	連続した線分
7	PolyQuadraticBezierSegment	連続した2次ベジエ曲線

Segments.xaml

<Canvas>
<Path Stroke="Black" StrokeThickness="1" >
<Path.Data>
<PathGeometry>
<PathGeometry.Figures>
<PathFigure StartPoint="50,50">
<PathFigure.Segments>
<ArcSegment Size="45,45" RotationAngle="60" IsLargeArc="True" SweepDirection="Clockwise" Point="100,100"/>
<BezierSegment Point1="100,0" Point2="200,200" Point3="200,100"/>
<LineSegment Point="250,100" />
<QuadraticBezierSegment Point1="100,200" Point2="200,200"/>
<PolyBezierSegment Points="100,100 100,200 250,300 200,200 200,250 100,300" />
<PolyLineSegment Points="0,200 100,200" />
<PolyQuadraticBezierSegment Points="0,180 50,150 0,80 45,45" />
</PathFigure.Segments>
</PathFigure>
</PathGeometry.Figures>
</PathGeometry>
</Path.Data>
</Path>
</Canvas>

Loadedイベントでの描画

private void LayoutRoot_Loaded(object sender, RoutedEventArgs e)
{
ArcSegment as1 = new ArcSegment();
as1.Size=new Size(45,45);
as1.RotationAngle=60;
as1.IsLargeArc=true;
as1.SweepDirection=SweepDirection.Clockwise;
as1.Point = new Point(100, 100);
BezierSegment bs1=new BezierSegment();
bs1.Point1=new Point(100,0);
bs1.Point2=new Point(200,200);
bs1.Point3 = new Point(200, 100);
LineSegment ls1 = new LineSegment();
ls1.Point = new Point(250, 100);
QuadraticBezierSegment qbs1 = new QuadraticBezierSegment();
qbs1.Point1 = new Point(100, 200);
qbs1.Point2 = new Point(200, 200);
PolyBezierSegment pbs1 = new PolyBezierSegment();
pbs1.Points.Add(new Point(100, 100));
pbs1.Points.Add(new Point(100, 200));
pbs1.Points.Add(new Point(250, 300));
pbs1.Points.Add(new Point(200, 200));
pbs1.Points.Add(new Point(200, 250));
pbs1.Points.Add(new Point(100, 300));
PolyLineSegment pls1 = new PolyLineSegment();
pls1.Points.Add(new Point(0, 200));
pls1.Points.Add(new Point(100, 200));
PolyQuadraticBezierSegment pqbs1 = new PolyQuadraticBezierSegment();
pqbs1.Points.Add(new Point(0, 180));
pqbs1.Points.Add(new Point(50, 150));
pqbs1.Points.Add(new Point(0, 80));
pqbs1.Points.Add(new Point(45, 45));
PathFigure pf1 = new PathFigure();
pf1.StartPoint = new Point(50, 50);
pf1.Segments.Add(as1);
pf1.Segments.Add(bs1);
pf1.Segments.Add(ls1);
pf1.Segments.Add(qbs1);
pf1.Segments.Add(pbs1);
pf1.Segments.Add(pls1);
pf1.Segments.Add(pqbs1);
PathGeometry pg1=new PathGeometry();
pg1.Figures.Add(pf1);
Path path1 = new Path();
path1.Stroke = new SolidColorBrush(Colors.Black);
path1.Data = pg1;
Canvas canvas1 = new Canvas();
canvas1.Children.Add(path1);
LayoutRoot.Children.Add(canvas1);
}

５．プログラムの説明

以下に、Page.xaml と Page.xaml.cs の全文を載せます。
他に、2つのクラスを使っています。
Scale クラスは、生成される座標の最大最小から描画の倍率を計算するのに使っています。
描画領域いっぱいの描画をしようと言う意図です。

using System;
using System.Windows;
namespace L_system1
{
public class Scale
{
const double MARGIN = 0.04;
double min_x = double.MaxValue;
double min_y = double.MaxValue;
double max_x = double.MinValue;
double max_y = double.MinValue;
readonly double actualWidth;
readonly double actualHeight;
public Scale(double actualWidth, double actualHeight)
{
this.actualWidth = actualWidth;
this.actualHeight = actualHeight;
}
public void SetPoint(Point point)
{
if (point.X > max_x) max_x = point.X;
if (point.X < min_x) min_x = point.X;
if (point.Y > max_y) max_y = point.Y;
if (point.Y < min_y) min_y = point.Y;
}
public double Magnification
{
get
{
return Math.Min(
actualWidth / (max_x - min_x),
actualHeight / (max_y - min_y)
) * (1.0 - MARGIN);
}
}
public double TranslateX { get { return -(min_x - (max_x-min_x) * MARGIN / 2); } }
public double TranslateY { get { return -(min_y - (max_y - min_y) * MARGIN / 2); } }
}
}

StepElement クラスは、[,]文字に対応したスタック動作を行うのに使っています。
スタックするべきデータです。

using System.Windows;
namespace L_system1
{
public class StepElement
{
public readonly Point point;
public readonly double angle;
public StepElement(Point point, double angle)
{
this.point = point;
this.angle = angle;
}
}
}

この話の要点は、L-system を Path にして描画することです。
これは、Page.xaml.cs の Button_Click()メソッドで行っています。「描画」ボタンが押された時の処理で、

前回の表示（Pathオブジェクト）をキャンバスから削除する。
式や繰り返し回数などの入力項目を取り込む。
そのエラーをチェックし、エラーなら警告し、以下の処理を行わない。
式を繰り返し回数展開した文字列を作る。
この文字列をインタプリットしてPathオブジェクトを作る。
Pathオブジェクトを構成している座標値から、描画領域にフィットするように、移動量、縮小率を計算して、Transformオブジェクトを作り、Pathに適用する。
Path をキャンバスに追加する。

と、言ったように少し長い処理になっています。
要点は、４，５です。

４の「式を繰り返し回数展開した文字列を作る。」は、以下の通りです。

string F = initial_state;
for (int i = 0; i < depth; i++)
{
F = F.Replace("F", replace_rule);
}

５の「この文字列をインタプリットしてPathオブジェクトを作る。」は、以下の通りです。

//生成された文字列のインタプリット
Scale scale = new Scale(canvas1.ActualWidth,
canvas1.ActualHeight);//描画の倍率計算用
scale.SetPoint(initial_point);
//位置と方向の初期化
Point point = initial_point;
double a = initial_angle;
//Figureコレクションの要素にパスを記録
PathFigure pf1 = new PathFigure();
pf1.StartPoint = point;
//スタックのクリア
stack.Clear();
//スタックが使われる場合は、複数のPathFigure
//オブジェクトがPathGeometryに追加される。
PathGeometry pg1 = new PathGeometry();
//各文字に応じた処理
foreach (char c in F)
{
switch (c)
{
case '+':
a += angle;
break;
case '-':
a -= angle;
break;
case '[':
stack.Push(new StepElement(point, a));
break;
case ']':
StepElement se = stack.Pop();
point = se.point;
a = se.angle;
if (pf1.Segments.Count > 0)
{
pg1.Figures.Add(pf1);
pf1 = new PathFigure();
}
pf1.StartPoint = point;
break;
case 'F':
point = Move(point, a);
scale.SetPoint(point);//座標の最大最上を保存して描画の倍率の計算に使う
pf1.Segments.Add(new LineSegment() { Point = point });
break;
}
}
//インタプリット終了
//figureコレクションの追加
if (pf1.Segments.Count > 0)
pg1.Figures.Add(pf1);

５．１．Page.xaml

<UserControl x:Class="L_system1.Page"
xmlns="http://schemas.microsoft.com/winfx/2006/xaml/presentation"
xmlns:x="http://schemas.microsoft.com/winfx/2006/xaml"
Width="420" Height="320">
<Grid x:Name="LayoutRoot" Background="Lavender" Loaded="LayoutRoot_Loaded">
<Grid.RowDefinitions>
<RowDefinition Height="20"/>
<RowDefinition/>
</Grid.RowDefinitions>
<Grid.ColumnDefinitions>
<ColumnDefinition/>
<ColumnDefinition Width="120"/>
</Grid.ColumnDefinitions>
<Grid Grid.Row="0" Grid.ColumnSpan="2" Margin="20,0,20,0" >
<TextBlock VerticalAlignment="Center" Foreground="Teal">L-system (XAMLのPath表現の利用)</TextBlock>
<TextBlock HorizontalAlignment="Right" VerticalAlignment="Bottom" Foreground="Lime">(C)mikeo_410</TextBlock>
</Grid>
<Canvas Grid.Row="1" Grid.Column="0" x:Name="canvas1" Background="Bisque"/>
<Grid Grid.Row="1" Grid.Column="1" Background="Lavender">
<StackPanel>
<TextBlock Text="初期状態：" TextWrapping="Wrap" Foreground="Firebrick"/>
<TextBox Text="" TextWrapping="Wrap" x:Name="initial_formula"/>
<TextBlock Text="置換規則：" TextWrapping="Wrap" Foreground="Firebrick"/>
<TextBox Text="" TextWrapping="Wrap" x:Name="replace_formula"/>
<TextBlock Height="Auto" Width="Auto" Text="繰り返し：" TextWrapping="Wrap" Foreground="Firebrick"/>
<ComboBox x:Name="combobox_depth" IsDropDownOpen="False" Margin="20,0,20,0"/>
<TextBlock Text="曲がる角度：" TextWrapping="Wrap" Height="16" Width="100" Foreground="Firebrick"/>
<TextBox Text="" TextWrapping="Wrap" x:Name="angle1" Height="24" Width="100"/>
<Button Content="描画" Click="Button_Click">
<Button.BorderBrush>
<LinearGradientBrush EndPoint="0.5,1" StartPoint="0.5,0">
<GradientStop Color="#FFA3AEB9"/>
<GradientStop Color="#FF8399A9" Offset="0.375"/>
<GradientStop Color="#FF718597" Offset="0.375"/>
<GradientStop Color="#FFEA1414" Offset="1"/>
</LinearGradientBrush>
</Button.BorderBrush>
<Button.Background>
<LinearGradientBrush EndPoint="0.5,1" StartPoint="0.5,0">
<GradientStop Color="#FF000000"/>
<GradientStop Color="#FFEA1414" Offset="1"/>
</LinearGradientBrush>
</Button.Background>
</Button>
<TextBlock Height="Auto" Width="Auto" Text="" TextWrapping="Wrap" x:Name="message1" Foreground="#FFEA1414"/>
</StackPanel>
</Grid>
</Grid>
</UserControl>

５．２．Page.xaml.cs

using System;
using System.Collections.Generic;
using System.Windows;
using System.Windows.Controls;
using System.Windows.Media;
using System.Windows.Shapes;
using System.Windows.Browser;
using SilverlightLibrary;
namespace L_system1
{
public partial class Page : UserControl
{
public Page()
{
InitializeComponent();
}
//-------------------------------------------------------------------------------
//ページの表示の初期化
private void LayoutRoot_Loaded(object sender, RoutedEventArgs e)
{
//----------------------------------
//小窓に表示するためのブラウザの設定
HtmlPage.Document.SetProperty("title", "L-system (XAMLのPath表現の利用)");
//決まったサイズで表示するサンプルなので、AUCサーバの付加するヘッダを削除
//ヘッダは、通常のHTMLの前に記述されている。（!DOCTYPEより前）
//それでもDocumentのDomではBodyに含まれる。
HtmlElement body = HtmlPage.Document.Body;
if (body.Children.Count > 0)
if (((HtmlElement)(body.Children[0])).TagName == "a")
body.RemoveChild((HtmlElement)body.Children[0]);
if (body.Children.Count > 1)
if (((HtmlElement)(body.Children[1])).TagName == "br")
body.RemoveChild((HtmlElement)body.Children[1]);
//悪さはしていないと思うが、htmlとheadの間に
if (body.Children.Count > 2)
if (((HtmlElement)(body.Children[2])).TagName == "!")
body.RemoveChild((HtmlElement)body.Children[1]);
//決まったサイズで表示するサンプルなので、AUCサーバの付加するフッタを削除
HtmlElement[] parents = HtmlPageUtil.ParentsByTagName(HtmlPage.Document, "center");
if (parents.Length > 0)
HtmlPageUtil.RemoveChildByTagName(parents[parents.Length - 1], "center");
//----------------------------------
//表示画面の初期化
//繰り返し回数を選ぶコンボボックスの初期化
for (int i = 0; i <= 4; i++)
combobox_depth.Items.Add(i.ToString());
combobox_depth.SelectedIndex = 2;
//角度の初期化
angle1.Text = "90";
//サンプルの式
initial_formula.Text = "F+F+F+F";
replace_formula.Text = "F+F-F-FF+F+F-F";
}
//-------------------------------------------------------------------------------
//インタプリタ定数
const double step_length = 10;//'F'で移動するる量。スケーリングするので線幅に影響
readonly Point initial_point = new Point(0, 0);//位置の初期値
const double initial_angle = 0.0;//方向の初期値
//-------------------------------------------------------------------------------
//インタプリタ変数
double angle; //曲がるときの角度
int depth; //繰り返し回数
string initial_state; //初期値
string replace_rule; //置換規則
// [,] に対応したスタック
Stack<StepElement> stack = new Stack<StepElement>();
//-------------------------------------------------------------------------------
//新しい線分の終点を計算
Point Move(Point point, double a)
{
return new Point(point.X + step_length * Math.Cos(a), point.Y - step_length * Math.Sin(a));
}
//-------------------------------------------------------------------------------
//ユーザーが入力した式のチェック
bool CheckFormula(string F)
{
if (F.Length <= 0) return false;
foreach (char c in F)
if ((c != '+') && (c != '-') && (c != '[') && (c != ']') && (c != 'F')) return false;
return true;
}
//-------------------------------------------------------------------------------
// 描画ボタンが押された。インタプリットして描画。
private void Button_Click(object sender, RoutedEventArgs e)
{
//----------------------------------
//前回の入力エラーメッセージの消去
message1.Text = "";
//----------------------------------
//前回の警告表示の削除
if (canvas1.Children.Count > 0)
canvas1.Children.RemoveAt(0);
//----------------------------------
//入力されたオプションを取り込む
initial_state = initial_formula.Text;
if (!CheckFormula(initial_state))
{
message1.Text = "初期状態の式は F,+,-,[,] で指定してください。";
return;
}
replace_rule = replace_formula.Text;
if (!CheckFormula(replace_rule))
{
message1.Text = "初期状態の式は F,+,-,[,] で指定してください。";
return;
}
depth = combobox_depth.SelectedIndex;
try
{
angle = Convert.ToDouble(angle1.Text);
angle = (angle / 180) * Math.PI;
}
catch
{
message1.Text = "曲がる角度を度で指定してください。";
return;
}
//----------------------------------
//L-system の式を実行。展開した文字列を作る
string F = initial_state;
for (int i = 0; i < depth; i++)
{
F = F.Replace("F", replace_rule);
}
//----------------------------------
//生成された文字列のインタプリット
Scale scale = new Scale(canvas1.ActualWidth,
canvas1.ActualHeight);//描画の倍率計算用
scale.SetPoint(initial_point);
//位置と方向の初期化
Point point = initial_point;
double a = initial_angle;
//Figureコレクションの要素にパスを記録
PathFigure pf1 = new PathFigure();
pf1.StartPoint = point;
//スタックのクリア
stack.Clear();
//スタックが使われる場合は、複数のPathFigure
//オブジェクトがPathGeometryに追加される。
PathGeometry pg1 = new PathGeometry();
//各文字に応じた処理
foreach (char c in F)
{
switch (c)
{
case '+':
a += angle;
break;
case '-':
a -= angle;
break;
case '[':
stack.Push(new StepElement(point, a));
break;
case ']':
StepElement se = stack.Pop();
point = se.point;
a = se.angle;
if (pf1.Segments.Count > 0)
{
pg1.Figures.Add(pf1);
pf1 = new PathFigure();
}
pf1.StartPoint = point;
break;
case 'F':
point = Move(point, a);
scale.SetPoint(point);//座標の最大最上を保存して描画の倍率の計算に使う
pf1.Segments.Add(new LineSegment() { Point = point });
break;
}
}
//インタプリット終了
//figureコレクションの追加
if (pf1.Segments.Count > 0)
pg1.Figures.Add(pf1);
//----------------------------------
//キャンバス全体に表示するための移動、スケーリング量計算
TranslateTransform tt1 = new TranslateTransform();
tt1.X = scale.TranslateX;
tt1.Y = scale.TranslateY;
ScaleTransform st1 = new ScaleTransform();
st1.ScaleX = st1.ScaleY = scale.Magnification;
TransformGroup tg1 = new TransformGroup();
tg1.Children.Add(tt1);
tg1.Children.Add(st1);
//----------------------------------
//パスの作成
Path path1 = new Path();
path1.Data = pg1;
path1.Stroke = new SolidColorBrush(Colors.Black);
path1.StrokeThickness = 1;
path1.RenderTransform = tg1;
//----------------------------------
//キャンバスへ追加
canvas1.Children.Add(path1);
}
}
}

Amazon.co.jp ウィジェット

mikeo_410