查看“︁簡單多邊形”︁的源代码

[[File:Two simple polygons and a self-intersecting polygon.svg|thumb|兩個簡單多邊形（綠色和藍色）和一個自相交的[[複雜多邊形]]（紅色，右下角，[[複雜多邊形|非簡單多邊形]]）]]
在[[幾何學]]中，'''簡單多邊形'''是指邊沒有自我相交，也沒有破洞的[[多邊形]]。
也就是說，它是由有限多個[[線段]]組成的[[多邊形鏈|分段線性]][[若尔当曲线定理|若尔当曲线]]。
簡單多邊形包括作為特殊情況的[[凸多邊形]]、非自相交的[[星形多邊形]]和單調多邊形。
簡單多邊形除了相鄰的邊在頂點處交於一點外，所有的邊都不相交。

簡單多邊形的[[外角]]和為360[[度 (角)|度]]（{{math|2π}}[[弧度]]）。
每個具有{{math|''n''}}條邊的簡單多邊形都可以透過其{{math|''n'' − 3}}條對角線進行{{link-en|多邊形三角剖分|Polygon triangulation|三角剖分}}，並且根據[[美术馆问题#美术馆定理|美術館定理]]，其內部所有區域可以從其中至少<math>\lfloor n/3\rfloor</math>個頂點可見。

簡單多邊形通常被視為[[計算幾何]]問題的輸入，包括「檢查[[多邊形中的點|點是否在多邊形的內部]]」、面積計算、簡單多邊形的凸包、{{link-en|多邊形三角剖分|Polygon triangulation|三角剖分}}和歐幾里德最短路徑等。

其他與簡單多邊形相關之幾何學中的構造包括[[施瓦茨-克里斯托费尔映射]]，用於找尋涉及簡單多邊形的[[共形映射]]、點集的{{link-en|多邊形化|Polygonalization}}、用於多邊形的[[构造实体几何]]公式以及多邊形的{{link-en|可見圖|Visibility graph}}。

== 定義 ==
{{File2
|zh-hans=Parts of a simple polygon zh-hans.svg
|zh-hant=Parts of a simple polygon zh-hant.svg
|1=upright=1.25|2=right|3=thumb|4=簡單多邊形}}
簡單多邊形是[[歐幾里德平面]]中由線段組成的閉合曲線，這些線段首尾相連形成[[多邊形鏈]]。在這個多邊形鏈中，除了因連續線段的關係，共用了線段端點，以及多邊形鏈的首尾共用線段端點之外，任何兩個線段都不能彼此相交。<ref name=preparata-shamos>{{cite book
 | last1 = Preparata | first1 = Franco P. | author1-link = Franco P. Preparata
 | last2 = Shamos | first2 = Michael Ian | author2-link = Michael Ian Shamos
 | doi = 10.1007/978-1-4612-1098-6
 | isbn = 978-1-4612-1098-6
 | page = [https://archive.org/details/computationalgeo0000prep/page/18 18]
 | publisher = Springer-Verlag
 | series = Texts and Monographs in Computer Science
 | title = Computational Geometry: An Introduction
 | url = https://archive.org/details/computationalgeo0000prep | year = 1985
}}</ref>有時候，簡單多邊形的「簡單」這個修飾詞會被省略，並假定「多邊形」代表的是簡單多邊形。<ref name=everett-corneil>{{cite journal
 | last1 = Everett | first1 = Hazel
 | last2 = Corneil | first2 = Derek | author2-link = Derek Corneil
 | doi = 10.1016/0925-7721(95)00021-Z
 | issue = 2
 | journal = [[Computational Geometry (journal)|Computational Geometry: Theory & Applications]]
 | mr = 1353288
 | pages = 51–63
 | title = Negative results on characterizing visibility graphs
 | volume = 5
 | year = 1995}}</ref>

形成多邊形的線段稱為稜或邊。線段的端點稱為頂點<ref name=preparata-shamos/>或角。邊和頂點是更正式的術語，但在同時涉及[[圖論]]的[[圖 (數學)|圖]]之邊和頂點的情境中可能會有歧義；更口語的術語「[[稜]]」和「角」可以用來避免這種歧義。<ref name=compatible>{{cite journal
 | last1 = Aronov | first1 = Boris | author1-link = Boris Aronov
 | last2 = Seidel | first2 = Raimund | author2-link = Raimund Seidel
 | last3 = Souvaine | first3 = Diane | author3-link = Diane Souvaine
 | doi = 10.1016/0925-7721(93)90028-5
 | issue = 1
 | journal = [[Computational Geometry (journal)|Computational Geometry: Theory & Applications]]
 | mr = 1222755
 | pages = 27–35
 | title = On compatible triangulations of simple polygons
 | volume = 3
 | year = 1993| doi-access = free
 }}</ref>每個頂點恰好是兩條邊的交點，且邊的數量始終等於頂點的數量。<ref name=preparata-shamos/>有些文獻來源允許兩個線段形成平角（180度、π弧度）<ref name=malkevitch>{{cite web
 | last = Malkevitch
 | first = Joseph
 | title = Are precise definitions a good idea?
 | url = https://www.ams.org/publicoutreach/feature-column/fc-2016-01
 | publisher = American Mathematical Society
 | work = AMS Feature Column
 | year = 2016
 | access-date = 2023-11-14
 | archive-date = 2023-06-18
 | archive-url = https://web.archive.org/web/20230618113441/https://www.ams.org/publicoutreach/feature-column/fc-2016-01
 | dead-url = no
 }}</ref>，但也有些來源不允許平角的頂角，而是要求形成平角的兩條邊要合併成一條較長的邊。<ref name=mccallum-avis>{{cite journal
 | last1 = McCallum | first1 = Duncan
 | last2 = Avis | first2 = David | author2-link = David Avis
 | doi = 10.1016/0020-0190(79)90069-3
 | issue = 5
 | journal = [[Information Processing Letters]]
 | mr = 552534
 | pages = 201–206
 | title = A linear algorithm for finding the convex hull of a simple polygon
 | volume = 9
 | year = 1979}}</ref>如果兩個頂點是多邊形某條對應之線段的兩個端點，則稱這兩個頂點相鄰。<ref name=4marks>{{cite book
 | last1 = de Berg | first1 = M. | author1-link = Mark de Berg
 | last2 = van Kreveld | first2 = M. | author2-link = Marc van Kreveld
 | last3 = Overmars | first3 = Mark | author3-link = Mark Overmars
 | last4 = Schwarzkopf | first4 = O. | author4-link = Otfried Cheong
 | edition = 3rd
 | page = 58
 | publisher = Springer
 | title = Computational Geometry: Algorithms and Applications
 | year = 2008}}</ref>

簡單多邊形有時稱為'''若爾當多邊形'''，因為簡單多邊形是一種[[若尔当曲线定理|若尔当曲线]]；[[若尔当曲线定理]]可以用來證明簡單多邊形將平面分成兩個區域。<ref name=meisters>{{cite journal
 | last = Meisters | first = G. H.
 | doi = 10.2307/2319703
 | issue = 6
 | journal = [[The American Mathematical Monthly]]
 | jstor = 2319703
 | mr = 0367792
 | pages = 648–651
 | title = Polygons have ears
 | volume = 82
 | year = 1975}}</ref>事實上，[[卡米尔·若尔当]]對該定理的原始證明以簡單多邊形的特殊情況（沒有證明的情況下陳述）作為起點。<ref name=hales>{{cite journal
 | last = Hales
 | first = Thomas C.
 | author-link = Thomas Callister Hales
 | department = From Insight to Proof: Festschrift in Honour of Andrzej Trybulec
 | issue = 23
 | journal = [[Studies in Logic, Grammar and Rhetoric]]
 | publisher = University of Białystok
 | title = Jordan’s proof of the Jordan curve theorem
 | url = https://www.maths.ed.ac.uk/~v1ranick/papers/hales1.pdf
 | volume = 10
 | year = 2007
 | access-date = 2023-11-14
 | archive-date = 2023-07-17
 | archive-url = https://web.archive.org/web/20230717212740/https://www.maths.ed.ac.uk/~v1ranick/papers/hales1.pdf
 | dead-url = no
 }}</ref>根據{{link-en|若尔当－薛弗利斯定理|Jordan–Schönflies theorem}}，多邊形內部的區域<ref name=preparata-shamos/>形成一個拓樸上等價於[[圓盤|開圓盤]]的有界集<ref name=thomassen>{{cite journal
 | last = Thomassen | first = Carsten | author-link = Carsten Thomassen (mathematician)
 | doi = 10.1080/00029890.1992.11995820
 | issue = 2
 | journal = [[The American Mathematical Monthly]]
 | jstor = 2324180
 | mr = 1144352
 | pages = 116–130
 | title = The Jordan-Schönflies theorem and the classification of surfaces
 | url = https://archive.org/details/sim_american-mathematical-monthly_1992-02_99_2/page/116 | volume = 99
 | year = 1992}}</ref>，具有有限但非零的面積。<ref name=margalit-knott>{{cite journal
 | last1 = Margalit | first1 = Avraham
 | last2 = Knott | first2 = Gary D.
 | doi = 10.1016/0097-8493(89)90059-9
 | issue = 2
 | journal = Computers & Graphics
 | pages = 167–183
 | title = An algorithm for computing the union, intersection or difference of two polygons
 | url = https://archive.org/details/sim_computers-graphics_1989_13_2/page/167 | volume = 13
 | year = 1989}}</ref>簡單多邊形的拓樸結構等價於圓形<ref name=niven-zuckerman>{{cite journal
 | last1 = Niven | first1 = Ivan | author1-link = Ivan M. Niven
 | last2 = Zuckerman | first2 = H. S.
 | doi = 10.2307/2315660
 | journal = [[The American Mathematical Monthly]]
 | mr = 225216
 | pages = 1195–1200
 | title = Lattice points and polygonal area
 | url = https://archive.org/details/sim_american-mathematical-monthly_1967-12_74_10/page/1195 | volume = 74
 | year = 1967}}</ref>，其外部區域為無界連通開集，並具有無限大的面積。<ref name=margalit-knott/>儘管簡單多邊形的正式定義通常是一系列線段的系統，但也可以（在非正式用法中很常見）將簡單多邊形定義為平面中的封閉集，即包含多邊形內部的這些線段之聯集。<ref name=preparata-shamos/>

簡單多邊形的對角線是該多邊形任兩個頂點所連成的線段，簡單多邊形的對角線必定完全位於多邊形內部。<ref name=aggarwal-suri>{{cite journal
 | last1 = Aggarwal | first1 = Alok
 | last2 = Suri | first2 = Subhash | author2-link = Subhash Suri
 | doi = 10.1016/0020-0190(90)90167-V
 | issue = 1
 | journal = [[Information Processing Letters]]
 | mr = 1069001
 | pages = 13–18
 | title = Computing the longest diagonal of a simple polygon
 | url = https://archive.org/details/sim_information-processing-letters_1990-06-15_35_1/page/n18 | volume = 35
 | year = 1990}}</ref>

== 性質 ==
在簡單多邊形中，某個頂點的內角為該頂點與相鄰的兩條邊在多邊形內部所跨的角度。若頂點的內角小於180度（平角，{{math|π}}弧度），則稱該頂點為凸頂點；若內角大於180度則稱該頂點為凹頂點。若頂點的內角為{{math|''θ''}}，並且小於180度，則該頂點的外角定義為其補角180度{{math|−''θ''}}（{{math|π}}弧度{{math|−''θ''}}），即從一個有向邊轉動到下一個有向邊的轉角。外角在凸頂點處為正，在凹頂點處為負。對於每個簡單多邊形，外角之和為360度（一整圈，{{math|2π}}弧度），因此，對於具有{{math|''n''}}條邊的簡單多邊形，內角總和為{{math|''n''}}減2的結果乘上180度（{{math|(''n''−2)π}}弧度）。<ref name=rich2>{{cite book
 | last1 = Richmond | first1 = Bettina | author1-link = Bettina Richmond
 | last2 = Richmond | first2 = Thomas
 | edition = 2nd
 | isbn = 9781470472047
 | page = 421
 | publisher = American Mathematical Society
 | series = Pure and Applied Undergraduate Texts
 | title = A Discrete Transition to Advanced Mathematics
 | volume = 63
 | year = 2023}}</ref>

[[File:Triangulation 3-coloring.svg|thumb|已經三角化的簡單十一邊形：三角化的9個三角形來自有11條邊和8條對角線]]
每個簡單多邊形都可以透過部分的對角線將之劃分為內部不相交的若干個三角形。當簡單多邊形有{{math|''n''}}條邊時，這樣的分割需要使用到{{math|''n''−3}}條對角線，並分割成{{math|''n''−2}}個三角形。由此產生的分割稱為多邊形的{{link-en|多邊形三角剖分|Polygon triangulation|三角剖分}}。<ref name=meisters/>已經被三角剖分的簡單多邊形可以由多邊形的內角和共用對角線的兩個三角形所形成之四邊形的交比來唯一確定。<ref name=cross-ratio>{{cite journal
 | last = Snoeyink | first = Jack
 | doi = 10.1007/PL00009481
 | issue = 4
 | journal = [[Discrete & Computational Geometry]]
 | mr = 1721028
 | pages = 619–631
 | title = Cross-ratios and angles determine a polygon
 | volume = 22
 | year = 1999| doi-access = free
 }}</ref>

根據{{link-wd|Q25304543}}，每個非三角形的簡單多邊形都有兩個耳，即有兩個有此特性的頂點：該頂點相鄰兩頂點的對角線完全位於多邊形內部。<ref name=meisters/>一個相關定理指出，每個[[非凸多邊形|非凸]]的簡單多邊形都有一個嘴，即有一個有此特性的頂點：該頂點相鄰兩頂點的對角線完全位於多邊形外部。恰好有兩個耳和一個嘴的多邊形稱為{{link-en|擬人多邊形|Anthropomorphic polygon}}。<ref name=toussaint>{{cite journal
 | last = Toussaint | first = Godfried | authorlink = Godfried Toussaint
 | doi = 10.2307/2324033
 | issue = 1
 | journal = [[The American Mathematical Monthly]]
 | jstor = 2324033
 | mr = 1083611
 | pages = 31–35
 | title = Anthropomorphic polygons
 | url = https://archive.org/details/sim_american-mathematical-monthly_1991-01_98_1/page/31 | volume = 98
 | year = 1991}}</ref>

[[File:Art gallery problem.svg|left|thumb|從放置在4個標記頂點的攝影機可以完全看到這個多邊形藝術畫廊中的42個頂點]]
根據[[美术馆问题#美术馆定理|美術館定理]]，在有{{math|''n''}}個頂點的簡單多邊形中，總是可以找到最多<math>\lfloor n/3\rfloor</math>個具有以下屬性之頂點的子集：在這些選定的頂點上可見所有其他頂點（美術館定理的概念就是最少需要多少位守衛站在哪些位置才能無死角地監視整個美術館，所以對應概念就是多邊形裡的每一個頂點都可以和這個頂點子集裡的其中一個頂點連成一線<ref name=Chvatal>{{citation|first=V.|last=Chvátal|authorlink=Václav Chvátal|title=A combinatorial theorem in plane geometry|journal=Journal of Combinatorial Theory, Series B|volume=18|pages=39–41|year=1975|doi=10.1016/0095-8956(75)90061-1}}.</ref>）。這意味著，對於多邊形中的每個點{{math|''p''}}都存在一條只經過多邊形內部點的{{math|''p''}}與那些選定頂點其中一點相連的線段。證明這一點的一種方法是在多邊形的三角剖分上使用圖形著色：總是可以用三種顏色對頂點進行著色，使得三角剖分中的每條邊或對角線都有兩個不同顏色的端點。多邊形的每個點對於每種顏色的頂點都是可見的，例如在所選的三角剖分中包含了三角形三個頂點中的其中一個頂點。其中一種顏色最多被<math>\lfloor n/3\rfloor</math>個頂點使用，因此證明了這個定理。<ref name=fisk>{{cite journal
 | last = Fisk | first = S.
 | doi = 10.1016/0095-8956(78)90059-X | doi-access = free
 | issue = 3
 | journal = [[Journal of Combinatorial Theory, Series B]]
 | page = 374
 | title = A short proof of Chvátal's watchman theorem
 | volume = 24
 | year = 1978}}</ref>

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

{{link-en|單調多邊形|Monotone polygon}}是相對於直線L而言，每條垂直於L的直線都只穿過該多邊形一次（例如[[星狀多邊形]]就有可能會穿過多邊形的兩個不同的部分，也就是穿過兩次）。等價地，單調多邊形是一個邊界可以分為兩個[[單調折線|單調多邊形鏈]]的多邊形，這兩個[[多邊形鏈]]的子序列頂點投影到直線L上時，在直線L上的順序與在多邊形鏈中的順序相同。<ref name=preparata-supowit>{{cite journal
 | last1 = Preparata | first1 = Franco P. | author1-link = Franco P. Preparata
 | last2 = Supowit | first2 = Kenneth J.
 | doi = 10.1016/0020-0190(81)90091-0
 | issue = 4
 | journal = [[Information Processing Letters]]
 | pages = 161–164
 | title = Testing a simple polygon for monotonicity
 | volume = 12
 | year = 1981}}</ref>

== 推廣 ==
=== 簡單多面體 ===
簡單多邊形的概念也可以推廣到三維空間中，對應的概念為'''簡單多面體'''，即不存在面自我相交也沒有空洞的多面體<ref>{{cite web| url=https://reference.wolfram.com/language/ref/SimplePolyhedronQ.html.zh?source=footer| website=reference.wolfram.com| title=SimplePolyhedronQ| access-date=2023-11-20| archive-date=2023-11-20| archive-url=https://web.archive.org/web/20231120155641/https://reference.wolfram.com/language/ref/SimplePolyhedronQ.html.zh?source=footer| dead-url=no}}</ref>。簡單多面體除了相鄰的面在多面體的稜處相交一次外，沒有任何的面與其他面相交。所有凸多面體都是簡單多面體，簡單多面體也包括了部分的凹多面體和非凸多面體。在這個定義下，與簡單多面體相對的概念為[[複雜多面體]]，即面存在自我相交情形的多面體。

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

== 參見 ==
*[[複雜多邊形]]
*[[展開圖]]

== 參考文獻 ==
{{Reflist|2}}

== 外部連結 ==
*{{Mathworld | urlname=SimplePolygon}}

{{多邊形}}

[[Category:多邊形類型]]