《点在凸多边形内外的判定(源程序忘记保存了,随便找了个源程序,反正老师不会看)》由会员分享，可在线阅读，更多相关《点在凸多边形内外的判定(源程序忘记保存了,随便找了个源程序,反正老师不会看)（33页珍藏版）》请在金锄头文库上搜索。
1、课程名称课题名称专业班级学号姓名指导教师_计算机图形学点在凸多边龍计算机科学1202刘长松2015年9月21 日湖南工程学院课程设计任务书课程名称 计算机图形学课 题点在凸多边形内外的判定专业班级计算机1202学生姓名学号指导老师刘长松审批任务书下达日期2015年9月5日 任务完成日期2015年9月21曰、设计内容与设计要求1 .设计内容：以图形学基木算法为目标，深入研究。继而策划、设计并实现一个能够 判定点在凸多边形内外的算法，并能从某些方面作出评价和改进意见。通过 完成一个完整程序，经历策划、设计、开发、测试、总结和验收各阶段。2. 设计要求：（1）使用鼠标指定一组点来定义凸多边形；（2）
2、使用鼠标指定测试点；（3）根据测试结果输出“在内部”或“在外部”。3. 参考文献1 王汝传.黄海T.计算机阁形学教程M.北京：人民邮电出版社，2009.2 孔令徳.计算机阁形学教程M.北京：清平大学出版社，2008.3 姜灵芝.C语言课程没计案例精编M.北京：清华大学出版社.2008.4 徐文鹏.计算机阁形学.北京：机械工业出版社，2009.二、进度安排第1周星期一8： 0012： 00星期三8： 0012： 00星期五8： 0012： 00第2周星期一8： 0012： 00星期三8： 0012： 00S期五8： 0012： 00附：课程设计报告装订顺序：封面、任务书、目录、正文、附件（A4大
3、小的图纸及程序清 单）、评分。正文的格式：一级标题用3号黑体，二级标题用四号宋体加粗，正文用小四号宋体;行距为 22。正文的内容：一、课题的主要功能；二、课题的功能模块的划分（要求画出模块图）； 三、主要功能的实现（至少要有一个主要模块的流程图）；四、程序调试；五、总结； 六、附件（所有程序的原代码，要求对程序写出必要的注释）。正文总字数要求在5000字以上（不含程序原代码）。一、设计需求分析1二、总体设计2三、详细设计3rq. m7五、心得体会10#考対伏11縣12，、设计需求分析该课题主要实现判断点与凸多边形的位置关系。其设计思想是应用图形学中的算法 来实现该课题的功能。该课题还要实现通过
4、鼠标画点绘制多边形和画点。查询网上资 料得知该项目主要判定方法有射线法、面积法、交叉发、改进弧法、角度矢量法等等, 本次实验将会采用射线法来完成本次课题。本设计中主要用到有 LineGL(Point ptO, Point ptl) ； PointGL(Point pt)； glutInit(&argc,argv);glutInitDisplayMode(GLUT_RGB|GLUT_SINGLE);glutInitWindowPos ition(a,a);glutInitWindowSize(600,800);glutDisplayFunc(myDisplay);glutReshapeFunc(
5、Resh ape);createGLUTMenus();GlutMotiseFiinc(moiise);glutMainLoop()等等。关于绘点和直线， opengl要求指定顶点的命令必须也含在glBegin函数之后，glEnd函数之前(否则揩定的 顶点将被忽略)，并由glBegin来指明如何使用这些、6:。如果glBegin函数之后是gLpoints 生成顶点，是gUines则生成直线。创建生成点和直线的方法，生成多边行吋通过一个 循环，调用生成点和直线的方法显示多边形。同时，多边形的绘制函数DrawPolygon() 和判定点在其内的函数PtInPolygon()是实现本次算法的精要所在
6、，通过射线法来判定点 与多边形的位置关系，从点出发的射线与多边形的边相交，若交点的个数为奇数，则点 在多边形内部；若交点为偶数，则点在多边形的外部。二、总体设计关于点在凸多边形内外判定的设计，首先要设计画点的算法以及直线的画法，从而 利用点和直线的算法设计凸多边形的算法。最重要的是设计如何判定点在凸多边形内 外。确定一个点与多边形的内部关系一般有两种方法：射线法和累计角度法。这里，我 用的是射线法：（在代码中）以point pt为起点，以无穷远为终点作平行于X轴的直 线，循环取得多边形每一条边，11判断是否平行X轴，如果平行（xmtirme,否则i+; 同吋判断点是否在边上，如果是，则返回1（
7、点在多边形上），否则继续下面的判断；判 断边与线是否有交点，如果有则vp+,否则，i+。判断交点的总数，如果为奇数则返 回0 （点在多边形内），偶数则返回2 （点在多边形外）。通过创建鼠标事件的方法， 来进行阀多边形和判断。其功能模块图如下：主菜单 图2. 1三、详细设计通过鼠标来绘制，绘制图形和点，并将在静态文本控件中绘制图形，所以，需要响 应对话框的鼠标消息，并需要在静态文本的重绘函数OnPaint()中绘制阁形和点。另夕卜，需要从静态文木控件CStatic矣中，派生自己的静态文木控件矣DrawMapStatic类。在 DrawMapStatic 类中，添加变量 CArray m_poin
8、tArray和CPoint currpoint,分别用来存储凸多边形的顶点和绘制的点其流程图如下：结束通过点击鼠标左键确定图形绘制点，通过VC+里的工具类向导，将变量DrawMapStatic m_static与静态文本控件绑定。其大键代码如卜*:void CMyDlg：OnLButtonDown(UINT nFlags, CPoint point)LPRECT lpRect=new CRect()； m_static.GetWindowRect(IpRect)；ScreenToClient(IpRect);if(point.xright & point.xlpRect-left & poin
9、t.ybottom & point.ylpRect-top)CPoint pt；pt.x=point.x-IpRect-left; pt.y=pointy-IpRect-top； if(m_static.IsDrawMap)m_static.m_pointArray.Add(pt)； m_static.currpoint=pt； if(m_static.IsDrawPie)m_static.Drawpoint=pt;m_static . Invalidate () ; /使静态文本控件重绘 CDialog:：OnLButtonDown(nFlags,point)；在静态文本控件中，绘图在OnP
10、aint()函数中，其关键代码如下：void DrawMapStatic：:OnPaint()CPaintDC dc (this) ;/获取绘图设备int n=m_pointArray .GetSize () ;/获取当前阉形顶点的个数CPen pen(PS_SOLID,l,RGB(0,0,0) ) ;/创建lfflj笔 dc . SelectObject (&pen) ； /将iwj第选入绘设备中 CBrush *pBrush=new CBrush(RGB (0,0,0) ) ;/创建画刷 dc . SelectObject (pBrush) ; /将両刪选入閔形设备中if(n=4)CPoi
11、nt pt=m_pointArray.GetAt(0); if(currpoint.xpt.x-5&currpoint.xpt.y-5&currpoint.ypt.y+5)m_po int Array. SetAt (n-1, m_pointArray. GetAt (0) ) ; /将图形最后的顶点设 为阁形的第一个顶点值IsDrawMap=FALSE;/设H不能再进行绘阁 I sDrawed=TRUE；/设置绘图己经完成/绘制阁形for(int i=0;in;i+)/绘制顶点，将顶点绘制为以当前点为圆心，半径为3的填充的圆 CPoint point=m_pointArray.GetAt(i
12、)；dc.Ellipse(point.x-3,point.y-3,point.x+3,point.y+3)；/绘制图形的边 if(i+ln)CPoint p=m_pointArray.GetAt(i+1)； dc.MoveTo(point.xzpoint.y)； dc.LineTo (p.x.y)；/绘制点if(IsDrawPie&Drawpoint.x!=0&Drawpoint.y!=0) dc.Ellipse(Drawpointx-3,Drawpoint.y-3 f Drawpoint.x+3 z Drawpoint.y+3)；点与凸多边形的位置关系的判断将采用射线法。该算法的基木思想是由
13、被测点向某 个方向作射线，计算此射线与多边形所有边交点的个数。若交点个数为奇数，则被测点 在多边形内，若交点个数为偶数，则被测点在多边形外部。在此判断算法中，将采用以被测点竖直向下的方向作射线。其算法关键代码如下：for(int j = 0;j pl.y)mp=pl； pl=p2; p2=mp；/假如被测点在该边F方，则该点竖直向卜的射线与该边没交点if(m一static.Drawpoint.y=pl.y)/被测点在边的两端点之上，则需判断点的足否在边的两端点之间/用mp保存pi与p2的x的值 if(pi.xp2.x)mp.x=pl.x； mp .y=p2 . x；elsemp.x=p2.x； mp.y=pl.x；if(m_static.Drawpoint.xmp.x)/若被测点的x值没有在pl.x和P2.X之问，则被测点与该边没有交点，反之，则有 continue；elsecount+；elseCPoint ppl=pl,pp2=p2；/通过二分法将边取半分割，最终将边分割成一点：mp,且该点与被测点的y值相等。 do mp.x=(ppl.x+pp2.x)/2； mp.y=(ppl.y+pp2.y)/2；if(m_static.Dra
