复杂多边形
复杂多边形是指多边形的一种分类。 指具有边自我相交或者有破洞的多边形，或者说其边除了相邻边在顶点处相交之外，也存在其他互相相交的边。 这个概念与简单多边形相对。 复杂多边形的英语为Complex polygon，这个词汇则有多种的定义，一种是上述复杂多边形的定义，另一种是位于复数空间的复多边形[注 1]。
复杂多边形这个概念常用于计算机科学中，因为复杂多边形的填色相较于简单多边形复杂得多，需要使用特殊的算法才能完成对复杂多边形的内部上色。
在复杂多边形中，自相交偶数次的部分算做多边形的外部，[1]以五角星为例，五角星中央交出的五边形不算做五角星的内部，换句话说，即是此复杂多边形的孔洞。[2]
定义
在数学上，复杂多边形定义为具有边自我相交或者有破洞的多边形。而在计算机科学中，定义稍有不同。在计算机科学中，复杂多边形除了边自我相交外，还代表着该多边形可能由多个封闭的边界组成的多边形，其中一个边界会形成该多边形主要边界的孔洞。[2]
除此之外，在计算机科学中的复杂多边形也会考虑边自我相交的情况[1]，此时对于这个多边形顶点数的计算，仅会计算边的端点，不会计算边与边相交所产生的顶点。
性质
涉及到有界区域的积分和闭合线积分的公式在复杂多边形区域“由内而外”部分以次数计算内外部时（最内部为实际上的内部，向外遇到一个边界时视为外部，再遇到一个边界时视为内部以此类推）仍然适用。
复杂多边形的孔洞可以来自自相交所形成的区域，[3]也可以来自位于最外周界内部的边界或子多边形。位于主要边界内部的较小作为孔洞的子简单多边形边界，其内角等同于整个复杂多边形的外角，其360度减内角的值才是整个复杂多边形的内角，所以位于复杂多边形主要边界内部的较小简单多边形的内角（对于整个复杂多边形而言）通常是优角。
在复杂多边形周围移动时，顶点处转向的总量可以是360度（2π）的任意整数倍，例如五角星顶点处转向的总量为720度，而有角度的“8”顶点处转向的总量为0度。
复合多边形
复合多边形是指由多个单独封闭的相连线段（子多边形）所组成的多边形，例如六角星由两个独立的三角形组合而成。[4]复合多边形都是复杂多边形，若组合的方式是一个大多边形包含一个小多边形，即大多边形内部有一个较小的多边形（例如回字形），则内部多边形视为整个复合多边形的孔洞，也就是一个有“破洞”的多边形。
推广
复杂多面体
复杂多边形的概念也可以推广到三维空间中。对应的概念是复杂多面体。复杂多面体代表存在面有自我相交情形的多面体。[5]所有复杂多面体都是非凸多面体。星形正多面体都是复杂多面体。与复杂多面体相对的概念是简单多面体。
参见
注释
- ^ 此处的complex polygon中，complex代表复数（Complex Number、 ），因此称为复多边形或复数空间多边形（简称复数多边形）。然而在计算机图形学中， 也有一个称为complex polygon的概念，但是在这种情况下，complex并不意味着“复数域上的结构”，因此不会将其称为复多边形。 一般数学或几何学也有这种概念，尤其在讨论多边形是否存在自相交的情况，在这种情况下complex polygon应被称为复杂多边形，这意味着该多边形存在着自相交的情况，即simple（非简单闭合曲线），因此称为complex（意味着复杂或不简单）。 而又有一类多边形称为复合多边形，其表示多个多边形组成的复合图形，其名称不应与复多边形和复杂多边形混淆。
参考文献
- ^ 1.0 1.1 Paul Bourke. Polygons and meshes:Surface (polygonal) Simplification. 1997 [2016-05]. （原始内容存档于2019-12-31）.
- ^ 2.0 2.1 Rae Earnshaw, Brian Wyvill (Ed); New Advances in Computer Graphics: Proceedings of CG International ’89, Springer, 2012, page 654.
- ^ 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）.
- ^ Inchbald, Guy. Morphic Polytopes and Symmetries. Complex Symmetries (Springer). 2021: 57–70.
- ^ 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.