浏览量:206

6.1. 多边形简介

本篇文章禁止用于任何商业目的,版权申明、版本说明等见《前言》。

PDF文档和源码下载地址:https://github.com/twinklingstar20/Programmers_Computational_Geometry

6.1. 多边形简介

计算几何上,有限条线段包围的密闭区域称为多边形,如图6.1所示,图(a)是多边形,图(b)出现了曲线,不是多边形,图(c)没有形成密闭的区域,也不是多边形。经常可以用一个点的序列来表示一个多边形,即\(P=\{{{V}_{0}},{{V}_{1}},\cdots ,{{V}_{n-1}}\}\)。构成多边形的线段\(\overline{{{V}_{i}}{{V}_{i+1}}}\)称为多边形的,相邻的两条边仅在端点相交,交点称为多边形的顶点,具有共同端点的边称为相邻边,比如\(\overline{{{V}_{i-1}}{{V}_{i}}}\)\(\overline{{{V}_{i}}{{V}_{i+1}}}\)是两条相邻边,与同一个顶点\({{V}_{i}}\)相关联的两条边\(\overline{{{V}_{i-1}}{{V}_{i}}}\)\(\overline{{{V}_{i}}{{V}_{i+1}}}\)形成的位于多边形内部的角称为多边形的内角。内角小于等于180的顶点称为凸点,相对应的,内角大于180的顶点称为凹点。显然,若多边形是逆时针顺序排列,点\({{V}_{i+1}}\)在边\(\overline{{{V}_{i-1}}{{V}_{i}}}\)的左(右)侧,则\({{V}_{i+1}}\)是凸(凹)点;顺时针顺序排列,则相反。

2015-3-23 14-53-00

图6.1 多边形和非多边形,(a)多边形,(b)有曲线,(c)没有形成密闭区域

内角都不大于180的简单多边形,称为凸多边形,即不存在凹点。它的任意一条边所在的直线都可以把平面分成两个半平面,凸多边形的顶点都在同一个半平面上,而且连接任意两个顶点的线段都在多边形内部或者边界上。

相邻边不相交的多边形称为简单多边形,与它相对应的是复杂多边形。至少存在一个内角大于180的简单多边形,称为凹多边形,即至少存在一个凹点的简单多边形。凹多边形上至少存在一条边,它所在的直线把平面分成两个半平面,使得凹多边形上的点不在同一个半平面上。

2015-3-23 14-53-17

图6.2 几种多边形,(a)凸多边形,(b)凹多边形,(c)复杂多边形

本章只涉及不带洞的简单多边形,显然,多边形把平面分成三部分:内部、边界和外部。如图6.2所示的几种多边形,(a)是凸多边形,(b)是凹多边形,(a)和(b)都是简单多边形,而(c)是复杂多边形。内部指的是灰色部分所示的区域,除去灰色区域和边界就是多边形的外部。

2015-3-23 14-53-32

图6.3 对于给定直线的单调多边形和非单调多边形

若给定一条直线\(L\),任意一条与\(L\)垂直的直线与多边形最多相交两次,称这样的多边形称为单调多边形[4,13]。若任意一个与\(L\)垂直的直线\(L'\),跟多边形链C最多只有一个交点,称该多边形链是严格单调的,即\(L'\bigcap C\)为空或者一个点。若\(L'\bigcap C\)为空或者一个点或者一条线段,则称这样的多边形链是单调的。显然,对于任意一条直线,凸多边形都是单调的。如图1.3所示,左边的多边形在垂直方向上是单调的,多边形链{5,6,7,8,0}是严格单调的,多边形链{0,1,2,3,4,5}是单调的,但是不是严格单调的,因为边2,3是水平的。相反,图6.3右侧的多边形在垂直方向上不是单调的。若直线\(L\)\(X\)轴方向重合,得到的单调多边形称为X单调多边形;若直线\(L\)\(Y\)轴方向重合,得到的单调多边形称为Y单调多边形,图6.3左侧的多边形就是\(Y\)单调多边形。一些多边形相对于多条直线,都表现出单调性,同样,也有一些多边形相对于任意直线,都没有单调性。

对于单调多边形的三角剖分,可以在线性时间内完成,因此可以把多边形分解成多个单调多边形,分解过程需要\(O(n\log n)\)的复杂度[13]。判定一个多边形是否是单调多边形只需要\(O(n)\)的复杂度[16],因此,若能提前能判定一个多边形是单调的,那么它的三角剖分就可以在线性时间内完成。

 

2015-3-23 14-53-47

图6.4 星状多边形

若一个多边形内存在一点,使得多边形的每条边界对该点可见,称这样的多边形为星状多边形,如图6.4的左侧多边形所示,点\(Z\)对多边形的所有边界可见。也就是说,多边形内存在点\(Z\),使得对于多边形内的所有点与点\(Z\)构成在线段都在多边形内。由满足这个性质的点\(Z\)构成的区域,称为多边形的核,如图1.4的右侧多边形所示,若核的面积为零(点或者线段),称这样的星状多边形是退化的,相反,面积不为零的情况,就是非退化的。显然,核不为空的多边形才能称得上星状多边形,它的核一定是由多边形的边形成的半平面的交。星状多边形也是简单多边形,用一个数学形式来表示几种多边形间的关系为:凸多边形\(\subset \)星状多边形\(\subset \)简单多边形。如果需要判断一个简单多边形是否是星状的,只需要判断多边形的核是否为空,Lee&Preparata[17](1973)提出一种线性复杂度计算多边形核的算法,周[18](2000)简化了该算法,只处理凹点的情况。

 

spacer

Leave a reply