第8章 數(shù)論算法及計(jì)算幾何算法

1、第八章第八章 數(shù)論算法及計(jì)算幾何算法數(shù)論算法及計(jì)算幾何算法8.5 凸包問題凸包問題1、問題提出、問題提出 給定一個(gè)點(diǎn)集給定一個(gè)點(diǎn)集SP0,P1,Pn-1，它的凸包是一，它的凸包是一個(gè)最小的凸多邊形個(gè)最小的凸多邊形P，且滿足，且滿足S中的每個(gè)點(diǎn)或者在中的每個(gè)點(diǎn)或者在P的邊界上或者在的邊界上或者在P的內(nèi)部。的內(nèi)部。 如果點(diǎn)集如果點(diǎn)集S是是兩個(gè)點(diǎn)兩個(gè)點(diǎn)的集合，顯然它的凸包是連接這的集合，顯然它的凸包是連接這兩個(gè)點(diǎn)的線段；兩個(gè)點(diǎn)的線段； 如果如果S是由是由三個(gè)不共線的點(diǎn)三個(gè)不共線的點(diǎn)組成的集合，那么凸包是組成的集合，那么凸包是以這三個(gè)點(diǎn)為頂點(diǎn)的三角形；以這三個(gè)點(diǎn)為頂點(diǎn)的三角形； 如果如果三點(diǎn)共線三點(diǎn)共

2、線，則凸包是以距離最遠(yuǎn)的兩個(gè)點(diǎn)為端，則凸包是以距離最遠(yuǎn)的兩個(gè)點(diǎn)為端點(diǎn)的線段。點(diǎn)的線段。 對(duì)于對(duì)于更大的集合更大的集合，在直觀上，可以把，在直觀上，可以把S中的每個(gè)點(diǎn)看中的每個(gè)點(diǎn)看作訂在地上的木樁，那么凸包就是將所有木樁圍起作訂在地上的木樁，那么凸包就是將所有木樁圍起來的一個(gè)拉緊的橡皮繩的形狀，如圖來的一個(gè)拉緊的橡皮繩的形狀，如圖8-1所示。所示。解決方法：解決方法： 1、窮舉搜索法、窮舉搜索法 2、分治法、分治法1、算法思想、算法思想 ： 根據(jù)根據(jù)凸多邊形的定義凸多邊形的定義，對(duì)于一個(gè)由，對(duì)于一個(gè)由n個(gè)點(diǎn)組成的集個(gè)點(diǎn)組成的集合合S中的任意兩個(gè)點(diǎn)中的任意兩個(gè)點(diǎn)Pi和和Pj，當(dāng)且僅當(dāng)該集合中的，當(dāng)

3、且僅當(dāng)該集合中的其它點(diǎn)要么位于穿過其它點(diǎn)要么位于穿過Pi和和Pj直線的同側(cè)，要么位于直線的同側(cè)，要么位于線段線段PiPj上。則線段上。則線段PiPj是該集合凸多邊形邊界的是該集合凸多邊形邊界的一部分。對(duì)每一個(gè)點(diǎn)都做一遍檢驗(yàn)之后，滿足條件一部分。對(duì)每一個(gè)點(diǎn)都做一遍檢驗(yàn)之后，滿足條件的線段就構(gòu)成了該凸包的邊界。的線段就構(gòu)成了該凸包的邊界。8.5.1凸包問題的窮舉搜索法凸包問題的窮舉搜索法2、算法求解步驟、算法求解步驟 ：步驟步驟1：對(duì)于集合中的任意兩點(diǎn)對(duì)于集合中的任意兩點(diǎn)Pi和和Pj ，定義穿過兩點(diǎn)，定義穿過兩點(diǎn)Pi和和Pj的直線方程的直線方程 。 (x-xi) / (xj-xi) =(y-yi)

4、 / (yj-yi)步驟步驟2：將點(diǎn)集將點(diǎn)集S中的中的其余點(diǎn)其余點(diǎn)代入直線方程，然后檢查代入直線方程，然后檢查是否位于線段同側(cè)，如果不是，說明線段是否位于線段同側(cè)，如果不是，說明線段PiPj不是點(diǎn)不是點(diǎn)集集S的凸多邊形的邊界。的凸多邊形的邊界。 否則，否則，PiPj是凸多邊形的邊界。是凸多邊形的邊界。步驟步驟3：對(duì)點(diǎn)集中的每個(gè)點(diǎn)，重復(fù)上述步驟對(duì)點(diǎn)集中的每個(gè)點(diǎn)，重復(fù)上述步驟1和步驟和步驟2，直到找出全部多邊形的邊界。直到找出全部多邊形的邊界。 3、算法程序語言描述、算法程序語言描述 詳見課本詳見課本4、算法分析、算法分析 點(diǎn)集中的點(diǎn)構(gòu)成的線段數(shù)目最多為點(diǎn)集中的點(diǎn)構(gòu)成的線段數(shù)目最多為n(n-1)/

5、2，對(duì)每，對(duì)每一條線段，最壞情況要檢查點(diǎn)集中其余一條線段，最壞情況要檢查點(diǎn)集中其余n-2個(gè)點(diǎn)個(gè)點(diǎn)屬屬于哪個(gè)半平面，于哪個(gè)半平面， 故算法的時(shí)間復(fù)雜性為故算法的時(shí)間復(fù)雜性為O(n3) 8.5.2凸包問題的分治法凸包問題的分治法1、算法思想、算法思想 將點(diǎn)集將點(diǎn)集S中的點(diǎn)按照中的點(diǎn)按照x坐標(biāo)升序排序坐標(biāo)升序排序，x坐標(biāo)相同的坐標(biāo)相同的按照按照y坐標(biāo)升序排序，排好序的序列存放在點(diǎn)結(jié)構(gòu)坐標(biāo)升序排序，排好序的序列存放在點(diǎn)結(jié)構(gòu)數(shù)組數(shù)組P中。中。 那么那么最左邊的點(diǎn)最左邊的點(diǎn)P0、最右邊的點(diǎn)、最右邊的點(diǎn)Pn-1肯定是凸包上肯定是凸包上的點(diǎn)。的點(diǎn)。 線段線段P0Pn-1將集合將集合S中的點(diǎn)分成兩個(gè)集合中的點(diǎn)分

6、成兩個(gè)集合S1和和S2。 子集子集S1的凸包由線段的凸包由線段P0Pn-1作為下邊界、多節(jié)鏈條作作為下邊界、多節(jié)鏈條作為上邊界組成。這條上邊界稱為為上邊界組成。這條上邊界稱為上包上包。 子集子集S2的凸包由線段的凸包由線段P0Pn-1作為上邊界、多節(jié)鏈條作作為上邊界、多節(jié)鏈條作為下邊界組成。這條下邊界稱為為下邊界組成。這條下邊界稱為下包下包。 整個(gè)集合的凸包由上包和下包構(gòu)成。如圖整個(gè)集合的凸包由上包和下包構(gòu)成。如圖8-2所示。所示。2、算法求解步驟、算法求解步驟 構(gòu)造上包步驟：構(gòu)造上包步驟： 找到子集找到子集S1中的點(diǎn)中的點(diǎn)Pmax，它是距離線段，它是距離線段P0Pn-1最遠(yuǎn)的點(diǎn)最遠(yuǎn)的點(diǎn) 連接

7、連接 ，找出，找出S1中位于直線中位于直線 左邊的點(diǎn)，左邊的點(diǎn)，這些點(diǎn)構(gòu)成集合這些點(diǎn)構(gòu)成集合S11；找出；找出S1中位于直線中位于直線 左邊的左邊的點(diǎn)，這些點(diǎn)構(gòu)成集合點(diǎn)，這些點(diǎn)構(gòu)成集合S12；P0PmaxPn-1內(nèi)部的點(diǎn)不予考內(nèi)部的點(diǎn)不予考慮。慮。 遞歸構(gòu)造遞歸構(gòu)造S11和和S12的上包，然后簡單地將它們連接起來，的上包，然后簡單地將它們連接起來，得到得到S1的的上包上包。 構(gòu)造下包步驟：構(gòu)造下包步驟： 找到子集找到子集S2中的點(diǎn)中的點(diǎn)Pmin，它是距離線段，它是距離線段P0Pn-1最遠(yuǎn)的點(diǎn)最遠(yuǎn)的點(diǎn) 連接連接 ，找出，找出S2中位于直線中位于直線 右邊的點(diǎn)，右邊的點(diǎn)，這些點(diǎn)構(gòu)成集合這些點(diǎn)構(gòu)成集

8、合S21；找出；找出S2中位于直線中位于直線 右邊的右邊的點(diǎn)，這些點(diǎn)構(gòu)成集合點(diǎn)，這些點(diǎn)構(gòu)成集合S22；P0PminPn-1內(nèi)部的點(diǎn)不予考內(nèi)部的點(diǎn)不予考慮慮 遞歸構(gòu)造遞歸構(gòu)造S21和和S22的下包，然后簡單地將它們連接起來，的下包，然后簡單地將它們連接起來，得到得到S2的的下包下包 。max0PP1nmaxPPmax0PP1nmaxPPmin0PP1nminPPmin0PP1nminPP3、 算法程序語言描述算法程序語言描述 詳見課本詳見課本8.6最接近點(diǎn)對(duì)問題最接近點(diǎn)對(duì)問題1、問題提出、問題提出 最接近點(diǎn)對(duì)問題要求給定平面上最接近點(diǎn)對(duì)問題要求給定平面上n個(gè)點(diǎn)組成的集個(gè)點(diǎn)組成的集合合S，找出其中

9、，找出其中n個(gè)點(diǎn)組成的點(diǎn)對(duì)中距離最近的一個(gè)點(diǎn)組成的點(diǎn)對(duì)中距離最近的一對(duì)點(diǎn)對(duì)點(diǎn) 。 該問題具有很大的實(shí)際應(yīng)用價(jià)值，該問題具有很大的實(shí)際應(yīng)用價(jià)值，例如例如，一個(gè)控，一個(gè)控制空中或者海上交通的系統(tǒng)就需要了解制空中或者海上交通的系統(tǒng)就需要了解2個(gè)最近個(gè)最近的交通工具，以預(yù)測可能產(chǎn)生的相撞事故。的交通工具，以預(yù)測可能產(chǎn)生的相撞事故。2、解決問題方法、解決問題方法 窮舉搜索、分治法（略）窮舉搜索、分治法（略）8.6.1最接近點(diǎn)對(duì)問題的窮舉搜索法最接近點(diǎn)對(duì)問題的窮舉搜索法1、算法思想、算法思想 分別計(jì)算點(diǎn)集中每一對(duì)點(diǎn)的距離分別計(jì)算點(diǎn)集中每一對(duì)點(diǎn)的距離Dij，從中找出值最小的那，從中找出值最小的那對(duì)點(diǎn)。對(duì)點(diǎn)。

10、 為了避免點(diǎn)對(duì)的重復(fù)計(jì)算，算法只考慮為了避免點(diǎn)對(duì)的重復(fù)計(jì)算，算法只考慮ij的情況的情況.2、算法描述、算法描述Double shortdis( )double temp=,d=0; for(int i=0; in-1;i+ ) for(int j=i+1; jn,j+ ) d=sqrt( (pow( pi.x-pj.x) , 2)+pow(pi.y-pj.y),2 ); if(dtempt) tempt=d; p1=pi; p2=pj; 3、算法分析、算法分析從算法描述可知循環(huán)體內(nèi)的時(shí)間是常數(shù)時(shí)間，循環(huán)從算法描述可知循環(huán)體內(nèi)的時(shí)間是常數(shù)時(shí)間，循環(huán)次數(shù)次數(shù) ， 因此算法的時(shí)間復(fù)雜性為因此算法的時(shí)

11、間復(fù)雜性為O(n2) 。2) 1( nn8.6.2最接近點(diǎn)對(duì)問題的分治法最接近點(diǎn)對(duì)問題的分治法1、算法思想、算法思想 將所給平面上的將所給平面上的n個(gè)點(diǎn)的集合個(gè)點(diǎn)的集合S分成規(guī)模大致相等分成規(guī)模大致相等的兩個(gè)子集的兩個(gè)子集S1和和S2。遞歸求解。遞歸求解S1和和S2中的最接中的最接近點(diǎn)對(duì)；近點(diǎn)對(duì)； 集合集合S中的最接近點(diǎn)對(duì)：中的最接近點(diǎn)對(duì)： 或者是子問題或者是子問題S1的解的解； 或者是或者是子問題子問題S2的解的解， 或者是一或者是一個(gè)點(diǎn)在個(gè)點(diǎn)在S1中中，一個(gè)點(diǎn)在一個(gè)點(diǎn)在S2中的情況組成中的情況組成的最接近點(diǎn)對(duì)。的最接近點(diǎn)對(duì)。 一維情形下最小點(diǎn)對(duì)：一維情形下最小點(diǎn)對(duì)： 算法描述：算法描述：S

12、tep1：用：用xm將將x1,x2,xn分成兩部分分成兩部分S1和和S2 Step2：遞歸求：遞歸求S1中最接近點(diǎn)對(duì)，其距離為中最接近點(diǎn)對(duì)，其距離為d1；Step3：遞歸求：遞歸求S2中最接近點(diǎn)對(duì)，其距離為中最接近點(diǎn)對(duì)，其距離為d2；Step4：求：求S1中的最大值中的最大值p，S2中的最小值中的最小值q；Step5：計(jì)算：計(jì)算d3=|p-q|；Step6：比較：比較d1,d2,d3確定哪個(gè)是最接近點(diǎn)對(duì)。確定哪個(gè)是最接近點(diǎn)對(duì)。 算法分析算法分析解此遞歸方程可得解此遞歸方程可得T(n)=O(nlogn)。3)()2/(23)1()(nnOnTnOnT 二維情形二維情形 算法描述：算法描述：Ste

13、p1：選取一垂直線：選取一垂直線l：x=xm作為分割線。其中作為分割線。其中xm為為S中中各點(diǎn)各點(diǎn)x坐標(biāo)的中位數(shù)。由此將坐標(biāo)的中位數(shù)。由此將S分割為分割為S1和和S2Step2：遞歸求：遞歸求S1中最接近點(diǎn)對(duì)，其距離為中最接近點(diǎn)對(duì)，其距離為d1Step3：遞歸求：遞歸求S2中最接近點(diǎn)對(duì)，其距離為中最接近點(diǎn)對(duì)，其距離為d2Step4：令：令d=min(d1,d2)Step5：找出：找出S1中的某個(gè)點(diǎn)中的某個(gè)點(diǎn)p和和S2中的某個(gè)點(diǎn)中的某個(gè)點(diǎn)q組成的點(diǎn)對(duì)組成的點(diǎn)對(duì)(p,q) （難點(diǎn)）（難點(diǎn)）Step6：比較：比較|p-q|,d1,d2確定哪個(gè)是最接近點(diǎn)對(duì)確定哪個(gè)是最接近點(diǎn)對(duì) 思考：如何找出點(diǎn)對(duì)思考：

14、如何找出點(diǎn)對(duì)(p,q) ？ 如果如果|p-q|小于小于d，則，則p點(diǎn)分布在點(diǎn)分布在P1帶形區(qū)域內(nèi)帶形區(qū)域內(nèi)(左虛線和分左虛線和分割線割線l所夾的區(qū)域所夾的區(qū)域)，q點(diǎn)分布在點(diǎn)分布在P2帶形區(qū)域內(nèi)帶形區(qū)域內(nèi)(右虛線和分右虛線和分割線割線l所夾的區(qū)域所夾的區(qū)域)。如圖。如圖8-5所示所示 對(duì)于P1中任意一點(diǎn)p，與它距離小于d的點(diǎn)分布在以p點(diǎn)為圓心，以d為半徑的圓內(nèi)。因此，與點(diǎn)p構(gòu)成最接近點(diǎn)對(duì)的P2中的點(diǎn)一定落在一個(gè)d2d的矩形R中。如圖8-6所示。 由由d的意義可知，矩形的意義可知，矩形R中任何中任何兩個(gè)兩個(gè)S中的點(diǎn)的距離都大于等中的點(diǎn)的距離都大于等于于d。由此可知，至少可以將。由此可知，至少可以將d2d的矩形的矩形R分割成如圖分割成如圖8-7所示的六部分，其中任何一部所示的六部分，其中任何一部分包含分包含P2中的點(diǎn)最多有一個(gè)中的點(diǎn)最多有一個(gè) 因此，在矩形因此，在矩形R中最多只有中最多只有6個(gè)個(gè)P2中的點(diǎn)與中的點(diǎn)與p構(gòu)成最接近點(diǎn)對(duì)構(gòu)成最接近點(diǎn)對(duì) 思考：針對(duì)思考：針對(duì)P1中的任意一點(diǎn)中的任意一點(diǎn)p，檢查