堆疊式線段追蹤

　
用 recursion 在線段複雜時會造成 stack overflow，
因此需要 heap 解。

LineTrace 提供了 singleton 介面，但不建議在大型專案中使用，
因為它除了有 global variable 的缺點外，
和其他類別合作時，會引入建構解構上的相依性，難以 debug。
應盡量把 LineTrace 設計成 class component 來用。

#include "global.h"
#include "help_fn.h"
#include "new_arr.h"

//-------------------------------------------------------------
// state 紀錄圖中每一點的追蹤狀態:
//
//      ６７８
//      ５米１
//      ４３２
//
// 狀態 = 0 表示非邊線點
//-------------------------------------------------------------

class LineTrace
{
    enum {W=512, H=512};         //狀態圖的最大寬高

    int        w, h;             //檢測邊界
    IplImage*  out;              //輸入邊線圖, 同時用來存放輸出結果
    IplImage*  mark;             //阻隔點, 遇阻隔點則不再追蹤下去

    int        nPos;             //堆疊頂端指標
    int*       posx;             //紀錄追蹤位置的堆疊
    int*       posy;             //
    uchar*     state;            //標示圖中每一點的追蹤狀態

    static LineTrace* self;      //Singleton

    void check_vaild()           //確認資料的有效性
    {
        if (out == 0) ERROR_MSG_("out == 0");
        if (mark== 0) ERROR_MSG_("mark == 0");
        if (out->width  > W) 
            ERROR_MSG3_("影像寬度: %d > %d", out->width, W);
        if (out->height > H) 
            ERROR_MSG3_("影像高度: %d > %d", out->height, H);
    }

public:

    static LineTrace& instance()
    {
        if (self == 0) self = new LineTrace;
        return *self;
    }
    static void release()
    {
        delete self;
    }

    LineTrace()
    {
        posx  = new int  [W*H];
        posy  = new int  [W*H];
        state = new uchar[W*H];
    }
   ~LineTrace()
    {
        delete[] posx;
        delete[] posy;
        delete[] state;
    }
    void setImage (IplImage* out_, IplImage* mark_)
    {
        out  = out_;
        mark = mark_;
        check_vaild();
    }

    void trace (int ox, int oy)         // (ox,oy) = trace 的起始座標
    {
        static CvScalar red = cvScalar (0,255,0);
        int x, y;                           //目前 trace 到的點座標
        int dir;                            //目前要 trace 的方位
        CvScalar c, c2;

        check_vaild();
        nPos = 0;

        #define PUSH(px,py) \
            nPos++;\
            posx[nPos] = x = px;\
            posy[nPos] = y = py;\
            dir = state[nPos] = 1;

        #define POP \
            nPos--;\
            x = posx[nPos];\
            y = posy[nPos];\
            dir = state[nPos];

        PUSH (ox,oy);                       //邊界衛兵 :-)
        PUSH (ox,oy);                       //將起始座標推入堆疊
                                            //開始進行線段追蹤
        while (nPos > 1) 
        {
            if (nPos >= W*H) 
                ERROR_MSG_("stack overflow!");

            if (dir == 1) {                 //若是第一次檢測某個座標點
                c  = cvGet2D (out,  y, x);  //就取出顏色值
                c2 = cvGet2D (mark, y, x);

                if (c.val[0] == 0 ||        //若不是邊緣線
                    c2.val[0] > 0){         //或是遇到阻礙點 
                    POP;                    //便回復先前的狀態
                    continue;               //退回上個節點
                }
                cvSet2D (out, y, x, red);   //標示追蹤過的線
            }
            if (dir <= 0) {                 //這是不可能發生的
                puts ("error!"); getch();
            }
            if (dir > 8) {                  //若所有方向都檢測過了
                POP                         //便回復先前的狀態     
                continue;                   //退回上個節點
            }
            else {
                state[nPos]++;              //遞增目前節點的方向值
                switch (dir) {              //移至特定方位的鄰居點       
                    case 1: x++;      break;
                    case 2: x++; y++; break;
                    case 3:      y++; break;
                    case 4: x--; y++; break;
                    case 5: x--;    ; break;
                    case 6: x--; y--; break;
                    case 7:      y--; break;
                    case 8: x++; y--; break;    
                }
                PUSH (x,y);                 //將鄰居點推入堆疊頂端
            }                               //進行邊線追蹤
        }
        #undef PUSH
        #undef POP
    }
};

LineTrace* LineTrace::self = 0;


#define ef else if 


//-------------------------------------------------------------
// 說明:
//     壓著左鍵移動滑鼠  - 畫出線條
//     按中間的滾輪鍵    - 加入阻隔點
//     在線段上按右鍵    - 進行線段追蹤
//     按空白鍵         - 重置畫面
//     按 ESC          - 離開程式 
//-------------------------------------------------------------

struct Painter
{
    static LineTrace tracer;                //線段追蹤器
    static IplImage* src;                   //畫板
    static IplImage* mark;                  //阻隔點
    static CvPoint   pt;                    //先前的點座標

    Painter (char* path = 0)                //可傳入黑白圖檔
    {
        if (path) src = cvLoadImage (path, CV_LOAD_IMAGE_GRAYSCALE);
        else      src = cvCreateImage (cvSize (400,400), 8, 3);

        mark = cvCreateImage (cvGetSize (src), 8, 3);
        reset();
        tracer.setImage (src, mark);
        cvNamedWindow ("image", 1);
        cvSetMouseCallback ("image", on_mouse, 0);
    }
   ~Painter()
    {                                       //釋放資源
        cvDestroyWindow ("image");
        cvReleaseImage (&src);
        cvReleaseImage (&mark);
    }
    static void reset()                     //清除畫面
    {
        cvZero (src);
        cvZero (mark);
    }

    static void on_mouse (int event, int x, int y, int flags, void*)
    {
        static CvScalar white = CV_RGB (255,255,255);

        if (src == 0) return;
     
        if (event == CV_EVENT_LBUTTONUP)        //如果放開了滑鼠左鍵
            //!(flags & CV_EVENT_FLAG_LBUTTON))   //或按下了其他鍵
            pt = cvPoint (-1,-1);               //便重置描繪起始點

        ef (event == CV_EVENT_MBUTTONUP) 
        {
            cvCircle (mark, cvPoint(x,y), 4, white, -1);
            cvCircle (src,  cvPoint(x,y), 4, CV_RGB(0,180,255), -1);
            show();
        }
        ef (event == CV_EVENT_RBUTTONUP) 
        {
            puts ("start tracing");
            for (int j,i=-1; i<2; ++i)
                for (j=-1; j<2; ++j)
                    tracer.trace (x+i, y+j);
            puts ("end tracing");
            show();
        }        
        ef (event == CV_EVENT_LBUTTONDOWN)
            pt = cvPoint (x,y);
        ef (event == CV_EVENT_MOUSEMOVE &&      //若移動滑鼠
            (flags & CV_EVENT_FLAG_LBUTTON) )   //且壓著左鍵
        {
            CvPoint p = cvPoint (x,y);
            if (pt.x < 0) pt = p;
            cvLine (src, pt, p, white, 1, 8, 0);
            pt = p;
            show();
        }
    }
    static void show()
    {
        cvShowImage ("image", src);
    }
};

LineTrace Painter::tracer;
IplImage* Painter::src;
IplImage* Painter::mark;
CvPoint   Painter::pt;


int main()
{
    Painter painter;
    painter.show();
    
    while (true)
    {
        int key = cvWaitKey(0);
 
        if (key == 27)  break;
        ef (key == ' ') {
            painter.reset();
            painter.show();
        }
    }
}

執行結果：
畫了張圖做測試~~~