再帰曲線 ヒルベルト曲線(アルゴリズム)

Hilbert Curve Recursive Algorithm

ヒルベルト曲線は、四つのルールで描画されます。四つの描画関数でルールを実現します。n段の関数の中で、それぞれの(n-1)段の関数を呼び出しながら、四角形の三辺を規定の向きで描画します。四つの描画関数は、ldr(n)、urd(n)、rul(n)、dlu(n)という名前で、l,r,u,dは、左、右、上、下の方向を表します。

　 

ldr(n)のルールは、rul(n) ： urd(n-1)、→、 rul(n-1)、↑ 、rul(n-1)、← 、dlu(n-1)です。下は、ldr(1)、ldr(2)、ldr(3)で描画した絵です。矢印は、固定の長さの線分を引くという意味です。

VC++のプログラムを表示します。

typedef struct tagFPOINT
{
    double x;
    double y;
} FPOINT;

int Hilbert_x = 0;
int Hilbert_y = 0;
int Hilbert_delta = 10;
void ldr(int n, CDC* pDC)
{
    if (n > 0)
    {
        dlu(n-1, pDC); Hilbert_x -= Hilbert_delta; pDC->LineTo(Hilbert_x, Hilbert_y);//←
        ldr(n-1, pDC); Hilbert_y += Hilbert_delta; pDC->LineTo(Hilbert_x, Hilbert_y);//↓
        ldr(n-1, pDC); Hilbert_x += Hilbert_delta; pDC->LineTo(Hilbert_x, Hilbert_y);//→
        urd(n-1, pDC);
    }
}
void urd(int n, CDC* pDC)
{
    if (n > 0)
    {
        rul(n-1, pDC); Hilbert_y -= Hilbert_delta; pDC->LineTo(Hilbert_x, Hilbert_y);//↑
        urd(n-1, pDC); Hilbert_x += Hilbert_delta; pDC->LineTo(Hilbert_x, Hilbert_y);//→
        urd(n-1, pDC); Hilbert_y += Hilbert_delta; pDC->LineTo(Hilbert_x, Hilbert_y);//↓
        ldr(n-1, pDC);
    }
}
void rul(int n, CDC* pDC)
{
    if (n > 0)
    {
        urd(n-1, pDC); Hilbert_x += Hilbert_delta; pDC->LineTo(Hilbert_x, Hilbert_y);//→
        rul(n-1, pDC); Hilbert_y -= Hilbert_delta; pDC->LineTo(Hilbert_x, Hilbert_y);//↑
        rul(n-1, pDC); Hilbert_x -= Hilbert_delta; pDC->LineTo(Hilbert_x, Hilbert_y);//←
        dlu(n-1, pDC);
    }
}
void dlu(int n, CDC* pDC)
{
    if (n > 0)
    {
        ldr(n-1, pDC); Hilbert_y += Hilbert_delta; pDC->LineTo(Hilbert_x, Hilbert_y);//↓
        dlu(n-1, pDC); Hilbert_x -= Hilbert_delta; pDC->LineTo(Hilbert_x, Hilbert_y);//←
        dlu(n-1, pDC); Hilbert_y -= Hilbert_delta; pDC->LineTo(Hilbert_x, Hilbert_y);//↑
        rul(n-1, pDC);
    }
}
void CRecursiveCurvesView::HilbertCurve(int n)
{
    CClientDC dc(this);
    CRect r;
    GetClientRect(&r);
    Hilbert_x = r.Width() - 10;
    Hilbert_y = 10;
    Hilbert_delta = 26;
    dc.MoveTo(Hilbert_x,  Hilbert_y);
    ldr(n, &dc);
}