和圓有關(guān)離散化方法

1、和圓有關(guān)離散化方法引言：一道經(jīng)典的問題引言：一道經(jīng)典的問題lN個矩形，求他們的面積并。l解決方法：離散化。l取每個矩形的上下邊界，將平面分為若干部分，然后計算每一部分的面積。引言：新的問題引言：新的問題l由于矩形的邊界為折線，如果我們用折線的轉(zhuǎn)折點(diǎn)作為分界點(diǎn)，則折線被化簡為許多線段。所以離散化法取得了成功。l如果需要統(tǒng)計的并不是矩形，而是某些曲線圖形，怎么辦？l對于曲線來說，根本沒有所謂的轉(zhuǎn)折點(diǎn)，傳統(tǒng)的離散化法似乎對這一類問題失效了。l而梯形和弓形的面積很容易求出l但如果增加一些其他的分割線，我們發(fā)現(xiàn)，整個圖形由若干梯形和弓形構(gòu)成。引言：新的問題引言：新的問題l事實(shí)上，如果我們對于劃分后每一部

2、分的性質(zhì)要求不那么嚴(yán)格，劃分還是可以繼續(xù)下去的。l如圖，圖形被劃分為5部分，初看特征不明顯。圓的離散化算法圓的離散化算法l算法的一般步驟：根據(jù)問題將平面中的圓分割成若干區(qū)域，使每個區(qū)域具有一定簡單的粗粒屬性。一般可用直線分割。根據(jù)屬性確定區(qū)域內(nèi)圓的具體算法，計算每個區(qū)域中結(jié)果。綜合每個區(qū)域的結(jié)果，給出問題的最終答案。l圓的離散化算法關(guān)鍵在于保證區(qū)域內(nèi)數(shù)據(jù)在整體上易于處理。算法應(yīng)用實(shí)例算法應(yīng)用實(shí)例l以上便是離散化法在圓的計算幾何問題中最基本的應(yīng)用。而這里將通過兩道例題詳細(xì)說明。l例1 Dolphin Pool (Tehran 2000)l例2 Empire strikes back (ural

3、1520)Dolphin Pool (Tehran 2000)l給定N(N=20)個圓的圓心坐標(biāo)(xi,yi)和半徑Ril求平面內(nèi)在圓外的封閉區(qū)域的個數(shù)。l例如：如下四個圓構(gòu)成一個圓外的封閉區(qū)域l沒有任何兩個圓相切，且沒有任何一個圓的圓心在另一個圓內(nèi)。封閉區(qū)域初步分析初步分析l盡管圓的位置有一定的限制，但可能的情況還是很多的，我們希望有一個通用的算法來解決所有情況而不分類討論，避免增加編程復(fù)雜度和錯誤幾率。l由于輸入輸出都是整數(shù)，似乎題目對于精度的要求不高，并且坐標(biāo)的范圍較小(x,y=1000)。于是可以使用一個基于floodfill的算法。基于基于Floodfill的算法概述的算法概述l在原

4、圖中建立點(diǎn)陣。l標(biāo)記所有在圓內(nèi)的點(diǎn)為已訪問。l使用深度優(yōu)先遍歷(DFS)求連通塊數(shù)l連通塊數(shù)減1即為答案l可以看到，這個算法的效率和正確性都由點(diǎn)陣的密集程度決定。l而對于這道題目的時限來說，這個算法遠(yuǎn)遠(yuǎn)不能達(dá)到要求，因此我們需要改進(jìn)算法。 第一次離散化第一次離散化l考慮點(diǎn)陣中的每一橫行，我們發(fā)現(xiàn)圓在每一橫行上覆蓋的一定是一個連續(xù)區(qū)間。l因此，可以僅記錄每一個圓在當(dāng)前橫線上覆蓋的區(qū)間而不記錄每個點(diǎn)具體的被覆蓋情況。l考慮平面內(nèi)的一條平行于x軸的直線?？梢院苋菀椎挠嬎愠雒恳粋€圓在其上覆蓋的區(qū)間。第一次離散化第一次離散化區(qū)間合并區(qū)間合并l接下來，將所有的被覆蓋區(qū)間合并。這一問題需要應(yīng)用到基本數(shù)據(jù)結(jié)構(gòu)

5、棧，可以在線性時間復(fù)雜度內(nèi)解決。l區(qū)間合并完成后，可以得到所有未被覆蓋的區(qū)間。第一步離散化第一步離散化圖論模型圖論模型l建圖，每個未覆蓋區(qū)間為一個頂點(diǎn)，相鄰兩條橫線上的區(qū)間如果相交，則在它們之間連一條邊。然后判斷在建成的圖中有多少個連通塊。l判斷圖中的連通塊數(shù)量可以使用按層次遍歷的方式減少空間需求。仍存在的問題仍存在的問題l經(jīng)過初步的離散化，上述算法的正確性和速度都有很大提高。但由于ACM競賽要求程序必須通過全部數(shù)據(jù)，而該算法對于某些極限數(shù)據(jù)的精度仍不能令人滿意，因此還有進(jìn)一步改進(jìn)算法的必要。第二次離散化第二次離散化l仔細(xì)觀察程序的運(yùn)行，我們發(fā)現(xiàn)它似乎作了許多無用的工作，如下圖：l我們一眼可知

6、，下圖中所有的區(qū)間同屬于同一連通塊。但是我們的程序卻為了得到這一結(jié)果在不斷的迭代。l于是，我們有了一個新的想法：跳過無用的橫行。第二次離散化第二次離散化l事實(shí)上，區(qū)間之間的繼承關(guān)系在大多數(shù)時候并沒有發(fā)生改變，僅在少數(shù)時刻才會有所改動：一個圓新出現(xiàn)時，將一個區(qū)間分為兩半。一個圓最下端，兩個區(qū)間合并為一個。兩圓相交，一個區(qū)間逐漸減小直至消失。兩圓相交，一個新的區(qū)間生成。l這樣，我們可以求出所有的點(diǎn)事件，并模擬區(qū)間的生長消亡，從而求出最終答案。l但是，如果完全按照上述想法編程實(shí)現(xiàn)，編程復(fù)雜度非常高。事實(shí)上，我們可以考慮一種懶惰的實(shí)現(xiàn)方式。第二次離散化第二次離散化圖示圖示點(diǎn)事件小結(jié)小結(jié)l至此，本題已被

7、完美解決，時間復(fù)雜度為O(N3)。l回顧我們得到算法的步驟：根據(jù)題目描述得到一種簡單的算法。通過離散化不斷將其時間復(fù)雜度降低，并將精度提高。l可以看到，使用了離散化法后，我們輕易地得到了一個簡單而優(yōu)秀的算法。例例2 Empire strikes back(ural 1520)l平面中有1個大圓和N(N=300)個小圓，大圓圓心為(0,0)，小圓圓心都在大圓內(nèi)。所有小圓半徑相同。l求使所有小圓能覆蓋整個大圓的小圓最小半徑。初步分析初步分析l由于題目僅需求出一個實(shí)數(shù)，因此我們考慮使用二分法求得答案。l在已知小圓半徑的情況下，我們所需要做的工作僅僅是判斷大圓是否被小圓完全覆蓋。試探性離散化試探性離散

8、化l如果使用和例1相同的離散化策略，得到的時間復(fù)雜度為O(N3*k)，k為二分的次數(shù)，這個時間復(fù)雜度太高了！l之所以會出現(xiàn)離散化失敗的情況，是因?yàn)槲覀儧]有透徹的分析問題。l由于已經(jīng)二分了答案，所以問題已被轉(zhuǎn)化為一個判定性問題，而我們?nèi)允褂迷冉鉀Q計數(shù)性問題的思路解題，必然無法設(shè)計出高效的算法。l當(dāng)然，這一處理并不能使算法的時間復(fù)雜度有所改進(jìn)。但是，如果整體觀察所有特殊點(diǎn)，會發(fā)現(xiàn)它們所組成的圖形正好是所有小圓分別向左向右移動一小步得到新的圓之和。l這樣我們可以根據(jù)這一特性進(jìn)行離散化。離散化算法改進(jìn)離散化算法改進(jìn)l由于題目僅需我們判斷一條橫線是否被完全覆蓋，因此取特殊點(diǎn)似乎是一個不錯的想法?？紤]橫

9、線上所有關(guān)鍵點(diǎn)(線段的左右端點(diǎn))，并取它們左右兩端距離非常接近的點(diǎn)作為特殊點(diǎn)。如果所有的特殊點(diǎn)都被覆蓋，則整條橫線一定被完全覆蓋。第二次離散化第二次離散化l注意到，每一個圓在向左向右偏移后，得到的新的圓一部分在原先的圓內(nèi)，可以不做考慮。而向左向右偏移后得到的圖形之和與原先的圓非常相近，可以認(rèn)為是相同的。l于是問題轉(zhuǎn)化為，其他N-1個小圓在這個小圓上覆蓋的邊界是否完全覆蓋了大圓在這個小圓上覆蓋的邊界。l這和例1中第一步離散化時得到的問題非常相似，可以使用類似的方法解決。時間復(fù)雜度分析時間復(fù)雜度分析l算法總復(fù)雜度 O(N2logN*k)二分的復(fù)雜度 O(k)區(qū)間排序的復(fù)雜度O(NlogN)區(qū)間合并

10、的復(fù)雜度O(N)枚舉N個圓O(N)l事實(shí)上，如果采用一些其他的小優(yōu)化，可以將算法的復(fù)雜度進(jìn)一步降低為O(N2logN+NlogNk)小結(jié)小結(jié)l回顧我們得到最終算法的步驟：一開始，我們分析問題，得到了一種簡單的算法。然后，我們嘗試?yán)秒x散化法對其進(jìn)行優(yōu)化，但傳統(tǒng)的離散化得到的時間復(fù)雜度十分不理想。于是我們進(jìn)一步分析問題的特性，并通過轉(zhuǎn)化問題的方式得到了一個新的離散化法，最終完美解決了此題。l由此可見，離散化法并不僅僅是把圖形按照橫縱坐標(biāo)劃分為若干區(qū)域。對于同一個問題，不同的離散化法得到的算法效率相差甚遠(yuǎn)?？偨Y(jié)及討論總結(jié)及討論l離散化法作為一種較為樸素的處理方法，可以解決多數(shù)與圓有關(guān)的計算幾何問題

11、。l成功的關(guān)鍵是要把握區(qū)域劃分的精細(xì)程度：過細(xì)區(qū)域劃分，單元內(nèi)的計算簡單，但整合復(fù)雜度增加。區(qū)域劃分過粗，會使單元內(nèi)的計算無法實(shí)現(xiàn)。l雖然這里分析的是圓，但很容易推廣到其他曲線的計算幾何問題。區(qū)間合并動畫區(qū)間合并動畫l每次插入一個區(qū)間時，先察看棧頂區(qū)間是否和即將進(jìn)棧的區(qū)間相交，如果相交則將棧頂區(qū)間出棧和新插入的區(qū)間合并，然后繼續(xù)察看棧頂區(qū)間，直至棧頂區(qū)間和新插入的區(qū)間不相交或棧已被清空。l然后新的區(qū)間進(jìn)棧。1，23，52，91，91，9一些其他的小優(yōu)化一些其他的小優(yōu)化l事實(shí)上，如果在排序時，按照區(qū)間的中點(diǎn)的極角進(jìn)行排序，則區(qū)間的序和小圓半徑長度無關(guān)，排序可以在預(yù)處理時完成，復(fù)雜度可降為O(N2 (logN+k)。l由于每個小圓被完全覆蓋所需要的最小半徑都是相互獨(dú)立的，因此可以認(rèn)為它是一個常數(shù)，而我們所求出的就是這個常數(shù)的大小。因此可以在枚舉每個圓的時候，先判斷一下它在當(dāng)前