多边形扫描转换 采用活化边表的有序边表算法多边形填充（MFC）

void CCGPainterView::ScanLineFillConvert(CDC* pDC, CPoint startPoint, COLORREF fillCol, COLORREF boundaryCol)

{

    /* 定义结构体用于活性边表 AET 和新边表 NET*/

    typedef struct XET

    {

        double x;

        double dx, ymax;

        XET* next;

    }AET, NET;

    //CPoint *ThePolygon.m_Vertex;

    int vertNum = ThePolygon.m_VerticeNumber;

    /* 计算最高点 y 的坐标，扫描线扫到 y 的最高点就结束 */

    int MaxY = ThePolygon.m_Vertex[0].y;

    int MinY = ThePolygon.m_Vertex[0].y;

    int i;

    for (i = 1; i < vertNum; i++) {

        if (ThePolygon.m_Vertex[i].y > MaxY)

            MaxY = ThePolygon.m_Vertex[i].y;

        if (MinY > ThePolygon.m_Vertex[i].y)

            MinY = ThePolygon.m_Vertex[i].y;

    }

    /* 初始化 AET 表，这是一个有头结点的链表 */

    AET* pAET = new AET;

    pAET->next = NULL;

    /* 初始化 NET 表，这也是一个有头结点的链表，头结点的 dx，x，ymax 都初始化为 0*/

    NET* pNET[1024];

    for (i = 0; i <= MaxY; i++) {

        pNET[i] = new NET;

        pNET[i]->dx = 0;

        pNET[i]->x = 0;

        pNET[i]->ymax = 0;

        pNET[i]->next = NULL;

    }

    /* 扫描并建立 NET 表 */

    for (i = MinY; i <= MaxY; i++) {

        /*i 表示扫描线，扫描线从多边形的最底端开始，向上扫描 */

        for (int j = 0; j < vertNum; j++)

            /* 如果多边形的该顶点与扫描线相交，判断该点为顶点的两条直线是否在扫描线上方

             * 如果在上方，就记录在边表中，并且是头插法记录，结点并没有按照 x 值进行排序，毕竟在更新 AET 的时候还要重新排一次

             * 所以 NET 表可以暂时不排序

            */

            if (ThePolygon.m_Vertex[j].y == i) {

                /* 笔画前面的那个点 */

                if (ThePolygon.m_Vertex[(j - 1 + vertNum) % vertNum].y > ThePolygon.m_Vertex[j].y) {

                    NET* p = new NET;

                    p->x = ThePolygon.m_Vertex[j].x;

                    p->ymax = ThePolygon.m_Vertex[(j - 1 + vertNum) % vertNum].y;

                    p->dx = double((ThePolygon.m_Vertex[(j - 1 + vertNum) % vertNum].x - ThePolygon.m_Vertex[j].x)) / double((ThePolygon.m_Vertex[(j - 1 + vertNum) % vertNum].y - ThePolygon.m_Vertex[j].y));

                    p->next = pNET[i]->next;

                    pNET[i]->next = p;

                }

                /* 笔画后面的那个点 */

                if (ThePolygon.m_Vertex[(j + 1 + vertNum) % vertNum].y > ThePolygon.m_Vertex[j].y) {

                    NET* p = new NET;

                    p->x = ThePolygon.m_Vertex[j].x;

                    p->ymax = ThePolygon.m_Vertex[(j + 1 + vertNum) % vertNum].y;

                    p->dx = double((ThePolygon.m_Vertex[(j + 1 + vertNum) % vertNum].x - ThePolygon.m_Vertex[j].x)) / double((ThePolygon.m_Vertex[(j + 1 + vertNum) % vertNum].y - ThePolygon.m_Vertex[j].y));

                    p->next = pNET[i]->next;

                    pNET[i]->next = p;

                }

            }

    }

    /* 建立并更新活性边表 AET*/

    for (i = MinY; i <= MaxY; i++) {

        /* 更新活性边表 AET，计算扫描线与边的新的交点 x，此时 y 值没有达到临界值的话 */

        NET* p = pAET->next;

        while (p) {

            p->x = p->x + p->dx;

            p = p->next;

        }

        /* 更新完以后，对活性边表 AET 按照 x 值从小到大排序 */

        AET* tq = pAET;

        p = pAET->next;

        tq->next = NULL;

        while (p) {

            while (tq->next && p->x >= tq->next->x)

                tq = tq->next;

            NET* s = p->next;

            p->next = tq->next;

            tq->next = p;

            p = s;

            tq = pAET;

        }

        /* 从 AET 表中删除 ymax==i 的结点 */

        AET* q = pAET;

        p = q->next;

        while (p) {

            if (p->ymax == i) {

                q->next = p->next;

                delete p;

                p = q->next;

            }

            else {

                q = q->next;

                p = q->next;

            }

        }

        /* 将 NET 中的新点加入 AET，并用插入法按 X 值递增排序 */

        p = pNET[i]->next;

        q = pAET;

        while (p) {

            while (q->next && p->x >= q->next->x)

                q = q->next;

            NET* s = p->next;

            p->next = q->next;

            q->next = p;

            p = s;

            q = pAET;

        }

        /* 配对填充颜色 */

        p = pAET->next;

        while (p && p->next) {

            for (float j = p->x; j <= p->next->x; j++) {

                pDC->SetPixel(static_cast<int>(j), i, fillCol);

            }

            p = p->next->next;

        }

    }

}