計算幾何總結(jié)

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

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

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

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

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

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

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

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

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