iT邦幫忙

0

[筆記本: 演算法] 多邊形篇 Part 1 - Simple Polygon 簡單多邊形

多邊形

多邊形定義為各點互相直線連接所圍成的無開口圖形。
多邊形又包含以下幾個種類:

  • Simple Polygon 簡單多邊形
  • Convex Polygon 凸多邊形
  • Concave Polygon 凹多邊形

https://ithelp.ithome.com.tw/upload/images/20181217/201136222YDe5rsAaC.png

簡單多邊形

簡單多邊形必須符合多邊形條件且任何一邊都沒有交叉。
但如何以N點建造一個簡單多邊形並且確定任何一邊都沒有交叉?

Naïve Method 樸素法

簡單方法利用點列表的順序連接各點,在與最後一點與第一點連接完成多邊形。
因為這種方法是隨機依照列表順序(任何一種列表)連接各點,因此畫出來的圖形並無絕對。
下圖為兩種成功畫出簡單多邊形的例子。
https://ithelp.ithome.com.tw/upload/images/20181217/20113622v5PI99eK6u.png

結論

這種方法在大多數例子都無法成功畫出簡單多邊形,因為這種方法沒有一定的點對點連接順序。
下圖為非簡單多邊形的例子。
https://ithelp.ithome.com.tw/upload/images/20181217/201136227bAYIFeodS.png

Circular Scan 圓型掃描

圓型掃描是在所有點中選擇一個中心點進行掃描,每次掃描到得點加入列表中,如果同一條線上兩個以上的點,則以離中心點最近的優先加入列表。
雖然隨機選擇中心點有可能成功建立簡單多邊形,但也可能錯誤選擇中心點。
下圖為隨機選擇一點(非從點列表中選擇)為中心點的例子。
https://ithelp.ithome.com.tw/upload/images/20181217/201136224v2fy9f3L0.png

如果加以分析,會發現隨機選擇一點為中心點,還是會無法讓第一點及最後一點正確連接。
https://ithelp.ithome.com.tw/upload/images/20181217/20113622r4CYfIMsgs.png

為了避免第一點及最後一點錯誤連接,中心點必須選擇點列表的一點。
但是隨機選擇,還是無法確保所建立的多邊形為簡單多邊形。
因此,可以選擇在最大或最小X值的點或是在最大或最小Y值的點。
下圖為選擇最大X值的點。
https://ithelp.ithome.com.tw/upload/images/20181217/20113622IHj5Z8Oj5c.png

以中心點加以分析會發現,第一點及最後一點所延伸到圓的直線,會是扇形的兩邊。
https://ithelp.ithome.com.tw/upload/images/20181217/20113622BmKlmXHtVT.png

結論

如果隨機選擇中心點或是點列表中隨機一點,都無法確保所建立的多邊形為簡單多邊形。
但是選擇在最大或最小X值的點或是在最大或最小Y值的點,可以改善並建立簡單多邊形

傳送門:[筆記本: 演算法] 多邊形篇 Part 2 - Convex Hull 凸包
傳送門:[筆記本: 演算法] 多邊形篇 Part 3 - Furthest Pair of Points 最遠兩點配對


尚未有邦友留言

立即登入留言