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、Axis-parallel Polygon、Axis-aligned 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

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

凸多邊形內任選一點作為基準點(例如最低最左頂點)。凸多邊形的所有頂點,按照角度排序。以二元搜尋找出給定點在哪個夾角之內,以外積判斷給定點是否在此夾角構成的三角形裡面。

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

UVa 12048

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

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

要小心處理的情況:射線穿過頂點、射線與邊重疊。

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

UVa 634 11030 10348

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

梯形剖分。掃描線由下往上移動,每當遇到頂點,就切割一塊垂直區間。針對一塊垂直區間,掃描線由左往右移動,每當遇到邊,就切割一塊水平區間。

首先二元搜尋垂直區間,然後二元搜尋水平區間,就能知道水平往右射線穿過多少條邊。

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

多邊形拆成邊,樹套樹。第一層線段樹,依照Y區間儲存邊;第二層二元搜尋樹,依照X座標排序邊。涵蓋射線起點的線段樹節點們,各自查詢二元搜尋樹,就能知道水平往右射線穿過多少條邊。

O(Nlog²N)預處理,O(log²N)求答案。

二元搜尋樹改成串列。涵蓋射線起點的線段樹節點們,各自窮舉串列,就能知道水平往右射線穿過多少條邊。

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

Line–Polygon Intersection

判斷直線是否與凸多邊形相交

窮舉凸多邊形每一條邊,判斷相交。時間複雜度O(N)。

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

在直線的垂線方向上,尋找凸多邊形的兩個極點,然後判斷是否在直線兩側。

凸多邊形的所有頂點暨下一條邊,按照角度排序。角度範圍是0°到360°,形成嚴格遞增數列。直線的垂線化成兩個角度(相差180°),分別二元搜尋,得到兩個極點。實作時,不必計算實際角度,改用點積與叉積來比較角度大小。

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

ICPC 4837

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

窮舉簡單多邊形每一條邊,判斷相交。時間複雜度O(N)。

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

多邊形拆成線段。線段存入資料結構Uniform Grid、Quadtree、KD-Tree、BVH、R-Tree,以便快速查詢相交。

O(N²)預處理,O(N)求答案,實務上遠少於N²和N。

Point–Polygon Distance

點與凸多邊形的距離

窮舉凸多邊形每一條邊,計算距離。時間複雜度O(N)。

我們無法使用二元搜尋。點與凸多邊形各點的距離們,點與凸多邊形各邊的距離們,沒有遞增遞減性質。

不斷查詢點與凸多邊形的距離

目前沒有快速的演算法。只能使用枚舉法。

網路上可以找到一個錯誤的演算法,只能求出點與凸多邊形各點的最短距離:

一、凸多邊形頂點,建立Voronoi Diagram,以便快速查詢最近頂點。二、Voronoi Diagram,建立Point Location資料結構,以便快速查詢所屬區域。

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

Arrangement

Arrangement

大量線條,形成大量區域,稱作「布置」。

線條可以是直線、線段、曲線。

UVa 754 1708

Planar Straight Line Graph

尋找交點,截斷線條,以便建立點與邊。

形成「平面直線圖」:點不重疊、邊不相交、邊呈直線。

名稱源自圖論的「平面圖」:點不重疊、邊不相交。

Half-edge

緊接著,一條無向邊改成兩條有向邊,以便建立界與面。

這種有向邊,俗稱「半邊」。

資料結構

布置包含四種元件:點、邊、界、面。

兩點得一邊,多邊得一界,多界得一面。

四種元件習慣拆開處理,各自採用適合的資料結構。

資料結構:點

大量資料的資料結構「Array」。

點:座標們

資料結構:邊

圖的資料結構「Adjacency Lists」。

點:出邊們(依照角度排序)
邊:反向邊、起點、終點

資料結構:界

多邊形的資料結構「Array」。

界:擁有的邊(外界逆時針、內界順時針)
邊:所屬的界、上一條邊、下一條邊

一個界擁有多條邊,通通串連在一起。兩種方式:

一、主角是點,窮舉轉角。

二、主角是邊,繞行邊界。

資料結構:面

互斥集的資料結構「Disjoint-sets Forest」。

面:擁有的界

一個面擁有多個界,通通聯集在一起。三種方式:

一、射線法:每個外界的極點(例如最左點),往外切一刀(例如水平往左射線),找到第一個擊中的界,屬於同一面。

二、平移的掃描線:原理同上。從左往右掃描,維護一棵線段樹,以便快速找到第一個擊中的界。因為最左點已排序,所以Disjoint-sets Forest總是添加樹葉。Disjoint-sets Forest簡化成Disjoint-set Array,聯集的時間複雜度簡化成O(1)。

三、設定一個極大的正方形邊界,有洞多邊形切開為簡單多邊形:原理同上。一個面只有一個界。雖然界與面數量翻倍,但是實際上只多了幾條邊,而且也不需要Disjoint-sets Forest了。

【待補程式碼】

資料結構:點邊界面(Doubly Connected Edge List)

DCEL是四種元件的資料結構的豪華總匯。

DCEL原本只包含點與邊,但是實務上又追加了界與面。

一、每個點紀錄所有出邊。以便取得鄰點。
二、每個點排序所有出邊。平面圖才有的特性。
三、每條邊紀錄所屬面。以便取得鄰面。
四、每條邊紀錄反向邊。以便取得另一個鄰面。
五、每個界紀錄所有邊。以便判斷內外。
六、每個面記錄所有界。以便判斷區域。
點:座標、出邊們(逆時針順序)
邊:反向邊、起點、終點、所屬的界、上一條邊、下一條邊、所屬的面
界:起始邊(外界逆時針、內界順時針)、下一個界
面:外界(只有一個)、內界們

求得布置

掃描線。「Segment Intersection」略作修改。時間複雜度O((N+K)logN),N是線段端點數量,K是交點數量。

Point Location

不斷查詢一個點在哪個區域,區域是三角剖分。

散步法:任選一個三角形、其一條邊、其一個點,作為起點,朝向目標前進,穿越相鄰三角形。

O(N)預處理,O(K)求答案。K是交點數量。

Kirkpatrick's Algorithm:重新三角剖分。我沒有學會。

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

不斷查詢一個點在哪個區域,區域是凸分割。

我沒有研究。

不斷查詢一個點在哪個區域,區域是簡單多邊形。

解法如同「不斷查詢一個點是否在簡單多邊形內部」。

所有多邊形拆成線段。從給定點開始,往隨便一個方向射出一條射線(例如水平往右射線),找出最先擊中的簡單多邊形。

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

UVa 1075 ICPC 4125

不斷查詢一個點在哪個區域,區域是有洞多邊形。

有洞多邊形改成簡單多邊形,所有多邊形拆成線段。

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

UVa 12310

Polyhedron

Polyhedron

「多面體」。許多個面,邊緣對著邊緣,包覆成一圈的圖形。

三種元件:點、邊、面。

點的資料結構

約定俗成是陣列:每個格子儲存點座標,三個浮點數XYZ。

查詢點編號、查詢最近點:額外使用區域資料結構,諸如Uniform Grid、Quadtree,請見本站文件「Region」。

面的資料結構

約定俗成是陣列:每個格子儲存多邊形頂點的編號。

查詢面編號、查詢最近面:額外使用區域資料結構,諸如BVH、R-Tree,請見本站文件「Region」。

排序所有面:額外使用位置排序資料結構BSP Tree,請見本站文件「Position」。

邊的資料結構

約定俗成是DCEL:每個點紀錄所有鄰邊(鄰點編號)、每個點排序所有鄰邊(逆時針順序)、每條邊紀錄反向邊、每條邊紀錄所屬面。請見本站文件「Arrangement」。

查詢邊編號:查詢面編號之後,檢查所有鄰邊。

Polytope

Polytope

「多胞形」。多邊形推廣到任意維度。

點、線段、多邊形、多面體,分別是零一二三維的多胞體。

Simplex

「單體」、「單形」。每個維度的最基礎的多胞形。

點、線段、三角形、四面體,分別是零一二三維的單體。

Simplicial Complex

「單體複形」、「複形」。一大堆單體。可以相互銜接,銜接之處也是單體。