计算几何复习题.doc

计算几何期末复习题二. 简答题1. 在编写几何计算程序时,应该坚持的原则有哪些?答：尽量使用加减等有理运算,避免使用开方,除法等无理运算.2. 如果一个几何计算系统采用浮点计算,那么这个系统可能不可靠。这个不可 靠是由什么原因引起的?答：浮点数的精度不够，出现允差，判断结果矛盾。3. 如果一个几何计算系统全部采用整数计算并且没有除法运算和无理计算,那 么这个系统仍然可能不可靠。这个不可靠是由什么原因引起的?答：可能产生数据溢出问题。4. Windows 应用程序是消息驱动程序,并且消息中的大部分是窗口消息。给出 3 个预定义的窗口消息名称并说明这些消息什么时候发生。答：1.WM_LBUTTONDOWN（按下鼠标左键）2.WM_LBUTTONUP(释放鼠标左键)3.WM_RBUTTONDOWN（按下鼠标右键）4.WM_RBUTTONUP(释放鼠标右键)5. Windows 应用程序提供许多预定义的窗口类型(也叫控件)供程序员使用,它们 具有各自独特的窗口特征。请给出 3 种预定义窗口类型,给出它们的中文名和英 文名。答： CButton 按钮 CControlBar 控制条 CComboBox 组合框 6. 单多面体的Euler-Poincare公式是什么?写出这个公式并说明公式中每个变量 的含义。将一个多面体的每个面进行三角剖分后这个公式是否仍然成立?答：公式：V-E+F=2*(S-G)+R 解释：S: shell壳的个数 G：Genus 亏格数 R：ring内环个数V：vextex顶点个数 E：edge边个数 F：face面的个数 成立7. 出由端点 P0(x0, y0, z0)与 P1(x1, y1, z1)所确定的直线段的参数方程。(用矢量形式 或分量形式均可)。答：p=po+（P1-p0）t; t0，18. 已知空间不在一条直线上的 3 点 P0(x0, y0, z0)、P1(x1, y1, z1)、P2(x2, y2, z2),写 出经过这 3 点的平面的参数方程。(用矢量形式或分量形式均可)。答:p(u,v)=p0+u(p1-p0)+v(p2-p0)9. 我们说平面点集的 Delaunay 三角剖分是一个“好”的三角剖分。这里的“好” 指的是什么?(指出一点即可。)答：因为它是一个最小角最大化的三角剖分方法11.形体的表面模型和实体模型分别适合的领域是什么?一个采用半边数据结构描述的多面体属于表面模型还是实体模型?答：表面模型：动画领域 实体领域：工程 CAD 属于实体模型12. 采用交互编辑手段进行三维形体的几何建模的方法有哪些?答：布尔集合运算 体素建模 整体操作 局部操作 扫面操作13. 给定空间一点 P1(x1, y1, z1)和一个平面,平面的普遍方程为 Ax+By+Cz+D=0。 请说明如何判断 P1 在平面上、正侧或负侧。假设所有参数均为浮点数,并且计 算量越小越好。答：令=Ax1+By1+Cz1+D 若Eps 则点在平面上 若= Eps 则点在平面内 若-Eps 则点在平面下14. 给定空间一点 P1 和一条直线,该直线由直线上一点 P0 与方向矢量 v 来描述。 请给出计算 P1 到该直线距离 d 的矢量形式计算公式。答： d=|（p1-p0）v| | |v| |15. 给定空间一点 P0 和一条直线段 P1P2。请给出计算 P0 到该直线段距离 d 的矢 量形式计算公式。答： 当（p0-p1）（p2-p1）0时，d=|p1-p0|；当（p0-p2）（p1-p2）p20)if(p20=p00&p00=p10) return true; else return false; if(p10p20)if(p10=p00&p00=p20) return true; else return false; else return false ;3. 给定平面上一点 P0 和一直线段 P1P2,假定所有坐标值为浮点数,并且允差 已定义(即程序中的 EPS)。请按照要求给出判断它们是否相交的函数实现(C+语 言):#define EPS 1e-5bool IsPointSegmentIntersected(float P02, float P12, float P22) / 返回值,true 表示相交,false 表示不相交。/ P0 是被判断点的坐标,P1 与 P2 是被判断的两个端点坐标。 / 下面是你的函数实现.答：if(p10*p21+p11*p00+p20*p01-p00*p21-p10*p01-p20*p11p20)if(p20=p00&p00=p10) return true; else return false; if(p10p20)if(p10=p00&p00=p20) return true; else return false; else return false ;4. 假定点坐标为整数,并且计算三角形二倍代数面积的函数已定义。请按照要 求编写计算平面点集凸包的卷包裹算法的实现函数:struct Point int x, y; /点结构体的定义int Area2(Point p0, Point p1, Point p2); / 计算三角形二倍代数面积的函数声明void WrapHull(Point P , int n, Point C , int& m)/ 输入:P 为用数组表示的输入点集,下标为 0n-1,n 为点集中点的个数 / 输出:用数组 C 存储凸包上的点,用 m 返回凸包上点的个数 / 下面为你的实现代码.void WrapHull(Point P , int n, Point C , int& m)int s=0,j=1;for(int i=1;in;i+)if(Pi.yPs.y)s=i;C0=Ps;int start=s;doint k=0;if(k=s)k+;for(int i=;i0)int temp=i; i=k; k=temp;s=k;Cj=Ps;j+;while(s!=start);return (m=sizeof(C);5. 在平面点集凸包 Graham 扫描算法的 C 语言实现中,需要调用 qsort 库函数来 实现点的排序。而调用 qsort 的关键是编写一个固定形参的函数 Compare 来比较 两个点的大小。假定 y 坐标最小的最右点已存储在 P0处,另外假设没有三点共 线问题,坐标点为整数,计算三角形二倍代数面积的函数已定义。请给出 Compare 函数的实现():struct Point int x, y; /点结构体的定义 Point *P; /存放点集的数组int n; /点集中点的个数int Compare(void *t1, void *t2)/ 输入:必须为两个指向 void 的指针,t1 与 t2/ 返回值:只能是-1,0 或 1。如果 t1 所指向的元素小于 t2 所指向的元素返回-1; / 如果相等返回 0;否则返回 1。 /下面是你的实现代码.int Compare(void *t1, void *t2) Point *pi=(Point *)t1;Point *pj=(Point *)t2;int a=Aera2(p0,*pi,*pj);/三角形二倍代数面积计算函数if(a0)return -1;else if(a0) j+;if(Aera2(Pn-2,Pn-1,P0)0) j+;for(int i=0;i0) j+;if(j=n) return true;elsereturn false;7. 已知点坐标为浮点数,平面多边形采用点的数组描述,方向为逆时针。假定 计算三角形二倍代数面积的函数已定义。请按照要求编写计算多边形面积的实现 函数:struct Point float x, y; /点结构体的定义float Area2(Point p0, Point p1, Point p2); / 计算三角形二倍代数面积的函数声明float PolygonArea(Point P , int n)/ 输入:P 为用点的数组表示的多边形,下标为 0n-1,n 为多边形的顶点个数 / 返回值:多边形的面积 / 下面为你的实现代码.答：float PolygonArea(Point P , int n)int i=1;double sum1,sum2=0;do sum1=Aera2(P0,Pi,Pi+1) sum2+=sum1; i+;while(i!=n);return -0.5*sum2;/方向为逆时针时面积为负值8. 已知点坐标为浮点数,平面多边形采用顶点的循环链表来描述,方向为逆时 针。假定计算三角形二倍代数面积的函数已定义。请按照要求编写计算多边形面 积的实现函数:struct Point float x, y; /点结构体的定义 struct Vertex /顶点结构体的定义 Point p;Vertex *prev, *next; /顶点循环链表中的前驱和后继 ;float Area2(Point p0, Point p1, Point p2); / 计算三角形二倍代数面积的函数声明float PolygonArea(Vertex *firstv)/ 输入:firstv 为顶点循环链表中的其中一个顶点的指针 / 返回值:多边形的面积 / 下面为你的实现代码.答：float PolygonArea(Vertex *firstv)Vertex *p1,*p2; p1= v1-next; p2=p1-next;double sum1,sum2=0;do sum1=Aera2(firstv-p,p1-p,p2-p);sum2+=sum1;p1=p1-next;p2=p1-next;while(p2!=firstv);return -0.5*sum2;/方向为逆时针时面积为负值9. 已知点坐标为浮点数,空间平面多边形采用顶点的循环链表来描述。请编写 一 C 语言函数,根据 Newell 公式稳定地计算该多边形的法矢量:struct Vertex /顶点结构体的定义 float x, y, z; /顶点的三维坐标Vertex *prev, *next; /顶点循环链表中的前驱和后继 ;void PolygonNormal(Vertex *firstv, float norm3 )/ 输入:firstv 为顶点循环链表中的其中一个顶点的指针 / 输出:多边形的法矢量通过数组 norm 返回 / 下面为你的实现代码.答：void PolygonNormal(Vertex *firstv, float norm3 ) for(int i=0;inext.y)*(p.z+p-next.z);/xnorm1+=(p.x-p-next.x)*(p.z+p-next.z);/y norm2+=(p.x-p-next.x)*(p.y+p-next.y);/zp=p-next;while(p!=firstv);return norm;/10.给定平面上一点 q 和一个凸多边形 P,多边形采用顶点的数组描述,方向为 逆时针。已知所有点坐标均为整数,不考虑溢出问题。假定计算三角形二倍代数 面积的函数已定义。请按照要求编写判断 q 是否在 P 内部的实现函数:struct Point int x, y; /点结构体的定义int Area2(Point p0, Point p1, Point p2); / 计算三角形二倍代数面积的函数声明bool IsPointInConvexPolygon(Point q, Point P , int n)/ 输入:P 为用点的数组表示的多边形,下标为 0n-1,n 为多边形顶点个数 / q 为判断点/ 返回值:如果 q 在 P 内返回 true,否则返回 false。在边界上也算作在内。 / 下面为你的实现代码.答:bool IsPointInConvexPolygon(Point q, Point P , int n) int i=0,j=1; bool flag=false; double sum1,sum2=1;doif(i=n-1) j=0; sum1=Aera2(q,Pi,Pj); if(sum1*sum20) sum2=sum1; flag=true; else break; i+; j+;while(i!=n); return flag;/12. 下面的代码先给出了平面剖分的半边数据结构的一部分,以及返回伙伴半边 函数 mate()的定义。请利用 mate()编写符合这个数据结构的一个 C 语言函数,用 来找出给定顶点的最近相邻顶点。要求尽可能少地访问无用顶点,尽可能不要除 法和其他无理运算。struct Half; struct Edge;struct Vertex /顶点节点的结构体;/顶点的坐标 /指向以该顶点为起点的其中一个半边int x, y;Half *h;Vertex *prev, *next; /在顶点链表中的前驱与后继,在空间上不一定邻近struct Half Vertex *startv; /起始顶点Edge *ownere; /所属边Half *prev, *next; /在某面的半边循环链表中的前驱与后继,;struct Edge Half *h1, *h2;/在空间上一定是邻近的Ed