多邊形掃描演算法
『壹』 求一道計算機圖形學編程題解答
你把問題一部一部拆開來解決不就行了嘛....
首先你先解決滑鼠輸入頂點繪制多邊形的問題。
(把繪制後的白底黑線的多邊形圖看成是像素矩陣，作為你填充演算法的輸入)
然後再看書，研究填充演算法
最後用程序實現演算法，完成填充。
一步一步來，就能做出來。這個問題拆解開來之後，一點都不難，要相信你自己。
要學會把復雜的問題分解成簡單的問題，這是念大學必須要學會的方法論。
念大學其實要學的是：碰到問題，如何解決問題。
學會了解決問題的各種方法，理論上來說，天下就沒有「無解決方案"的問題，你也會得到長足的進步，思路一下子會開闊。
『貳』 求助：誰有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/>}
}
}
}
}
}
『叄』 已知n凸多邊形的各頂點坐標 如何將他們順時針排列
(1)找一個內點
(2)計算這個內點到各頂點的角度0-360度
(3)按角度排序
找一個內點：
任選3點x1,y1,x2,y2,x3,y3
計算：
x0=(x1 + x2 + x3)/3
y0=(y1 + y2 + y3)/3.
計算這個內點到各頂點的角度：
dy=yi-y0
dx=xi-x0
ds=sqrt(dx*dx+dy*dy)
sin(Ai) = dy/ds
判斷象限。
排序不用說了吧。
『肆』 如何修改掃描線演算法，使它能處理邊自交的多邊形
1. 對多邊形的每一條邊進行掃描轉換，即對 多邊形邊界所經過的象素作一個邊界標志。 2.填充。對每條與多邊形相交的掃描線，按 從左到右的順序，逐個訪問該掃描線上的象 素。 取一個布爾變數inside來指示當前點的狀態， 若點在多邊形內，則inside為真。若點在多 邊形外，則inside為假。 Inside 的初始值為假，每當當前訪問象素為 被打上標志的點，就把inside取反。對未打 標志的點，inside不變。
『伍』 邊緣填充演算法屬於()演算法一種。
邊緣填充演算法屬於A 多邊形掃描轉換
『陸』 基於圖論的最小多邊形自動搜索演算法
圖是由點集和邊集所構成的抽象概念，圖的性質實質上可以表現為拓撲關系。如圖4.8b所示，點集由分叉點構成(4個分叉點，分別是1，2，3，4)，邊集則由地層線構成(7條地層線，分別是①，②，③，④，⑤，⑥，⑦)。需要說明的是，這里的邊是廣義上的邊，可能是直線段，也可能是多線段。
最小多邊形的自動搜索在GIS的空間分析中應用較多，搜索可分為無拓撲和含拓撲兩類。無拓撲自動搜索則完全依靠幾何計算來判斷，如夾角變化趨勢的多邊形自動搜索演算法(梁曉文等，2005)，該演算法主要依靠弧段間夾角計算來判斷，通過「左轉」或「右轉」的方法能夠唯一確定最小多邊形，原理簡單，但程序設計過程極其煩瑣。採用圖論的方法來實現，原理相對復雜，需要掌握數據結構知識，但程序代碼設計過程比較簡潔，具有擴展性。
為了簡單起見，以圖4.8b中地層線①為例，說明搜索過程。從分叉點1開始，沿地層線①在分叉點2與地層線②和③鄰接，地層線②和③又分別在分叉點3和4與兩地層線鄰接。整個鄰接關系可以用一個樹(tree)型結構來表示(圖4.10)，終止條件是回到分叉點1，形成閉合迴路或者出現自相交，則停止搜索。這樣，產生4條有意義的多邊形為：1-①-2-②-3-⑥-1，1-①-2-②-3-④-4-⑤-1，1-①-2-③-4-④-3-⑥-1，1-①-2-③-4-⑤-1。
圖4.10 分叉點1沿①為起始方向的連通圖
在上述4條連通多邊形中，面積最小者對應的就是一個最小多邊形(周秋生，1996)。若多邊形點對為(x1，y1)，(x2，y2)，…，(xn，yn)，面積可採用下式來計算：
S=
最終，得到3個最小多邊形。從圖論的觀點來看，所研究的圖是一個連通的平面圖。若圖有n個分叉點，m條廣義邊，p個最小多邊形，則平面圖的面數(包括外部面)f=p+1。
根據歐拉公式(孫家廣，1998)：
f+m-n=2 (4.2)
可以得到最小多邊形數目為
p=m-n+1 (4.3)
見圖4.4b中，m=7，n=5，則p=7-5+1=3。據此可以作為搜索結果正確與否的判斷方式之一。
『柒』 掃描演算法增加方向和減少方向算出來的值一樣嗎.
一樣
要實現區域的掃描線填充必須先確定填充區邊界與屏幕掃描線的交點位置。然後，將填充色應用於掃描線上位於填充區域內部的每一段。掃描線填充演算法利用奇偶規則識別同一內部區域（參見）。最簡單的填充區域是多邊形，因為每一掃描線和多邊形的交點可通過求解一對聯立的線性方程來獲得，其中掃描線的方程是y = 常數。
給出了多邊形區域的實心填充的掃描線過程。對每一條與多邊形相交的掃描線，與邊的交點從左向右排序，且將每一對交點之間的像素位置包括這對交點在內，設定為指定顏色。在圖4.20的例子中，與邊界的四個交點像素位置定義了兩組內部像素。這樣，填充色應用於從x=10到x = 14的5個像素和從x = 18到x = 24的7個像素。如果圖案填充應用於多邊形，則沿一條掃描線的每一像素顏色由與填充圖案重疊的位置來確定。
『捌』 怎麼用opengl掃描線演算法填充多邊形
掃描線演算法是光柵圖形學的內容，底層硬體實現。opengl是不會關注這種細節的。你寫這樣的代碼
glBegin(GL_POLYGON);
glVertex3f(...);
...
glVertex3f(...);
glEnd();
畫一個多邊形，但底層的光柵化到底是怎麼實現的，是否使用掃描線演算法，你是不可以控制的。