第一講 算法基礎(chǔ)及計(jì)算幾何

GIS算法基礎(chǔ)

AlgorithmofGIS第一講

算法基礎(chǔ)及計(jì)算幾何課程介紹——任務(wù)本門(mén)課任務(wù)：對(duì)GIS基礎(chǔ)軟件、應(yīng)用軟件以及GIS應(yīng)用過(guò)程中的基本算法以及其應(yīng)用做一個(gè)較為全面的介紹和分析。2課程介紹——算法算法的起源與發(fā)展：起源于9世紀(jì)，波斯數(shù)學(xué)家比阿勒.霍瓦里松的著作《代數(shù)對(duì)話錄》；20世紀(jì)，英國(guó)數(shù)學(xué)家圖靈提出圖靈論；算法概念：指的是完成一個(gè)任務(wù)所需要的具體步驟和方法。3課程介紹——算法計(jì)算機(jī)程序本質(zhì)上是算法。輸入算法輸出4油鹽醬醋等調(diào)料課程介紹——算法GIS算法特點(diǎn)：①GIS算法用來(lái)解決地學(xué)領(lǐng)域中的問(wèn)題，但是算法不是孤立的，GIS的算法借鑒和發(fā)展了其他學(xué)科的研究成果；②GIS算法是用來(lái)處理海量地理信息數(shù)據(jù)的，涉及許多復(fù)雜的空間運(yùn)算，不同于簡(jiǎn)單的數(shù)據(jù)查詢、編輯等操作；③地理信息系統(tǒng)與實(shí)際應(yīng)用、工程開(kāi)發(fā)有著密切的關(guān)系，與一般算法的重要區(qū)別在于所要處理問(wèn)題的不確定性，無(wú)法被定性、定量成一個(gè)純算法問(wèn)題。5課程介紹——與其他學(xué)科間的關(guān)系GIS與各類(lèi)學(xué)科都有密切的聯(lián)系GIS算法與地理科學(xué)、計(jì)算機(jī)科學(xué)、數(shù)學(xué)等都有千絲萬(wàn)縷的聯(lián)系GIS的許多算法都是從計(jì)算幾何、計(jì)算機(jī)圖形學(xué)、離散數(shù)學(xué)演化而來(lái)的6課程介紹——算法在GIS中的地位GIS算法是整個(gè)地理信息科學(xué)的核心基本的GIS空間數(shù)據(jù)結(jié)構(gòu)、各種各樣的空間拓?fù)潢P(guān)系必需的GIS空間關(guān)系的表達(dá)與描述到各種各樣的空間拓?fù)潢P(guān)系從高級(jí)的時(shí)態(tài)多維GIS到GIS空間數(shù)據(jù)挖掘與知識(shí)發(fā)現(xiàn)GIS算法都是地理信息系統(tǒng)的基石。72算法設(shè)計(jì)與分析2.1概述2.2算法設(shè)計(jì)原則2.3算法復(fù)雜性度量2.4最優(yōu)算法2.5算法的評(píng)價(jià)82.1概述算法是解決問(wèn)題精確方法的描述。待解決問(wèn)題的描述：

應(yīng)該準(zhǔn)確、簡(jiǎn)練、清楚，可以使用形式化的模型來(lái)刻畫(huà)問(wèn)題。使用數(shù)學(xué)模型刻畫(huà)問(wèn)題是比較簡(jiǎn)明、嚴(yán)格的，一旦問(wèn)題形式化，就可以依據(jù)嚴(yán)格的模型對(duì)問(wèn)題求解。92.1概述算法設(shè)計(jì)

算法設(shè)計(jì)的任務(wù)是對(duì)各類(lèi)具體問(wèn)題設(shè)計(jì)良好的算法以及研究設(shè)計(jì)算法的規(guī)律和方法。常用的算法有窮舉搜索法、遞歸法、回溯法、貪心法、分治法等。

算法分析

算法分析的任務(wù)是對(duì)設(shè)計(jì)出的每一個(gè)具體的算法，利用數(shù)學(xué)工具，討論各種復(fù)雜度，以探討某種具體算法適用于哪類(lèi)問(wèn)題，或某類(lèi)問(wèn)題宜采用哪些解法。

102.2算法設(shè)計(jì)原則正確性：算法的正確性是指算法能否正確的解決一個(gè)問(wèn)題。如果一個(gè)算法自身有缺陷或者算法不適用于該問(wèn)題，那么算法將不會(huì)解決問(wèn)題；確定性：算法的確定性是指算法的每個(gè)步驟必須含義明確，對(duì)于每種可能的情況，算法都可能給出確定的操作。采用同一種算法，在同樣的條件下無(wú)論計(jì)算多少次，始終能得到確定的結(jié)果。清晰性：算法的設(shè)計(jì)要模塊化。每個(gè)模塊都可以獨(dú)立地編寫(xiě)、測(cè)試，最后組裝完成整個(gè)算法。使算法結(jié)構(gòu)清晰，簡(jiǎn)單易讀，容易理解、測(cè)試和修改。112.3算法復(fù)雜性度量問(wèn)題的規(guī)模：用一個(gè)與問(wèn)題相關(guān)的整數(shù)量來(lái)衡量問(wèn)題的大小，這個(gè)整數(shù)量表示輸入數(shù)據(jù)量的尺度。時(shí)間復(fù)雜性：利用某算法處理一個(gè)問(wèn)題規(guī)模為n的輸入所需要的時(shí)間，是n的函數(shù)，記為T(mén)(n)?？臻g復(fù)雜性：利用某算法處理一個(gè)問(wèn)題規(guī)模為n的輸入所需要的存儲(chǔ)空間，是n的函數(shù)，記為S(n)。122.3算法復(fù)雜性度量——時(shí)間復(fù)雜性階的增長(zhǎng)O符號(hào)Ω符號(hào)Θ符號(hào)復(fù)雜性類(lèi)與o符號(hào)13時(shí)間復(fù)雜性——階的增長(zhǎng)觀察下面幾個(gè)算法（函數(shù)）：算法A：如果可以找到某個(gè)常量c>0，以大小為n的輸入時(shí)，算法的運(yùn)行時(shí)間至多為cn2

；算法B：不同階的函數(shù)（例如dn3）A與B作比較，常量并不起多大的作用函數(shù)f(n)=n2logn+10n2+n，n越大低階項(xiàng)影響越小。算法A和B的運(yùn)行時(shí)間分別為n2階和n3階的。函數(shù)f(n)為n2logn階的。14隨著n越來(lái)越大，c將逐漸不起作用時(shí)間復(fù)雜性——階的增長(zhǎng)時(shí)間復(fù)雜性：也叫漸進(jìn)運(yùn)行時(shí)間，指的是在算法運(yùn)行時(shí)間的函數(shù)中，去除低階項(xiàng)和首項(xiàng)常數(shù)后余下的部分。15時(shí)間復(fù)雜性——階的增長(zhǎng)1617時(shí)間復(fù)雜性——階的增長(zhǎng)元運(yùn)算:對(duì)于任何計(jì)算步驟，不管輸入數(shù)據(jù)或執(zhí)行的算法，它的代價(jià)總是以一個(gè)時(shí)間常量為上界，則稱(chēng)該計(jì)算步驟為元運(yùn)算。固定大小運(yùn)算對(duì)象上元運(yùn)算的例子：

①算術(shù)運(yùn)算，包括加減乘除；

②比較和邏輯運(yùn)算；

③賦值運(yùn)算，包括遍歷表和指針賦值。

18時(shí)間復(fù)雜性——O符號(hào)（歐麥克輪）O表示算法的運(yùn)行時(shí)間，但是不一定是實(shí)際運(yùn)行時(shí)間，可能只是運(yùn)行時(shí)間的上限。一般來(lái)說(shuō)，說(shuō)一個(gè)算法的運(yùn)行時(shí)間時(shí)O(g(n))是指當(dāng)輸入的大小等于或超過(guò)某個(gè)閾值n0時(shí)，其運(yùn)行時(shí)間的上限是g(n)的c倍，c是正常數(shù)。19時(shí)間復(fù)雜性——O符號(hào)O符號(hào)定義：令f(n)和g(n)是從自然數(shù)集到非負(fù)實(shí)數(shù)集的兩個(gè)函數(shù)，如果存在一個(gè)自然數(shù)n0和一個(gè)常數(shù)c>0使得：則稱(chēng)f(n)為O(g(n))如果存在，則蘊(yùn)含著f(n)=O(g(n))20時(shí)間復(fù)雜性——Ω符號(hào)Ω符號(hào)在運(yùn)行時(shí)間的一個(gè)常數(shù)因子內(nèi)提供一個(gè)下界。eg：插入排序法，元運(yùn)算次數(shù)至少是cn，c為常數(shù)，這時(shí)稱(chēng)排序算法的運(yùn)行時(shí)間時(shí)Ω(n)。Ω符號(hào)可能不指示一個(gè)算法確切的運(yùn)行時(shí)間。如果輸入大小大于或等于某一閾值n0，其運(yùn)行時(shí)間下界是g(n)的c倍，c為正常數(shù)，則稱(chēng)算法是Ω(g(n))。21時(shí)間復(fù)雜性——Ω符號(hào)Ω符號(hào)定義：令f(n)和g(n)是從自然數(shù)集到非負(fù)實(shí)數(shù)集的兩個(gè)函數(shù)，如果存在一個(gè)自然數(shù)n0和一個(gè)常數(shù)c>0使得：則稱(chēng)f(n)為Ω(g(n))如果存在，則蘊(yùn)含著f(n)=Ω(g(n))22時(shí)間復(fù)雜性——Θ符號(hào)Θ符號(hào)：每一個(gè)元運(yùn)算需要的常量時(shí)間。存在與算法有關(guān)的兩個(gè)常數(shù)c1和c2，在n大于等于n0的任何大小的輸入情況下，算法運(yùn)行時(shí)間在c1n2和c2n2之間。對(duì)于任何大小等于或者超過(guò)某一閾值n0的輸入，如果運(yùn)行時(shí)間在下限c1g(n)和上限c2g(n)之間，則稱(chēng)算法的運(yùn)行時(shí)間為Θ(g(n))階的。Θ符號(hào)是用來(lái)表示算法的精確階的，蘊(yùn)含著在算法的運(yùn)行時(shí)間上有確切界限。23時(shí)間復(fù)雜性——Θ符號(hào)Θ符號(hào)定義：令f(n)和g(n)是從自然數(shù)集到非負(fù)實(shí)數(shù)集的兩個(gè)函數(shù)，如果存在一個(gè)自然數(shù)n0和兩個(gè)常數(shù)c1和c2使得：則稱(chēng)f(n)為Θ(g(n))如果存在，則蘊(yùn)含著f(n)=Θ(g(n))，c為大于0的常數(shù)。24時(shí)間復(fù)雜性——復(fù)雜性與o符號(hào)o符號(hào):為了說(shuō)明復(fù)雜性類(lèi)相同的兩個(gè)函數(shù)屬于不同的類(lèi)。定義：令f(n)和g(n)是從自然數(shù)集到非負(fù)數(shù)集的兩個(gè)函數(shù)，如果對(duì)每一個(gè)常數(shù)c>0，存在正整數(shù)n0，使得所有n≥n0

，都有成立，則稱(chēng)f(n)是o(g(n))的。25時(shí)間復(fù)雜性——復(fù)雜性與o符號(hào)如果存在，則蘊(yùn)含著f(n)=o(g(n))。262.3算法復(fù)雜性度量——空間復(fù)雜性空間：為了解求問(wèn)題的實(shí)例而執(zhí)行的計(jì)算步驟所需要額內(nèi)存空間（或字）數(shù)目，不包括用來(lái)存儲(chǔ)輸入的空間。算法空間復(fù)雜性不可能超過(guò)運(yùn)行時(shí)間的復(fù)雜性。S(n)=O(T(n))272.4最優(yōu)算法定義：如果可以證明任何一個(gè)求解問(wèn)題A的算法必定是Ω(f(n))，則把在Ω(f(n))時(shí)間內(nèi)求解問(wèn)題A的任何算法稱(chēng)為最優(yōu)算法。沒(méi)有考慮空間復(fù)雜性。282.5算法的評(píng)價(jià)估計(jì)算法運(yùn)行時(shí)間最壞情況與平均情況分析平攤分析輸入大小和問(wèn)題實(shí)例292.5算法的評(píng)價(jià)——估計(jì)算法運(yùn)行時(shí)間計(jì)算迭代次數(shù)：運(yùn)行時(shí)間常常和循環(huán)次數(shù)成正比。302.5算法的評(píng)價(jià)——估計(jì)算法運(yùn)行時(shí)間計(jì)算基本運(yùn)行的頻度基本運(yùn)算：如果算法中一個(gè)元運(yùn)算具有最高頻度，所有其他元運(yùn)算頻度均在其頻度的常數(shù)倍內(nèi)，則稱(chēng)這個(gè)運(yùn)算為基本運(yùn)算。兩個(gè)部分：確定一種基本運(yùn)算，應(yīng)用漸進(jìn)表達(dá)式找出運(yùn)算執(zhí)行的階。312.5算法的評(píng)價(jià)——估計(jì)算法運(yùn)行時(shí)間計(jì)算基本運(yùn)行的頻度候選基本運(yùn)算：在分析搜索和排序算法時(shí)，如果元素比較時(shí)元運(yùn)算，則可選其為基本運(yùn)算；矩陣乘法算法中，選擇數(shù)量乘法運(yùn)算；遍歷一個(gè)鏈表，可以選擇設(shè)置或更新指針的運(yùn)算；在圖的遍歷中，可以選擇訪問(wèn)節(jié)點(diǎn)的動(dòng)作和對(duì)被訪問(wèn)節(jié)點(diǎn)的計(jì)數(shù)所有的元運(yùn)算都不是基本運(yùn)算，可能是因?yàn)槎喾N運(yùn)算結(jié)合在一起的頻度與算法運(yùn)行時(shí)間成正比。此時(shí)，可用執(zhí)行這些運(yùn)算的總次數(shù)的函數(shù)表示運(yùn)行時(shí)間。322.5算法的評(píng)價(jià)——估計(jì)算法運(yùn)行時(shí)間使用遞推關(guān)系332.5算法的評(píng)價(jià)——最壞情況與平均情況分析情況1：算法運(yùn)行時(shí)間與輸入值無(wú)關(guān)，只與用元素?cái)?shù)目測(cè)度的大小有關(guān)。如：兩個(gè)n×n的矩陣相加。情況2：算法運(yùn)行時(shí)間不僅依賴(lài)于輸入的個(gè)數(shù)，還依賴(lài)于它的形式。如：排序法。不可能找到一個(gè)與輸入大小和形式都相關(guān)的描述時(shí)間復(fù)雜性的函數(shù)，輸入形式只能被忽略。342.5算法的評(píng)價(jià)——最壞情況與平均情況分析對(duì)于插入排序法，考慮3個(gè)排列：a，輸入元素按降序排列；b，輸入元素隨機(jī)排列；c，輸入元素按升序排列。352.5算法的評(píng)價(jià)——最壞情況與平均情況分析最壞情況分析平均情況分析362.5算法的評(píng)價(jià)——平攤分析運(yùn)算的平攤運(yùn)行時(shí)間：算法在整個(gè)執(zhí)行過(guò)程中所用時(shí)間的平均值。平攤分析保證了運(yùn)行的平均代價(jià)，也保證了算法在最壞情況下的平均開(kāi)銷(xiāo)。與平均分析時(shí)間不同。比最壞情況分析更困難。372.5算法的評(píng)價(jià)——輸入大小和問(wèn)題實(shí)例算法性能的測(cè)度通常是輸入大小、順序和分布的函數(shù)。輸入大小的概念屬于算法分析的實(shí)踐部分，需要通過(guò)實(shí)例進(jìn)行分析。常用輸入大小的測(cè)度：排序和搜索：數(shù)組或表中元素的數(shù)目；圖的算法：圖中的邊或者頂點(diǎn)的數(shù)目，或者二者都有；計(jì)算幾何：點(diǎn)、頂點(diǎn)、邊、線段或者多邊形的個(gè)數(shù)表示矩陣運(yùn)算：矩陣的維數(shù)；數(shù)論算法和密碼學(xué)：輸入的比特?cái)?shù)。3839算法基礎(chǔ)計(jì)算幾何本講內(nèi)容

40算法的概念

算法是完成特定任務(wù)的有限指令集。所有的算法必須滿足下面的標(biāo)準(zhǔn)：輸入輸出明確性有限性有效性41算法的概念

算法的研究包括很多重要和活躍的領(lǐng)域，可以分為四個(gè)不同的領(lǐng)域：怎樣設(shè)計(jì)算法怎樣驗(yàn)證算法怎樣分析算法怎樣測(cè)試程序測(cè)試評(píng)測(cè)（性能度量）42GIS算法的計(jì)算幾何基礎(chǔ)（矢量）P21

如果一條線段的端點(diǎn)是有次序之分的,我們把這種線段稱(chēng)為有向線段(directedsegment)。如果有向線段p1p2的起點(diǎn)P1在坐標(biāo)原點(diǎn)，我們可以把它稱(chēng)為矢量P2。Op1p243矢量加減法

Op1QPP+QOp1QPP-Q

設(shè)二維矢量P=（x1,y1），Q=（x2,y2）則矢量加法定義為P+Q=（x1+x2,y1+y2）;同樣的，矢量減法定義為P-Q=（x1-x2,y1-y2）44矢量叉積

計(jì)算矢量叉積是直線和線段相關(guān)算法的核心部分。設(shè)矢量P=（x1,y1），Q=（x2,y2）,則矢量叉積定義為（0,0）、p1、p2和p1p2所組成的平行四邊形的帶符號(hào)的面積，即P×Q=x1·y2-x2·y1，其結(jié)果是個(gè)標(biāo)量。顯然有性質(zhì)P×Q=-（Q×P）和P×-Q=-（P×Q）。

叉積的一個(gè)重要的性質(zhì)是可以通過(guò)它的符號(hào)判斷兩矢量的相互之間的順逆時(shí)針關(guān)系：若P×Q>0，則P在Q的順時(shí)針?lè)较?；若P×Q<0，則P在Q的逆時(shí)針?lè)较?；若P×Q=0，則P與Q共向,但可能同向也可能反向。45折線段的拐向判斷

折線段的拐向判斷方法，可以直接由矢量叉積的性質(zhì)推出，對(duì)于有公共端點(diǎn)的線段p0p1和P1P2，通過(guò)計(jì)算（p2-p0）×(P1-p0)的符號(hào)便可以給出折線段的拐向。p0p1p2基（p2-p0）×(P1-p0)<0，則P0P1在P1點(diǎn)拐向左側(cè)后得到P1P2p0p1p2基（p2-p0）×(P1-p0)>0，則P0P1在P1點(diǎn)拐向右側(cè)后得到P1P2p0p1p2基（p2-p0）×(P1-p0)=0，則P0P1P2三點(diǎn)共線46判斷點(diǎn)是否在線段上

設(shè)點(diǎn)為Q，線段為P1P2，判斷點(diǎn)Q在該線段上的依據(jù)是（Q-P1）×（P2-P1）=0且Q在以P1P2為對(duì)角頂點(diǎn)的矩形內(nèi)。前者保證Q點(diǎn)在直線P1P2上，后者是保證Q點(diǎn)不在線段P1P2的延長(zhǎng)線上或反向延長(zhǎng)線上，對(duì)于這一步驟可用以下過(guò)程實(shí)現(xiàn)：If(min(p1x,p2x)<=Qx<=max(p1x,p2x))and(min(p1y,p2y)<=Qy<=max(p1y,p2y))Thenreturntrue;Elsereturnfalse;

特別要注意的是，由于需要考慮水平線段和垂直線段兩種特殊情況，min(p1x,p2x)<=Qx<=max(p1x,p2x)和

(min(p1y,p2y)<=Qy<=max(p1y,p2y)兩個(gè)條件必須同時(shí)滿足才能返回真值。47判斷兩線段是否相交（算法一）快速排斥實(shí)驗(yàn)跨立實(shí)驗(yàn)48判斷兩線段是否相交（快速排斥實(shí)驗(yàn)）設(shè)以線段P1P2為對(duì)角線的矩形為R，設(shè)以線段Q1Q2為對(duì)角的矩形為T(mén)，如果R和T不相交，顯然兩線段不會(huì)相交49判斷兩線段是否相交（跨立實(shí)驗(yàn)）

如果兩線段相交，則兩線段必然相互跨立對(duì)方。若p1p2跨立Q1Q2，則矢量（P1-Q1）和（P2-Q2）位于矢量（Q2-Q1）的兩側(cè)，則（P1-Q1）×（Q2-Q1）×（P2-Q1）×

（Q2-Q1）〈0。當(dāng)（P1-Q1）×（Q2-Q1）=0時(shí)，說(shuō)明

（P1-Q1）×（Q2-Q1）共線，但是因?yàn)橐呀?jīng)通過(guò)快速排斥實(shí)驗(yàn)，所以P1一定在線段Q1Q2上；同理

（Q2-Q1）×（P2-Q1）=0說(shuō)明P2一定在線段Q1Q2上。所以判斷P1P2跨立Q1Q2的依據(jù)是：（P1-Q1）×（Q2-Q1）×

（Q2-Q1）×（P2-Q1）≥0。同理判斷Q1Q2跨立P1P2的依據(jù)是（Q1-P1）×（P2-P1）×

（P2-P1）×（Q2-P1）≥0。50判斷兩線段是否相交（算法一）通過(guò)快速排斥實(shí)驗(yàn)未通過(guò)快速排斥實(shí)驗(yàn)未通過(guò)跨立實(shí)驗(yàn)通過(guò)跨立實(shí)驗(yàn)51判斷兩線段是否相交（算法二）

定義ABCD為二維空間的點(diǎn)，則有向線段AB和CD的參數(shù)方程為AB=A+r(B-A),r∈[0,1)CD=C+s(D-C),s∈[0,1)如果AB與CD相交，則A+r(B-A)=C+s(D-C)→Ax+r(Bx-Ax)=Cx+s(Dx-Cx),Ay+r(By-Ay)=Cy+s(Dy-Cy),r,s∈[0,1),解方程，求r和s52

設(shè)P為直線AB和CD的交點(diǎn)，則P=A+r（B-A）→Px=Ax+r(Bx-Ax),Py=Ay+r(By-Ay)

如果(0≤r≤1)and(0≤s≤1)，則有向線段AB和CD的交點(diǎn)存在，否則交點(diǎn)不存在。如果（Bx-Ay）(Dy-Cy)-(By-Ay)(Dx-Cx)為0，則AB和CD平行。如果（Ay-Cy）(Dx-Cx)-(Ax-Cx)(Dy-Cx)也為0，則AB和CD共線。如果直線AB和CD相交，而交點(diǎn)不位于線段AB和CD之間，則交點(diǎn)位置可以通過(guò)以下條件進(jìn)行判斷：如果r>1,則P位于有向線段AB的延長(zhǎng)線上；如果r<0,則P位于有向線段BA的延長(zhǎng)線上；如果s>1,則P位于有向線段CD的延長(zhǎng)線上；如果s<0,則P位于有向線段DC的延長(zhǎng)線上；判斷兩線段是否相交（算法二）53判斷距形是否包含點(diǎn)

只要判斷該點(diǎn)的橫坐標(biāo)和縱坐標(biāo)是否夾在矩形的左右邊和上下邊之間。insideoutsideonon54判斷線段、折線、多邊形是否在矩形中

因?yàn)榫匦问莻€(gè)凸集，所以只要判斷所有點(diǎn)是否都在矩形中就可以了。55判斷矩形是否在矩形中目標(biāo)矩形

只要比較左右邊界和上下邊界就可以了。56判斷圓是否在矩形中

圓在矩形中的充要條件是：圓心在矩形中且圓的半徑小于或等圓心到矩形四邊的距離的最小值57判斷點(diǎn)是否在多邊形中射線法轉(zhuǎn)角法585960判斷線段是否在多邊形中

必要條件1:線段的兩個(gè)端點(diǎn),都在多邊形內(nèi):

必要條件2:線段和多邊形的所有邊都不相交61判斷線段是否在多邊形中

線段和多邊形交于線段的兩端點(diǎn)并不會(huì)影響線段是否在多邊形內(nèi),但是多邊形的某個(gè)頂點(diǎn)和線段相交,還必須判斷兩相鄰交點(diǎn)之間的的線段是否包含于多邊形內(nèi)部。62判斷線段是否在多邊形中

命題1：如果線段和多邊形的兩相鄰交點(diǎn)，P1P2的中點(diǎn)P’也在多邊形內(nèi)，則P1P2之間所有的點(diǎn)都在多邊形內(nèi)。

推論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)是否在線段上就可以了。63判斷線段是否在多邊形中

至此，得出算法如下：If線段PQ的端點(diǎn)不都在多邊形內(nèi)thenreturnfalse;else

點(diǎn)集pointSet初始化為空

for多邊形的每條邊Sdoif線段的每條邊在s上

then將該端點(diǎn)加入pointSet：

elseifs的某個(gè)端點(diǎn)在線段PQ上

then將該端點(diǎn)加入pointSet：

elseifs和線段PQ相交//肯定是內(nèi)交

thenreturnfalse;else

將pointSet中的點(diǎn)按照X-Y坐標(biāo)排序

forpointSet中每?jī)蓚€(gè)相鄰點(diǎn)pointSet[i],pointSet[i+1],doifpointSet[i],pointSet[i+1]的中點(diǎn)不在多邊形中

thenreturnfalse;elsereturntrue這個(gè)過(guò)程中的排序因?yàn)榻稽c(diǎn)數(shù)目肯定遠(yuǎn)小于多邊形的頂點(diǎn)數(shù)目n,所以最多是常數(shù)級(jí)的復(fù)雜度，幾乎可以忽略不計(jì)。因此整個(gè)算法的復(fù)雜度也是O（n）。

64判斷多邊形是否在多邊形中

只要判斷多邊形的每條邊是否在多邊形內(nèi)即可。判斷一個(gè)有m個(gè)頂點(diǎn)的多邊形是否在一個(gè)有n個(gè)頂點(diǎn)的多邊形內(nèi)的復(fù)雜度為O（m×n）65判斷矩形是否在多邊形中

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

只要計(jì)算圓心到多邊形的每條邊的最短距離，如果該距離大于或等于圓半徑則該圓在多邊形內(nèi)。67判斷點(diǎn)是否在圓中

計(jì)算到圓心到該點(diǎn)的距離，如果小于或等于半徑則該點(diǎn)在圓內(nèi)。68判斷線段、折線、矩形、多邊形是否在圓中c

因?yàn)閳A是凸集，所以只要判斷是否每個(gè)頂點(diǎn)都在圓內(nèi)即可。69判斷圓是否在圓中

設(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)。70計(jì)算兩條共線線段的交點(diǎn)長(zhǎng)線段短線段l2l1l2l1l2l1l2l1公共線段71計(jì)算線段或直線與線段的交點(diǎn)（一）

設(shè)一條線段為L(zhǎng)0=P1P2，另一條線段或直線為L(zhǎng)1=Q1Q2，要計(jì)算的就是L0和L1的交點(diǎn)。

第一步：首先判斷L0和L1是否相交（方法如前），如果不相交則沒(méi)有交點(diǎn)，否則說(shuō)明L0和L1一定有交點(diǎn)，下面就將L0和L1都看作直線來(lái)考慮。

第二步：如果P1和P2橫坐標(biāo)相同，即L0平行于y。（1）或L1也平行于y軸，有兩種情況。每一種情況：若P1的縱坐標(biāo)和Q1的縱坐標(biāo)相同，說(shuō)明L0和L1共線，假如L1是直線，則有無(wú)窮的交點(diǎn)，假如L1是線段，可用“計(jì)算兩條共線線段的交點(diǎn)”的算法來(lái)求交點(diǎn)。第二種情況：否則說(shuō)明L0和L1平行，則沒(méi)有交點(diǎn)。（2）若L1不平行于y軸，則交點(diǎn)橫坐標(biāo)為p1的橫坐標(biāo)，代入到L1的直線方程中，可以計(jì)算出交點(diǎn)縱坐標(biāo)。

第三步：如果P1和P2的橫坐標(biāo)不同，但是Q1Q2橫坐標(biāo)相同，即L1平行于y軸，則交點(diǎn)橫坐標(biāo)為Q1的橫坐標(biāo)，代入到L0的直線方程中，可以計(jì)算出交點(diǎn)縱坐標(biāo)。72計(jì)算線段或直線與線段的交點(diǎn)（二）

第四步：如果P1和P2縱坐標(biāo)相同，即L0平行于x軸。（1）或L1也平行于x軸，有兩種情況。每一種情況：若P1的橫坐標(biāo)和Q1的橫坐標(biāo)相同，說(shuō)明L0和L1共線，假如L1是直線，則有無(wú)窮的交點(diǎn)，假如L1是線段，可用“計(jì)算兩條共線線段的交點(diǎn)”的算法來(lái)求交點(diǎn)。第二種情況：否則說(shuō)明L0和L1平行，則沒(méi)有交點(diǎn)。（2）若L1不平行于x軸，則交點(diǎn)縱坐標(biāo)為p1的縱坐標(biāo)，代入到L1的直線方程中，可以計(jì)算出交點(diǎn)橫坐標(biāo)。

第五步：如果P1和P2縱坐標(biāo)不同，如果1和Q2縱坐標(biāo)相同，即L1平行于x軸，則交點(diǎn)縱坐標(biāo)為Q1的縱坐標(biāo)，代入到L0的直線方程中可以計(jì)算出交點(diǎn)橫坐標(biāo)。73

第六步：剩下的情況就是L1和L0的斜率均存在且不為零的情況。計(jì)算線段或直線與線段的交點(diǎn)（三）（1）計(jì)算出L0的斜率K0，L1的斜的斜率K1。（2）如果K1=K2，則有兩種情況。第一種情況：如果Q1在L0上，則說(shuō)明L0和L1共線，假如L1是直線，則有無(wú)窮交點(diǎn)，假如L1是線段可用“計(jì)算兩條共線線段交點(diǎn)”的算法求交點(diǎn)；第二種情況：如果Q1不在L0上，則說(shuō)明L0和L1平行，則沒(méi)有交點(diǎn)。（3）聯(lián)立兩直線的方程組可以解出交點(diǎn)來(lái)。74求線段或直線與圓的交點(diǎn)

設(shè)圓心為O，圓半徑為r，直線（或線段）L上的兩點(diǎn)為P1，P2。

第一步，如果L是線段且P1，P2都包含在圓O內(nèi)，則沒(méi)有交點(diǎn)；否則進(jìn)行下一步。第二步，如果L平行于y軸。（1）計(jì)算圓心到L的距離d;（2）如果d>r，則L和圓沒(méi)有交點(diǎn)；（3）利用勾股定理，可以求出兩交點(diǎn)坐標(biāo)，但要注意考慮L和圓的相切情況。第三步，如果L平行于x軸，做法與L平行于y軸的情況類(lèi)似。第四步，如果L既不平行于x軸，也不平行y軸，可以求出L的斜率K，然后列出L的點(diǎn)斜式方程，和圓方程聯(lián)立即可求出L和圓的兩個(gè)交點(diǎn)。第五點(diǎn)，如果L是線段，對(duì)于第二至第四步中求出的交點(diǎn)還要分別判斷是否屬于該線段的范圍內(nèi)。75中心點(diǎn)的計(jì)算

多邊形的中心點(diǎn)（又叫做質(zhì)心或重心）可以通過(guò)將多邊形分割成為三角形，求取三角形的中心點(diǎn)，然后將三角形的中心點(diǎn)加權(quán)求各取得。三角形的中心點(diǎn)（Cx,Cy）是三角形的三個(gè)角