計(jì)算幾何總結(jié)

1、計(jì)算幾何計(jì)算幾何一、向量基礎(chǔ)知識(shí)向量基礎(chǔ)知識(shí)1、向量的點(diǎn)乘、向量的點(diǎn)乘(Dot(DotProduct)Product)與高中數(shù)學(xué)課本的定義類似，但是略有不同，我們將用代數(shù)的語言來定義點(diǎn)乘。兩個(gè)同維向量和的點(diǎn)乘定義為：??12...nxxx?a??12...nyyy?b1122nnxyxyxy??????Tabab?其結(jié)果是一個(gè)實(shí)數(shù)。在平面上和空間中，它的幾何意義是：和的點(diǎn)乘是的模和在上射影的模ababa的乘積，就是：cos??ababa

2、b這里是和的夾角，這和高中數(shù)學(xué)課本是一致的。于是，我們可以求兩個(gè)向量的夾角：cosababcos??ababab當(dāng)然，這一條性質(zhì)仍然保持不變。0????abab2、向量的叉乘、向量的叉乘(Cross(CrossProduct)Product)嚴(yán)格的說，兩個(gè)向量的叉乘是三維向量的二元運(yùn)算。兩個(gè)三維向量和111xyz???aijk的叉乘定義為(這里是空間的三個(gè)基底)：222xyz???bijkijk??????111122121121221

3、222xyzyzyzxzxzxyxyxyz????????ijkabijk其結(jié)果仍然是一個(gè)三維向量。向量叉乘的幾何意義是：?ab(1)它垂直于所在的平面；ab(2)它的模等于以為鄰邊構(gòu)成的平行四邊形的面積，即；absinabab(3)它的方向根據(jù)右手定則判定：將右手四個(gè)手指按照到的方向收攏，則大拇指的方向就是積的方ab向。。退一步，在平面上，我們不嚴(yán)謹(jǐn)?shù)亩x叉乘，實(shí)際上是認(rèn)為兩個(gè)向量的為0，并???ab0abAk?認(rèn)為所得的結(jié)果不是一個(gè)

4、向量，而是一個(gè)數(shù)值，就是說，如果和，那么我們認(rèn)為11xy??aij?22xy??bij?，這個(gè)數(shù)的絕對值是以為臨邊構(gòu)成的平行四邊形的面積。11122122xyxyxyxy????ab??ab??根據(jù)向量叉乘的值正負(fù)，我們可以判定兩個(gè)平面向量的旋轉(zhuǎn)關(guān)系(順時(shí)針或逆時(shí)針)，實(shí)際上是根據(jù)右手定則判斷的。如果，那么從轉(zhuǎn)到是逆時(shí)針；如果，那么從轉(zhuǎn)到是順時(shí)針；如果0??ab??a?b?0??ab??a?b?，順時(shí)針和逆時(shí)針旋轉(zhuǎn)是一樣的。0??ab?

5、?二、計(jì)算幾何基礎(chǔ)算法二、計(jì)算幾何基礎(chǔ)算法1、三角形面積、三角形面積。當(dāng)然，還有其他的許多方法，包括大家熟知的以及Hero公式。2ABCABACS??A????????1sin2SabC?個(gè)線段相交于滿足。COC?????1OAtAB?????????1010、兩條直線的交點(diǎn)、兩條直線的交點(diǎn)解方程，實(shí)際上是把兩條直線寫成方向向量的參數(shù)方程求解。12OAtABOCtCD???????????????????1111、檢查多邊形的凸性、檢查

6、多邊形的凸性按照順時(shí)針的方向檢查每個(gè)三元對，如果所有的這樣的三元對都滿足是正數(shù)，則多()ABCABAC?????????邊形是凸的。1212、點(diǎn)在非凸多邊形內(nèi)部、點(diǎn)在非凸多邊形內(nèi)部判定一個(gè)點(diǎn)是否在一個(gè)多邊形內(nèi)部，從該點(diǎn)引出一條射線，滿足射線與多邊形的交點(diǎn)非多邊形的頂點(diǎn)，考察射線與多邊形的公共點(diǎn)個(gè)數(shù)，點(diǎn)在一個(gè)多邊形內(nèi)部當(dāng)且僅當(dāng)公共點(diǎn)個(gè)數(shù)為奇數(shù)。這個(gè)方法在高維的情形下也是適用的。三、凸包三、凸包給出一些平面上的點(diǎn)，找一個(gè)面積最小的凸多邊形，

7、使得所給的點(diǎn)都不在這個(gè)凸多邊形的外部。這個(gè)凸多邊形叫做這些點(diǎn)的凸包。下圖是凸包的一個(gè)例子。求二維凸包有許多方法。這里，我們先介紹一種“卷包裹法”(Giftwrapping)，是最簡單的方法。將一個(gè)肯定在凸包上的點(diǎn)(例如，縱坐標(biāo)最小者，當(dāng)不止一個(gè)時(shí)，取橫坐標(biāo)最大者)記為，從出發(fā)，向右做一條水平射線，以為中心將1v1v1v該射線逆時(shí)針旋轉(zhuǎn)，直到接觸到某個(gè)點(diǎn)(如果碰到多個(gè)點(diǎn)，選個(gè)最遠(yuǎn)2v的)，則也為凸包的一個(gè)頂點(diǎn)，再以為中心，…，這樣下去直到

8、該射2v2v線又接觸到。這樣得到的即為凸包的n個(gè)頂點(diǎn)。這樣的過1v12nvvv?程類似于卷包裹直到把點(diǎn)集中的點(diǎn)都卷入為止。射線的傾斜角可以通過反正切求得。對于每個(gè)旋轉(zhuǎn)中心，我們都要判斷對于哪一個(gè)點(diǎn)，傾斜角最小的，這需要的時(shí)間。由于可能有n??On個(gè)點(diǎn)都要這樣進(jìn)行，所以這樣算法的復(fù)雜度是，雖然復(fù)雜度比較高，但是有很好的推廣性，高維的凸??2On包也可以這樣做。下面介紹復(fù)雜度低一些的Graham掃描法，也是容易編程和容易記憶的。這個(gè)算法的基

9、本思想是按著順時(shí)針或者逆時(shí)針的方向加點(diǎn)，檢查是否存在大于的角被建立，這將使得多邊形變成凹的。如果有三個(gè)點(diǎn)形?成超過的角，則刪去中間的那個(gè)點(diǎn)。檢查角度可以通過計(jì)算相鄰兩邊的叉乘完成。?尋找凸包：尋找凸包：?計(jì)算每個(gè)點(diǎn)的角度(與中心和x軸形成的角)排序(0到)2??加入頭兩個(gè)點(diǎn)?對于每個(gè)其它點(diǎn)(不是最后一個(gè)點(diǎn))?使它是凸包的下一個(gè)點(diǎn)?檢查它與前面兩個(gè)點(diǎn)是否形成超過的角?o不斷刪去前一個(gè)點(diǎn)，直到不出現(xiàn)超過的角??加入最后一個(gè)點(diǎn)o執(zhí)行上述的刪除