简单多边形
几何学名词
在几何形状中,简单多边形是由直线,非相交的线段或“边”组成的扁平形状,其成对连接以形成封闭路径。 如果两边相交,那么多边形并不简单。 经常省略限定词“简单”,上述定义通常被理解为多边形。数学家通常使用“多边形”来表示由线段而不是封闭区域构成的形状,然而有些可能使用“多边形”来指由有限序列组成的封闭路径限定的平面图 的直线段(即通过闭合的多边形链)。 根据使用的定义,该边界可以不形成多边形本身的一部分。
简介
在几何形状中,简单多边形是由直线,非相交的线段或“边”组成的扁平形状,其成对连接以形成封闭路径。 如果两边相交,那么多边形并不简单。 经常省略限定词“简单”,上述定义通常被理解为多边形。
简单多边形还可定义为:
1.周界不自交的多边形。
2.满足条件:
1)顶点与顶点不重合。
2)顶点不在边上。
3.边与边不相交的多边形。
简单多边形分凸多边形凹多边形两种。
通常需要在拐角处相遇的两个边缘形成不直线(180°)的角度;否则,共线线段将被视为单侧的部分。
数学家通常使用“多边形”来表示由线段而不是封闭区域构成的形状,然而有些可能使用“多边形”来指由有限序列组成的封闭路径限定的平面图 的直线段(即通过闭合的多边形链)。 根据使用的定义,该边界可以不形成多边形本身的一部分。
简单的多边形也被称为约旦多边形,因为约旦曲线定理可以用来证明这样的多边形将平面划分成两个区域,即它内部的区域和其外部的区域。 平面上的多边形当且仅当在拓扑上等同于一个圆时才是简单的,它的内部在拓扑上等同于一个磁盘。
属性
上面给出的定义确保了以下属性:
1.多边形包围一个总是具有可测量区域的区域(称为其内部)。
2.构成多边形(称为边)的线段仅在其端点(称为顶点)或更少的正式“角”处相遇。
3.两个边缘完全相交。
4.边数总是等于顶点数。
弱简单多边形
如果非交叉线段的集合形成了与磁盘拓扑相当的平面区域的边界,则该边界称为弱简单多边形。在右边的图像中,根据这个定义,ABCDEFGHJKLM是一个弱简单的多边形,蓝色标记了它作为边界的区域。这种类型的弱简单多边形可以在计算机图形和CAD中出现,作为具有孔的多边形区域的计算机表示:对于每个孔,创建“切割”以将其连接到外部边界。参考上述图像,ABCM是具有孔FGHJ的平面区域的外部边界。切割ED将孔与外部连接,并在所得到的弱简单多边形表示中遍历两次。
在弱简单多边形的替代和更一般的定义中,它们是相同组合类型的简单多边形的序列的极限,在Fréchet距离下的收敛,这使得这样的多边形允许段接触但不能交叉的概念形成。然而,这种类型的弱简单多边形不需要形成区域的边界,因为其“内部”可以是空的。例如,参考上述图像,根据该定义,多边形链ABCBA是弱简单的多边形:它可以被视为多边形ABCFGHA的“挤压”的限制。
计算问题
在计算几何中,几个重要的计算任务涉及到一个简单多边形形式的输入;在每个这些问题中,内部和外部之间的区别在问题定义中至关重要。
多边形测试中的点涉及为简单多边形P和查询点q确定q是否位于P内部。
计算多边形面积的简单公式是已知的;也就是多边形内部的区域。
多边形分区是一组不重叠的原始单位(例如正方形),其联合等于多边形。多边形分区问题是在某种意义上找到最小的分区的问题,例如:具有最小单位数或具有最小总长度单位的分区。
多边形分区的特殊情况是多边形三角剖分:将简单多边形分成三角形。虽然凸多边形易于三角测量,但是对于一般简单多边形进行三角测量更为困难,因为我们必须避免增加跨多边形的边。然而,Bernard Chazelle在1991年表明,任何具有n个顶点的简单多边形可以在Θ(n)时间内进行三角测量,这是最佳的。也可以使用相同的算法来确定闭合多边形链是否形成简单多边形。
多边形上的布尔运算:由多边形区域定义的点集合的各种布尔运算。
简单多边形的凸包可以比其他类型的输入的凸包更有效地计算,例如点集的凸包。
Voronoi图的简单多边形
一个简单多边形的中轴/拓扑骨架/直骨架
一个简单多边形的偏移曲线
闵可夫斯基求和简单多边形
参考资料
最新修订时间:2024-07-06 20:29
目录
概述
简介
参考资料