计算机图形学第五章作业答案Final.docVIP

习题1答案 习题1. 设空间有两条线段AB和CD，其端点坐标分别为，和，，怎样判断它们是否相交？若相交，求出交点坐标。 解法1解答： 由端点坐标可知线段AB和CD的参数方程分别为： 如果线段AB和CD相交，则存在和，使下面的方程组： 由（1）式，（2）式即可求出和： 将求得的和代入（3）式，若满足（3）式，则线段AB和CD所在的直线相交。此时如果有： 则线段AB和CD相交，否则不相交。令代入线段AB的参数方程中或者令代入线段CD的参数方程即可求出交点坐标。 解法2解答： 由端点坐标可知线段AB和CD的参数方程分别为： 线段AB和CD在z=0平面上的正投影线段A’B’和C’D’端点坐标分别为，，，。 根据书中第一节介绍的方法（本答案不再重复该方法）可以判断出A’B’和C’D’是否有交点，如果没有交点，则线段AB和CD也没有交点。 如果有交点，假设交点坐标为。因为做的是正投影，所以该交点对应的线段上的被投影点的x、y坐标值相同。假设线段AB和CD上对应该交点的点的坐标分别为和。将坐标值分别代入线段AB和CD的参数方程中，可以分别计算出和，如果=，则线段AB和CD相交，且交点坐标为，否则不相交。 习题15答案 习题15. 写一个算法，能迅速地判断一条直线与一个凸多边形是否相交，若相交求出交点。 解答： 设直线由两点和确定，凸多边形由顶点序列、···（共n个顶点）确定。 算法基本思想如下： 选定多边形顶点序列中点及点，其中，两点构成多边形的一条对角线。判断这两点与直线的位置关系，有如下几种情况： 两点都在直线上，则直线与多边形交于此两点； 两点有一点在直线上，在直线上的点是直线与多边形的一个交点： 如果点在直线上，则检查和与点的位置关系：如点在直线上，则与直线重合，此时认为与是直线与多边形的交点；如与点在直线异侧，则直线与多变形上从点开始到点构成的边所形成的折线有一个交点，可以求出该交点，直线与多边形有此交点和两个交点；如与点在直线同侧，则直线不会与多变形上从点开始到点构成的边所形成的折线有交点；如点在直线上，则与直线重合，此时认为与是直线与多边形的交点；如与点在直线异侧，则直线与多边形上从点开始到点构成的边所形成的折线有一个交点，可以求出该交点，直线与多边形有此交点和两个交点；如与点在直线同侧，则直线不会与多边形上从点开始到点构成的边所形成的折线有交点。如果检查完，与都在同侧，则多边形只与直线有一个交点。 如果点在直线上，则检查和与点的位置关系：如点在直线上，则与直线重合，此时认为与是直线与多边形的交点；如与点在直线异侧，则直线与多变形上从点开始到点构成的边所形成的折线有一个交点，可以求出该交点，直线与多边形有此交点和两个交点；如与点在直线同侧，则直线不会与多变形上从点开始到点构成的边所形成的折线有交点；如点在直线上，则与直线重合，此时认为与是直线与多边形的交点；如与点在直线异侧，则直线与多边形上从点开始到点构成的边所形成的折线有一个交点，可以求出该交点，直线与多边形有此交点和两个交点；如与点在直线同侧，则直线不会与多边形上从点开始到点构成的边所形成的折线有交点。如果检查完，与都在同侧，则多边形只与直线有一个交点。 两点都不在直线上，且在直线异侧，则直线与多边形有两个交点。并且可知，直线是分别与多边形上从点开始到点构成的边所形成的折线，以及从点开始到点构成的边所形成的折线各有一个交点，即直线与被由点和点所构成的对角线分割出的多边形的两部分各有一个交点。 两点都不在直线上，且在直线同侧，此时直线可能会与被对角线分割成两部分的多边形中的一部分有交点，不会与两部分同时有交点。可以判断出直线有可能与那一部分有交点，然后此部分与选定的对角线形成了一个新的凸多边形，对此多边形再次应用本算法；如果直线与两部分都不可能有交点的话，则直线与多边形无交点。此处判断直线与多边形的哪一部分有可能有交点或者不可能有交点可采用如下方法： 比较点和点到直线的距离，如果点离直线较近，则分别检查和点：如点与点和点在直线的异侧，或者点比点离直线更近，则直线可能会与从点开始到点构成的边所形成的折线有交点，利用从点开始到点构成一个新的多边形再次应用本算法，否则直线不会与此部分有交点；如点与点和点在直线的异侧，或者点比点离直线更近，则直线可能会与从点开始到点构成的边所形成的折线有交点，利用从点开始到点构成一个新的多边形再次应用本算法，否则直线不会与此部分有交点。如果对角线分割出的两部分都不会与直线有交点，则直线与凸多边形无交点。 上面算法中要求出直线与多边形边所形成的折线的交点，可以采用如下算法思想来求得： 设要求交点的折线的顶点序列编号为m_start到m_end（m_endm_start）； 如果m_end – m_start = 1，则这两个编号的点构成了多