图形学作业与答案.doc - 精品课程建设平台
摘要：优缺点：边缘填充算法的数据结构和程序结构都简单的多，缺点：执行时许对帧缓冲器中的大批元素反复赋值，故速度不必扫描线算法快，另外，如果区域内原来有其他的颜色， ... 关键词：算法,数据结构 类别：专题技术
来源：牛档搜索（Niudown.COM）
本文系牛档搜索（Niudown.COM）根据用户的指令自动搜索的结果，文中内涉及到的资料均来自互联网，用于学习交流经验，作品其著作权归原作者所有。不代表牛档搜索（Niudown.COM）赞成本文的内容或立场，牛档搜索（Niudown.COM）不对其付相应的法律责任！
第三章作业与答案
3.1 试证：若把（3.30）改为
??xi?1??cos??y???b?i?1??sin??a则该式可用于产生椭圆
a??sin???x?x??x?icb??c? ???cos???yi?yc??yc??(x?xc)2/a2?(y?yc)2/b2?1
上的点，从而可用于绘椭圆。 证明：将待证式展开得：
xi+1 = xc + (xi-xc)cos?- (yi-yc)?asin? bayi+1 = yc + (xi-xc)sin? + (yi-yc)cos?
b该式即为计算椭圆内接多边形顶点的递推公式，并可知椭圆的长短轴分别为 a和b，中心点为(xc,yc),对称轴平行于坐标轴，即： (x?xc)2/a2?(y?yc)2/b2?1 证毕。
3.2 用二元函数的泰勒（Taylor）展式证明（3.16），并把正负法推展到绘椭圆
(x?xc)2/a2?(y?yc)2/b2?1
证明：二元函数的泰勒（Taylor）展开式：
设函数f(x,y)在点（x,y）某一邻域内连续，且有直至n+1阶的连续偏导数，给xi以增量?x；给yi以增量?y,使连接点（xi,yi）、(xi+?x,yi+?y)的直线段仍在点（xi,yi）的邻域内，则可将函数值f(xi+?x,yi+?y)近似表示为?x,?y 的n 次多项式：
f(xi+?x,yi+?y)=f(xi,yi)+( ?x
??+?y)f(xi,yi)+ ?x?y1?1??2
( ?x+?y)·f(xi,yi)+…+( ?x+?
?x?x2!n!?yy
?n
)·f(xi,yi)+ Rn ?y 由此所产生的误差Rn是一个比?x2??y2高于n阶的无穷小。
由圆的方程：(x-xc) 2+ (y-yc) 2 - R2 =0 2(xi-xc) 当f(xi,yi)≤0时 ( ?x＝0
-2(yi-yc) 当f(xi,yi)＞0时 ?x＝0，?y＝-1
21?1?2 2?f( ?x+?y)·f(xi,yi)= ( ?x
?x2!2!?x?y??f?+?y)f(xi,yi)= ?x
?x?x?y?xi
+?y
?f?y?yi= ?
x＝1，?y
?xi+2?x?y
?f?x?xi
?f?y?yi+?
?f2y?y2
?yi)
1 当f(xi,yi)≤0时, ?x＝1，?y＝0
=
1 当f(xi,yi) ＞0时, ?x＝0，?y＝-1
F(xi,yi)+2(xi-xc)+1当f(xi,yi)≤0
时f(xi+?x,yi+?y)=F(xi+1,yi+1) ≈
F(xi,yi)-2(yi-yc)+1 当f(xi,yi) ＞0时
证毕。
由椭圆方程：(x?xc)2/a2?(y?yc)2/b2?1?0 ；转化为：
b2(x?xc)2?a2(y?yc)2?a2b2?0
同理推出椭圆正负法(不分上、下区的简单)递推公式为：
F(xi,yi)+2b2(xi-xc)+b2当f(xi,yi)≤0
f(xi+?x,yi+?y)=F(xi+1,yi+1)≈
F(xi,yi)-2 a2 (yi-yc) +a2 当f(xi,yi)＞0
3.3 试证：若把（3.24）改为
a??cos??sin???xi?xc??xc??xi?1??b???y???b???y? y?yc??i?1??sin??c?cos???i?a?则该式可用于产生椭圆
(x?xc)2/a2?(y?yc)2/b2?1
上的点，从而可用于绘椭圆。 证明：假设椭圆的中心在（xc，yc），长短轴分别为a，b，对称轴平行于坐标轴，则椭圆的参数方程为
x?acos??xc,y?bsin??yc
则顶点序列的第I个顶点Pi的坐标为（xi ,yi）（ao，则下一个顶点cs?i,bnis?i）Pi+1的坐标为（xi+1 ,yi+1）应该满足
xi?1?acos(?i??)?xc, yi?1?bsin(?i??) ?yc 经过整理可得
xi?1?xc?a(cos?cos??sin?sin?)yi?1?yc?b(sin?cos??cos?sin?)
因为xi?acos?i?xc, yi?bsin?i ?yc 整理可得
a??cos? -sin???xi?xc??xc??xi?1??b???，这就是计算椭圆的第推公式 ???y???a??i?1??sin? cos???yi?yc??yc????b?
3.4 多边形的顶点和点阵表示各有什么优点？
答：顶点表示是用多边形的顶点的序列来描述多边形，该表示几何意义强、占内存少。（但他不能直观地说明哪些像素在多边形内）。点阵表示用位于多边形内的像素的集合来描述多边形。该方法虽然没有多边形的几何信息，是面着色所需要的图像表示形式。
3.5多边形扫描填充的扫描线算法利用了区域的连续性、扫描线连续性和边的连续性，在数据结构和算法中各体现在何处？
答：ET数据结构体现了区域的连贯性、边的连贯性。AEL体现了扫描线的连贯性、边的连贯性。AEL的动态增删及排序集中体现了扫描线的连贯性和边的连贯性。
3.6任意给定五边形的五个顶点坐标，利用多边形填充的扫描线算法，编写程序生成一个实心五边形。
答：
typedef struct tEdge{ int yUpper; int xIntersect; float 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=p->next; } }
edge->next=q->next; q->next=edge; }
int yNext(int k,int cnt,CPoint *points) {
int j;
if((k+1)>(cnt-1)) j=0; else
j=k+1;
while(points[k].y==points[j].y) if((j+1)>(cnt-1)) j=0; else j++;
return(points[j].y); }
void makeEdgerec(CPoint lower,CPoint 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 edge->yUpper=upper.y-1; else edge->yUpper=upper.y; insertEdge(edges[lower.y],edge); } void buildEdgeList(int cnt,CPoint *points,Edge * edges[]) { Edge *edge; CPoint p1,p2; int i,yprev=points[cnt-2].y; p1.x=points[cnt-1].x; p1.y=points[cnt-1].y; for(i=0;i *