多邊形填充演算法

❶ 填充演算法的種子填充演算法

種子填充演算法又稱為邊界填充演算法。其基本思想是：從多邊形區域的一個內點開始，由內向外用給定的顏色畫點直到邊界為止。如果邊界是以一種顏色指定的，則種子填充演算法可逐個像素地處理直到遇到邊界顏色為止。
種子填充演算法常用四連通域和八連通域技術進行填充操作。
從區域內任意一點出發，通過上、下、左、右四個方向到達區域內的任意像素。用這種方法填充的區域就稱為四連通域；這種填充方法稱為四向連通演算法。
從區域內任意一點出發，通過上、下、左、右、左上、左下、右上和右下八個方向到達區域內的任意像素。用這種方法填充的區域就稱為八連通域；這種填充方法稱為八向連通演算法。
一般來說，八向連通演算法可以填充四向連通區域，而四向連通演算法有時不能填充八向連通區域。例如，八向連通填充演算法能夠正確填充如圖2.4a所示的區域的內部，而四向連通填充演算法只能完成如圖2.4b的部分填充。
圖2.4 四向連通填充演算法
a) 連通域及其內點 b) 填充四連通域
四向連通填充演算法：
a） 種子像素壓入棧中；
b） 如果棧為空，則轉e)；否則轉c)；
c） 彈出一個像素，並將該像素置成填充色；並判斷該像素相鄰的四連通像素是否為邊界色或已經置成多邊形的填充色，若不是，則將該像素壓入棧；
d） 轉b）；
e） 結束。
四向連通填充方法可以用遞歸函數實現如下：
演算法2.3 四向連通遞歸填充演算法：
void BoundaryFill4(int x, int y, long FilledColor, long BoundaryColor)
{
long CurrentColor;
CurrentColor = GetPixelColor(x,y);
if (CurrentColor != BoundaryColor && CurrentColor != FilledColor)
{
SetColor(FilledColor);
SetPixel (x,y);
BoundaryFill4(x+1, y, FilledColor, BoundaryColor);
BoundaryFill4(x-1, y, FilledColor, BoundaryColor);
BoundaryFill4(x, y+1, FilledColor, BoundaryColor);
BoundaryFill4(x, y-1, FilledColor, BoundaryColor);
}
}
上述演算法的優點是非常簡單，缺點是需要大量棧空間來存儲相鄰的點。一個改進的方法就是：通過沿掃描線填充水平像素段，來處理四連通或八連通相鄰點，這樣就僅僅只需要將每個水平像素段的起始位置壓入棧，而不需要將當前位置周圍尚未處理的相鄰像素都壓入棧，從而可以節省大量的棧空間。

❷ 求助：誰有C++的多邊形掃描線填充演算法的源代碼！

typedef struct tEdge
{ int yUpper;
float xIntersect,dxPerScan;
struct tEdge *next;
}Edge;
void insertEdge(Edge *list Edge *edge)//將結點插入邊表
{
Edge *p,*q=list;
p=q->next;
while (p!=NULL)
{ if (edge->xIntersect<p->xIntersect) p=NULL;
else { q=p; p=p->next;}
}
edge->next=q->next;
q->next=edge;
}

int yNext(int k,int cnt, dcPt *pts)//求奇異點
{
int j;
if ((k+1)>(cnt-1)) j=0;
else j=k+1;
while (pts[k].y==pts[j].y)
if((j+1)>(cnt-1)) j=0;
else j++;
return (pts[j].y);
}

void makeEdgeRec(dcPt lower,dcPt upper,int yComp, Edge *edge, Edge *edges[]) //生成邊表結點，並插入到邊表中
{
edge->dxPerScan=(float)(upper.x-lower.x)/(upper.y-lower.y);
edge->xIntersect=lower.x;
if (upper.y<yComp)
edge->yUpper=upper.y-1;
else
edge->yUpper=upper.y;
insertEdge(edges[lower.y],edge);
}

void buildEdgeList(int cnt,dcPt *pts, Edge *edges[])//創建邊表的主體函數
{
Edge *edge;
dcPt v1,v2;
int i,yPrev=pts[cnt-2].y;
v1.x=pts[cnt-1].x; v1.y=pts[cnt-1].y;
for (i=0;i<cnt;i++)
{ v2=pts[i];
if (v1.y!=v2.y)
{ edge=(Edge *)malloc(sizeof(Edge));
if (v1.y<v2.y)
makeEdgeRec(v1,v2,yNext(i,cnt,pts),edge,edges);
else makeEdgeRec(v2,v1,yPrev,edge,edges);
}
yPrev=v1.y;
v1=v2;
}
}

void buildActiveList(int scan,Edge * active,Edge *edges[])//建立活動邊表的主題函數
{ Edge *p,*q;
p=edges[scan]->next;
while (p)
{ q=p->next;
insertEdge(active,p);
p=q;
}
}

void fillScan(int scan,Edge *active)//填充一對交點
{
Edge *p1,*p2;
int i
p1=active->next;
while(p1)
{
p2=p1->next;
for (i=p1->xIntersect;i<p2->xIntersect;i++)
setPixel((int)i,scan);
p1=p2->next;
}
}

void delectAfter(Edge *q)//刪除鏈表中結點
{
Edge *p=q->next;
q->next=p->next;
free(p);
}

void updateActiveList(int scan,Edge *active)//填充完後，更新活動邊表
{
Edge *q=active,*p=active->next;
while (p)
if (scan>=p->yUpper)
{
p=p->next;
deleteAfter(q);
}
else
{ p->xIntersect=p->xIntersect+p->dxPerScan;
q=p;
p=p->next;
}
}

void resortActiveList(Edge *active)//對活動邊表結點重新排序
{
Edge *q,*p=active->next;
active->next=NULL;
while(p)
{ q=p->next;
insertEdge(active,p);
p=q;
}
}

void scanFill(int cnt,dcPt *pts)//多邊形填充主體程序
{
Edge *edge[WINDOW_HEIGHT],*active;
int i,scan;
for (i=0;i<WINDOW_HEIGHT;i++)
{
edges[i]=(Edge *)malloc(sizeof(Edge));
edges[i]->next=NULL;
}
buildEdgeList(cnt,pts,edges);
active=(Edge *)malloc (sizeof(Edge));
active->next=NULL;
for(scan=0;scan<WINDOW_HEIGHT;scan++)
{
buildActiveList(scan,active,edges);
if (active->next)
{fillScan(sacn,active);<br/> updateActiveList(scan,active);<br/> resortActiveList(active);<br/>}
}
}
}
}
}

❸ C語言實現多邊形填充

/*直角三角形，輸入行數，輸出*/
#include <stdio.h>
void main()/*如果TC編譯不通過，則去掉void*/
{
int n;
scanf("%d",&n);
for (int i = 1;i <= n;i++)
{
for (int j = 0;j < i;j++)
printf("*");
printf("\n");
}
}
/*等腰三角形，輸入行數，輸出*/
#include <stdio.h>
void main()/*如果TC編譯不通過，則去掉void*/
{
int n;
scanf("%d",&n);
for (int i = 1;i <= n;i++)
{
for (int k = 1;k <= n-i;k++)
printf(" ");
for (int j = 0;j < 2*i-1;j++)
printf("*");
printf("\n");
}
}
以上在VS2005上編譯通過

❹ 邊緣填充演算法屬於()演算法一種。

邊緣填充演算法屬於A 多邊形掃描轉換

❺ 用VC在mfc下編寫多邊形邊緣填充演算法，要求自動判別多邊形再填充顏色，謝謝啦。

你是指把顏色填充整個多邊形嗎？我原來設計過一個演算法可以檢測所有閉合區域內的所有點，不局限於多邊形，不過比較費時。需要就說

❻ 簡單掃描線性填充和與邊相關掃描線填充演算法的區別

1. 對多邊形的每一條邊進行掃描轉換，即對 多邊形邊界所經過的象素作一個邊界標志。 2.填充。對每條與多邊形相交的掃描線，按 從左到右的順序，逐個訪問該掃描線上的象 素。 取一個布爾變數inside來指示當前點的狀態， 若點在多邊形內，則inside為真。若點在多 邊形外，則inside為假。 Inside 的初始值為假，每當當前訪問象素為 被打上標志的點，就把inside取反。對未打 標志的點，inside不變。

❼ 求一個C語言實現的種子填充多邊形演算法程序

/*如果是用線填充，程序如下。如果是用點填充需要用到堆棧和系統底層庫函數或者用畫點函數putpixel()。 下面實例是用掃描線填充長方形，開始要輸入長方形的左上頂點坐標和右下頂點坐標以及填充掃描線的間距(>=1)，如果間距等於1，就是完全填充(實填充)。 一個完整的c程序如下,程序在win-tc和tc2.0下都調試通過。 */ #include<stdio.h> #include<stdlib.h> #include<conio.h> #include<graphics.h> void draw(int x1,int y1,int x2,int y2,int delta) {int nx1,ny1,nx2,ny2; nx1=x1,ny1=y2-delta,nx2=x1+delta,ny2=y2; while((ny1>=y1)&&(nx2<=x2)) {line(nx1,ny1,nx2,ny2); ny1-=delta; nx2+=delta; } if(nx2>x2) {ny2-=nx2-x2; nx2=x2; while(ny1>y1) {line(nx1,ny1,nx2,ny2); ny1-=delta; ny2-=delta; } nx1+=y1-ny1; ny1=y1; while(nx1<x2) {line(nx1,ny1,nx2,ny2); nx1+=delta; ny2-=delta; } } else {nx1+=y1-ny1; ny1=y1; while(nx2<x2) {line(nx1,ny1,nx2,ny2); nx2+=delta; nx1+=delta; } ny2-=nx2-x2; nx2=x2; while(ny2>y1) {line(nx1,ny1,nx2,ny2); ny2-=delta; nx1+=delta; } } } int main(void) {int x1,y1,y2,x2,delta; int driver=DETECT,mode; printf("Please input lefttop(x1,y1) and rightbottom(x2,y2) of rectangle and delta:\n"); scanf("%d%d%d%d%d",&x1,&y1,&x2,&y2,&delta); initgraph (&driver,&mode,"C:\\TC"); /*這里*/ rectangle(x1,y1,x2,y2); draw(x1,y1,x2,y2,delta); gotoxy(1,1); printf("Press any key to exit!"); getch(); closegraph(); return 0; } /*說明：將main()函數中的initgraph(&gdriver,&gmode,"");中的""更改為你的TC安裝目錄,一般tc必須安裝在c盤根目錄下，所以就是initgraph(&gdriver,&gmode,"C:\\TC");如你的TC安裝目錄為D盤的Tools目錄下的TC目錄，那麼上述語句改為： initgraph(&gdriver,&gmode,"D:\\Tools\\TC"); 同時保證在D:\\Tools\\TC目錄里有文件EGAVGA.BGI,萬一不行，將本程序復制到你的TC安裝目錄下再運行。 */

❽ 簡述邊界表示的四連通區域的種子填充演算法的基本思想和執行步驟

一、種子填充演算法思想：
首先填充種子所在的尚未填充的一區段,然後確定與這一區段相鄰的上下兩條掃描線上位於該區段內是否存在需要填充的新區段,如果存在,則依次把每個新區段最右端的象素作為種子放入堆棧。反復這個過程,直到堆棧為空。
二、種子填充演算法步驟：
1、初始化堆棧。
2、種子壓入堆棧。
3、While（堆棧非空）從堆棧彈出種子象素。

❾ Qt4如何對閉合多邊形進行填充

http://www.kuqin.com/qtdocument/qpainter.html#drawPolygon

void QPainter::drawPolygon ( const QPointArray & a, bool winding = FALSE, int index = 0, int npoints = -1 )
繪制a中，從a[index]開始（index默認為0）的npoints個點確定的多邊形。
如果npoints為－1（默認），直到數組的最後的所有點都被使用（也就是說a.size()-index條線確定的多邊形）。
第一個點總是被連接到最後一個點上。
多邊形被當前brush()填充。如果winding為真，多邊形會被使用纏繞填充演算法（winding fill algorithm）填充。如果winding為假，多邊形會被使用奇偶（交錯）填充演算法（even-odd (alternative) fill algorithm）填充。
請參考drawLineSegments()、drawPolyline()和QPen。
實例：desktop/desktop.cpp和picture/picture.cpp。