一直都想寫這篇文章,由於我本身作實驗的時候困擾了好久,網上貌似沒看到徹底正確的代碼,或許是我沒有找到。這個的算法原本很簡單,因此我這裏並不敘述邊界標誌算法通常性的算法思想了,我只討論實踐中遇到的問題,因此看這篇文章以前,你最好已經明白邊界標誌算法的大體流程了。接下來就討論一下:因爲咱們要用到前面的算法畫直線,以及原本在計算機上畫圖,就是一個近似的問題,因此這個算法實踐時會遇到一些問題,其實就兩個問題:c++
1.畫多邊形的邊界時,必需要用斜率大於1的算法,不然會出錯。緣由:你想一下,咱們是用掃描線去掃的,它是從y=1慢慢變大,每次遇到邊界就flag取反,那麼若是直線算法是很精確的討論了斜率大於1和斜率小於1的狀況時,在斜率小於1的時候就會出錯。由於小於1的時候是x每次增長1,y有可能不變的,由於這是一個近似的過程,因此原本理論上一條掃描線上只有一個點的,實際上卻在那一條掃描線上出現了好幾個點,這樣咱們取反就可能會出錯。因此畫邊界時,必定要注意。算法
2.極值點要單獨討論。在說這個問題的解決方案時,我先說下我是怎麼標記邊界的,首先是我要畫出要填色的多邊形邊界,而後呢,這時背景色和邊界色確定就不同了!因此呢,就能夠經過獲取當前點的顏色來判斷是不是邊界。接下來,就討論極值點的問題,咱們知道遇到極值點,雖然是邊界,可是呢,flag不取反的,因此呢,咱們畫好邊界之後,將極值點塗爲背景色就好了,這樣就能夠沿用之前的算法。函數
理解以上2點,基本上就沒什麼錯誤了,程序以下(估計你不能直接使用下面代碼,由於我只貼出了主要部分,理解以上兩點,你確定能寫出來的!):spa
//主程序code
void CPadPolyView::OnDraw(CDC* pDC)
{
CPadPolyDoc* pDoc = GetDocument();
ASSERT_VALID(pDoc);
// TODO: add draw code for native data here
COLORREF color=RGB(0,0,0);
COLORREF clr,set=RGB(255,0,0);
int flag=-1;
//先把直線畫了
for(int i=0;i<m_lc.m_dot.c;i=i+2)
{
DrawBresenham(p[i][0],p[i+1][0],p[i][1],p[i+1][1],color,pDC);
}
DrawExtreamPoint(pDC);
//獲得全部點
for(i=ymin;i<=ymax;i++)
{
flag=-1;
for(int j=xmin;j<=xmax;j++)
{
clr=pDC->GetPixel(j,i);
if(flag==1)
{
pDC->SetPixel(j,i,set);rem
}
if(clr==color)
{
flag=-flag;
}
}
}
}float
//因此的邊界都用斜率大於1的直線算法程序
void CPadPolyView::DrawBresenham(int x1,int x2,int y1,int y2,COLORREF color,CDC* pDC)
{
int flag=0;
float k;
k=(float)(x2-x1)/(float)(y2-y1);
flag=1;
float y=y1;
float x=x1;
int m_y1,m_y2;
if(y1==y2)
{
int xmax=x2;
x=x1;
if(x1>x2)
{
x=x2;
xmax=x1;
}
for(int i=x;i<xmax;i++)
{
pDC->SetPixel(i,y1,color);
}
}
else
{
if(y1>y2)
{
m_y1=y2;
m_y2=y1;
x=x2;
}
else
{
m_y1=y1;
m_y2=y2;
x=x1;
}
for(int i=m_y1;i<m_y2;i++)
{
pDC->SetPixel(int(x+0.5),i,color);
x=x+k;
}
}
}計算機
//將極值點塗爲背景色解決方案
void CPadPolyView::DrawExtreamPoint(CDC* pDC)
{
int temp=m_lc.m_dot.ec;
COLORREF color=RGB(255,255,255);
for(int i=0;i<temp;i++)
{
pDC->SetPixel(ep[i][0],ep[i][1],color);
}
}
//計算極值點的函數
void CDot::GetExtremePoint() { ec=0; int x,y,tempy,temp; int flag=1; CString str; for(int i=0;i<c;i++) { x=p[i][0]; y=p[i][1]; tempy=p[i+flag][1];//第一條邊的y flag=-flag; for(int j=i+1;j<c;j++) { if((p[j][0]==x)&&(p[j][1]==y)) { temp=j%2; if(temp==0) { temp=1; } else { temp=-1; } if(p[j+temp][1]>y)//其中一個點大於y { if(tempy>y)//都大於y,不算,是極值點 { ep[ec][0]=x; ep[ec][1]=y; ec++; } } else if(p[j+temp][1]<y) { if(tempy<y) { ep[ec][0]=x; ep[ec][1]=y; ec++; } } } } } }