跳转到内容

简单多边形

维基百科，自由的百科全书
两个简单多边形（绿色和蓝色）和一个自相交的复杂多边形（红色，右下角，非简单多边形）

在几何学中，简单多边形是指边没有自我相交，也没有破洞的多边形。 也就是说，它是由有限多个线段组成的分段线性若尔当曲线。 简单多边形包括作为特殊情况的凸多边形、非自相交的星形多边形和单调多边形。 简单多边形除了相邻的边在顶点处交于一点外，所有的边都不相交。

简单多边形的外角和为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”