多边形位置关系判断程序.doc

《多边形位置关系判断程序.doc》由会员上传分享，免费在线阅读，更多相关内容在学术论文-天天文库。

1、多边形位置关系判断程序作业简介一.需求说明对软件需求完全理解对于软件开发工作的成功是至关重要的，需求说明的任务是发现、规范的过程，有益于提高软件开发过程中的能见度，便于对软件开发过程中的控制与管理，便于采用工程方法开发软件，提高软件的质量，便于开发人员、维护人员、管理人员之间的交流、协作，并作为工作成果的原始依据，并且在向潜在用户传递软件功能、性能需求，使其能够判断该软件是否与自己的需求相关。我们的程序的功能是可以判断在同一平面内任意两个多边形之间的位置关系，其位置关系分为：相交，相离，包含3种情况。输入条件是两个多边形各自的边数及每个多边形各自顶点的坐标，输

2、入多边形坐标时要注意按逆时针或顺时针的顺序输入，不然程序将无法构成多边形，出现错误。输出是两个多边形的位置关系结果，是相交，相离，包含（能反应哪个多边形包含另外一个多边形）之间的一种情况。二．作业目的秉承着实践出真知的思想，为了让我们更好的理解和运用所学的C语言及CAD技术知识，老师布置了这次团队合作项目。本项目不仅能提高我们对C言语和CAD技术的理解掌握，更可以培养我们的团队合作精神，在完成项目的过程中，我们会遇到种种困难，而当我们并肩作战，克服困难后，我们会发现彼此间更加信任，友谊更加深厚。我们体会到团队合作的意义，而团队合作精神是以后步入社会必不可少的。

3、三．成果描述本产品是一个具有判断任意两个在同一平面内多边形之间的位置关系的程序，其核心开发语言是C语言，具体有C语言技术和CAD技术结合实现。本产品通俗易懂，即使没有C语言和CAD技术基础知识的人也能熟练使用，本产品本身不是一个具有完善功能的软件，只是其中一个具有独立功能的程序。如结合其他程序一起使用，将具有完整的功能。四．应用目标当今社会，制造业正处于高速发展中，竞争异常激烈，在激烈的的竞争中时间显得尤为宝贵，本程序的应用目标就是在产品设计和制造过程等中迅速判断空间位置关系，可以判断是否发生干涉等问题，比如在机械制造中利用本程序迅速判断待加工体机床是否发生干

4、涉，在零件装配时，装配件间是否发生干涉等等。利用本程序，可以节约大量时间，为使用者减轻工作量让其拥有更强的竞争力。五．参考资料《C程序设计（第二版）》谭浩强编著清华大学出版社《计算机图形学（第三版）》孙家广等编著清华大学出版社《程序设计基础（C语言）第二版》郑平安曾大亮编著清华大学出版社《VisualC++开发入门与编程实践》屈磊李媛媛编著电子工业出版社六．算法说明这个算法的核心为参数法的应用：参数法：已知第一条线段两点：（X0,Y0）,(X1,Y1)参数方程为：X=(X1-X0)*T1+X0;(0<=T1<=1)Y=(Y1-Y0)*T1+Y0;(0<=T1<

5、=1)同理：第二条线段参数方程（（X2,Y2）,(X3,Y3)　）X=(X３-X２)*T2+X２;(0<=T2<=1)Y=(Y３-Y２)*T2+Y２;(0<=T2<=1)联立方程得：X=(X1-X0)*T1+X0=(X３-X２)*T2+X２Y=(Y1-Y0)*T1+Y0=(Y３-Y２)*T2+Y２即(X1-X0)*T1+(X0-X２)=(X３-X２)*T2(Y1-Y0)*T1+(Y0-Y２)=(Y３-Y２)*T2其中0<=T1<=1，0<=T2<=1令X1-X0=E,X0-X2=F,X３-X２=GY1-Y0=H,Y0-Y２=M,Y３-Y２=N即E*T1+F=G

6、*T2H*T2+M=N*T2解得：T1=(M*G-F*N)/(E*N-H*G)T2=(M*E-F*H)/(E*N-H*G)下面进行分类讨论：E*N-H*G!=0时T1和T2均有确定解这时如果0<=T1,T2<=1则交点落在两线段之间，两线段相交E*N-H*G=0时，即（X1-X0）*（Y３-Y２）=(Y1-Y0)*(X3-X2)1).X1-X0!=0且X3-X2!=0推得K1=(Y1-Y0)/（X1-X0）=（Y３-Y２）/(X3-X2)=K2即两线段平行（两线段均存在斜率）2).X1-X0=0且X3-X2=0此时由于两线段两端点不重合，即Y1-Y0!=0且Y

7、３-Y２!=0即两线段均不存在斜率，均垂直于X轴，两线段平行3).X1-X0=E和X0-X2=F中有一个为0，假设X1-X0!=0且X3-X2=0，由于（X1-X0）*（Y３-Y２）=(Y1-Y0)*(X3-X2)，推得Y3-Y2=0,从而（X2,Y2）,(X3,Y3)两点重合，舍去。同理，也不可能X1-X0=0且X3-X2!=0所以由以上可得E*N-H*G=0是两线段平行的充要条件。（1-1）当E*N-H*G=0时，做近一步讨论：I)M*G-F*N!=0且M*E-F*H!=0时由T1,T2的表达式可得T1,T2均无解，即由几何关系可得此时两条线段平行且相距一

8、定距离。所以此时两线段无交点。II)M