GDI+坐標(biāo)空間及其變換

坐標(biāo)空間及其變換GDI十在視圖和窗口中繪圖或定位總是在一個(gè)二維坐標(biāo)系進(jìn)行，依據(jù)作用方法的不同，坐標(biāo)有多種表示方法，并且各種不同坐標(biāo)之間可以相互轉(zhuǎn)換。世界坐標(biāo)系、設(shè)備坐標(biāo)系和頁(yè)面坐標(biāo)系GDI+為我們提供了三種坐標(biāo)空間:世界坐標(biāo)系、頁(yè)面坐標(biāo)系和設(shè)備坐標(biāo)系。世界坐標(biāo)系是應(yīng)用程序用來(lái)進(jìn)行圖形輸入輸出所使用的一種與設(shè)備無(wú)關(guān)的笛卡爾坐標(biāo)系。通常，我們可以根據(jù)自己的需要和方便定義一個(gè)自己的世界坐標(biāo)系，這個(gè)坐標(biāo)系稱為用戶坐標(biāo)系。例如，前面DrawLine(&newPen,20,10,200,100);中的坐標(biāo)都是以這個(gè)用戶坐標(biāo)系為基準(zhǔn)的，默認(rèn)時(shí)使用像素為單位。設(shè)備坐標(biāo)系是指顯示設(shè)備或打印設(shè)備坐標(biāo)系下的坐標(biāo)，它的特點(diǎn)是以設(shè)備上的象素點(diǎn)為單位。對(duì)于窗口中的視圖而言，設(shè)備坐標(biāo)的原點(diǎn)在客戶區(qū)的左上角，x坐標(biāo)從左向右遞增，y坐標(biāo)自上而下遞增。由于設(shè)備的分辨率不同，相同坐標(biāo)值的物理位置可能不同。如對(duì)于邊長(zhǎng)為100的正方形，當(dāng)顯示器為640x480和800x600時(shí)的大小是不一樣的。頁(yè)面坐標(biāo)系是指某種映射模式下的一種坐標(biāo)系。所謂映射是指將世界坐標(biāo)系通過(guò)某種方式進(jìn)行的變換。默認(rèn)時(shí)，設(shè)備坐標(biāo)和頁(yè)面坐標(biāo)是一致的。坐標(biāo)映射和坐標(biāo)原點(diǎn)的設(shè)置為了能保證打印或顯示的結(jié)果不受設(shè)備的影響，GDI+定義了一些映射方法和屬性來(lái)決定設(shè)備坐標(biāo)和頁(yè)面坐標(biāo)之間的關(guān)系。這些映射方法和屬性有：SetPageUnit和GetPageUnit這兩個(gè)屬性函數(shù)是用來(lái)設(shè)置和獲取每個(gè)單位所對(duì)應(yīng)的實(shí)際度量單位。它通?？梢杂邢铝械闹担篣nitDisplay--每個(gè)頁(yè)面單位為1/75英寸；UnitPixel--每個(gè)頁(yè)面單位為1個(gè)像素，此時(shí)頁(yè)面坐標(biāo)與設(shè)備坐標(biāo)相同；UnitPoint--每個(gè)頁(yè)面單位為1/72英寸；

Unitinch--每個(gè)頁(yè)面單位為1英寸；UnitDocument--每個(gè)頁(yè)面單位為1/300英寸；UnitMillimeter--每個(gè)頁(yè)面單位為1毫米。例如，或?qū)x_GDIPlusDlg示例中的繪圖代碼修改成：usingnamespaceGdiplus;Graphicsgraphics(dc.m_hDC);graphics.SetPageUnit(UnitMillimeter);PennewPen(Color(255,0,0),3);HatchBrushnewBrush(HatchStyleCross,Color(255,0,255,0),Color(255,0,0,255));graphics.DrawRectangle(&newPen,50,50,100,60);graphics.FillRectangle(&newBrush,50,50,100,60);其結(jié)果如圖所示。則筆畫寬度為3,以及矩形的左上角頂點(diǎn)坐標(biāo)和大小其結(jié)果如圖所示。圖7.4圖7.4將頁(yè)面單位設(shè)置為皇米后的結(jié)果SetPageScale和GetPageScale當(dāng)上面的繪圖代GDI+的這兩個(gè)屬性函數(shù)分別用來(lái)設(shè)置和獲取頁(yè)面的當(dāng)上面的繪圖代碼變成：graphics.SetPageScale((REAL)0.1);PennewPen(Color(255,0,0),3);代碼中，REAL是一個(gè)浮點(diǎn)類型的定義。上述代碼的結(jié)果如圖2所示。TranslateTransformGDI+的TranslateTransform方法用來(lái)改變坐標(biāo)的原點(diǎn)位置，例如TranslateTransform(100,50)是將坐標(biāo)原點(diǎn)移到點(diǎn)(100,50)。畫筆畫筆是用來(lái)繪制各種直線和曲線的一種圖形工具，GDI+的Pen類為畫筆提供了豐富的方法。一般來(lái)說(shuō)，我們可以通過(guò)其構(gòu)造函數(shù)來(lái)指定畫筆的顏色和寬度，其定義如下：Pen(constColor&color,REALwidth);其中，color是用來(lái)指定畫筆顏色，width用來(lái)指定畫筆寬度。REAL是一個(gè)float類型定義，而Color是GDI+的一個(gè)顏色類，它既可以指定一個(gè)ARGB顏色類型，也可以使用GDI+預(yù)定義的顏色值，甚至可以將COLORREF轉(zhuǎn)換成Color類型的顏色。例如，下面的代碼都是創(chuàng)建一個(gè)寬度為3,顏色為藍(lán)色的畫筆：PennewPen(Color(0,0,255),3);//當(dāng)Color只有三個(gè)實(shí)參時(shí)，顏色Alpha分量值為255。PennewPen(Color::Blue,3);COLORREFcrRef=RGB(0,0,255);Colorcolor;color.SetFromCOLORREF(crRef);PennewPen(color,3);除了顏色外，GDI+的Pen類還提供SetDashStyle和SetDashPattern方法來(lái)設(shè)置畫筆的預(yù)定義風(fēng)格和自定義類型。其中，預(yù)定義風(fēng)格可以有：DashStyleSolid(實(shí)線)、DashStyleDash(虛線)、DashStyleDot(點(diǎn)線)、DashStyleDashDot(點(diǎn)劃線)、DashStyleDashDotDot(雙點(diǎn)劃線)和DashStyleCustom(自定義類型)。例如下列代碼，其結(jié)果如圖7.6所示：Graphicsgraphics(pDC->m_hDC);Penpen(Color(255,0,0,255),15);pen.SetDashStyle(DashStyleDash);graphics.DrawLine(&pen,0,50,400,150);pen.SetDashStyle(DashStyleDot);graphics.DrawLine(&pen,0,80,400,180);pen.SetDashStyle(DashStyleDashDot);graphics.DrawLine(&pen,0,110,400,210);但是，在工程應(yīng)用中，預(yù)定義風(fēng)格的畫筆有時(shí)并不能滿足實(shí)際的需求，而必須自己定義一些線型，這需要通過(guò)SetDashPattern函數(shù)來(lái)實(shí)現(xiàn)。SetDashPattern的原型如下:其中，dashArray是一個(gè)包含短劃和間隔長(zhǎng)度的數(shù)組，count表示數(shù)組的大小。注意，dashArray中的短劃長(zhǎng)度和間隔長(zhǎng)度是成對(duì)出現(xiàn)的，例如下列代碼是使用自定義類型的畫筆，其結(jié)果如圖7.7所示。2,//短劃長(zhǎng)為22,//間隔為215,//短劃長(zhǎng)為152);//間隔為2Penpen(Color(255,0,0,0),5);pen.SetDashPattern(dashVals,4);graphics.DrawLine(&pen,5,20,405,200);需要說(shuō)明的是，GDI+的Pen類還提供SetStartCap和SetEndCap方法來(lái)設(shè)置一條直線的起始端和終止端的樣式。例如下面的代碼，其結(jié)果如圖7.8所示。Graphicsgraphics(pDC->m_hDC);Penpen(Color(255,0,0,255),15);pen.SetStartCap(LineCapFlat);pen.SetEndCap(LineCapSquare);graphics.DrawLine(&pen,50,50,250,50);pen.SetStartCap(LineCapRound);pen.SetEndCap(LineCapRoundAnchor);graphics.DrawLine(&pen,50,100,250,100);pen.SetStartCap(LineCapDiamondAnchor);pen.SetEndCap(LineCapArrowAnchor);graphics.DrawLine(&pen,50,150,250,150);畫刷和漸變畫刷用于指定填充的特性，GDI+為填充色和陰影線畫刷提供了SolidBrush和HatchBrush類。通過(guò)它們的構(gòu)造函數(shù)直接可以創(chuàng)建一個(gè)畫刷，其構(gòu)造函數(shù)的原型如下：HatchBrush(HatchStylehatchStyle,constColor&foreColor,constColor&backColor);其中，foreColor和backColor用來(lái)指定陰影線顏色和填充的背景顏色，背景色可以不指定。hatchStyle用來(lái)指定陰影線的樣式，它可以是這樣的一些預(yù)定義樣式：HatchStyleHorizontal（水平線）、HatchStyleVertical（垂直線）、HatchStyleForwardDiagonal（上斜線）、HatchStyleBackwardDiagonal（下斜線）、HatchStyleCross（十字線）以及HatchStyleDiagonalCross（交叉線）等。當(dāng)然，還有許多樣式如HatchStyle30Percent（30%填充）、HatchStyleSolidDiamond（實(shí)心菱形）等，這里不一一列舉。由于在前面的示例中，對(duì)這種簡(jiǎn)單的畫刷的使用已介紹過(guò)，因而這里著重討論漸變畫刷的創(chuàng)建和使用。GDI+提供了LinearGradientBrush和PathGradientBrush類分別用來(lái)創(chuàng)建一^直線漸變和路徑漸變畫刷。直線漸變是指在一個(gè)矩形區(qū)域使用兩種顏色進(jìn)行過(guò)渡（漸變），過(guò)渡方向可以是水平、垂直以及對(duì)角線方向。LinearGradientBrush構(gòu)造函數(shù)的原型如下：Color&colorl,Color&color2）;LinearGradientBrush（Rect&rect,Color&colorl,Color&color2,REALangle,BOOLisAngleScalable）;LinearGradientBrush（Rect&rect,Color&color1,Color&color2,LinearGradientModemode）;其中，point1和point2分別用來(lái)指定矩形區(qū)域的左上角和右下角點(diǎn)坐標(biāo)，color1和color2分別用來(lái)指定漸變起始和終止的顏色°rect用來(lái)指定一個(gè)矩形區(qū)域的大小和位置，angle用來(lái)指定漸變的方向角度，正值為順時(shí)針。isAngleScalable是一個(gè)即將廢除的參數(shù)。mode用來(lái)指定漸變的方法，它可以是LinearGradientModeHorizontal（水平方向）、LinearGradientModeVertical（垂直方向）、LinearGradientModeForwardDiagonal（從左下到右上的對(duì)角線方向）和LinearGradientModeBackwardDiagonal（從左上到右下的對(duì)角線方向）。需要說(shuō)明的是，Point和Rect是GDI+新的數(shù)據(jù)類型，它們和MFC的CPoint和CRect類的功能基本一樣，但它們相互之間不能混用。路徑漸變畫刷是用漸變顏色來(lái)填充一個(gè)封閉的路徑。一個(gè)路徑既可以由一系列的直線和曲線構(gòu)成，也可以由其它對(duì)象來(lái)構(gòu)造。路徑漸變是一種中心顏色漸變模式，它從路徑的中心點(diǎn)向四周進(jìn)行顏色漸變。PathGradientBrush構(gòu)造函數(shù)的原型如下：PathGradientBrush(constPoint*points,INTcount,WrapModewrapMode);其中，path用來(lái)指定一個(gè)路徑指針，points和count分別用來(lái)指定組成路徑的一系列直線端點(diǎn)的數(shù)組及其大小，wrapMode是一個(gè)可選項(xiàng)，用來(lái)指定填充的包圍模式。一個(gè)包圍模式用來(lái)決定是否在區(qū)域內(nèi)部、在區(qū)域外部以及所有區(qū)域都填充。默認(rèn)時(shí)，其值為WrapModeClamp，即在區(qū)域內(nèi)部填充。下面的代碼說(shuō)明了上述兩種漸變畫刷的使用方法：m_hDC);GraphicsPathpath;//構(gòu)造一個(gè)路徑path.AddEllipse(50,50,200,100);//使用路徑構(gòu)造一個(gè)畫刷PathGradientBrushpthGrBrush(&path);//將路徑中心顏色設(shè)為藍(lán)色pthGrBrush.SetCenterColor(Color(255,0,0,255));//設(shè)置路徑周圍的顏色為藍(lán)芭，但alpha值為0Colorcolors[]={Color(0,0,0,255));INTcount=1;pthGrBrush.SetSurroundColors(colors,&count);graphics.FillRectangle(&pthGrBrush,50,50,200,100);LinearGradientBrushlinGrBrush(Point(300,50),Point(500,150),Color(255,255,0,0),//紅色Color(255,0,0,255));//藍(lán)色graphics.FillRectangle(&linGrBrush,300,50,200,100);結(jié)果如圖7.9所示。需要說(shuō)明的是，畫筆和畫刷還可使用一個(gè)圖片來(lái)創(chuàng)建。例如下列代碼，其結(jié)果如圖7.10所示。m_hDC);Imageimage(Limagejpg);TextureBrushtBrush(&image);PentexturedPen(&tBrush,10);graphics.DrawLine(&texturedPen,25,25,325,25);tBrush.SetWrapMode(WrapModeTileFlipXY);graphics.FillRectangle(&tBrush,25,100,300,200);

圖形幾何變換圖形變換一般是對(duì)圖形的幾何信息經(jīng)過(guò)幾何變換后產(chǎn)生新的圖形。常見(jiàn)二維圖形的變換有平移、比例、對(duì)稱、旋轉(zhuǎn)、錯(cuò)切等。圖形幾何變換最有效的手段是采用矩陣變換，GDI+就有這樣的矩陣類Matrix，它為我們提供了許多變換的方法，如Invert（轉(zhuǎn)置）、Multiply（矩陣相乘）、Rotate（旋轉(zhuǎn)）等。例如下面的代碼就是Matrix::Rotate一個(gè)例子，其結(jié)果如圖7.11所示。m_hDC);Penpen(Color(255,0,0,255));Matrixmatrix;matrix.Translate(40,0);//先平移matrix.Rotate(30,MatrixOrderAppend);//后旋轉(zhuǎn)graphics.SetTransform(&matrix);graphics.DrawEllipse(&pen,0,0,100,50);需要說(shuō)明的是，代碼中的MatrixOrderAppend用來(lái)指明第二個(gè)矩陣(若有)的操作次序是后置的，即matrixlOPmatrix2,OP表示某種操作；若為MatrixOrderPrepend則表示matrix2OPmatrixl。而SetTransform則指定一個(gè)矩陣對(duì)點(diǎn)坐標(biāo)進(jìn)行變換，新的坐標(biāo)點(diǎn)(x*,y*)結(jié)果可用下列公式來(lái)表示：廠mumi2口、m22 0[x*y*1]=[xy1]l血w1J=[m11x+m21y+dxm12x+m22y+dy1]式中，dx和dy用來(lái)指定x和y方向的平移量，若dx=dy=0,則：當(dāng)m21=m12=0，m11=-1，m22=1時(shí)，有x*=-x，y*=y，產(chǎn)生與y軸對(duì)稱的反射圖形；當(dāng)m21=m12=0，m11=1，m22=-1時(shí)有x*=x，y*=-y，產(chǎn)生與x軸對(duì)稱的反射圖形；當(dāng)m21=m12=0，m11=m22=-1時(shí)有x*=-x，y*=-y，產(chǎn)生與原點(diǎn)對(duì)稱的反射圖形；當(dāng)m21=m12=1，m11=m22=0時(shí)有x*=y，y*=x，產(chǎn)生與直線y=x對(duì)稱的反射圖形；當(dāng)m21=m12=-1，m11=m22=0時(shí)有x*=-y，y*=-x，產(chǎn)生與直線y=-x對(duì)稱的反射圖形；而當(dāng)m11=m22=cosq，m21=-m12=sinq時(shí)則進(jìn)行旋轉(zhuǎn)變換。例如下列代碼，其結(jié)果如圖7.12所示。m_hDC);Penpen(Color::Blue,3);graphics.DrawLine(&pen,150,50,200,80);pen.SetColor(Color::Gray);Matrixmatrix(-1,0,0,1,150,50);//使用第一種情況graphics.SetTransform(&matrix);graphics.DrawLine(&pen,0,0,50,30);其中，Matrix的構(gòu)造函數(shù)有如下定義:需要說(shuō)明的是，除了使用Matrix進(jìn)行圖形變換外，Graphics本身提供相應(yīng)的變換方法，如RotateTransform（旋轉(zhuǎn)變換）、ScaleTransform（比例變換）和TranslateTransform（平移變換）等。基本繪圖函數(shù)在前面許多示例中，我們已經(jīng)用到如DrawLine等基本繪圖函數(shù)。除此之外，還有許多這樣的函數(shù)，并且每個(gè)繪圖函數(shù)都有其重載形式，這給我們帶來(lái)了許多方便。表7.1列出這些基本繪圖函數(shù)。表1GDI+常用基本繪圖函數(shù)

繪圖函數(shù)功能描述DrawArc繪制一條圓弧曲線，范圍由起止角大小決定，大小由矩形或長(zhǎng)寬值指定DrawBezier繪制一條由一系列型值頂點(diǎn)決定的三次Bezier曲線DrawBeziers繪制一系列的三次Bezier曲線DrawClosedCurve繪制一條封閉的樣條曲線DrawCurve繪制一條樣條曲線DrawEllipse繪制一條橢圓輪廓線，大小由矩形或長(zhǎng)寬值指定DrawLine繪制一條直線DrawPath繪制由GraphicsPath定義的路徑輪廓線DrawPie繪制一條扇形（餅形）輪廓線DrawPolygon繪制一個(gè)多邊形的輪廓線DrawRectangle繪制一個(gè)矩形FillEllipse填充一^橢圓區(qū)域FillPath填充一個(gè)由路徑指定的區(qū)域FillPie填充一個(gè)扇形（餅形）區(qū)域FillPolygon填充一個(gè)多邊形區(qū)域FillRectangle填充一個(gè)矩形區(qū)域FillRectangles用同一個(gè)畫刷填充一系列矩形區(qū)域FillRegion填充—區(qū)域（Region）的內(nèi)部下面的代碼是通過(guò)路徑用兩條樣條曲線構(gòu)造一個(gè)復(fù)雜的區(qū)域，然后填充它，其結(jié)果如圖7.13所示。m_hDC);Penpen(Color::Blue,3);Pointpoint1(50,200);Pointpoint2(100,150);Pointpoint3(160,180);Pointpoint4(200,200);Pointpoint5(230,150);Pointpoint6(220,50);Pointpoint7(190,70);Pointpoint8(130,220);PointcurvePoints[8]={pointl,point2,point3,point4,point5,point6,point7,point8);Point*pcurvePoints=curvePoints;GraphicsPathpath;path.AddClosedCurve(curvePoints,8,0.5);PathGradientBrushpthGrBrush(&path);pthGrBrush.SetCenterColor(Color(255,0,0,255));Colorcolors[]={Color(0,0,0,255));INTcount=1;pthGrBrush.SetSurroundColors(colors,&count);graphics.DrawClosedCurve(&pen,curvePoints,8,0.5);graphics.FillPath(&pthGrBrush,&path);幾何算法矢量減法設(shè)二維矢量P=(x1,y1),Q=(x2,y2)則矢量減法定義為：P-Q=(x1-x2,y1-y2)顯然有性質(zhì)P-Q=-(Q-P)如不加說(shuō)明，下面所有的點(diǎn)都看作矢量，兩點(diǎn)的減法就是矢量相減；矢量叉積設(shè)矢量P=(x1,y1)，Q=(x2,y2)則矢量叉積定義為：PxQ=x1*y2-x2*y1 得到的是一個(gè)標(biāo)量顯然有性質(zhì)PxQ=-(QxP)Px(-Q)=-(PxQ)如不加說(shuō)明，下面所有的點(diǎn)都看作矢量，點(diǎn)的乘法看作矢量叉積；叉乘的重要性質(zhì)：>若PxQ>0,則P在Q的順時(shí)針?lè)较?gt;若PxQ<0,則P在Q的逆時(shí)針?lè)较?gt;若PxQ=0,則P與Q共線，但可能同向也可能反向判斷點(diǎn)在線段上設(shè)點(diǎn)為Q，線段為P1P2，判斷點(diǎn)Q在該線段上的依據(jù)是：(Q-P1)x(P2-P1)=0且Q在以P1，P2為對(duì)角頂點(diǎn)的矩形內(nèi)判斷兩線段是否相交我們分兩步確定兩條線段是否相交：. 快速排斥試驗(yàn)設(shè)以線段P1P2為對(duì)角線的矩形為R，設(shè)以線段Q1Q2為對(duì)角線的矩形為T，如果R和T不相交，顯然兩線段不會(huì)相交；, 跨立試驗(yàn)如果兩線段相交，則兩線段必然相互跨立對(duì)方，如圖1所示。在圖1中，P1P2跨立Q1Q2，則矢量(P1-Q1)和(P2-Q1)位于矢量(Q2-Q1)的兩側(cè)，即(P1-Q1)x(Q2-Q1)*(P2-Q1)x(Q2-Q1)<0上式可改寫成(P1-Q1)x(Q2-Q1)*(Q2-Q1)x(P2-Q1)>0當(dāng)(P1-Q1)x(Q2-Q1)=0時(shí)，說(shuō)明(P1-Q1)和(Q2-Q1)共線，但是因?yàn)橐呀?jīng)通過(guò)快速排斥試驗(yàn)，所以P1一定在線段Q1Q2上；同理，(Q2-Q1)x(P2-Q1)=0說(shuō)明P2一定在線段Q1Q2上。所以判斷P1P2跨立Q1Q2的依據(jù)是：(P1-Q1)x(Q2-Q1)*(Q2-Q1)x(P2-Q1)>0同理判斷Q1Q2跨立P1P2的依據(jù)是：(Q1-P1)x(P2-P1)*(P2-P1)x(Q2-P1)>0至此已經(jīng)完全解決判斷線段是否相交的問(wèn)題。判斷線段和直線是否相交如果線段P1P2和直線Q1Q2相交，則P1P2跨立Q1Q2，即：(P1-Q1)x(Q2-Q1)*(Q2-Q1)x(P2-Q1)>0判斷矩形是否包含點(diǎn)只要判斷該點(diǎn)的橫坐標(biāo)和縱坐標(biāo)是否夾在矩形的左右邊和上下邊之間。判斷線段、折線、多邊形是否在矩形中因?yàn)榫匦问莻€(gè)凸集，所以只要判斷所有端點(diǎn)是否都在矩形中就可以了。判斷矩形是否在矩形中只要比較左右邊界和上下邊界就可以了。判斷圓是否在矩形中圓在矩形中的充要條件是：圓心在矩形中且圓的半徑小于等于圓心到矩形四邊的距離的最小值。判斷點(diǎn)是否在多邊形中以點(diǎn)P為端點(diǎn)，向左方作射線L,由于多邊形是有界的，所以射線L的左端一定在多邊形外，考慮沿著L從無(wú)窮遠(yuǎn)處開(kāi)始自左向右移動(dòng)，遇到和多邊形的第一個(gè)交點(diǎn)的時(shí)候，進(jìn)入到了多邊形的內(nèi)部，遇到第二個(gè)交點(diǎn)的時(shí)候，離開(kāi)了多邊形，……所以很容易看出當(dāng)L和多邊形的交點(diǎn)數(shù)目C是奇數(shù)的時(shí)候，P在多邊形內(nèi)，是偶數(shù)的話P在多邊形外。但是有些特殊情況要加以考慮。如果L和多邊形的頂點(diǎn)相交，有些情況下交點(diǎn)只能計(jì)算一個(gè)，有些情況下交點(diǎn)不應(yīng)被計(jì)算（自己畫個(gè)圖就明白了）；如果L和多邊形的一條邊重合，這條邊應(yīng)該被忽略不計(jì)。為了統(tǒng)一起見(jiàn)，我們?cè)谟?jì)算射線L和多邊形的交點(diǎn)的時(shí)候，1。對(duì)于多邊形的水平邊不作考慮；2。對(duì)于多邊形的頂點(diǎn)和L相交的情況，如果該頂點(diǎn)是其所屬的邊上縱坐標(biāo)較大的頂點(diǎn)，則計(jì)數(shù)，否則忽略；3。對(duì)于P在多邊形邊上的情形，直接可判斷P屬于多邊行。由此得出算法的偽代碼如下：count—0；以P為端點(diǎn)，作從右向左的射線L；fOr多邊形的每條邊sdoifP在邊s上thenreturntrue；ifs不是水平的thenifs的一個(gè)端點(diǎn)在L上且該端點(diǎn)是s兩端點(diǎn)中縱坐標(biāo)較大的端點(diǎn)thencount—count+1elseifs和L相交thencount—count+1;ifcountmod2=1thenreturntrueelsereturnfalse；其中做射線L的方法是：設(shè)P'的縱坐標(biāo)和P相同，橫坐標(biāo)為正無(wú)窮大（很大的一個(gè)正數(shù)），則P和P'就確定了射線L。這個(gè)算法的復(fù)雜度為O（n）。判斷線段是否在多邊形內(nèi)線段在多邊形內(nèi)的一個(gè)必要條件是線段的兩個(gè)端點(diǎn)都在多邊形內(nèi)；如果線段和多邊形的某條邊內(nèi)交（兩線段內(nèi)交是指兩線段相交且交點(diǎn)不在兩線段的端點(diǎn)），因?yàn)槎噙呅蔚倪叺淖笥覂蓚?cè)分屬多邊形內(nèi)外不同部分，所以線段一定會(huì)有一部分在多邊形外。于是我們得到線段在多邊形內(nèi)的第二個(gè)必要條件：線段和多邊形的所有邊都不內(nèi)交；線段和多邊形交于線段的兩端點(diǎn)并不會(huì)影響線段是否在多邊形內(nèi)；但是如果多邊形的某個(gè)頂點(diǎn)和線段相交，還必須判斷兩相鄰交點(diǎn)之間的線段是否包含與多邊形內(nèi)部。因此我們可以先求出所有和線段相交的多邊形的頂點(diǎn)，然后按照X-Y坐標(biāo)排序，這樣相鄰的兩個(gè)點(diǎn)就是在線段上相鄰的兩交點(diǎn)，如果任意相鄰兩點(diǎn)的中點(diǎn)也在多邊形內(nèi)，則該線段一定在多邊形內(nèi)。證明如下：命題1：如果線段和多邊形的兩相鄰交點(diǎn)P1，P2的中點(diǎn)P'也在多邊形內(nèi)，則P1,P2之間的所有點(diǎn)都在多邊形內(nèi)。證明：假設(shè)P1,P2之間含有不在多邊形內(nèi)的點(diǎn)，不妨設(shè)該點(diǎn)為Q，在P1,P'之間，因?yàn)槎噙呅问情]合曲線，所以其內(nèi)外部之間有界，而P1屬于多邊行內(nèi)部，Q屬于多邊性外部，P'屬于多邊性內(nèi)部，P1-Q-P完全連續(xù)，所以P1Q和QP'一定跨越多邊形的邊界，因此在P1,P'之間至少還有兩個(gè)該線段和多邊形的交點(diǎn)，這和P1P2是相鄰兩交點(diǎn)矛盾，故命題成立。證畢由命題1直接可得出推論：推論2:設(shè)多邊形和線段PQ的交點(diǎn)依次為P1,P2,Pn，其中Pi和Pi+1是相鄰兩交點(diǎn)，線段PQ在多邊形內(nèi)的充要條件是：P，Q在多邊形內(nèi)且對(duì)于i=1,2,,n-1，Pi,Pi+1的中點(diǎn)也在多邊形內(nèi)。在實(shí)際編程中，沒(méi)有必要計(jì)算所有的交點(diǎn)，首先應(yīng)判斷線段和多邊形的邊是否內(nèi)交，倘若線段和多邊形的某條邊內(nèi)交則線段一定在多邊形外；如果線段和多邊形的每一條邊都不內(nèi)交，則線段和多邊形的交點(diǎn)一定是線段的端點(diǎn)或者多邊形的頂點(diǎn)，只要判斷點(diǎn)是否在線段上就可以了。至此我們得出算法如下：if線端PQ的端點(diǎn)不都在多邊形內(nèi)thenreturnfalse；點(diǎn)集pointSet初始化為空；for多邊形的每條邊sdoif線段的某個(gè)端點(diǎn)在s上then將該端點(diǎn)加入pointSet;elseifs的某個(gè)端點(diǎn)在線段PQ上then將該端點(diǎn)加入pointSet;elseifs和線段PQ相交 //這時(shí)候可以肯定是內(nèi)交thenreturnfalse;將pointSet中的點(diǎn)按照X-Y坐標(biāo)排序，X坐標(biāo)小的排在前面，對(duì)于X坐標(biāo)相同的點(diǎn)，Y坐標(biāo)小的排在前面；forpointSet中每?jī)蓚€(gè)相鄰點(diǎn)pointSet[i],pointSet[i+1]doifpointSet[i],pointSet[i+1]的中點(diǎn)不在多邊形中thenreturnfalse;returntrue;這個(gè)算法的復(fù)雜度也是O(n)。其中的排序因?yàn)榻稽c(diǎn)數(shù)目肯定遠(yuǎn)小于多邊形的頂點(diǎn)數(shù)目n，所以最多是常數(shù)級(jí)的復(fù)雜度，幾乎可以忽略不計(jì)。判斷折線在多邊形內(nèi)只要判斷折線的每條線段是否都在多邊形內(nèi)即可。設(shè)折線有m條線段，多邊形有n個(gè)頂點(diǎn)，則復(fù)雜度為O(m*n)。判斷多邊形是否在多邊形內(nèi)只要判斷多邊形的每條邊是否都在多邊形內(nèi)即可。判斷一個(gè)有m個(gè)頂點(diǎn)的多邊形是否在一個(gè)有n個(gè)頂點(diǎn)的多邊形內(nèi)復(fù)雜度為O(m*n)。判斷矩形是否在多邊形內(nèi)將矩形轉(zhuǎn)化為多邊形，然后再判斷是否在多邊形內(nèi)。判斷圓是否在多邊形內(nèi)只要計(jì)算圓心到多邊形的每條邊的最短距離，如果該距離大于等于圓半徑則該圓在多邊形內(nèi)。計(jì)算圓心到多邊形每條邊最短距離的算法在后文闡述。判斷點(diǎn)是否在圓內(nèi)計(jì)算圓心到該點(diǎn)的距離，如果小于等于半徑則該點(diǎn)在圓內(nèi)。判斷線段、折線、矩形、多邊形是否在圓內(nèi)因?yàn)閳A是凸集，所以只要判斷是否每個(gè)頂點(diǎn)都在圓內(nèi)即可。判斷圓是否在圓內(nèi)設(shè)兩圓為01,02，半徑分別為r1,r2,要判斷02是否在01內(nèi)。先比較r1，r2的大小，如果r1<r2則02不可能在01內(nèi)；否則如果兩圓心的距離大于r1-r2，則02不在01內(nèi)；否則02在01內(nèi)。計(jì)算點(diǎn)到線段的最近點(diǎn)如果該線段平行于X軸（Y軸），則過(guò)點(diǎn)point作該線段所在直線的垂線，垂足很容易求得，然后計(jì)算出垂足，如果垂足在線段上則返回垂足，否則返回離垂足近的端如果該線段不平行于X軸也不平行于Y軸，則斜率存在且不為0。設(shè)線段的兩端點(diǎn)為pt1和pt2，斜率為：k=(pt2.y-pt1.y)/(pt2.x-pt1.x)；該直線方程為：y=k*(x-pt1.x)+pt1.y其垂線的斜率為-1/k，垂線方程為：y=(-1/k)*(x-point.x)+point.y聯(lián)立兩直線方程解得：x=(kA2*pt1.x+k*(point.y-pt1.y)+point.x)/(kA2+1)y=k*(x-pt1.x)+pt1.y；然后再判斷垂足是否在線段上，如果在線段上則返回垂足；如果不在則計(jì)算兩端點(diǎn)到垂足的距離，選擇距離垂足較近的端點(diǎn)返回。計(jì)算點(diǎn)到折線、矩形、多邊形的最近點(diǎn)只要分別計(jì)算點(diǎn)到每條線段的最近點(diǎn)，記錄最近距離，取其中最近距離最小的點(diǎn)即可。計(jì)算點(diǎn)到圓的最近距離如果該點(diǎn)在圓心，則返回UNDEFINED連接點(diǎn)P和圓心0，如果PO平行于X軸，則根據(jù)P在O的左邊還是右邊計(jì)算出最近點(diǎn)的橫坐標(biāo)為centerPoint.x-radius或centerPoint.x+radius，如圖4(a)所示；如果PO平行于Y軸，則根據(jù)P在O的上邊還是下邊計(jì)算出最近點(diǎn)的縱坐標(biāo)為centerPoint.y+radius或centerPoint.y-radius，如圖4(b)所示。如果PO不平行于X軸和Y軸，則PO的斜率存在且不為0，如圖4(c)所示。這時(shí)直線PO斜率為k=(P.y-O.y)/(P.x-O.x)直線PO的方程為：y=k*(x-P.x)+P.y設(shè)圓方程為：(x-O.x)A2+(y-O.y)A2=rA2，聯(lián)立兩方程組可以解出直線PO和圓的交點(diǎn)，取其中離P點(diǎn)較近的交點(diǎn)即可。計(jì)算兩條共線的線段的交點(diǎn)對(duì)于兩條共線的線段，它們之間的位置關(guān)系有圖5所示的幾種情況。圖5(a)中兩條線段沒(méi)有交點(diǎn)；圖5(b)和(d)中兩條線段有無(wú)窮焦點(diǎn)；圖5(c)中兩條線段有一個(gè)交點(diǎn)。設(shè)linel是兩條線段中較長(zhǎng)的一條，line2是較短的一條，如果linel包含了line2的兩個(gè)端點(diǎn)，則是圖5(d)的情況，兩線