跳至內容

簡單多邊形

維基百科，自由的百科全書
兩個簡單多邊形（綠色和藍色）和一個自相交的複雜多邊形（紅色，右下角，非簡單多邊形）

在幾何學中，簡單多邊形是指邊沒有自我相交，也沒有破洞的多邊形。 也就是說，它是由有限多個線段組成的分段線性若爾當曲線。 簡單多邊形包括作為特殊情況的凸多邊形、非自相交的星形多邊形和單調多邊形。 簡單多邊形除了相鄰的邊在頂點處交於一點外，所有的邊都不相交。

簡單多邊形的外角和為360度（2π弧度）。 每個具有n條邊的簡單多邊形都可以透過其n − 3條對角線進行三角剖分（英語：Polygon triangulation），並且根據美術館定理，其內部所有區域可以從其中至少個頂點可見。

簡單多邊形通常被視為計算幾何問題的輸入，包括「檢查點是否在多邊形的內部」、面積計算、簡單多邊形的凸包、三角剖分（英語：Polygon triangulation）和歐幾里德最短路徑等。

其他與簡單多邊形相關之幾何學中的構造包括施瓦茨-克里斯托費爾映射，用於找尋涉及簡單多邊形的共形映射、點集的多邊形化（英語：Polygonalization）、用於多邊形的構造實體幾何公式以及多邊形的可見圖（英語：Visibility graph）。

定義

[編輯]
簡單多邊形

簡單多邊形是歐幾里德平面中由線段組成的閉合曲線，這些線段首尾相連形成多邊形鏈。在這個多邊形鏈中，除了因連續線段的關係，共用了線段端點，以及多邊形鏈的首尾共用線段端點之外，任何兩個線段都不能彼此相交。[1]有時候，簡單多邊形的「簡單」這個修飾詞會被省略，並假定「多邊形」代表的是簡單多邊形。[2]

形成多邊形的線段稱為稜或邊。線段的端點稱為頂點[1]或角。邊和頂點是更正式的術語，但在同時涉及圖論的圖之邊和頂點的情境中可能會有歧義；更口語的術語「稜」和「角」可以用來避免這種歧義。[3]每個頂點恰好是兩條邊的交點，且邊的數量始終等於頂點的數量。[1]有些文獻來源允許兩個線段形成平角（180度、π弧度）[4]，但也有些來源不允許平角的頂角，而是要求形成平角的兩條邊要合併成一條較長的邊。[5]如果兩個頂點是多邊形某條對應之線段的兩個端點，則稱這兩個頂點相鄰。[6]

簡單多邊形有時稱為若爾當多邊形，因為簡單多邊形是一種若爾當曲線；若爾當曲線定理可以用來證明簡單多邊形將平面分成兩個區域。[7]事實上，卡米爾·若爾當對該定理的原始證明以簡單多邊形的特殊情況（沒有證明的情況下陳述）作為起點。[8]根據若爾當－薛弗利斯定理（英語：Jordan–Schönflies theorem），多邊形內部的區域[1]形成一個拓樸上等價於開圓盤的有界集[9]，具有有限但非零的面積。[10]簡單多邊形的拓樸結構等價於圓形[11]，其外部區域為無界連通開集，並具有無限大的面積。[10]儘管簡單多邊形的正式定義通常是一系列線段的系統，但也可以（在非正式用法中很常見）將簡單多邊形定義為平面中的封閉集，即包含多邊形內部的這些線段之聯集。[1]

簡單多邊形的對角線是該多邊形任兩個頂點所連成的線段，簡單多邊形的對角線必定完全位於多邊形內部。[12]

性質

[編輯]

在簡單多邊形中，某個頂點的內角為該頂點與相鄰的兩條邊在多邊形內部所跨的角度。若頂點的內角小於180度（平角，π弧度），則稱該頂點為凸頂點；若內角大於180度則稱該頂點為凹頂點。若頂點的內角為θ，並且小於180度，則該頂點的外角定義為其補角180度−θ（π弧度−θ），即從一個有向邊轉動到下一個有向邊的轉角。外角在凸頂點處為正，在凹頂點處為負。對於每個簡單多邊形，外角之和為360度（一整圈，2π弧度），因此，對於具有n條邊的簡單多邊形，內角總和為n減2的結果乘上180度（(n−2)π弧度）。[13]

已經三角化的簡單十一邊形：三角化的9個三角形來自有11條邊和8條對角線

每個簡單多邊形都可以透過部分的對角線將之劃分為內部不相交的若干個三角形。當簡單多邊形有n條邊時，這樣的分割需要使用到n−3條對角線，並分割成n−2個三角形。由此產生的分割稱為多邊形的三角剖分（英語：Polygon triangulation）。[7]已經被三角剖分的簡單多邊形可以由多邊形的內角和共用對角線的兩個三角形所形成之四邊形的交比來唯一確定。[14]

根據雙耳定理（英語：Two ears theorem），每個非三角形的簡單多邊形都有兩個耳，即有兩個有此特性的頂點：該頂點相鄰兩頂點的對角線完全位於多邊形內部。[7]一個相關定理指出，每個非凸的簡單多邊形都有一個嘴，即有一個有此特性的頂點：該頂點相鄰兩頂點的對角線完全位於多邊形外部。恰好有兩個耳和一個嘴的多邊形稱為擬人多邊形（英語：Anthropomorphic polygon）。[15]

從放置在4個標記頂點的攝影機可以完全看到這個多邊形藝術畫廊中的42個頂點

根據美術館定理，在有n個頂點的簡單多邊形中，總是可以找到最多個具有以下屬性之頂點的子集：在這些選定的頂點上可見所有其他頂點（美術館定理的概念就是最少需要多少位守衛站在哪些位置才能無死角地監視整個美術館，所以對應概念就是多邊形裡的每一個頂點都可以和這個頂點子集裡的其中一個頂點連成一線[16]）。這意味著，對於多邊形中的每個點p都存在一條只經過多邊形內部點的p與那些選定頂點其中一點相連的線段。證明這一點的一種方法是在多邊形的三角剖分上使用圖形著色：總是可以用三種顏色對頂點進行著色，使得三角剖分中的每條邊或對角線都有兩個不同顏色的端點。多邊形的每個點對於每種顏色的頂點都是可見的，例如在所選的三角剖分中包含了三角形三個頂點中的其中一個頂點。其中一種顏色最多被個頂點使用，因此證明了這個定理。[17]

特例

[編輯]

所有凸多邊形都是簡單多邊形。另一類重要的簡單多邊形是星狀多邊形（不是星形多邊形，星形多邊形可能有自我相交的情況，此處指的是星形外觀的多邊形），該多邊形存在一個從每個頂點皆可見的點，這個點可能是在內部或邊界上。[1]

單調多邊形（英語：Monotone polygon）是相對於直線L而言，每條垂直於L的直線都只穿過該多邊形一次（例如星狀多邊形就有可能會穿過多邊形的兩個不同的部分，也就是穿過兩次）。等價地，單調多邊形是一個邊界可以分為兩個單調多邊形鏈的多邊形，這兩個多邊形鏈的子序列頂點投影到直線L上時，在直線L上的順序與在多邊形鏈中的順序相同。[18]

推廣

[編輯]

簡單多面體

[編輯]

簡單多邊形的概念也可以推廣到三維空間中，對應的概念為簡單多面體，即不存在面自我相交也沒有空洞的多面體[19]。簡單多面體除了相鄰的面在多面體的稜處相交一次外，沒有任何的面與其他面相交。所有凸多面體都是簡單多面體，簡單多面體也包括了部分的凹多面體和非凸多面體。在這個定義下，與簡單多面體相對的概念為複雜多面體，即面存在自我相交情形的多面體。

有另外一個概念也稱為簡單多面體，即簡單多胞形的三維例子，但他的定義不同，它的定義是每個頂點只與三條邊相鄰的多面體，兩者相差甚遠。

參見

[編輯]

參考文獻

[編輯]
  1. ^ 1.0 1.1 1.2 1.3 1.4 1.5 Preparata, Franco P.; Shamos, Michael Ian. Computational Geometry: An Introduction. Texts and Monographs in Computer Science. Springer-Verlag. 1985: 18. ISBN 978-1-4612-1098-6. doi:10.1007/978-1-4612-1098-6. 
  2. ^ Everett, Hazel; Corneil, Derek. Negative results on characterizing visibility graphs. Computational Geometry: Theory & Applications. 1995, 5 (2): 51–63. MR 1353288. doi:10.1016/0925-7721(95)00021-Z. 
  3. ^ Aronov, Boris; Seidel, Raimund; Souvaine, Diane. On compatible triangulations of simple polygons. Computational Geometry: Theory & Applications. 1993, 3 (1): 27–35. MR 1222755. doi:10.1016/0925-7721(93)90028-5 可免費查閱. 
  4. ^ Malkevitch, Joseph. Are precise definitions a good idea?. AMS Feature Column. American Mathematical Society. 2016 [2023-11-14]. （原始內容存檔於2023-06-18）. 
  5. ^ McCallum, Duncan; Avis, David. A linear algorithm for finding the convex hull of a simple polygon. Information Processing Letters. 1979, 9 (5): 201–206. MR 0552534. doi:10.1016/0020-0190(79)90069-3. 
  6. ^ de Berg, M.; van Kreveld, M.; Overmars, Mark; Schwarzkopf, O. Computational Geometry: Algorithms and Applications 3rd. Springer. 2008: 58. 
  7. ^ 7.0 7.1 7.2 Meisters, G. H. Polygons have ears. The American Mathematical Monthly. 1975, 82 (6): 648–651. JSTOR 2319703. MR 0367792. doi:10.2307/2319703. 
  8. ^ Hales, Thomas C. Jordan’s proof of the Jordan curve theorem (PDF). From Insight to Proof: Festschrift in Honour of Andrzej Trybulec. Studies in Logic, Grammar and Rhetoric (University of Białystok). 2007, 10 (23) [2023-11-14]. （原始內容存檔 (PDF)於2023-07-17）. 
  9. ^ Thomassen, Carsten. The Jordan-Schönflies theorem and the classification of surfaces. The American Mathematical Monthly. 1992, 99 (2): 116–130. JSTOR 2324180. MR 1144352. doi:10.1080/00029890.1992.11995820. 
  10. ^ 10.0 10.1 Margalit, Avraham; Knott, Gary D. An algorithm for computing the union, intersection or difference of two polygons. Computers & Graphics. 1989, 13 (2): 167–183. doi:10.1016/0097-8493(89)90059-9. 
  11. ^ Niven, Ivan; Zuckerman, H. S. Lattice points and polygonal area. The American Mathematical Monthly. 1967, 74: 1195–1200. MR 0225216. doi:10.2307/2315660. 
  12. ^ Aggarwal, Alok; Suri, Subhash. Computing the longest diagonal of a simple polygon. Information Processing Letters. 1990, 35 (1): 13–18. MR 1069001. doi:10.1016/0020-0190(90)90167-V. 
  13. ^ Richmond, Bettina; Richmond, Thomas. A Discrete Transition to Advanced Mathematics. Pure and Applied Undergraduate Texts 63 2nd. American Mathematical Society. 2023: 421. ISBN 9781470472047. 
  14. ^ Snoeyink, Jack. Cross-ratios and angles determine a polygon. Discrete & Computational Geometry. 1999, 22 (4): 619–631. MR 1721028. doi:10.1007/PL00009481 可免費查閱. 
  15. ^ Toussaint, Godfried. Anthropomorphic polygons. The American Mathematical Monthly. 1991, 98 (1): 31–35. JSTOR 2324033. MR 1083611. doi:10.2307/2324033. 
  16. ^ Chvátal, V., A combinatorial theorem in plane geometry, Journal of Combinatorial Theory, Series B, 1975, 18: 39–41, doi:10.1016/0095-8956(75)90061-1 .
  17. ^ Fisk, S. A short proof of Chvátal's watchman theorem. Journal of Combinatorial Theory, Series B. 1978, 24 (3): 374. doi:10.1016/0095-8956(78)90059-X 可免費查閱. 
  18. ^ Preparata, Franco P.; Supowit, Kenneth J. Testing a simple polygon for monotonicity. Information Processing Letters. 1981, 12 (4): 161–164. doi:10.1016/0020-0190(81)90091-0. 
  19. ^ SimplePolyhedronQ. reference.wolfram.com. [2023-11-20]. （原始內容存檔於2023-11-20）. 

外部連結

[編輯]
取自「https://zh.wikipedia.org/w/index.php?title=簡單多邊形&oldid=80498516」