第六章图形运算.doc

第六章 图形运算6.1 线段的交点计算在本节中，我们将实现线段的交点计算。分两种情况：1、只有两条线段待求交，2、有多条线段待求交。我们编写两段程序，第一段实现两条线段的求交，这是比较简单的，第二段实现多条线段的求交，它以第一段程序为基础。1、 两条线段的求交。假设有两条平面上的线段，其两个端点的分别是：B1,E1,B2,E2,则由教材知其交点坐标应该按如下步骤计算。1） 计算行列式值：2） 如果，则计算参数值：，注意：只有且的时候两线段才真正相交。代码：1） 首先建立MFC工程：Ch6_Sec12） 双击ResourceView标签中的Menu，编辑菜单项资源。在菜单中添加命令项：【两条线段求交】，其ID号设置为IDC_ INTSEC_TWOLINE，将Pop-up项去掉。3） 右键单击【两条线段求交】，选择Classwizzard，建立CCh6_Sec1View类的消息响应函数：OnIntsecTwoline()。4） 点击ClassView标签，双击类名：CCh6_Sec1View，为其添加如下的私有成员变量：5） 在CCh6_Sec1View的构造函数中添加如下代码：6） 为CCh6_Sec1View类添加鼠标左键消息响应函数：OnLButtonDown，OnLButtonUp，OnMouseMove，在其中分别添加如下代码（黑体部分）：void CCh6_Sec1View:OnLButtonDown(UINT nFlags, CPoint point) m_lBDown = TRUE;m_BPointsm_Num_Lines = point;m_EPointsm_Num_Lines = point;CView:OnLButtonDown(nFlags, point);void CCh6_Sec1View:OnLButtonUp(UINT nFlags, CPoint point) m_lBDown = FALSE;m_Num_Lines +;CView:OnLButtonUp(nFlags, point);void CCh6_Sec1View:OnMouseMove(UINT nFlags, CPoint point) CClientDC dc(this);dc.SetROP2(R2_NOT);if(m_lBDown)dc.MoveTo(m_BPointsm_Num_Lines);dc.LineTo(m_EPointsm_Num_Lines);m_EPointsm_Num_Lines = point;dc.MoveTo(m_BPointsm_Num_Lines);dc.LineTo(m_EPointsm_Num_Lines);CView:OnMouseMove(nFlags, point);7） 添加CCh6_Sec1View类的成员函数：BOOL TwoLines(CPoint B1,CPoint E1,CPoint B2,CPoint E2,CPoint& IntPt);其代码如下：8） 为CCh6_Sec1View类添加成员函数：void DrawPoint(CPoint P);其代码如下：9） 在消息响应函数OnIntsecTwoline中添加如下代码：BOOL Intersected = FALSE;for(int row = 0; row m_Num_Lines; row+)for(int col = row + 1; col m_BPt;CPoint EPt = Seg-m_EPt;double t1 = (x - m_BPt.x) /(double) (m_EPt.x - m_BPt.x);double t2 = (x - BPt.x) / (double)(EPt.x - BPt.x);double y1 = m_BPt.y + (m_EPt.y - m_BPt.y) * t1;double y2 = BPt.y + (EPt.y - BPt.y) * t2;if(y1 y2)return TRUE;return FALSE;4) 创建一个“事件点”类：EventPt，其定义如下：5) 为CCh6_Sec1View类定义如下三个成员变量：6) 为CCh6_Sec1View类的构造函数添加如下代码m_HeadSSL = new StatusSL;m_Num_EventPts = 0;7) 为CCh6_Sec1View类添加如下成员函数StatusSL* BelowInSSL(StatusSL* CurSegment);/得到扫描线状态表中位于CurSegment之上的线段StatusSL* AboveInSSL(StatusSL* CurSegment);/得到扫描线状态表中位于CurSegment之下的线段void DelASegInSSL(CPoint BPt, CPoint EPt);/将扫描线状态表中起点和终点分别为BPt和EPt的线段删除出扫描线状态表void InsASegInSSL(StatusSL* Segment);/将Segment加入到扫描线状态表中的合适位置void SwitchInSSL(StatusSL* S1, StatusSL* S2,StatusSL* tempS);/在扫描线状态表中交换S1和S2void InitEventPList();/初始化事件点进度表EventPt getMinEventpt();/得到事件点进度表中的最小元素,将其取出，并将事件点进度表中最后一个元素转移到这个位置void InsIntoEtPtLt(EventPt x);/将x插入到事件点x插入到事件点进度表中BOOL Member(EventPt x);/判断点x是否在事件点进度表中8) 以上各函数的代码可见光盘。9) 点击ResourceView标签，双击Menu，在【两条线段求交】之后再添加一个菜单命令【多条线段求交】，其ID号设置为：IDC_MULTI_SEGS，并在CCh6_Sec1View类中为其添加消息响应函数：OnMultiSegs()，其代码如下：InitEventPList();/将初始的所有线段的端点放入事件点进度表中int Index = 0;/收集到的交点的个数EventPt P;StatusSL* S;StatusSL* S1;StatusSL* S2;StatusSL* S3;StatusSL* S4;StatusSL* tempS;EventPt IntsecPts2;int num_IntsetPts;while (m_Num_EventPts)/m_Num_EventPts != 0代表事件点进度表非空num_IntsetPts = 0;P = getMinEventpt();m_Num_EventPts -;if(P.m_Type = left)S = P.m_Seg1;InsASegInSSL(S);S1 = AboveInSSL(S);S2 = BelowInSSL(S);if(S & S1 & TwoLines(S-m_BPt, S-m_EPt, S1-m_BPt, S1-m_EPt, IntsecPtsnum_IntsetPts.m_Pt)IntsecPtsnum_IntsetPts.m_Seg1 = S;IntsecPtsnum_IntsetPts.m_Seg2 = S1;IntsecPtsnum_IntsetPts.m_Type = intersection;num_IntsetPts +;if(S & S2 & TwoLines(S-m_BPt,S-m_EPt,S2-m_BPt,S2-m_EPt, IntsecPtsnum_IntsetPts.m_Pt)IntsecPtsnum_IntsetPts.m_Seg1 = S;IntsecPtsnum_IntsetPts.m_Seg2 = S2;IntsecPtsnum_IntsetPts.m_Type = intersection;num_IntsetPts +;else if(P.m_Type = right)S = P.m_Seg1;S1 = AboveInSSL(S);S2 = BelowInSSL(S);if(S1 & S2 & TwoLines(S1-m_BPt,S1-m_EPt,S2-m_BPt,S2-m_EPt, IntsecPtsnum_IntsetPts.m_Pt)if(IntsecPtsnum_IntsetPts.m_Pt.x P.m_Pt.x)IntsecPtsnum_IntsetPts.m_Seg1 = S1;IntsecPtsnum_IntsetPts.m_Seg2 = S2;IntsecPtsnum_IntsetPts.m_Type = intersection;num_IntsetPts +;DelASegInSSL(S-m_BPt,S-m_EPt);else if(P.m_Type = intersection)S1 = P.m_Seg1;S2 = P.m_Seg2;if(S2-HigherThan(S1,P.m_Pt.x - 1)tempS = S1;S1 = S2;S2 = tempS;S3 = AboveInSSL(S1);S4 = BelowInSSL(S2);if(S3 & S2 & TwoLines(S3-m_BPt,S3-m_EPt,S2-m_BPt,S2-m_EPt, IntsecPtsnum_IntsetPts.m_Pt)if(IntsecPtsnum_IntsetPts.m_Pt.x P.m_Pt.x)IntsecPtsnum_IntsetPts.m_Seg1 = S3;IntsecPtsnum_IntsetPts.m_Seg2 = S2;IntsecPtsnum_IntsetPts.m_Type = intersection;num_IntsetPts+;if(S4 & S1 & TwoLines(S4-m_BPt,S4-m_EPt,S1-m_BPt,S1-m_EPt, IntsecPtsnum_IntsetPts.m_Pt)if(IntsecPtsnum_IntsetPts.m_Pt.x P.m_Pt.x)IntsecPtsnum_IntsetPts.m_Seg1 = S4;IntsecPtsnum_IntsetPts.m_Seg2 = S1;IntsecPtsnum_IntsetPts.m_Type = intersection;num_IntsetPts+;SwitchInSSL(S1,S2,tempS);for(int i = 0; i num_IntsetPts; i+)if(!Member(IntsecPtsi)m_IntPointsIndex = IntsecPtsi.m_Pt;Index +;InsIntoEtPtLt(IntsecPtsi);m_Num_EventPts+;for(int i = 0; i point.y | (m_O.y = point.y & m_O.x point.x )m_O = point;DrawAPt(point);m_Num_Pts +;CView:OnLButtonDown(nFlags, point);5) 添加CCh6_Sec2View类的如下两个成员函数：并为其添加代码（黑体）：double CCh6_Sec2View:IFLeftRotation(CPoint P1, CPoint P2, CPoint P3)int x1 = P1.x;int y1 = P1.y;int x2 = P2.x;int y2 = P2.y;int x3 = P3.x;int y3 = P3.y;double delta = (x2 * y3 - x3 * y2) - (x1 * y3 - x3 * y1) + (x1 * y2 - x2 * y1); return delta;void CCh6_Sec2View:DrawAPt(CPoint point)CClientDC dc(this);dc.Arc(point.x - 4,point.y + 4,point.x + 4,point.y - 4,point.x,point.y + 4,point.x,point.y + 4);6) 在文件CCh6_Sec2View.cpp中添加如下的全局变量：CPoint O;7) 在文件CCh6_Sec2View.cpp添加如下的全局函数：int comp(const void* Pt1,const void* Pt2)CPoint P1 = *(CPoint*)Pt1;CPoint P2 = *(CPoint*)Pt2;double AglDge1;double AglDge2;double A;double B;if(P1 != O)A = (P1.x - O.x) / sqrt(pow(P1.x - O.x , 2) + pow(P1.y - O.y , 2);B = P1.y - O.y;if(B = 0)AglDge1 = 1 - A;elseAglDge1 = 3 + A;elseAglDge1 = 0;if(P2 != O)A = (P2.x - O.x) / sqrt(pow(P2.x - O.x , 2) + pow(P2.y - O.y , 2);B = P2.y - O.y;if(B = 0)AglDge2 = 1 - A;elseAglDge2 = 3 + A;elseAglDge2 = 0;if(AglDge1 AglDge2)return -1;else if(fabs(AglDge1 - AglDge2) m_O;if(m_Num_Pts 0)qsort(m_Pts,m_Num_Pts,sizeof(CPoint),comp);/执行算法CPoint v = O;int pre_i = m_Num_Pts - 1;int cur_i = 0;int nex_i = 1 % m_Num_Pts;int nextnext_i = 2 % m_Num_Pts;while (m_Ptsnex_i != m_Pts0) if(IFLeftRotation(m_Ptscur_i,m_Ptsnex_i,m_Ptsnextnext_i) 0)pre_i = cur_i;cur_i = nex_i;nex_i = nextnext_i;nextnext_i+;nextnext_i %= m_Num_Pts;elsefor(int i = nex_i; i m_Num_Pts - 1; i+)m_Ptsi = m_Ptsi+1;cur_i = pre_i;pre_i += m_Num_Pts - 1;pre_i %= m_Num_Pts;nex_i = (cur_i + 1) % m_Num_Pts;nextnext_i = (nex_i + 1) % m_Num_Pts;m_Num_Pts -;dc.MoveTo(m_Pts0);for(int i = 1; i = 0)Agl = 1 - A;elseAgl = 3 + A;return Agl;CPoint CCh6_Sec2View:Wrapping(CPoint u,double d2)CPoint P = m_Pts0;double Angle = 5;double tempAgl;for(int i = 0; i tempAgl)Angle = tempAgl;P = m_Ptsi;else if(fabs(Angle - tempAgl) pow(m_Ptsi.x - u.x,2) + pow(m_Ptsi.y - u.y,2)P = m_Ptsi;return P;6) 单击ResourceView标签，双击Menu，在【Graham算法】之后再添加一个菜单命令【Jarvis算法】，其ID号设为IDC_JARVIS。7) 鼠标右键点击【Jarvis算法】，选择Classwizzard，为其建立一个CCh6_Sec2View类的消息响应函数：OnJarvis，并在其中添加如下代码：double d2 = 1,0;CPoint v0 = m_O;CPoint v1;CPoint u;m_num_RPts = 0;m_RPtsm_num_RPts = v0;m_num_RPts+;u = v0;v1 = Wrapping(u,d);double d_mag;while (v1 != v0)m_RPtsm_num_RPts = v1;m_num_RPts +;d0 = v1.x - u.x;d1 = v1.y - u.y;d_mag = sqrt(d0 * d0 + d1 * d1);d0 /= d_mag;d1 /= d_mag;u = v1;v1 = Wrapping(u,d);CClientDC dc(this);dc.MoveTo(m_RPts0);for(int i = 1; i m_num_RPts; i+)dc.LineTo(m_RPtsi);dc.LineTo(m_RPts0);8) 建立【清屏】命令，代码如下：此段程序的用法是：首先，运行程序，界面如图：然后，用鼠标在屏幕上随意点击，产生一些杂乱的点，如图，然后，可点击【Graham算法】或者【Jarvis算法】，都会产生相同的结果，即刚才所产生的点的凸包。6.3 包含与重叠在本节的实验中，我们将实现如下三段程序：1、判断平面上某点是否在某个简单多边形内（关于简单多边形的定义请参见教材第5章第4节），2、判断平面上某点是否在某凸多边形内，3、判断某两个平面多边形是否有重叠，即是否相交。这3段程序都将集成在工程Ch6_Sec3中。6.3.1判断平面上某点与平面上某简单多边形的相对位置关系。我们将这种相对的位置关系分为：点在多边形内部、点在多边形外部、点在多边形边界上三种情况。实现步骤：1、 建立MFC工程，工程名为：Ch6_Sec3。2、 在CCh6_Sec3View的.h文件中定义如下枚举类型：3、 在CCh6_Sec3View的.h文件中定义如下成员变量：CPointm_Polygon512;intm_Num_Pts;CPointm_Pt;Type_Opera m_type_oper;4、 为CCh6_Sec3View类新建一个清屏函数ClearScreen，代码同第三章的同名函数。5、 打开Resource标签，双击Menu，添加一个Pop-up型的菜单项，Caption为“点与多边形相对位置关系检测”，在其下新建两个菜单命令：“简单多边形”，“凸多边形”，其ID号分别为：IDC_SIMPLE_POLY, IDC_CONVEX_POLY。6、 单击右键，选择ClassWizzard，在Object Ids栏中分别选择IDC_SIMPLE_POLY和IDC_CONVEC_POLY，在Class name栏选择CCh6_Sec3View，在Messages栏选择COMMAND，新建两个消息响应函数：OnSimplePoly(), OnConvexPoly()。7、 在函数OnSimplePoly()中添加如下代码：8、 为CCh6_Sec3View类建立如下的成员函数：DetectForSimplyPoly(), 其代码为：BOOL M = FALSE;BOOL atBdy = FALSE;int xP = m_Pt.x;int yP = m_Pt.y;double y;int xi;int yi;int xip1;int yip1;for(int i = 0; i m_Num_Pts - 1; i+)xi = m_Polygoni.x;yi = m_Polygoni.y;xip1 = m_Polygon(i + 1) % (m_Num_Pts - 1).x;yip1 = m_Polygon(i + 1) % (m_Num_Pts - 1).y;if(xP xi & xP = xi & xP = xip1) | (yP yi & yP yip1)continue;y = yi + (xP - xi) * (yip1 - yi) / (double)(xip1 - xi);if(fabs(y - yP) 0.0001)MessageBox(点在多边形的边界上.);atBdy = TRUE;break;if(y = 2m_Polygonm_Num_Pts - 1 = point;if(abs(point.x - m_Polygon0.x) 6 & abs(point.y - m_Polygon0.y) 6)if(m_Num_Pts 1)dc.MoveTo(m_Polygonm_Num_Pts - 2);dc.LineTo(m_Polygonm_Num_Pts - 1);m_Num_Pts +;break;case Detect_Intsect:break;CView:OnLButtonDown(nFlags, point);结束。6.3.2实现判断平面上某点与平面上某凸多边形之间的相对位置关系。同样，这种相对的位置关系也分为：点在多边形内部、点在多边形外部、点在多边形边界上三种，但为简便，我们将点在多边形的边界上的情况也算做点在多边形内部。在CCh6_Sec3的基础之上添加代码。实现步骤： 1、 在OnConvexPoly函数中添加如下代码2、 为了保证多边形顶点是按照屏幕的逆时针顺序输入的，在OnLButtonDown的dc.Arc(point.x - 4,point.y + 4,point.x + 4,point.y - 4,point.x,point.y + 4,point.x,point.y + 4);if(m_Num_Pts 1)dc.MoveTo(m_Polygonm_Num_Pts - 2);dc.LineTo(m_Polygonm_Num_Pts - 1);m_Num_Pts +;语句后面加入如下代码：if(m_type_oper = Convex_Poly & m_Num_Pts = 4)/the vertics of convex must be input in conterclockwise orderCPoint P1 = m_Polygonm_Num_Pts - 3 - m_Polygonm_Num_Pts - 4;CPoint P2 = m_Polygonm_Num_Pts - 2 - m_Polygonm_Num_Pts - 3;if(ComputeRelationship(CPoint(0,0),P1,P2) 1)k = (int)(i + j) / 2);D = ComputeRelationship(m_Polygon0,m_Polygonk,m_Pt);if(D 0)i = k;else if(D 0)j = k;else/D = 0, i.e., m_Pt is right on line 0kCPoint P1 = m_Pt - m_Polygon0;CPoint P2 = m_Pt - m_Polygonk;double cos_angle = P1.x * P2.x + P1.y + P2.y;if(cos_angle 0 & Dij 0 & Dj0 0)MessageBox(点在凸多边形的内部);elseMessageBox(点在凸多边形的外部);6.3.3实现判断平面上两个凸多边形是否相交，如果相交，将相交之后的多边形输出。继续在Ch6_Sec3工程之上添加代码。实验步骤：1、 为CCh6_Sec3View类新建如下成员变量：CPoint m_CPoly1512;intm_num_cpoly1;BOOL m_input_Poly1;CPoint m_CPoly2512;intm_num_cpoly2;BOOL m_input_Poly2;int m_FirstTimeForOutputFunction;CPoint m_ResultPoly512;intm_num_rPoly;2、 在构造函数CCh6_Sec3View()中添加语句：m_num_cpoly1 = m_num_cpoly2 = m_num_rPoly = 0;m_num_cpoly1 = m_num_cpoly2 = m_num_rPoly = 0;m_input_Poly1 = TRUE;m_input_Poly2 = FALSE;/先输入Poly1，后输入Poly2m_num_rPoly = 0;m_FirstTimeForOutputFunction = 0;3、 在鼠标左键点击消息响应函数OnLButtonDown中的Switch语句中添加如下代码：case Detect_Intsect:CPoint* temp_Poly;if(m_input_Poly1)temp_Poly = m_CPoly1;else/m_input_Poly2temp_Poly = m_CPoly2;switch(m_Num_Pts) case 0:/input the first vertics of a convex polytemp_Polym_Num_Pts = point;dc.Arc(point.x - 4,point.y + 4,point.x + 4,point.y - 4,point.x,point.y + 4,point.x,point.y + 4);break;default :/m_Num_Pts = 1temp_Po