複雜多邊形是指多邊形的一種分類。 指具有邊自我相交或者有破洞的多邊形,或者說其邊除了相鄰邊在頂點處相交之外,也存在其他互相相交的邊。 這個概念與簡單多邊形相對。 複雜多邊形的英語為Complex polygon,這個詞彙則有多種的定義,一種是上述複雜多邊形的定義,另一種是位於複數空間複多邊形[註 1]

具有自我相交邊界的複雜五邊形,是複雜多邊形的一個例子

複雜多邊形這個概念常用於計算機科學中,因為複雜多邊形的填色相較於簡單多邊形複雜得多,需要使用特殊的演算法才能完成對複雜多邊形的內部上色。

複雜多邊形中,自相交偶數次的部份算做多邊形的外部,[1]以五角星為例,五角星中央交出的五邊形不算做五角星的內部,換句話說,即是此複雜多邊形的孔洞。[2]

定義

編輯

在數學上,複雜多邊形定義為具有邊自我相交或者有破洞的多邊形。而在計算機科學中,定義稍有不同。在計算機科學中,複雜多邊形除了邊自我相交外,還代表著該多邊形可能由多個封閉的邊界組成的多邊形,其中一個邊界會形成該多邊形主要邊界的孔洞。[2]

除此之外,在計算機科學中的複雜多邊形也會考慮邊自我相交的情況[1],此時對於這個多邊形頂點數的計算,僅會計算邊的端點,不會計算邊與邊相交所產生的頂點。

性質

編輯

涉及到有界區域的積分和閉合線積分的公式在複雜多邊形區域「由內而外」部分以次數計算內外部時(最內部為實際上的內部,向外遇到一個邊界時視為外部,再遇到一個邊界時視為內部以此類推)仍然適用。

複雜多邊形的孔洞可以來自自相交所形成的區域,[3]也可以來自位於最外周界內部的邊界或子多邊形。位於主要邊界內部的較小作為孔洞的子簡單多邊形邊界,其內角等同於整個複雜多邊形的外角,其360度減內角的值才是整個複雜多邊形的內角,所以位於複雜多邊形主要邊界內部的較小簡單多邊形的內角(對於整個複雜多邊形而言)通常是優角

在複雜多邊形周圍移動時,頂點處轉向的總量可以是360度()的任意整數倍,例如五角星頂點處轉向的總量為720度,而有角度的「8」頂點處轉向的總量為0度。

複合多邊形

編輯

複合多邊形是指由多個單獨封閉的相連線段(子多邊形)所組成的多邊形,例如六角星由兩個獨立的三角形組合而成。[4]複合多邊形都是複雜多邊形,若組合的方式是一個大多邊形包含一個小多邊形,即大多邊形內部有一個較小的多邊形(例如回字形),則內部多邊形視為整個複合多邊形的孔洞,也就是一個有「破洞」的多邊形。

推廣

編輯

複雜多面體

編輯
 
四面半六面體是一種複雜多面體

複雜多邊形的概念也可以推廣到三維空間中。對應的概念是複雜多面體。複雜多面體代表存在面有自我相交情形的多面體。[5]所有複雜多面體都是非凸多面體。星形正多面體都是複雜多面體。與複雜多面體相對的概念是簡單多面體

參見

編輯

註釋

編輯
  1. ^ 此處的complex polygon中,complex代表複數(Complex Number、 ),因此稱為複多邊形複數空間多邊形(簡稱複數多邊形)。然而在計算機圖形學中, 也有一個稱為complex polygon的概念,但是在這種情況下,complex並不意味著「複數域上的結構」,因此不會將其稱為複多邊形。 一般數學或幾何學也有這種概念,尤其在討論多邊形是否存在自相交的情況,在這種情況下complex polygon應被稱為複雜多邊形,這意味著該多邊形存在著自相交的情況,即simple(非簡單閉合曲線),因此稱為complex(意味著複雜或不簡單)。 而又有一類多邊形稱為複合多邊形,其表示多個多邊形組成的複合圖形,其名稱不應與複多邊形複雜多邊形混淆。

參考文獻

編輯
  1. ^ 1.0 1.1 Paul Bourke. Polygons and meshes:Surface (polygonal) Simplification. 1997 [2016-05]. (原始內容存檔於2019-12-31). 
  2. ^ 2.0 2.1 Rae Earnshaw, Brian Wyvill (Ed); New Advances in Computer Graphics: Proceedings of CG International 』89, Springer, 2012, page 654.
  3. ^ Galetzka, Michael and Glauner, Patrick O. A simple and correct even-odd algorithm for the point-in-polygon problem for complex polygons (PDF). arXiv preprint arXiv:1207.3502. 2012 [2023-11-18]. (原始內容存檔 (PDF)於2023-10-17). 
  4. ^ Inchbald, Guy. Morphic Polytopes and Symmetries. Complex Symmetries (Springer). 2021: 57–70. 
  5. ^ Nejur, Andrei and Akbarzadeh, Masoud. Constrained manipulation of polyhedral systems. Proceedings of IASS Annual Symposia (International Association for Shell and Spatial Structures (IASS)). 2018, 2018 (16): 1–8.