再帰曲線 コッホ曲線(アルゴリズム)

Koch Curve Recursive Algorithm

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



n段の中にある１本の線分は、４本の(n-1)段の線分で構成されます。n段の線分の長さの1.0とすれば、(n-1)段の線分の長さは1/3で、(n-1)段の間中の２本線は６０°の三角状になります。下の絵は、６段のコッホ曲線です。自作の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::KochCurve(int n, FPOINT p1, FPOINT p2, CDC* pDC)
{
    if (n == 1)
    {
        DrawLine(p1, p2, pDC);
    }
    else
    {
        FPOINT pc1 = ShortenLine(p1, p2, 1.0 / 3.0);
        FPOINT pc2 = ShortenLine(p1, p2, 2.0 / 3.0);
        FPOINT pc = RotateLine(pc1, pc2, -acos(1.0/2.0));
        KochCurve(n - 1, p1, pc1, pDC);
        KochCurve(n - 1, pc1, pc, pDC);
        KochCurve(n - 1, pc, pc2, pDC);
        KochCurve(n - 1, pc2, p2, pDC);
    }
}

void CRecursiveCurvesView::OnKochCurve()
{
    CClientDC dc(this);
    FPOINT p1 = {200, 300};
    FPOINT p2 = {800, 300};
    KochCurve(6, p1, p2, &dc);
}