多边形扫描算法
‘壹’ 求一道计算机图形学编程题解答
你把问题一部一部拆开来解决不就行了嘛....
首先你先解决鼠标输入顶点绘制多边形的问题。
(把绘制后的白底黑线的多边形图看成是像素矩阵，作为你填充算法的输入)
然后再看书，研究填充算法
最后用程序实现算法，完成填充。
一步一步来，就能做出来。这个问题拆解开来之后，一点都不难，要相信你自己。
要学会把复杂的问题分解成简单的问题，这是念大学必须要学会的方法论。
念大学其实要学的是：碰到问题，如何解决问题。
学会了解决问题的各种方法，理论上来说，天下就没有“无解决方案"的问题，你也会得到长足的进步，思路一下子会开阔。
‘贰’ 求助：谁有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();
画一个多边形，但底层的光栅化到底是怎么实现的，是否使用扫描线算法，你是不可以控制的。