圖形學初步----------多邊形填充算法
參考博文：算法
https://blog.csdn.net/xiaowei_cqu/article/details/7693985數據結構
https://blog.csdn.net/xiaowei_cqu/article/details/7712451框架
https://blog.csdn.net/wodownload2/article/details/52154207函數
https://blog.csdn.net/u013044116/article/details/49737585/.net
https://blog.csdn.net/guanyuqiu/article/details/53010025指針
1、概述
通常來說，計算機的填充輪廓線的方法有兩大類：掃描轉換和種子填充。code
掃描轉換：按掃描線的順序肯定某一點是否位於多邊形或輪廓形範圍以內。這些算法通常從多邊形或輪廓線的「頂部」開始進行到「底部」。掃描轉換技術適用於光柵掃描設備和畫線顯示器。在畫線顯示器中用於畫剖面線或輪廓的陰影線。以下blog
種子填充：首先假定封閉輪廓線內某點是已知的。而後算法開始搜索與種子相鄰且位於輪廓線內的點。若是相鄰點不位於輪廓線內，那麼就已經到達輪廓線的邊界。若是相鄰點位於輪廓線內，那麼這個點就成爲新的種子點，而後繼續遞歸地搜索下去，種子填充算法只適用於光柵掃描設備。排序
2、多邊形填充
多邊形
多邊形在計算機中有頂點表示和點陣表示兩種。遞歸
頂點表示就是用多邊形的頂點序列來表示多邊形。點陣表示是用位於多邊形內的象素集合來表示多邊形。頂點表示佔內存少，幾何意義強，易於進行幾何變換；而點陣表示丟失了許多幾何信息（如邊界、頂點）。但光柵顯示圖形須要點陣表示形式。
多邊形的掃描轉換就是把多邊形的頂點表示轉換爲點陣表示。
多邊形掃描轉換
填充多邊形最簡單的方法就是：
檢查光柵的每一像素是否位於多邊形內。可是這種效率實在過低了。有人曾經想到要用包圍盒來減小計算量，所謂包圍盒就是包含該多邊形的最小矩形。只有在包圍盒的那些點須要檢查。可是這個算法若是遇到下右圖也不見得是種好方法。
因而有人提出了多邊形的掃描轉換，在給定的掃描線上，像素這種特性只在多邊形的邊和該掃描線交點處纔會發生變化。因而咱們就能夠拿這些交點來操做，經過一系列算法進行填充，好比下圖：
咱們能夠看到，掃描線2和多邊形交於x=1和x=8，這兩個交點把掃描線分紅了三段：
x<1 多邊形外 1<=x<=8 多邊形內 x>8 多邊形外
咱們只須要把1<=x<=8，y=2，這段像素置成填充的值，而x<1,y=2;x>8,y=2這段像素置成背景色就能夠了。以此類推，只要是能求出交點，讓計算機把交點認識清楚，就可以準確無誤的完成填充。那麼怎麼「認識」交點呢？
關於這個方法，有人提出了簡單的奇偶掃描轉換算法，它的主要思路就是：在掃描線開始時，奇偶位設置爲0，表示掃描線在多邊形的外部；掃描線與多邊形第一次相交時，奇偶位設置爲1，表示掃描線如今在多邊形的內部；到下一個交點時，奇偶位設置爲0，表示掃描線已經過多邊形，又在多邊形的外部。當奇偶位爲0時，像素設置成多邊形背景色，不然，設置爲多邊形色。
後來有人提出了更爲有效的有序邊表算法，它的基本思想是將多邊形邊與掃描線的交點進行排序。這個算法是本文的重點，最後會用代碼實現。
1，首先來講下這個算法用到的數據結構：邊表NET+活性邊表AET。原理上講，填充的時候是根據活性邊表AET進行填充的，可是活性邊表AET的更新又是依據邊表NET。那麼NET到底存儲的是什麼呢，用「邊」的思路理解有點彆扭，在我看來這個NET存儲的就是多邊形頂點與掃描線相交的信息：
數據結構：
x 當前掃描線與邊的交點座標；dx從當前掃描線到下一條掃描線間x的增量（(x2-x1)/(y2-y1)）；ymax 該邊所交的最高掃描線
數據結構代碼表示：
/*定義結構體用於活性邊表AET和新邊表NET*/
typedef struct XET
{
double x;
double dx, ymax;
XET* next;
}AET,NET;
舉例：
對於下圖多邊形：
它的邊表NET就是：
咱們看到掃描線1，它與P2(5,1)相交對吧~， 那麼x的值就是5，因爲通過P2的邊有兩條，而這兩條邊y的最大值分別是2,3；斜率的倒數分別是-3,2.5。因而邊表NET頭結點1後面跟的兩個節點就這樣寫了
爲何掃描線4的邊表爲空呢，由於掃描線4與多邊形相交的邊p1p6,p3p4已經被記錄了，再也不是新邊了，因此不記錄了。若是仍是看不懂的話，看這個blog，講的一看就懂：
https://blog.csdn.net/wodownload2/article/details/52154207
邊表根據多邊形進行初始化的代碼以下：
/*初始化頭結點*/
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了， 更新的原則就是：
一、根據給出的多邊形頂點座標，創建NET表；
求出頂點座標中最大y值ymax和最小y值ymin。
二、初始化AET表指針，使它爲空。
三、執行下列步驟直至NET和AET都爲空．
3.一、如NET中的第y類非空，則將其中的全部邊取出並插入AET中；
3.二、若是有新邊插入AET，則對AET中各邊排序；
3.三、對AET中的邊兩兩配對，（1和2爲一對，3和4爲一對，…），
將每對邊中x座標按規則取整，得到有效的填充區段，再填充．
3.四、將當前掃描線縱座標y值遞值1；
3.五、若是AET表中某記錄的ymax=yj，則刪除該記錄 （由於每條邊被看做下閉上開的）；
3.六、對AET中剩下的每一條邊的x遞增dx，即x' = x+ dx ．
想要看到具體動態的步驟仍是參考這篇博文，給的太詳細了，看完確定能知道是怎麼個流程：
https://blog.csdn.net/wodownload2/article/details/52154207
更新AET的代碼以下：
/*創建並更新活性邊表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;
}
}
因此整個函數的實現是這樣的：
void CCGPainterView::ScanlineConvertion(CDC *pDC, MyPolygon ThePolygon, COLORREF fillCol)
{
//Write your own scan-line convertion algorithm here.
/*定義結構體用於活性邊表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;
}
}
}
我是在vs2013下，MFC框架下執行，最後的執行效果以下，填充速度仍是很是快的：
本文主要是給出能運行的代碼，關於原理更爲詳盡的解釋請看參考blog。