1052 Quiz#1 筆劃類別 (Stroke) 參考程式

在這個測試裡, 我們要製作一個「筆劃」的類別, 目的是支援一個「1052Quiz1 隨意筆」的繪圖程式來運作, 這個程式執行起來的畫面如下:

你可以點上面的連結 (或是上面這張圖) 在你的機器上執行 (如果沒有安裝 vc2010, 需要有 vc10 redistributable DLLs， 請下載、解壓縮、拷貝 32bit\*.dll 或是 64bit\*.dll 到 c:\windows\system32)

你可以運用滑鼠在視窗裡隨意繪圖, 例如:

這個程式和 Windows 的小畫家不一樣, 小畫家是一個點陣圖的繪圖程式, 整個視窗是一個畫布, 畫出來的都是獨立的點, 每一筆並不是一個物件, 你不能再用滑鼠去點一個筆劃, 去修改原先的東西; 我們這個程式希望是一個向量化的繪圖程式, 所以我們希望用筆劃為單位來存放資料, 像上圖裡面就只有兩個筆劃。這個程式還沒有完整的功能, 目前可以開多個視窗、分割視窗、畫粗線條、畫細線條、清除畫布、存檔、讀檔、列印、預覽列印等等，複製/貼上、選取筆劃、選取區域中所有筆劃、刪除所選取筆劃、修改所選的筆劃的粗細、修改顏色、移動某一筆劃、放大/縮小、移到最上層、下移一層、上移一層，...都還沒有寫, 別擔心, 不是請你現在寫這些, 只是希望你設計一個筆劃的類別來儲存一筆所畫出來的資料, 以便支援這個程式。

這個程式的存檔功能在設計的時候, 存出去的 *.qz1 檔案是二進位模式的檔案, 在其它文字編輯器裡面讀出來會是亂碼, 不過再由這個程式讀進來的話還是可以顯示的。為了這次考試, 我們額外設計了一個功能是用文字模式來儲存 *.txt 的文字檔案如下圖:

選取上面的選單以後可以看到 Windows 標準的檔案選取對話盒:

填入檔案名稱 (例如 CS)、按下存檔可以把筆劃的資料存在 CS.txt 中

這個檔案中有上圖中筆劃的資料 (你可以自己產生資料檔案, 也可以下載下面的文字檔案)

CS.txt

以這個檔案來說, 裡面主要依序包含兩個筆劃的資料，格式說明如括號中文字:

2 (本檔案裡筆劃總數)
64 -45 140 -128 (「含括第一筆的最小長方形邊框」, 左上右下, 請見下圖說明)
5 (第一筆的粗細)
205 (第一筆的點數)
134 -60 (第一筆的第一點的 x 座標與 y 座標)
133 -60 (第一筆的第二點的 x 座標與 y 座標)
131 -57  。。。
。
。
。
126 -103
126 -103
97 -50 197 -142 (「含括第二筆的最小長方形邊框」, 左上右下, 請見下圖說明)
2 (第二筆的粗細)
344 (第二筆的點數)
180 -52 (第二筆的第一點的 x 座標與 y 座標)
180 -52 (第二筆的第二點的 x 座標與 y 座標)
180 -53 。。。
。
。
。
99 -138
99 -138

「含括某一筆劃的最小長方形邊框」所代表的意思如下圖:

也就是含括那一筆劃圖形的最小長方形 - (left, top, right, bottom), 也就是所有這個筆劃的圖形的 x 座標的範圍是 left+width ≤ x_i < right-width, y 座標的範圍是 bottom+width ≤ y_i < top-width, 這裡因為筆劃有寬度 width, 所以我們直接加上筆劃的寬度來簡單近似這個最小長方形, 也就是最小的長方形是覆蓋那些點座標的長方形四周再放大 width 格的那個長方形, 請注意所有的點的 x 座標都小於 right-width, 所有的點的 y 座標都大於 bottom+width。

下面是運用 stdio.h 函式庫來開啟這個檔案並且讀取資料的 C 程式, 程式直接把資料讀到一個自己定義的結構 struct Point 的陣列中

#include <stdio.h>
#include <assert.h>

struct Point
{
    int x;
    int y;
};

struct BoundingRect
{
    int left;
    int top;
    int right;
    int bottom;
};

int isEqual(BoundingRect br1, BoundingRect br2);
void calcBoundingRect(int length, int width, Point stroke[], BoundingRect *br);

int main()
{
    FILE *fp;
    int i, j, nStrokes;
    int widths[2];
    int lengths[2];
    BoundingRect brs[2], mybrs[2];
    Point strokes[2][500];

    fp = fopen("CS.txt", "r");
    if (fp==0)
    {
        printf("無法開啟 CS.txt\n");
        return 1;
    }
    fscanf(fp, "%d", &nStrokes);
    for (i=0; i<nStrokes; i++)
    {
        fscanf(fp, "%d%d%d%d", &brs[i].left, &brs[i].top,
                               &brs[i].right, &brs[i].bottom);
        fscanf(fp, "%d", &widths[i]);
        fscanf(fp, "%d", &lengths[i]);
        for (j=0; j<lengths[i]; j++)
            fscanf(fp, "%d%d", &strokes[i][j].x, &strokes[i][j].y);
        calcBoundingRect(lengths[i], widths[i], strokes[i], &mybrs[i]);
        printf("%d %d %d %d\n", brs[i].left, brs[i].top,
                                brs[i].right, brs[i].bottom);
        printf("%d %d %d %d\n", mybrs[i].left, mybrs[i].top,
                                mybrs[i].right, mybrs[i].bottom);
        assert(isEqual(brs[i], mybrs[i]));
    }
    fclose(fp);
    return 0;
}

int isEqual(BoundingRect br1, BoundingRect br2)
{
    return (br1.left==br2.left)&&
           (br1.top==br2.top)&&
           (br1.right==br2.right)&&
           (br1.bottom==br2.bottom);
}

void calcBoundingRect(int length, int width, Point stroke[], BoundingRect *br)
{
    int i;
    br->left = 10000, br->top = -10000;
    br->right = -10000, br->bottom = 10000;
    for (i=0; i<length; i++)
    {
        if (stroke[i].x < br->left)
            br->left = stroke[i].x;
        if (stroke[i].x > br->right)
            br->right = stroke[i].x;
        if (stroke[i].y < br->bottom)
            br->bottom = stroke[i].y;
        if (stroke[i].y > br->top)
            br->top = stroke[i].y;
    }
    br->left -= width;
    br->right += (width+1);
    br->top += width;
    br->bottom -= (width+1);
}

請撰寫一個 C++ 程式, 運用 iostream 開啟檔案並且讀取資料, 同時設計一個 Stroke 類別, 這個類別需要管理一筆劃裡面所有的點, 這個類別以及程式的要求如下：

1. 在私有資料區請用一個 C++ 標準函式庫中的 vector 型態的資料成員來存放這些點, 每一個點還是用上面的 struct Point 來表示; 請再運用上面的 struct BoundingRect 定義一個 BoundingRect 型態的資料成員記錄「含括某一筆劃的最小長方形邊框」
   
   
2. 請設計一個 Stroke::addPoint(Point) 的介面來把點依序加入這個 Stroke 類別的物件中, 由於在上面的視窗應用程式中, 滑鼠是由系統控制的物件, 滑鼠物件在左鍵按下時會傳送一個訊息給你的程式, 此時你的程式就可以去產生一個 Stroke 的物件, 其後只要滑鼠左鍵是按下的情況下, 每一小段時間滑鼠就會傳送一個目前所在位置 point 的訊息給你的應用程式, 你的程式在處理這個訊息的時候就可以呼叫 addPoint(point) 來把這個點加入筆劃中, 這個 Stroke 物件應該要有一個存放輸入狀態的布林變數 inputMode, 如果是 true 代表可以輸入, 直到滑鼠左鍵放開時你才去把這個變數設為 false (等一下我們會設計一個介面來完成這件事), 此後 addPoint(pt) 會沒有作用, 目前我們還不是寫視窗的程式, 請在 main 中由檔案中讀取筆劃裡面所有的點, 動態配置 (new) 一個 Stroke 物件, 把輸入狀態設為 true, 運用這個 addPoint 介面把讀到的點一筆一筆加入 Stroke 物件中
   
   
3. 因為我們的應用程式需要處理好多筆劃, 個別都是筆劃類別的物件, 所以 main 裡面請再運用一個 vector 來存放所有的筆劃物件
   
   
4. 請替 Stroke 類別設計一個 Stroke::calcBoundingRect() 的輔助函式, 這個函式應該能夠計算出「含括此筆劃的最小長方形邊框」, 並且請設計資料成員來存放邊框的左、上、右、下座標值 (這個邊框在最後系統中有兩個用途: 第一是繪圖系統重繪時可以只繪出需要的部份, 第二是我們以後用滑鼠來選取筆劃時, 可以快速測試是否可能是某一個筆劃)
   
   
5. 請設計一個 void Stroke::finish() 的介面, 想像一下上面的視窗應用程式中, 使用者放開滑鼠左鍵時, 視窗系統會傳送一個訊息給你的程式, 這個時候就需要呼叫這個 finish() 介面來結束輸入狀態, 同時順便呼叫 calcBoundingRect() 來計算最小長方形邊框
   
   
6. 請替 Stroke 類別設計一個 int Stroke::select1(Point pt, double r) 的介面, 這個介面很快地去比對參數 pt 是不是和筆劃中某一個點的距離小於 r (也就是在以 pt 為圓心, 半徑 r 的圓的範圍內), 請回傳 「pt 最接近筆劃中第幾個點」, 沒有比對到請回傳 -1, 這個介面其實是為了以後我們用滑鼠點選某一筆劃時, 判斷到底哪一筆劃的哪一點被點到了的功能寫的 (vector 類別的物件可以用陣列的方式來使用, 或是用 iterator 來使用)
   
   
7. 如果你時間夠的話請替 Stroke 類別在設計一個 int Stroke::select2(Point pt, double r) 的介面, 由於我們用最簡單的方式繪製這個筆劃, 也就是直接把相鄰的點連接起來, 如果滑鼠點到兩個點的連接線段, 應該也要算是選到這一個筆劃, 這個介面就是要很快地去比對參數 pt 是不是和筆劃中某兩個點的連線段距離小於 r, 這個功能你需要算一下點到直線的距離, 如果直線方程式表示成 f(x,y) = a x + b y + c = 0 的話, 任意點 (x₀, y₀) 到直線的距離是 | f(x₀, y₀) | / sqrt(a²+b²), 請回傳 「pt 最接近那個線段的兩個端點中的第一個點是筆劃中第幾個點」, 沒有比對成功請回傳 -1
   
   
8. 請替 Stroke 類別設計一個平移筆劃 void Stroke::shift(Point offset) 的介面, 未來在視窗版的應用程式中, 如果某一筆劃被選到了, 我們希望能夠平移這一筆劃
   
   
9. 請替 Stroke 類別設計一個刪除點 void Stroke::deletePoint(int i) 的介面, 未來在視窗版的應用程式中, 如果某一筆劃中第 i 個點被選到了, 我們希望能夠刪掉那一個點 (請查詢一下 vector 類別有一個 erase 的成員可以使用)
   
   
10. main 函式裡主要的動作如下
    
    a. 定義一個 Stroke 指標的 vector 來存放所有由檔案中讀到的筆劃
    
    b. 開啟檔案串流 (請固定檔案名稱為 CS.txt)
    
    c. 由檔案中依序讀出所有筆劃、所有點、動態配置出每一個 Stroke 物件, 每一筆劃讀完以後記得呼叫 finish()
    
    d. 運用 assert 確認計算出來的最小長方形邊框和檔案裡讀出來的是不是一致
    
    e. 請根據上面 CS.txt 設計資料運用 assert 來測試 select1, select2, shift, deletePoint 是否正確運作
    
    f. 解構所有的筆劃 (串流會自己在解構元中關閉, 所以可以不用特別去關閉它)

#include <iostream>
#include <fstream>
#include <cassert>
#include <vector>
#include <cmath>   // sqrt
#include <cstdlib> // exit
using namespace std;

struct Point
{
    Point(): x(0), y(0) {}
    Point(int x, int y): x(x), y(y) {}
    int x;
    int y;
};

struct BoundingRect
{
    BoundingRect(): left(0),top(0),right(0),bottom(0) {}
    int left;
    int top;
    int right;
    int bottom;
};

class Stroke
{
public:
    Stroke(int width);
    void addPoint(Point point);
    void finish();
    int select1(Point pt, double r);
    int select2(Point pt, double r);
    void shift(Point offset);
    void deletePoint(int idx);
    static void unitTest();
private:
    void calcBoundingRect();
    double lineDist(int idx, Point pt);
    bool isBoundingRectEqual(BoundingRect br);

    vector<Point> m_points;
    int m_width;
    bool m_inputMode;
    BoundingRect m_br;
};

Stroke::Stroke(int width)
    : m_width(width),
      m_inputMode(true)
{
}

void Stroke::addPoint(Point point)
{
    if (m_inputMode)
        m_points.push_back(point);
}

void Stroke::finish()
{
    m_inputMode = false;
    calcBoundingRect();
}

void Stroke::calcBoundingRect()
{
    int i;
    m_br.left = 10000, m_br.top = -10000;
    m_br.right = -10000, m_br.bottom = 10000;
    for (i=0; i<m_points.size(); i++)
    {
        if (m_points[i].x < m_br.left)
            m_br.left = m_points[i].x;
        if (m_points[i].x > m_br.right)
            m_br.right = m_points[i].x;
        if (m_points[i].y < m_br.bottom)
            m_br.bottom = m_points[i].y;
        if (m_points[i].y > m_br.top)
            m_br.top = m_points[i].y;
    }
    m_br.left -= m_width;
    m_br.right += (m_width+1);
    m_br.top += m_width;
    m_br.bottom -= (m_width+1);
}

int Stroke::select1(Point pt, double r)
{
    int i, min=-1;
    double d, dmin=10000.;
    for (i=0; i<m_points.size(); i++)
        if ((d=sqrt((double)(m_points[i].x-pt.x)*
                            (m_points[i].x-pt.x)+
                            (m_points[i].y-pt.y)*
                            (m_points[i].y-pt.y))) < r)
            if (d<dmin) dmin=d, min=i;
    if (min!=-1)
        return min;
    else
        return -1;
}

double Stroke::lineDist(int idx, Point pt)
{
    if (m_points[idx].x>=m_points[idx+1].x)
    {
        if (pt.x>m_points[idx].x||pt.x<m_points[idx+1].x)
            return 10000;
    }
    else
    {
        if (pt.x<m_points[idx].x||pt.x>m_points[idx+1].x)
            return 10000;
    }
    if (m_points[idx].y>=m_points[idx+1].y)
    {
        if (pt.y>m_points[idx].y||pt.y<m_points[idx+1].y)
            return 10000;
    }
    else
    {
        if (pt.y<m_points[idx].y||pt.y>m_points[idx+1].y)
            return 10000;
    }
    if (m_points[idx].x!=m_points[idx+1].x)
    {
        double a, b, c;
        a = (double)(m_points[idx].y-m_points[idx+1].y) /
                    (m_points[idx].x-m_points[idx+1].x);
        b = -1;
        c = m_points[idx+1].y-a*m_points[idx+1].x;
        return fabs(a*pt.x+b*pt.y+c) / sqrt(a*a+b*b);
    }
    else if (m_points[idx].y!=m_points[idx+1].y)
        return fabs((double)pt.x-m_points[idx].x);
    else
        return sqrt((double)(m_points[idx].x-pt.x)*
                            (m_points[idx].x-pt.x)+
                            (m_points[idx].y-pt.y)*
                            (m_points[idx].y-pt.y));
}

int Stroke::select2(Point pt, double r)
{
    int i, min=-1;
    double d, dmin=10000.;
    for (i=0; i<m_points.size()-1; i++)
        if ((d=lineDist(i, pt)) < r)
            if (d<dmin) dmin=d, min=i;
    if (min!=-1)
        return min;
    else
        return -1;
}

void Stroke::shift(Point offset)
{
    int i;
    if (m_inputMode) return;
    for (i=0; i<m_points.size(); i++)
    {
        m_points[i].x += offset.x;
        m_points[i].y += offset.y;
    }
    m_br.left += offset.x;
    m_br.right += offset.x;
    m_br.top += offset.y;
    m_br.bottom += offset.y;
}

void Stroke::deletePoint(int idx)
{
    if (m_inputMode) return;
    if (idx>=0&&idx<m_points.size())
        m_points.erase(m_points.begin()+idx);
    calcBoundingRect();
}

bool Stroke::isBoundingRectEqual(BoundingRect br)
{
    return (br.left==m_br.left)&&
           (br.top==m_br.top)&&
           (br.right==m_br.right)&&
           (br.bottom==m_br.bottom);
}

void Stroke::unitTest()
{
    int i, j, nStrokes;
    int width, length;
    Point point;
    BoundingRect br;
    Stroke *stroke;
    vector<Stroke *> strokes;
    ifstream ifs("CS.txt");
    if (!ifs) 
        cout << "CS.txt nout found!\n", exit(1);

    ifs >> nStrokes;
    for (i=0; i<nStrokes; i++)
    {
        ifs >> br.left >> br.top >> br.right >> br.bottom;
        ifs >> width >> length;
        stroke = new Stroke(width);
        for (j=0; j<length; j++)
        {
            ifs >> point.x >> point.y;
            stroke->addPoint(point);
        }
        stroke->finish();
        assert(stroke->isBoundingRectEqual(br));
        strokes.push_back(stroke);
    }

    assert(strokes[0]->select1(Point(125,-53),0.001)==13); // (125,-53)
    assert(strokes[0]->select1(Point(125,-53),2.001)==10); // (127,-53)
    assert(strokes[0]->select1(Point(125,-52),1.001)==13); // (125,-53)

    assert(strokes[1]->select1(Point(178,-53),0.001)==4); // (178,-53)

    assert(strokes[1]->select2(Point(146,-67),0.001)==-1); // 45:(147,-66)~46:(145,-67)
    assert(strokes[1]->select2(Point(146,-67),0.45)==45);

    assert(strokes[0]->select1(Point(125,-53),0.001)==13); // (125,-53)
    strokes[0]->deletePoint(13);
    assert(strokes[0]->select1(Point(125,-53),0.001)==-1);

    assert(strokes[1]->select1(Point(180,-52),0.001)==0);
    strokes[1]->shift(Point(10,5));
    assert(strokes[1]->select1(Point(190,-47),0.001)==0);
    
    for (i=0; i<nStrokes; i++)
        delete strokes[i];
    cout << "Unit test finished successfully!\n";
}

int main()
{
    Stroke::unitTest();
}

後續:

接下去能做的事情還蠻明顯的, 就是把整個視窗版的程式完成, 不過我們這學期的課程已經塞進去太多東西了, 不太可能在課程或是實習裡面安排時間講這些東西 (期中考後有一次實習會讓你配合一個視窗界面來寫程式), 如果有同學有興趣知道更詳細的設計方法, 可以讓我知道, 需要另外安排時間介紹。