计算机图形学第5章作业答案_Final_

习题1答案习题1.设空间有两条线段AB和CD，其端点坐标分别为(,,)aaaxyz，(,,)bbbxyz和(,,)cccxyz，(,,)dddxyz，怎样判断它们是否相交？若相交，求出交点坐标。解法1解答：由端点坐标可知线段AB和CD的参数方程分别为：)10(如果线段AB和CD相交，则存在1t和2t，使下面的方程组：121212()()(1)()()(2)()()(3)abacdcabacdcabacdcxxxtxxxtyyytyyytzzztzzzt由（1）式，（2）式即可求出1t和2t：12()()()()cdadccacddadcabdbccbdbcadacbababccacbdcabdbccbdbcadayyxxyxyxyxytyyxxyxyxyxyxyxyyyxxyxyxyxytyyxxyxyxyxyxyxy将求得的1t和2t代入（3）式，若满足（3）式，则线段AB和CD所在的直线相交。此时如果有：]1,0[,1,021tt则线段AB和CD相交，否则不相交。令1t代入线段AB的参数方程中或者令2t代入线段CD的参数方程即可求出交点坐标。解法2解答：由端点坐标可知线段AB和CD的参数方程分别为：)10(线段AB和CD在z=0平面上的正投影线段A’B’和C’D’端点坐标分别为),(aayx，),(bbyx，),(ccyx，),(ddyx。根据书中第一节介绍的方法（本答案不再重复该方法）可以判断出A’B’和C’D’是否有交点，如果没有交点，则线段AB和CD也没有交点。如果有交点，假设交点坐标为),(eeyx。因为做的是正投影，所以该交点对应的线段上的被投影点的x、y坐标值相同。假设线段AB和CD上对应该交点的点的坐标分别为),,(abeezyx和),,(cdeezyx。将),(eeyx坐标值分别代入线段AB和CD的参数方程中，可以分别计算出abz和cdz，如果abz=cdz，则线段AB和CD相交，且交点坐标为),,(abeezyx，否则不相交。习题15答案习题15.写一个算法，能迅速地判断一条直线与一个凸多边形是否相交，若相交求出交点。解答：设直线由两点),(11yx和),(22yx确定，凸多边形由顶点序列0P、1P···1nP（共n个顶点）确定。算法基本思想如下：选定多边形顶点序列中0P点及iP点，其中21ni，两点构成多边形的一条对角线。判断这两点与直线的位置关系，有如下几种情况：(1)两点都在直线上，则直线与多边形交于此两点；(2)两点有一点在直线上，在直线上的点是直线与多边形的一个交点：如果0P点在直线上，则检查1nP和1P与iP点的位置关系：○1如1nP点在直线上，则1nP0P与直线重合，此时认为1nP与0P是直线与多边形的交点；如1nP与iP点在直线异侧，则直线与多变形上从iP点开始到1nP点构成的边所形成的折线有一个交点，可以求出该交点，直线与多边形有此交点和0P两个交点；如1nP与iP点在直线同侧，则直线不会与多变形上从iP点开始到1nP点构成的边所形成的折线有交点；○2如1P点在直线上，则0P1P与直线重合，此时认为1P与0P是直线与多边形的交点；如1P与iP点在直线异侧，则直线与多边形上从1P点开始到iP点构成的边所形成的折线有一个交点，可以求出该交点，直线与多边形有此交点和0P两个交点；如1P与iP点在直线同侧，则直线不会与多边形上从1P点开始到iP点构成的边所形成的折线有交点。如果检查完1nP，0P与iP都在同侧，则多边形只与直线有一个交点0P。如果iP点在直线上，则检查1iP和1iP与0P点的位置关系：○1如1iP点在直线上，则1iPiP与直线重合，此时认为1iP与iP是直线与多边形的交点；如1iP与0P点在直线异侧，则直线与多变形上从0P点开始到1iP点构成的边所形成的折线有一个交点，可以求出该交点，直线与多边形有此交点和iP两个交点；如1iP与0P点在直线同侧，则直线不会与多变形上从0P点开始到1iP点构成的边所形成的折线有交点；○2如1iP点在直线上，则iP1iP与直线重合，此时认为iP与1iP是直线与多边形的交点；如1iP与0P点在直线异侧，则直线与多边形上从1iP点开始到0P点构成的边所形成的折线有一个交点，可以求出该交点，直线与多边形有此交点和iP两个交点；如1iP与0P点在直线同侧，则直线不会与多边形上从1iP点开始到0P点构成的边所形成的折线有交点。如果检查完1iP，1iP与0P都在同侧，则多边形只与直线有一个交点iP。(3)两点都不在直线上，且在直线异侧，则直线与多边形有两个交点。并且可知，直线是分别与多边形上从0P点开始到iP点构成的边所形成的折线，以及从iP点开始到0P点构成的边所形成的折线各有一个交点，即直线与被由iP点和0P点所构成的对角线分割出的多边形的两部分各有一个交点。(4)两点都不在直线上，且在直线同侧，此时直线可能会与被对角线分割成两部分的多边形中的一部分有交点，不会与两部分同时有交点。可以判断出直线有可能与那一部分有交点，然后此部分与选定的对角线形成了一个新的凸多边形，对此多边形再次应用本算法；如果直线与两部分都不可能有交点的话，则直线与多边形无交点。此处判断直线与多边形的哪一部分有可能有交点或者不可能有交点可采用如下方法：比较0P点和iP点到直线的距离，如果0P点离直线较近，则分别检查1nP和1P点：○1如1nP点与0P点和iP点在直线的异侧，或者1nP点比0P点离直线更近，则直线可能会与从iP点开始到0P点构成的边所形成的折线有交点，利用从iP点开始到0P点构成一个新的多边形再次应用本算法，否则直线不会与此部分有交点；○2如1P点与0P点和iP点在直线的异侧，或者1P点比0P点离直线更近，则直线可能会与从0P点开始到iP点构成的边所形成的折线有交点，利用从0P点开始到iP点构成一个新的多边形再次应用本算法，否则直线不会与此部分有交点。如果对角线分割出的两部分都不会与直线有交点，则直线与凸多边形无交点。上面算法中要求出直线与多边形边所形成的折线的交点，可以采用如下算法思想来求得：(1)设要求交点的折线的顶点序列编号为m_start到m_end（m_endm_start）；(2)如果m_end–m_start=1，则这两个编号的点构成了多边形的一条边，直线与该边有一个交点，求出该交点，算法结束；否则进行第(3)步；(3)计算m_middle=[(m_start+m_end)/2]；(4)判断m_start点、m_middle点和直线的位置关系：如果m_start点在直线上，则直线与折线有交点m_start点，算法结束；如果m_middle点在直线上，则直线与折线有交点m_end点，算法结束；如果m_start点和m_middle点在直线的同侧，则令m_start=m_middle，转到(2)步；如果m_start点和m_middle点在直线的异侧，则令m_end=m_middle，转到(2)步。此算法执行要求直线必须和折线有且只有一个交点，在最初算法中调用时均可保证这一点。算法的实现代码如下，分成两个函数：//获得折线与直线的交点//m_plist为多边形的顶点序列//m_start和m_end为要求交的多边形中的折线顶点序列的开始点和终止点//x1，y1，x2，y2指定直线//调用此方法表明折线与直线肯定有交点CPointCP5Q15View::GetIntersection(CArrayCPoint,CPoint*m_plist,intm_start,intm_end,intx1,inty1,intx2,inty2){//计算直线方程参数inta=y2-y1;intb=x1-x2;intc=x2*y1-x1*y2;intn=m_plist-GetSize();//m_start和m_end不是多边形其中一条边的两个顶点while(m_end-m_start1){CPointp1=(CPoint)m_plist-GetAt(m_start);//取m_start和m_end确定的折线顶点序列中的中间点intm_middle=(m_start+m_end)/2;//取中间点CPointp2=(CPoint)m_plist-GetAt(m_middle);intd1=a*p1.x+b*p1.y+c;intd2=a*p2.x+b*p2.y+c;//顶点即为交点if(d1==0){CPointjdp;jdp.x=p1.x;jdp.y=p1.y;returnjdp;}elseif(d2==0){CPointjdp;jdp.x=p2.x;jdp.y=p2.y;returnjdp;}//折半后前半与直线有交点elseif((d10&&d20)||(d10&&d20))m_end=m_middle;//继续分割前半部分elsem_start=m_middle;//继续分割后半部分}//确定了与直线相交的多边形的边//获得边的两个顶点CPointp1=(CPoint)m_plist-GetAt(m_start);CPointp2=(CPoint)m_plist-GetAt(m_end%n);//计算交点doubledelta=(p2.x-p1.x)*(y1-y2)-(x1-x2)*(p2.y-p1.y);doublet=((x1-p1.x)*(y1-y2)-(y1-p1.y)*(x1-x2))/delta;CPointjdp;jdp.x=(int)(p1.x+(p2.x-p1.x)*t);jdp.y=(int)(p1.y+(p2.y-p1.y)*t);returnjdp;}//获得直线与凸多边形的交点//m_list为凸多边形的顶点左边序列//x1，y1，x2，y2指定直线//m_intersection存放交点坐标voidCP5Q15View::GetIntersectionOfLAP(CArrayCPoint,CPoint*m_list,intx1,inty1,intx2,inty2,CArrayCPoint,CPoint*m_intersection){//计算直线方程参数inta=y2-y1;intb=x1-x2;intc=x2*y1-x1*y2;CArrayCPoint,CPointm_plist;for(inti=0;im_list-GetSize();i++)m_plist.Add(m_list-GetAt(i));while(true){//获得多边形顶点数量intn=m_plist.GetSize();//获得多边形顶点序列中中间的顶点intm_middle=(n-1)/2;//获得顶点序列中第一个点和中间点，此两点确定了多边形内部一条对角线CPointp1=(CPoint)m_plist.GetAt(0);CPointp2=(CPoint)m_plist.GetAt(m_middle);intd1=a*p1.x+b*p1.y+c;intd2=a*p2.x+b*p2.y+c;//p1,p2都在直线上，此两点即为直线与多边形交点if(d1==0&&d2==0){CPointjdp1,jdp2;jdp1.x=p1.x;jdp1.y=p1.y;jdp2.x=p2.x;jdp2.y=p2.y;m_intersection-Add(jdp1);m_intersection-Add(jdp2);return;}//p1，p2在直线的两侧，表明多边形与直线肯定有两个交点//并且直线与该对角线左右两侧由多边形的边构成的折线各有一个交点if((d10&&d20)||(d10&&d20)){//分别求直线与两条折线的交点CPointjdp1=this-GetIntersection(&m_plis