Polygon

Polygon

多邊形是由許多條邊、端點對著端點串接成一圈的圖形。

資料結構

想要紀錄一個多邊形的資訊,有許多種方法,例如:一、按照連接順序把多邊形的邊放到一個陣列裡面;二、按照連接順序把多邊形的頂點放到一個陣列裡面;三、挑一個頂點作為起點,從起點開始按照連接順序把各條邊的長度、邊與邊之間的夾角放到一個陣列裡面。

這幾種方法的空間複雜度都是O(N),N為多邊形的頂點數目,也可以說是邊的數目。

多邊形分類:數學的觀點

多邊形(Polygon):由許多條邊、端點對著端點串接成一圈的圖形。
簡單多邊形(Simple Polygon):所有的邊都不相交,只有相鄰的邊可以相交於一個頂點。
凹多邊形(Convave Polygon):多邊形內部必有兩點連線,穿過多邊形外部。
凸多邊形(Convex Polygon):多邊形內部所有兩點連線,都在多邊形內部。
正多邊形(Regular Polygon):每條邊都一樣長、每個角都一樣大的多邊形。
凸的正多邊形:就是我們熟悉的正三角形、正方形、正五邊形、……。
凹的正多邊形:就是正五角星、正七角星、正八角星、……。
       詳細資料請自行搜尋關鍵字Regular Star Polygon。

UVa 12300

多邊形分類:計算學的觀點

簡單多邊形(Simple Polygon)。所有的邊都不相交,只有相鄰的邊可以相交於一個頂點。

簡單多邊形圍出一個明確的封閉區域。一般的多邊形無法分辨內外,而簡單多邊形可以明確分辨內外。

沿邊走一回,剛好自旋360°;所有外角相加是360°。我們習慣讓頂點順序是逆時針方向,以符合叉積的方向。

單調多邊形(Monotone Polygon)。至少存在一條直線,這條直線的每一條垂直線,與單調多邊形的交點在兩點以下。

換句話說,單調多邊形旋轉至某個角度之後,可以切割成上下兩條鏈,兩條鏈都符合函數定義。單調多邊形可以寫成兩個函數。

換句話說,單調多邊形有兩條鏈,在某個方向上先單調遞增、再單調遞減,彷彿單峰函數。

簡單一句話:單調多邊形是兩條已排序的鏈。

凸多邊形(Convex Polygon)。總是朝同一個方向轉彎。

凸多邊形同時是簡單多邊形和單調多邊形,無論哪種方向都是單調多邊形。數學性質非常強!

正交多邊形(Orthogonal Polygon、Rectilinear Polygon)。每條邊都平行於座標軸,轉彎總是轉90°或270°。

有洞的多邊形(Polygon with Hole)。多邊形的內部有數個洞,洞的內部有數個多邊形。有洞的多邊形,其實不屬於多邊形,其實是數個多邊形。我們可以用順時針代表多邊形、逆時針代表洞。多邊形的聯集、交集、差集,結果常常是有洞的多邊形。

Polygon Area

多邊形面積(Surveyor's Formula)

凸多邊形是特例中的特例,我們試著從凸多邊形開始觀察。

運用分治法的思想,把凸多邊形分割成三角形,就容易計算面積了。取凸多邊形內部一點作為基準點,連線至各個頂點,把凸多邊形切開成許多個三角形。現在我們可以利用叉積,計算每個三角形的面積;然後通通加起來,得到凸多邊形面積。

詳細的步驟是:
一、建立基準點往各個頂點的向量。
二、依照頂點順序,計算相鄰向量的叉積,得到平行四邊形面積。
三、除以二,得到三角形面積。
四、三角形面積通通加起來,得到凸多邊形面積。

步驟三和步驟四可以顛倒,除以二的次數變成只有一次:
三、平行四邊形面積通通加起來,得到凸多邊形面積的兩倍。
四、除以二,得到凸多邊形面積。

事實上,基準點也可以在凸多邊形邊界、甚至是外部。此時叉積的結果有正值和負值,正值恰好對應到總面積,負值剛好對應到多餘面積。通通加起來,正負相消之後,恰好仍是凸多邊形面積。

基準點設定在原點是最方便的,如此一來就不必特地計算基準點往各個頂點的向量,可以直接拿相鄰兩點的座標計算叉積。

此演算法可以推廣到簡單多邊形,甚至是一般的多邊形。時間複雜度為O(N),N為多邊形的頂點數目。

我們可以把結果寫成數學式子,正是知名的行列式公式:

        1    | x1   x2   x3     xN-1   xN   x1 |
area = --- * |    ×    ×    ...      ×    ×    |
        2    | y1   y2   y3     yN-1   yN   y1 |

右下斜線相乘取正號,左下斜線相乘取負號,然後通通加起來,除以二。
如果是逆時針旋轉,求出來為正值。
如果是順時針旋轉,求出來為負值,必須再取絕對值。

一般來說我們會讓多邊形頂點順序為逆時針順序,以求得正值。

UVa 10060 10652 922

多面體體積

與多邊形面積的原理完全一樣。基本單元從三角形變成了四面體。

多邊形形心 / 多邊形重心

重力場均勻的時候,重心退化成為形心。

一群點的重心,是這些點的座標平均值,也就是X座標的平均值、Y座標的平均值。

多邊形的重心,則是多邊形內部暨邊界上所有點的座標平均值。但是不見得是所有頂點的座標平均值。

只有一些特別的多邊形,重心恰好是所有頂點的座標平均值──例如三角形的重心,恰好是三個頂點的座標平均值。

使用分治法的概念,把多邊形切開成許多個三角形,分別計算各個三角形的重心。然後以三角形面積作為權重,計算三角形重心的加權平均值,就得到多邊形的重心。

      o + p0 + p1          o + p1 + p2  
c0 = -------------   c1 = -------------   ...
           3       ,            3       ,

      cross(p0, p1)          cross(p1, p2)
a0 = ---------------   a1 = ---------------   ...
           2         ,            2         ,

            c0 * a0 + ... + c9 * a9
centroid = -------------------------
                 a0 + ... + a9

UVa 10002 132 ICPC 4838

Point in Polygon

判斷一個點是否在凸多邊形內部

很直覺但是不精準的方式,是沿著凸多邊形外圍繞一圈,看看點是不是在每一條邊的同側。若發現叉積皆小於零,即表示點在多邊形內部:若發現叉積等於零,即表示點在凸多邊形上、或在凸多邊形某條邊的延伸線上;若發現叉積大於零,則表示點在凸多邊形外部。

正確的方式,是將點到凸多邊形頂點的各條向量,利用叉積運算判斷是否都往同一方向旋轉,如果都是往同一方向旋轉,則表示點在凸多邊形內部;如果中途出現反方向旋轉,則表示點在凸多邊形外部;如果中途出現叉積為零的情況,表示點在凸多邊形上,而且就在對應的邊上。

時間複雜度為O(N),N為凸多邊形的頂點數目。

UVa 109 361 476 477 478 10078 10291 10321

不斷查詢一個點是否在凸多邊形內部

凸多邊形內任選一點作為原點(例如所有點的平均值),然後依角度大小排序凸多邊形的所有頂點。之後就可以用Binary Search找出給定的點在哪個夾角之內,最後判斷點是不是在此夾角構成的三角形裡面。

O(NlogN)預處理,O(logN)求答案。

UVa 12048

判斷一個點是否在簡單多邊形內部

從給定點開始,往隨便一個方向(實作時習慣水平往右)射出一條無限長射線,看看穿過多少條邊。如果穿過偶數次,表示點在簡單多邊形外部;如果穿過奇數次,表示點在簡單多邊形內部。

要小心處理射線穿過頂點、射線與邊重疊的情況。也要小心處理點在多邊形邊界上的情況。

時間複雜度為O(N),N為簡單多邊形的頂點數目。

UVa 634 11030 10348

不斷查詢一個點是否在簡單多邊形內部

http://en.wikipedia.org/wiki/Point_location

Visibility of Polygon

一個點的可見區域,被一個凸多邊形遮擋

點在凸多邊形內部。一定可以看見整個凸多邊形。回顧一下凸多邊形的定義:多邊形內部所有兩點連線,都在多邊形內部。令其中一點是給定的點,令另外一點是可見的點,兩點之間一定不會被凸多邊形遮擋。

點在凸多邊形上面。如果歸類於內部,可見區域就是整個凸多邊形;如果歸類於外部,可見區域的邊界,就是該點碰觸的邊的延長線。

點在凸多邊形外部。上下兩條切線圍住的區域受到影響,可見區域變成切線與凹面圍住的區域。找切線很簡單:建立點到凸多邊形各頂點的向量,運用叉積找出轉至最右、轉至最左的向量。

時間複雜度為O(N)。

UVa 746

一個點的可見區域,被一個簡單多邊形遮擋

點在多邊形內部。被一個簡單多邊形遮擋的可見區域,也是簡單多邊形。採用Incremental Method,從一個可見的頂點開始,依照逆時針順序,一次讀入一條邊,隨時更新當下的可見區域。一共分成六種情況:

一、可見區域直接增加一條邊。
二、可見區域增加一條割線。
  割線會撞到多邊形以後的邊,屆時就能求得割點。
三、可見區域切除看不見的部分,改為一條割線。
  割線會撞到可見區域以前的邊,必須倒退找割點。
四、同三。
五、同一。
六、同二。

http://arxiv.org/pdf/1111.3584v2.pdf

倒退找割點,頂多倒退N條邊。時間複雜度為O(N)。

附帶一提,如果預先找到兩個以上可見的頂點,就可以切斷成鏈,實施Divide and Conquer。

點在多邊形上面、外部。原理相同,不再贅述。

【待補程式碼】

UVa 10907

一個點的可見區域,被數個凸多邊形遮擋

點在凸多邊形外部、凸多邊形們都不相交,才有討論價值。

處理大量幾何資料,最常見的手法就是掃描線和旋轉卡尺了。此處採用旋轉的掃描線,以給定點為基準,依照極角大小掃描所有頂點。當下掃中的點,如果被前一點的鄰邊遮擋,就馬上刪除此點。時間複雜度O(NlogN)。

可以加速到O(N+HlogH)。牽涉到直線與凸多邊形交點的演算法。

一個點的可見區域,被數個簡單多邊形遮擋

http://www.visilibity.org/

採用旋轉的掃描線。先找到每個多邊形的兩條切線(以及到切點的距離)。所有切線按照角度排序之後,依序處理每個區間即可,用一棵二元樹動態維護每個多邊形的可見順序。時間複雜度O(NlogH),N是所有頂點的數目,H是所有多邊形的數目。

比較容易實作的方式。先找到視點到各頂點的射線(以及到頂點的距離)。所有射線按照角度排序之後,依序處理每個區間即可,用一棵二元樹動態維護每條邊的可見順序。時間複雜度O(NlogN)。

Kernel of Polygon

凸多邊形的核

位於多邊形內部,可以看到整個多邊形內部的地方,稱作「核」。「核」是設置監視攝影機、地標、廣告看板的好地方。「核」可能是風水最旺的地方。

一個多邊形的核,其實就是所有邊的「半平面交集」。一個多邊形的核,可能是一個凸多邊形、一條線段、一個點、空集合。

凸多邊形的核,顯然就是原本的凸多邊形。

簡單多邊形的核

直接套用半平面交集演算法,時間複雜度為O(NlogN)。借用Visibility of Polygon演算法的手法,時間複雜度得壓至O(N)。

ICPC 2512 UVa 588

Star-shaped Polygon

「星狀多邊形」就是擁有核的多邊形。與旋轉的掃描線有一點點關聯。

注意到「Star-shaped Polygon」與「Star Polygon」是完全不一樣的東西。

ICPC 3616

Polygon Offsetting(Under Construction!)

Polygon Clipping(Under Construction!)

用直線裁切多邊形

直接套用半平面交集演算法,時間複雜度為O(N^2)。

http://en.wikipedia.org/wiki/Sutherland–Hodgman_algorithm

UVa 10867 10974

用直線裁切凸多邊形

UVa 11989

Line-Polygon Intersection(Under Construction!)

判斷直線與凸多邊形相交

採用Incremental Method,拆解凸多邊形成為許多邊,變成判斷直線與大量線段相交。採用窮舉法,時間複雜度為O(N)。

不適合採用「Segment Intersection」,畢竟不必判斷凸多邊形自身的邊是否相交。

不斷查詢直線是否與一個凸多邊形相交

極大/極小頂點查詢 O(logN)
直線是否相交查詢 O(logN)

ICPC 4837

判斷直線與簡單多邊形相交

一樣是窮舉法。沒什麼特別的。

不斷查詢直線是否與一個簡單多邊形相交

說實在話,我也不會。也許是「Bounding Volume Hierarchy」資料結構。

Polygon Intersection(Under Construction!)

兩個凸多邊形的交集

半平面交集 O(NlogN)
平移掃描線 O(N)
交互前進 O(N)
外側向量超車擋在內側向量前面,車頭向內。
任選兩向量開始
先繞一圈找到交點
接下來再繞一圈,內側有前進的話,就會漸漸圍出交集
最後到達最初的交點時,結束
要小心退化的情況。

UVa 137 10321

兩個簡單多邊形的交集、聯集、差集

求出所有線段交點的演算法,略作修改。O(NlogN + K)。

UVa 805

Minkowski Sum(Under Construction!)

【待補文字】

Pairwise Sum的加強版,引入面積的概念。

改良版摺積,只在特定區域實施摺積。

minxxxsum 替pattern先取一個基準點,patter擺正,基準點延著障礙物外圍走一圈
          不是均勻擴張

dilation  pattern以各種姿態放在障礙物外圍
     是均勻擴張
          pattern可以簡化成一條直線、長度為直徑?