复杂多边形
复杂多边形是指多边形的一种分类。 指具有边自我相交或者有破洞的多边形,或者说其边除了相邻边在顶点处相交之外,也存在其他互相相交的边。 这个概念与简单多边形相对。 复杂多边形的英语为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.