はじめに
ヒルベルト曲線とは、ドイツの数学者ダフィット・ヒルベルトが考案したフラクタル図形の一つで、再帰的に定義できる空間充填曲線です。
大抵の人は、「ああ、どこかで見たことある」と思うような図形です。
ヒルベルト曲線は、コの字の形状を基本図形とし、以下の４つの基本描画ルールの再帰的組合せで描くことができます。
Ldr(n) = Dlu(n-1), Left, Ldr(n-1), Down, Ldr(n-1), Right, Urd(n-1)
Urd(n) = Rul(n-1), Up, Urd(n-1), Right, Urd(n-1), Down, Ldr(n-1)
Rul(n) = Urd(n-1), Right, Rul(n-1), Up, Rul(n-1), Left, Dlu(n-1)
Dlu(n) = Ldr(n-1), Down, Dlu(n-1), Left, Dlu(n-1), Up, Rul(n-1)
描画ルールのアルファベットはそれぞれ、
L:Left , D:Down , R:Right , U:Up
の意味です。n が 0 の時には、何も描画しません。
例えば、Rul(1)なら、右、上、左なので、コ字型の図形ということになります。
Ldr(4) とすれば、逆コの字を基準に４次のヒルベルト曲線を描画します。
実装する
コンソールアプリケーションとして作成しています。
以下、主なクラスです。
Program
プログラムをつかさどるクラス。HilbertCurveとDrawerを使って、図形を描画しています。
ここで、曲線の次数を与えています。
なお、次数を9以上にすると極端に結果がでるまでに時間がかかるようになります。当然ブラウザでこのファイルを描画するのも時間がかかります。
HilbertCurve
ヒルベルト曲線を定義しています。やっていることは、前述のヒルベルト曲線の定義をそのままC#のコードに落としたものです。
UrdやRulなどから始めても良いのですが、ここでは、Ldr を元となる図形としました。
ただ、ここで実際の線は引いていません。HirbertCurveクラスは、IObservableを実装していて、
線を引く代わりに、購読者クラス(Drawer)にその状態の変化を伝えています。
描画という行為からは完全に独立しています。
Drawer
描画を受け持つDrawerクラスは、IObserverを実装している購読者クラスです。
HilbertCurveからの通知を受け取り、線を描いて行きます。線を描くのに、Canvasクラスを利用しています。
EasyCanvas
NGraphicパッケージを利用して、線を描いています。結果はpngファイルにしています。
C#のコード
Program.cs
using System;
using System.Collections.Generic;
using System.Linq;
namespace HilbertCurve
{
class Program
{
static void Main(string[] args)
{
int generation = 6;
int w = 500;
var hilbert = new HilbertCurve();
var drawer = new Drawer(w, w, $"HilbertCurve{generation}.png");
hilbert.Subscribe(drawer);
hilbert.Start(w, generation);
}
}
}
HirbertCurve.cs
using System;
using System.Collections.Generic;
using System.Linq;
namespace HilbertCurve
{
public class Point
{
public float X { get; set; }
public float Y { get; set; }
public Point(float x, float y)
{
X = x;
Y = y;
}
}
public class DrawInfo
{
public Point Start { get; set; }
public Point End { get; set; }
}
public class HilbertCurve : IObservable<DrawInfo>
{
private float length;
private float X;
private float Y;
public void Start(int size, int n)
{
length = (float)(size / Math.Pow(2, n));
X = size - (float)(size / Math.Pow(2, n + 1));
Y = (float)(size / Math.Pow(2, n + 1));
Ldr(n);
foreach (var observer in _observers)
{
observer.OnCompleted();
}
}
// ┏
// ┗
void Ldr(int n)
{
if (n > 0)
{
Dlu(n - 1);
GoLeft();
Ldr(n - 1);
GoDown();
Ldr(n - 1);
GoRight();
Urd(n - 1);
}
}
// ┏┓
void Urd(int n)
{
if (n > 0)
{
Rul(n - 1);
GoUp();
Urd(n - 1);
GoRight();
Urd(n - 1);
GoDown();
Ldr(n - 1);
}
}
// ┓
// ┛
void Rul(int n)
{
if (n > 0)
{
Urd(n - 1);
GoRight();
Rul(n - 1);
GoUp();
Rul(n - 1);
GoLeft();
Dlu(n - 1);
}
}
// ┗┛
void Dlu(int n)
{
if (n > 0)
{
Ldr(n - 1);
GoDown();
Dlu(n - 1);
GoLeft();
Dlu(n - 1);
GoUp();
Rul(n - 1);
}
}
private void GoRight()
{
float newx = X;
float newy = Y;
newx = X + length;
DrawLine(newx, newy);
}
private void GoUp()
{
float newx = X;
float newy = Y;
newy = Y - length;
DrawLine(newx, newy);
}
private void GoDown()
{
float newx = X;
float newy = Y;
newy = Y + length;
DrawLine(newx, newy);
}
private void GoLeft()
{
float newx = X;
float newy = Y;
newx = X - length;
DrawLine(newx, newy);
}
private void DrawLine(float newx, float newy)
{
var state = new DrawInfo()
{
Start = new Point(X, Y),
End = new Point(newx, newy)
};
Publish(state);
X = newx;
Y = newy;
}
// 状況変化を知らせるために購読者に通知する
private void Publish(DrawInfo state)
{
foreach (var observer in _observers)
{
observer.OnNext(state);
}
}
private List<IObserver<DrawInfo>> _observers = new List<IObserver<DrawInfo>>();
public IDisposable Subscribe(IObserver<DrawInfo> observer)
{
_observers.Add(observer);
return observer as IDisposable;
}
}
}
Drawer.cs
using System;
using System.Collections.Generic;
using System.Linq;
namespace HilbertCurve
{
class Drawer : IObserver<DrawInfo>
{
private EasyCanvas _canvas;
private string _filepath;
public Drawer(int w, int h, string filepath)
{
_canvas = new EasyCanvas(w, h);
_filepath = filepath;
}
public void OnCompleted()
{
_canvas.Write(_filepath);
}
public void OnError(Exception error)
{
throw new NotImplementedException();
}
public void OnNext(DrawInfo value)
{
_canvas.DrawLine(value.Start.X, value.Start.Y, value.End.X, value.End.Y,
new NGraphics.Color("#0022FF"));
}
}
}
EasyCanvas.cs
using NGraphics;
using System;
using System.Collections.Generic;
using System.Linq;
namespace HilbertCurve
{
class EasyCanvas
{
private IImageCanvas canvas;
static EasyCanvas()
{
}
public EasyCanvas(int width, int height)
{
canvas = Platforms.Current.CreateImageCanvas(new Size(width, height), scale: 2);
}
public void SetPixel(int x, int y, NGraphics.SolidBrush brush)
{
canvas.FillRectangle(x, y, 1, 1, brush);
}
public void Write(string path)
{
canvas.GetImage().SaveAsPng(path);
}
internal void DrawLine(float x1, float y1, float x2, float y2, Color color)
{
canvas.DrawLine(x1, y1, x2, y2, color);
}
}
}
※ ソースコードは、GitHubで公開しています。
実行結果
以下は、 Ldr(5) で、5次のヒルベルト曲線を描いた結果です。
いやー、実に不思議な形をした図形です。
この記事は、Gushwell's C# Programming Pageで公開したものを大幅に変更・加筆したものです。