XY

  作者：路緣

原文網(wǎng)址：http://www.cnblogs.com/xuyuan77/archive/2008/10/13/1310269.html

德國數(shù)學(xué)家David Hilbert發(fā)現(xiàn)了一種曲線，首先把一個正方形等分成四個小正方形，依次從西南角的正方形中心出發(fā)往北到西北正方形中心，再往東到東北角的正方形中心，再往南到東南角正方形中心，這是一次迭代，如果對四個小正方形繼續(xù)上述過程，往下劃分，反復(fù)進(jìn)行，最終就得到一條可以填滿整個正方形的曲線，這就是Hibert曲線，其大致過程如下圖所示

                                Hibert曲線生成過程

下面我們來看如何寫程序生成這樣的曲線，其實不管迭代多少次，都是由如下的圖形

            基本圖 

構(gòu)成，唯一所不同的是開口方向不一樣。開口方向不一樣就涉及到圖像旋轉(zhuǎn)，圖像旋轉(zhuǎn)的基本知識接下來會介紹。目前我們最關(guān)心的是這樣生成的曲線過程右什么規(guī)律，從上述描述生成的過程就已經(jīng)看出了規(guī)律，當(dāng)然人肯定一眼就看出來了，但計算機(jī)如何知道呢？這就是生成Hibert曲線算法的關(guān)鍵了：

為了便于找出規(guī)律，我們來看下面一副圖

上圖中應(yīng)該是把所有開口方向（共四種）都涵蓋了。我們約定四種類型：

開口往南－0，開口往西－1，開口往北－2，開口往東－3。我們結(jié)合基本圖，就有這樣的規(guī)律，畫表如下：

其他的點(diǎn)類似也有類似的規(guī)律，這個規(guī)律才是我們編碼的基礎(chǔ)。是下次遞歸調(diào)用畫圖函數(shù)傳參數(shù)的前提。下面我們來看一下畫圖中涉及到的圖像旋轉(zhuǎn)的相關(guān)數(shù)學(xué)知識。

圖像旋轉(zhuǎn)

圖像旋轉(zhuǎn)是指把定義的圖像繞某一點(diǎn)以逆時針或順時針方向旋轉(zhuǎn)一定的角度，通常是指繞圖像的中心以逆時針方向旋轉(zhuǎn)。

假設(shè)圖像的左上角為（left, top),右下角為（right, bottom)，則圖像上任意點(diǎn)（x0, y0）繞其中心（xcenter, ycenter)逆時針旋轉(zhuǎn)angle角度后，新的坐標(biāo)位置（x′, y′）的計算公式為：

xcenter = (right － left ＋ 1) ／ 2 ＋ left;

ycenter = (bottom － top ＋ 1) ／ 2 ＋ top;

x′ =  (x0 － xcenter) cosθ － (y0 － ycenter) sinθ ＋ xcenter;

y′ =  (x0 － xcenter) sinθ ＋ (y0 － ycenter) cosθ ＋ ycenter;

與圖像的鏡像變換相類似，也采用按行逐點(diǎn)變換的方式實現(xiàn)圖像的旋轉(zhuǎn)。

現(xiàn)在一切都準(zhǔn)備就緒，我們來實現(xiàn)相關(guān)的算法如下：

/**//**********************************************************************************************
功能：實現(xiàn)繪制Hilbert曲線
參數(shù)：
    pDC:設(shè)備上下文
    n:維都
    len:邊長
    x:中心橫坐標(biāo)
    y:中心縱坐標(biāo)
    iType:繪畫類型，開口：0－南，1－西，2-北，3-東
    unit_length：最小單元長度
/**********************************************************************************************/
void CGraphicAppView::DrawHilbert(CDC* pDC, int n, int len, int x, int y, int iType, int unit_length)
{
    //存儲以x,y為中心的西南、西北、東北、東南四角定點(diǎn)的坐標(biāo)
    int arr[4][2];
    arr[0][0] = x -len/4; arr[0][1] =y+len/4; 
    arr[1][0] = x -len/4; arr[1][1] =y-len/4;
    arr[2][0] = x +len/4; arr[2][1] =y-len/4;
    arr[3][0] = x +len/4; arr[3][1] =y+len/4; 
    //存儲以x,y為中心的（西南、西北、東北、東南四角定點(diǎn)）經(jīng)過處理后的坐標(biāo)
    int a[4][2];
    memset(a, 0, sizeof(a));

    int sin_v=0,cos_v=1;//默認(rèn)為0度的值
    switch(iType)//根據(jù)不同的開口方向，對旋轉(zhuǎn)三角函數(shù)賦值
    {
    case 1://開口向左
        sin_v = 1; cos_v = 0;
        break;
    case 2://開口向上
        sin_v = 0; cos_v = -1;
        break;
    case 3:    //開口向右
        sin_v = -1; cos_v = 0;
        break;
    }

    for(int i = 0; i<4; i++)//完成旋轉(zhuǎn)
    {
        a[i][0] = (arr[i][0] - x)*cos_v - (arr[i][1] - y)*sin_v + x;
        a[i][1] = (arr[i][0] - x)*sin_v + (arr[i][1] - y)*cos_v + y;
    }

    CPen newPen(PS_DASHDOTDOT, 2, RGB(y%255, x%255, (y+x)%255));
    pDC->SelectObject(&newPen);        

    if(n > 1)
    {
        int length = len/2;
        DrawHilbert(pDC, n-1, length, a[0][0], a[0][1], (1+iType)%4,unit_length);
        DrawHilbert(pDC, n-1, length, a[1][0], a[1][1], iType,unit_length);
        DrawHilbert(pDC, n-1, length, a[2][0], a[2][1], iType,unit_length);
        DrawHilbert(pDC, n-1, length, a[3][0], a[3][1], (3+iType)%4,unit_length);

        switch(iType)
        {
        case 0:
        case 2:
            pDC->MoveTo(x-length + 0.5*unit_length, y + 0.5*unit_length);
            pDC->LineTo(x-length + 0.5*unit_length, y - 0.5*unit_length);

            pDC->MoveTo(x-0.5*unit_length, y - (1-iType)*0.5*unit_length);
            pDC->LineTo(x+0.5*unit_length, y - (1-iType)*0.5*unit_length);

            pDC->MoveTo(x+length - 0.5*unit_length, y + 0.5*unit_length);
            pDC->LineTo(x+length - 0.5*unit_length, y - 0.5*unit_length);
            break;
        case 1:
        case 3:
            pDC->MoveTo(x-0.5*unit_length, y -length + 0.5*unit_length);
            pDC->LineTo(x+0.5*unit_length, y -length + 0.5*unit_length);

            pDC->MoveTo(x+(2-iType)*0.5*unit_length, y - 0.5*unit_length);
            pDC->LineTo(x+(2-iType)*0.5*unit_length, y + 0.5*unit_length);

            pDC->MoveTo(x-0.5*unit_length, y +length - 0.5*unit_length);
            pDC->LineTo(x+0.5*unit_length, y +length - 0.5*unit_length);
            break;
        }
    }
    else
    {        
        pDC->MoveTo(a[0][0], a[0][1]);
        pDC->LineTo(a[1][0], a[1][1]);
        pDC->LineTo(a[2][0], a[2][1]);
        pDC->LineTo(a[3][0], a[3][1]);
    }
}

其次希望有朋友能有更好的算法，希望不吝賜教，先謝過了。最后我們來看一下迭代6次的一個運(yùn)行結(jié)果圖：

調(diào)用的代碼段如下：

void CGraphicAppView::OnDraw(CDC* pDC)
{
    CGraphicAppDoc* pDoc = GetDocument();
    ASSERT_VALID(pDoc);
    if (!pDoc)
        return;
    // TODO: add draw code for native data here
    int n = 6;
    long t = ::pow(2.0, n);
    int length = 400;
    int unit_length = length/t;
    DrawHilbert(pDC, n, length, 200, 200, 0, unit_length);
}