rectangle

擺得很正的矩形,四個邊都平行於座標軸

經過數學課程洗禮,大家看到矩形都是直覺想到長與寬。然而在計算學當中,我們傾向記錄左下角座標(X座標、Y座標的下界)與右上角座標(X座標、Y座標的上界)。

就算矩形退化成線段、點,這種記錄方式也不會有問題。

UVa 460 191

矩形相交

要判斷矩形相交相當麻煩,相交的情形有許多種。

逆向思考,事情就變得容易多了:判斷矩形不相交!以第二個矩形作為基準,第一個矩形完全落在其左方、右方、下方、上方,就是不相交。

如果是空心矩形,那麼還得偵測第一個矩形是不是被第二個矩形框住,以及第二個矩形是不是被第一個矩形框住。

大量矩形交集,之一

兩個矩形的交集還是矩形(可能退化成線段、點)。運用incremental method進行推理,大量矩形的交集當然還是矩形。

採用incremental method,一次讀入一個矩形,不斷更新交集。時間複雜度O(N),N是矩形數量。

大量矩形交集,之二

大量矩形聯集,之一

將聯集區域切割為數個矩形。採用incremental method,一次讀入一個矩形,不斷更新聯集。

下面這段程式碼僅計算聯集面積。至於聯集多邊形,就請讀者自行研究了。

時間複雜度的分析比較特別。每次更新聯集,都會增加一些矩形、減少一些矩形,所以很難估計矩形數量。

以宏觀視角觀察矩形數量。考慮所有矩形頂點,X軸離散化、Y軸離散化,最多產生(2N-1)×(2N-1)個格子。聯集區域一定是由這些格子構成,聯集區域的格子數量一定小於等於(2N-1)×(2N-1)。更進一步,聯集區域切割出來的矩形數量,一定小於等於格子數量!

更新聯集,也就是檢查聯集區域切割出來的每一個矩形,時間複雜度O(N²)。一共更新N次,總時間複雜度O(N³)。

大量矩形聯集,之二

一、X軸離散化、Y軸離散化。O(NlogN)
  最多產生(2N-1)×(2N-1)個小格。
二、窮舉每個小格、窮舉矩形,判斷每個小格屬於哪個矩形。O(N³)

UVa 870 221 688

大量矩形聯集,之三

一、X軸離散化,附帶矩形左右邊界資訊。O(NlogN)
二、Y軸離散化。O(NlogN)
三、每一個橫條,由左往右掃描,判斷每個小格是否在矩形裡。O(NN)
  以矩形上下邊界,判斷其左右邊界是否穿過當前橫條。
  遇到矩形左邊界+1,遇到矩形右邊界-1。

大量矩形聯集,之四

觀察相鄰的橫條。相鄰的橫條的聯集區域變化,與矩形的消失、出現密切相關。我們可以運用動態的資料結構,儲存第一個橫條的聯集區域,然後逐步更新每一個橫條。

一、依序處理每個橫條。
  首先建立第一個橫條的線段樹,節點附帶sum資訊。
  (預先離散化X軸。O(NlogN))
二、一次做一個橫條。看看哪些矩形離開了/進來了,更新線段樹。
  (預先離散化Y軸,附帶矩形上下邊界資訊。O(NlogN))
三、從頭到尾總共N個矩形離開了/進來了,線段樹更新總共2N次。O(NlogN)
  每做完一個橫條,樹根的sum就是該橫條之內的聯集區域面積總和。
  每做完一個橫條,就將sum累加至聯集面積。

ICPC 4758

Klee's measure problem

推廣到高維度。

circle

圓形

記錄圓心、半徑。

UVa 10180 10425 10674 ICPC 4120

圓形相交

判斷相交:圓心距大於等於半徑差、小於等於半徑和。

求得交點:一、餘弦定理,用半徑、圓心距求得半個扇形角。二、圓心向量,順時針和逆時針旋轉,縮放成半徑長度。

大量圓形聯集

UVa 10969 ICPC 3532

triangle

三角形

記錄三個頂點,以逆時針順序記錄。

UVa 11122 11275 11836

大量三角形聯集

我沒有研究。

ICPC 3809

convex set

凸集合

內部所有兩點連線,不會穿過外部。

Helly's theorem

一、一堆凸的東西,交集也是凸的。

二、二維的情況下,任選三個一組皆有交集,則全部合起來也有交集。三維的情況下,任選四個一組皆有交集,則全部合起來也有交集。以此類推。

大量凸集合交集(alternating projection)

任取一點,垂直投影(最短距離)到凸集合邊界,每個凸集合依序輪流。不斷投影,最後得到凸集合交集的邊界上一點。