因此我們可以先求出所有和線段相交的多邊形的頂點，然后按照X-Y坐標排序(X坐標小的排在前面，對于X坐標相同的點，Y坐標小的排在前面，這種排序準則也是為了保證水平和垂直情況的判斷正確)，這樣相鄰的兩個點就是在線段上相鄰的兩交點，如果任意相鄰兩點的中點也在多邊形內(nèi)，則該線段一定在多邊形內(nèi)。

　　證明如下：

　　命題1：

　　如果線段和多邊形的兩相鄰交點P1 ，P2的中點P' 也在多邊形內(nèi)，則P1, P2之間的所有點都在多邊形內(nèi)。

　　證明：

　　假設(shè)P1,P2之間含有不在多邊形內(nèi)的點，不妨設(shè)該點為Q，在P1, P'之間，因為多邊形是閉合曲線，所以其內(nèi)外部之間有界，而P1屬于多邊行內(nèi)部，Q屬于多邊性外部，P'屬于多邊性內(nèi)部，P1-Q-P'完全連續(xù)，所以P1Q和QP'一定跨越多邊形的邊界，因此在P1,P'之間至少還有兩個該線段和多邊形的交點，這和P1P2是相鄰兩交點矛盾，故命題成立。證畢。

　　由命題1直接可得出推論：

　　推論2：

　　設(shè)多邊形和線段PQ的交點依次為P1,P2,……Pn，其中Pi和Pi+1是相鄰兩交點，線段PQ在多邊形內(nèi)的充要條件是：P，Q在多邊形內(nèi)且對于i =1, 2,……, n-1，Pi ,Pi+1的中點也在多邊形內(nèi)。

　　在實際編程中，沒有必要計算所有的交點，首先應(yīng)判斷線段和多邊形的邊是否內(nèi)交，倘若線段和多邊形的某條邊內(nèi)交則線段一定在多邊形外；如果線段和多邊形的每一條邊都不內(nèi)交，則線段和多邊形的交點一定是線段的端點或者多邊形的頂點，只要判斷點是否在線段上就可以了。

　　至此我們得出算法如下：

　　if 線端PQ的端點不都在多邊形內(nèi)
　　then return false;
　　點集pointSet初始化為空;
　　for 多邊形的每條邊s
　　do if 線段的某個端點在s上
　　then 將該端點加入pointSet;
　　else if s的某個端點在線段PQ上
　　then 將該端點加入pointSet;
　　else if s和線段PQ相交 // 這時候已經(jīng)可以肯定是內(nèi)交了
　　then return false;
　　將pointSet中的點按照X-Y坐標排序;
　　for pointSet中每兩個相鄰點 pointSet[i] , pointSet[ i+1]
　　do if pointSet[i] , pointSet[ i+1] 的中點不在多邊形中
　　then return false;
　　return true;

　　這個過程中的排序因為交點數(shù)目肯定遠小于多邊形的頂點數(shù)目n，所以最多是常數(shù)級的復(fù)雜度，幾乎可以忽略不計。因此算法的時間復(fù)雜度也是O(n)。

判斷折線是否在多邊形內(nèi)：

　　只要判斷折線的每條線段是否都在多邊形內(nèi)即可。設(shè)折線有m條線段，多邊形有n個頂點，則該算法的時間復(fù)雜度為O(m*n)。

　判斷多邊形是否在多邊形內(nèi)：

　　只要判斷多邊形的每條邊是否都在多邊形內(nèi)即可。判斷一個有m個頂點的多邊形是否在一個有n個頂點的多邊形內(nèi)復(fù)雜度為O(m*n)。

　　判斷矩形是否在多邊形內(nèi)：

將矩形轉(zhuǎn)化為多邊形，然后再判斷是否在多邊形內(nèi)。

判斷圓是否在多邊形內(nèi)：

　　只要計算圓心到多邊形的每條邊的最短距離，如果該距離大于等于圓半徑則該圓在多邊形內(nèi)。計算圓心到多邊形每條邊最短距離的算法在后文闡述。

判斷點是否在圓內(nèi)：

計算圓心到該點的距離，如果小于等于半徑則該點在圓內(nèi)。

判斷線段、折線、矩形、多邊形是否在圓內(nèi):

因為圓是凸集，所以只要判斷是否每個頂點都在圓內(nèi)即可。

判斷圓是否在圓內(nèi)：

　設(shè)兩圓為O1,O2，半徑分別為r1, r2，要判斷O2是否在O1內(nèi)。先比較r1，r2的大小，如果r1<r2則O2不可能在O1內(nèi)；否則如果兩圓心的距離大于r1 - r2 ，則O2不在O1內(nèi)；否則O2在O1內(nèi)。

計算點到線段的最近點：

　　如果該線段平行于X軸（Y軸），則過點point作該線段所在直線的垂線，垂足很容易求得，然后計算出垂足，如果垂足在線段上則返回垂足，否則返回離垂足近的端點；如果該線段不平行于X軸也不平行于Y軸，則斜率存在且不為0。設(shè)線段的兩端點為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 = ( k^2 * pt1.x + k * (point.y - pt1.y ) + point.x ) / ( k^2 + 1) ，y = k * ( x - pt1.x) + pt1.y;然后再判斷垂足是否在線段上，如果在線段上則返回垂足；如果不在則計算兩端點到垂足的距離，選擇距離垂足較近的端點返回。

計算點到折線、矩形、多邊形的最近點：

只要分別計算點到每條線段的最近點，記錄最近距離，取其中最近距離最小的點即可。

計算點到圓的最近距離及交點坐標：

　　如果該點在圓心，因為圓心到圓周任一點的距離相等，返回UNDEFINED。

　　連接點P和圓心O，如果PO平行于X軸，則根據(jù)P在O的左邊還是右邊計算出最近點的橫坐標為centerPoint.x - radius 或 centerPoint.x + radius。如果PO平行于Y軸，則根據(jù)P在O的上邊還是下邊計算出最近點的縱坐標為 centerPoint.y -+radius或 centerPoint.y - radius。如果PO不平行于X軸和Y軸，則PO的斜率存在且不為0，這時直線PO斜率為k = （ P.y - O.y ）/ ( P.x - O.x )。直線PO的方程為：y = k * ( x - P.x) + P.y。設(shè)圓方程為:(x - O.x ) ^2 + ( y - O.y ) ^2 = r ^2，聯(lián)立兩方程組可以解出直線PO和圓的交點，取其中離P點較近的交點即可。

計算兩條共線的線段的交點：

　　對于兩條共線的線段，它們之間的位置關(guān)系有下圖所示的幾種情況。圖(a)中兩條線段沒有交點；圖 (b) 和 (d) 中兩條線段有無窮焦點；圖 (c) 中兩條線段有一個交點。設(shè)line1是兩條線段中較長的一條，line2是較短的一條，如果line1包含了line2的兩個端點，則是圖(d)的情況，兩線段有無窮交點；如果line1只包含line2的一個端點，那么如果line1的某個端點等于被line1包含的line2的那個端點，則是圖(c)的情況，這時兩線段只有一個交點，否則就是圖(b)的情況，兩線段也是有無窮的交點；如果line1不包含line2的任何端點，則是圖(a)的情況，這時兩線段沒有交點。