プログラミングメモ →目次

再帰曲線 ドラゴン曲線(アルゴリズム)

Dragon Curve Recursive Algorithm

ドラゴン曲線の生成アルゴリズムは、下記の図のように示します。

n段の中にある1本の線分は、2本の(n-1)段の線分で構成されます。n段の線分の長さの1.0とすれば、(n-1)段の線分の長さは0.7010(=1/√2)で、n段の線分との角度は45°です。上の絵は、12段のドラゴン曲線です。自作のVC++のプログラムを表示します。C-曲線の作り方と似ています。

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

void CRecursiveCurvesView::DrawLine(FPOINT p1,FPOINT p2, CDC* pDC)
{
    pDC->MoveTo((int)(p1.x+0.5), (int)(p1.y+0.5));
    pDC->LineTo((int)(p2.x+0.5), (int)(p2.y+0.5));
}

FPOINT CRecursiveCurvesView::RotateLine(FPOINT p1, FPOINT p2, double alpha)
{
    double x0 = p1.x;
    double y0 = p1.y;
    double x1 = p2.x - x0;
    double y1 = p2.y - y0;

    FPOINT pntRet;
    pntRet.x = x1 * cos(alpha) - y1 * sin(alpha) + x0;
    pntRet.y = x1 * sin(alpha) + y1 * cos(alpha) + y0;

    return pntRet;
}

FPOINT CRecursiveCurvesView::ShortenLine(FPOINT p1,FPOINT p2, double Ratio)
{
    FPOINT pntRet;

    if (p1.x == p2.x && p1.y == p2.y)
    {
        pntRet = p1;
    }
    if (p1.x == p2.x)
    {
        pntRet.x = p1.x;
        pntRet.y = p1.y + (p2.y - p1.y) * Ratio;
    }
    else if (p1.y == p2.y)
    {
        pntRet.y = p1.y;
        pntRet.x = p1.x + (p2.x - p1.x) * Ratio;
    }
    else
    {
        pntRet.x = p1.x + (p2.x - p1.x) * Ratio;
        pntRet.y = p1.y + (p2.y - p1.y) * Ratio;
    }
    return pntRet;
}

void CRecursiveCurvesView::DragonCurve(int n, FPOINT p1, FPOINT p2, CDC* pDC)
{
    if (n == 1)
    {
        DrawLine(p1, p2, pDC);
    }
    else
    {
        FPOINT pc = ShortenLine(p1, p2, 1.0 / sqrt(2.0));
        pc = RotateLine(p1, pc, -atan(1.0));
        DragonCurve(n - 1, p1, pc, pDC);
        DragonCurve(n - 1, p2, pc, pDC);
    }
}

void CRecursiveCurvesView::OnDragonCurve() 
{
    CClientDC dc(this);
    FPOINT p1 = {200, 300};
    FPOINT p2 = {456, 300};
    DragonCurve(12, p1, p2, &dc);
}