文本二維凸包

1、Two Dimenal Convex Hull二維凸包譯 by FeliCrazy(MSN felic)準(zhǔn)備知識幾何學(xué)數(shù)學(xué)模型給出平面內(nèi)的點集，找出面積最小的凸多邊形，使得這些點在這個多邊形之內(nèi)（或者在它的邊上）?？梢钥闯?，多邊形的頂點必須是給定點集中的點。例題：放牧奶牛農(nóng)夫想要修建一個柵欄，來防止討厭的當(dāng)?shù)卮髮W(xué)生在他的奶牛們睡覺的時候把它們掀翻。他的每頭奶牛都有一個最喜歡的吃草點，農(nóng)夫想要把這些點都圍在柵欄內(nèi)。農(nóng)夫要圍出一個凸的形狀，因為這樣更容易把奶牛趕進(jìn)牧場。幫助農(nóng)夫確定面積最小的而且包括所牛喜愛的吃草點的柵欄形狀。算法解決二維凸包問題有好幾種算法。這里，只介紹比較容易編碼和的“卷”算法

2、（其實就是所說的漢掃描法譯者注）。算法的基本是在一個肯定會在凸包內(nèi)的點周圍不斷地由順時針或逆時針方向增加頂點，并確保每個內(nèi)角都小于 180 度（保證最終是凸的）。如果三個連續(xù)的頂點的角度大于 180 度，刪掉中間的點?？梢杂脙蓚€沿著多邊形邊的連續(xù)向量的叉積來判斷角度是否大于 180 度。凸包算法流程：找出一個必定會在凸包內(nèi)的中點計算每個點和中點的連線與 x 軸的夾角（在 0360 度的范圍內(nèi)）根據(jù)這些夾角對頂點排序加入最初的兩個頂點對于除最后一個頂點以外的其余頂點讓其成為凸包上的下一個頂點檢查它和前面兩個頂點組成的角是否大于 180 度如果它和前面兩個頂點組成的角大于 180 度，那么把它前面

3、那個頂點刪掉 加入最后一個頂點完成上述的刪除任務(wù)檢查最后一個頂點和它的前一個頂點和第一個頂點所組成的角是否大于 180 度，或者最后一個頂點和第一、第二個頂點組成的角是否大于 180 度。如果第一種情況為真，刪除最后一個頂點，并且檢查倒數(shù)第二個頂點。如果第二種情況為真，刪除第一個頂點，繼續(xù)檢查。當(dāng)兩種情況都不為真時，停止。由于角度的計算方式，增加頂點的時間復(fù)雜度是線性的（就是所說的O(n) ）。因此，運行的時間復(fù)雜度決定于排序的時間復(fù)雜度，所以“卷法”的時間復(fù)雜度是 O( n log n)，這是最優(yōu)的。偽代碼這里是凸包算法的偽代碼：# # # # # # # # 123x(i), y(i) i

4、s the x,y of the i-th po zcrossprod(v1,v2) - z of the vectors v1, v2 if zcrossprod(v1,v2) itioncomponent0,then v2 is right of v1since we add counter-clockwise angle 180 deg(midx, midy) For all po (midx, midy)=s=(0, 0)i (midx,midy) + s)(x(i)/npos, 4 For all poy(i)/npo s i5 angle(i) = atan2(y(i) x(i)

5、- midx)- midy,6perm(i) = i7 #sort perm based on the angle() i.e., angle(perm(0) 11)and-2)zcrossprod(hull(hull-13 hull(hull-1),hull(hull-1) - p) 11)and-2)zcrossprod(hull(hull-19 hull(hull-1),hull(hull-1) - p)=2 andzcrossprod(p25 hull(hull-1),hull(hullstart) -p) =2 andzcrossprod(hull(hullstart) hull(h

6、ullstart+1) - hull(hullstart) 0)- p,3031323334hullstart = hullstart + flag = truewhile flag hull(hull) = p1hull= hull+ 1對于下面的，使用這些頂點：選擇一個中算夾角，并排序。現(xiàn)在，從加入最初的兩個頂點開始?，F(xiàn)在，加入第三個頂點。由于這步操作沒有和前兩個頂點一個大于 180 度的角，只需加入這個頂點。加入第四個頂點。這一次沒有大于 180 度的角，所以不必做的工作。加入第五個頂點。由于第三個，第四個，和第五個頂點了一個大于 180 度的角（一個“向右的”轉(zhuǎn)彎），刪去第四個頂點。第

7、二個，第三個，和第四個頂點沒有了加入第五個頂點的任務(wù)。一個大于 180 度的角，所以完成加入第六個，第七個，和第八 8 個頂點。這個過程中沒有附加的工作。接著，加入最后一個頂點。第八個，第九個，和第一個頂點“右轉(zhuǎn)”；刪除第九個頂點。第七個，第八個，和第一個頂點已經(jīng)完成了，第八個，第一個，和第二個頂點“右轉(zhuǎn)”，所以須刪除第一個頂點。現(xiàn)在，第八個，第二個，和第三個頂點“右轉(zhuǎn)”，所以頂點。又要刪除第二個剩下的頂點并不頂點的凸包?！白筠D(zhuǎn)”原則，所以已經(jīng)完成了任務(wù)，并且建立了給出問題提示類似把頂點放入多邊形的題目通常是求凸包。如果題目要求一個面積最小的凸多邊形，或者周長最小的凸多邊形，那么幾乎可以確定是

8、要求凸包了。推廣不幸的是，這個算法不能簡單地推廣到三維的情形。幸運的是，三維凸包算法全都超級復(fù)雜（以上的更），所以題目不太可能要你去求。如果你給多邊形加上任何限制條件時，這個算法就玩完了（例如，多邊形的頂點不多于 n 個，或者必須是矩形）。例題樹的難題 IOI 1991, problem 2已知：有一些樹，你必須用鐵絲圍繞這些樹，使得你用的鐵絲最短。計算哪些樹會在多邊形的頂點上和鐵絲的長度，還有農(nóng)夫的小屋是在多邊形內(nèi)，還是在它之外，還是跨過多邊形的邊？分析：多邊形的頂點和鐵絲的長度可以由問題直接得到。農(nóng)夫的小屋是坐標(biāo)軸上的一個矩形，你需要一點幾何學(xué)知識來確定矩形中的所有點都在凸包中，或者都在凸包外，或者一些在凸包內(nèi)，一些在凸包外。這樣你就可以得到你想要的查查幾何手冊，找一下這類問題的解法。的護(hù)城河建設(shè)已知：一些多邊形房屋，計算包含這些多邊形除去一個多邊形的護(hù)城河的最小長度。分析：計算