6. 多边形

浏览量:82

参考

      Peter Schorn, and Frederick Fisher. "Testing the convexity of a polygon." Graphics Gems IV. Academic Press Professional, Inc., 1994.       Eric Haines. "Point in polygon strategies." Graphics Gems IV. Academic Press Professional, Inc., 1994.       Franco P. Preparata, and

spacer
浏览量:109

6.9. 简单多边形的凸包化

本篇文章禁止用于任何商业目的,版权申明、版本说明等见《前言》。 PDF文档和源码下载地址:https://github.com/twinklingstar20/Programmers_Computational_Geometry 6.9. 简单多边形的凸包化 问题描述:将给定的简单多边形\({\rm P} = \{ {V_0},{V_1},...,{V_{n - 1}}\} \)凸包化。 求给定点集的凸包的算法下限是\(O(n\log n)\),但是将简单多边形凸包化的算法复杂度是线性的。McCallum&Avis (1979)提出了第一个正确的、线性复杂度的算法,后来的学者进一步对这个问题进行研究,提出了更为简单、高效、易懂的算法,其中Melkman 在1987年提出的线性算法是最好的,因为该算法不考虑简单多边形的朝向,实现简单、高效,只使用一个双端队列即可。 图6.48 简单多边形\({\rm P}\)的凸包化 如图6.48所示,就是由一个简单多边形\({\rm P}\)凸包化得到的凸多边形\(CH({\rm P})\),显然,多边形\({\rm P}\)在\(CH({\rm P})\)内部,而且构成\(CH({\rm P})\)的点集是构成\({\rm P}\)的点集的子集。 接下来,详细介绍Melkman算法,该算法主要用到的数据结构是双端队列,可以表示为\(deque=\{{{d}_{bott}},\cdots ,{{d}_{top}}\}\),\(bott\)表示队列的底部,\(top\)表示队列的顶部,而且有\({{d}_{top}}={{d}_{bott}}\)。对队列有4种操作: \(deque.\operatorname{push}\_back(v)\),将元素\(v\)存入队列顶部,执行的操作是:\(top=top+1,{{d}_{top}}=v\); \(deque.\operatorname{pop}\_back()\),将顶部的元素弹出,执行的操作是:\(top=top-1\); \(deque.\operatorname{push}\_front(v)\),将元素\(v\)存入队列底部,执行的操作是:\(bott=bott+1,{{d}_{bott}}=v\); \(deque.\operatorname{pop}\_front()\),将底部的元素弹出,执行的操作是\(bott=bott-1\)。 函数\(\operatorname{ORIENTATION}({{v}_{0}},{{v}_{1}},{{v}_{2}})\)实现的功能是判断点\({{v}_{2}}\)是否在由\({{v}_{0}},{{v}_{1}}\)确定的直线的右侧,如果在,返回1;如果三点\({{v}_{0}},{{v}_{1}},{{v}_{2}}\)共线,返回0;否则,返回-1,伪码如下所示: \(\operatorname{ORIENT}({{v}_{0}},{{v}_{1}},{{v}_{2}})\) /* \({{v}_{0}},{{v}_{1}},{{v}_{2}}\)表示三个点 */ 1.    \(d=({{v}_{2}}-{{v}_{0}})\times ({{v}_{1}}-{{v}_{0}})\);

spacer
浏览量:337

6.8. 线性对象与凸多边形的交

本篇文章禁止用于任何商业目的,版权申明、版本说明等见《前言》。 PDF文档和源码下载地址:https://github.com/twinklingstar20/Programmers_Computational_Geometry 6.8. 线性对象与凸多边形的交 Cyrus&Beck(1978)提出了一种判断直线与凸多边形相交测试的算法,该算法还可以解决三维空间上直线与凸多面体的相交测试问题,称之为Cyrus-Beck裁剪算法,Hill& Kelley(2008)中也有算法的描述,算法的复杂度为\(O(n)\)。 此外,针对凸多边形,可以应用二分查找,得到复杂度为\(O(\log n)\),判断直线与凸多边形的相交测试。 6.8.1. Cyrus-Beck裁剪算法 问题描述:线性对象\(L(t) = P + t\vec d\)与凸多边形\({\rm P} = \{ {V_0},{V_1},...,{V_{n - 1}}\} \)的相交测试,设凸多边形逆时针顺序的。 如图6.42所示,线性对象不仅可以用参数方程的形式表示,而且还可以用法线形式来表示。设凸包上的一条边是,边上指向外侧的法向量是\(\vec n\),边所在的直线可用法线形式表示为: \ 把参数方程\(L(t)\)代入等式(6.13),得到: \

spacer
浏览量:103

6.7. 直线与凸多边形的距离

本篇文章禁止用于任何商业目的,版权申明、版本说明等见《前言》。 PDF文档和源码下载地址:https://github.com/twinklingstar20/Programmers_Computational_Geometry 6.7. 直线与凸多边形的距离 问题描述:计算直线\(L(t) = Q + t \cdot \vec d\)与凸多边形\({\rm P} = \{ {V_0},{V_1}, \cdots ,{V_{n - 1}}\} \)的距离,设\({\rm P}\)是逆时针顺序且不存在连续的三个顶点共线的情况。 计算直线与多边形的距离,需要遍历多边形的每个顶点,时间复杂度是\(O(n)\),但对于凸多边形这种特殊情况,存在复杂度是\(O(\log n)\)的算法。 设\(d(L,{{V}_{i}})\)表示凸多边形上点\({{V}_{i}}\)与直线\(L\)的距离,其中\(0\le i\le n-1\),那么\({\rm P}\)与直线\(L\)的距离就可以表示为\(d(L,P)=\underset{0\le i\le n-1}{\mathop{min}}\,\left\{ d(L,{{V}_{i}}) \right\}\),就是找到\({\rm P}\)上与直线\(L\)距离最近的顶点。设与直线\(L\)垂直的方向是\(\vec{n}\),确保\({\rm P}\)上至少有一个顶点不在直线\(L\)由\(\vec{n}\)指向的一侧,那么与直线\(L\)最近的顶点,就是凸多边形\({\rm P}\)沿着方向\(\vec{n}\)的极点,如图6.41所示,\({{V}_{\max }}\)就是沿着方向\(\vec{n}\)的极点。将向量\(\vec{d}\)沿着逆时针方向旋转90。,就得到与它垂直的向量\(\vec{n}=\left( -{{{\vec{d}}}_{y}},{{{\vec{d}}}_{x}} \right)\)。若\(\vec{n}\cdot \left( {{V}_{0}}-Q

spacer
浏览量:98

6.6. 凸多边形的极点

本篇文章禁止用于任何商业目的,版权申明、版本说明等见《前言》。 PDF文档和源码下载地址:https://github.com/twinklingstar20/Programmers_Computational_Geometry 6.6. 凸多边形的极点 问题描述:给定一个凸多边形\(P=\{{{V}_{0}},{{V}_{1}},\cdots ,{{V}_{n-1}}\}\),求\(P\)沿着方向\(\vec{d}\)上的极点,设\(P\)是逆时针顺序且不存在连续的三个顶点共线的情况。 对于任意一个点集和方向,通过测试每个点,可以在线性时间内得到。但对于凸多边形这种特殊的情况,它沿着任意一个方向,都是一个单调多边形,可以分成两条单调的多边形链,可以应用二分搜索的思想,在时间内找到极点。 图6.38 凸多边形上的顶点投影到方向是\(\vec{d}\)的直线上 为了后面的算法论述,先对一些概念进行介绍。如图6.38所示,直线\(L\)所在的方向是\(\vec{d}\),把\(P\)上的顶点都投影到直线上,所有的投影点都介于\(\left\)之间,则顶点\({{V}_{\min }}\)和顶点\({{V}_{\max }}\)分别称为凸多边形沿着方向\(\vec{d}\)的最小极点和最大极点。若点\(

spacer
浏览量:153

6.5. 点与多边形的关系

本篇文章禁止用于任何商业目的,版权申明、版本说明等见《前言》。 PDF文档和源码下载地址:https://github.com/twinklingstar20/Programmers_Computational_Geometry 6.5. 点与多边形的关系 Haines Eric(1994) 详细地总结各种点与简单多边形关系的判定算法,并测试了不同算法的性能。判定点与一般的简单多边形关系的算法,有交叉法(Crossings Test),角度累积法(Angle Summation),增量角度法(Incremental Angle),三角扇法(Triangle Fan),栅格法(Grid Method),基于像素的测试法(Pixel Based Test)。其中,速度最快的是栅格法,但是它需要预处理操作,并且对内存的需求特别大。 判定点与凸多边形关系,同样有很多种方法,最容易想到的一种方法就是判断点是否在凸多边形每条边的外侧,只要存在一条这样的边,就可知点就在凸多边形外,否则,在凸多边形内。这种方法的复杂度是\(O(n)\),而Schneider et al(1985)描述了一种基于二分查找的算法,时间复杂度是\(O(\log n)\),是最快的判定算法。 对于点与简单多边形关系的判定问题,本小节将重点介绍交叉法和增量角度法,两种算法的思路完全不同,但是性能相当。对于点与凸多边形关系的判定问题,本小节将介绍基于二分查找的算法。 6.5.1. 交叉法 问题描述:判定点\(Q\)与简单多边形\({\rm P} = \{ {V_0},{V_1},...,{V_{n - 1}}\} \)的关系,其中\({{V}_{i}}=({{x}_{i}},{{y}_{i}})\),设简单多边形是逆时针顺序。 它是基于射线与边交点个数的奇偶性来判定的,基本思想是:由待判定点\(Q\),沿任意一个方向做一条射线,求出射线与多边形的交点个数,若交点个数是奇数,则点在多边形内,若是偶数,则在多边形外。如图6.30所示,点\({{Q}_{1}}\)在多边形外,由它引出的射线与多边形边有4个交点,交点个数是偶数;点\({{Q}_{2}}\)在多边形内,由它引出的射线与多边形边有1个交点,交点个数是奇数。为了算法的简便,射线的方向通常取(1,0)或者是(0,1)。 图6.30 根据射线和多边形边交点个数的奇偶性,判定点与多边形的关系 由待检测点引出的射线,可能经过多边形的顶点,或者与多边形的边发生重合。如图6.30所示,若\({{Q}_{2}}\)引出的射线经过顶点\({{V}_{3}}\),则计算交点时,射线与边\(\overline{{{V}_{2}}{{V}_{3}}}\)和边\(\overline{{{V}_{3}}{{V}_{4}}}\)都相交,交点个数是2,由此得出的结论“点\({{Q}_{2}}\)在多边形外”是错误的。O'Rourke (1998)介绍了一种解决方案,以待测试点为原点,方向是(1,0)作一条射线,求它与多边形的交点个数。对相交点的计数作如下限制:(1)若多边形一条边的一个端点严格位于射线之上,另一个端点严格位于射线之下,相交点个数加1;(2)与射线重合的边,直接忽略不计;(3)一条边位于射线之上,它的一个端点在射线上,相交点个数不变;(4)一条边位于射线之下,它的一个端点在射线上,相交点个数加1。 如图6.31所示,初始情况下,相交点计数值\(n=0\),经过点\({{V}_{15}}\),边\(\overline{{{V}_{15}}{{V}_{16}}}\)在射线上,计数值不变;边\(\overline{{{V}_{14}}{{V}_{15}}}\)与射线重合,忽略;经过点\({{V}_{14}}\),边\(\overline{{{V}_{13}}{{V}_{14}}}\)在射线下方,计数值加1,得\(n=1\);经过点\({{V}_{11}}\),边\(\overline{{{V}_{11}}{{V}_{12}}}\)在射线下方,计数值加1,得\(n=2\);依次类推,最终得到的计数值为\(n=5\),是一个奇数,判定点\(Q\)在多边形内。 设射线的原点是\(Q\)、方向是(1,0),边为\(\overline{{{V}_{i}}{{V}_{i+1}}}\),如何判断射线与边的关系呢?若边\(\overline{{{V}_{i}}{{V}_{i+1}}}\)的两个端点在\(Y\)轴上的分量大于\({{Q}_{y}}\)或者小于\({{Q}_{y}}\),则射线与边\({{V}_{i}}{{V}_{i+1}}\)一定不相交。否则,射线与边可能相交。边可以用参数方程表示为\(L(t)={{V}_{i}}+t({{V}_{i+1}}-{{V}_{i}}),0\le t\le 1\)。射线与边相交,设交点是\(T\),则交点\(Y\)轴上的分量是\({{T}_{y}}={{Q}_{y}}\),则有\({{Q}_{y}}={{y}_{i}}+t({{y}_{i+1}}-{{y}_{i}})\),因此可以解得 \

spacer
浏览量:114

6.4. 多边形的面积

本篇文章禁止用于任何商业目的,版权申明、版本说明等见《前言》。 PDF文档和源码下载地址:https://github.com/twinklingstar20/Programmers_Computational_Geometry 6.4. 多边形的面积 本节介绍二维和三维多边形面积的计算公式和几何推导方法,针对三维多边形的面积计算,有多种算法,比如三角形分解法、四边形分解法、投影法,本节只介绍三角形分解的方法,并给出相应的计算公式。 6.4.1. 二维空间 问题描述:求二维空间上的多边形\({\rm P} = \{ {V_0},{V_1},...,{V_{n - 1}}\} \)的面积,其中,\({{V}_{i}}=({{x}_{i}},{{y}_{i}})\)。 二维空间上的多边形\({\rm P}\)的面积通过等式(6.3)计算: \ 图6.26 逆时针方向排序的多边形 接下来,推导下等式(6.3),从几何的角度考虑,设多边形是按照逆时针方向进行排序的,如图6.26所示,\(O\)表示原点,则多边形的面积可以表示为: \

spacer
浏览量:263

6.3. 多边形判定

本篇文章禁止用于任何商业目的,版权申明、版本说明等见《前言》。 PDF文档和源码下载地址:https://github.com/twinklingstar20/Programmers_Computational_Geometry 6.3. 多边形判定 判断一个多边形是否是简单的,关键在于怎么判断多边形的边是否存在自相交,Shamos-Heoy(1976)提出了一种复杂度为\(O(n\log n)\)判断线段集是否存在相交的算法,可应用于判定一个多边形是否是简单的,可以采用第四章的Shamos-Hoey算法。判断一个简单多边形是否是单调的,Preparata&Supowit(1981)提出一种最优的性线复杂度的算法。判断一个多边形是否是凸的,如果先判断多边形是否是简单的,再判断是否存在大于180度的内角,算法需要\(O(n\log n)\)的时间,但Schorn& Fisher (1994)提出了一种最优的线性算法。 本小节将会介绍简单多边形的单调性和多边形的凸性判定算法。 6.3.1. 简单多边形的单调性 问题描述:判定二维空间上的简单多边形\({\rm P} = \{ {V_0},{V_1},...,{V_{n - 1}}\} \)是否是单调的,设简单多边形是逆时针顺序的。 图6.20 边与边的夹角 我们这里规定,边\({{e}_{0}}\)与边\({{e}_{1}}\)的夹角记为\(({{e}_{0}},{{e}_{1}})\),它的绝对值小于180度,如图6.20所示(a),边\({{e}_{1}}\)在边\({{e}_{0}}\)的逆时针方向,则边\({{e}_{0}}\)与边\({{e}_{1}}\)的夹角大于0度,即\(({{e}_{0}},{{e}_{1}})\succ 0\);如图(b)所示,边\({{e}_{1}}\)在边\({{e}_{0}}\)的顺时针方向上,夹角小于0度,即\(({{e}_{0}},{{e}_{1}})\prec 0\)。 设多边形的边\({{e}_{i}}=\overline{{{V}_{i}}{{V}_{i+1}}}\),令\({{C}_{0}}=\left( (1,0),{{e}_{0}} \right)\),\({{C}_{k}}=\sum\limits_{i=1}^{k}{({{e}_{i-1}},{{e}_{i}})},1\le k\le n-1\),称\({{C}_{k}}\)就是边\({{e}_{k}}\)的极角坐标,在极角坐标\({{C}_{i}}\)与\({{C}_{j}}\)之间会形成一个扇形区域,极角坐标\({{C}_{i}}\)沿着逆时针方向旋转至\({{C}_{j}}\)的扇形区域记为\(({{C}_{i}},{{C}_{j}})\)。 图6.21 简单多边形和它对应的极角坐标图 如图6.21示,图(a)是多边形\({\rm P}\),图(b)是它对应的极角坐标图。对于极角坐标图,我们可以想像为初始情况下有一条边\({{e}_{0}}\),把它看成类似于手表上的指针一样的有向向量,将它沿逆时针旋转角度\(\left\| ({{e}_{0}},{{e}_{1}}) \right\|\)至边\({{e}_{1}}\)的极角坐标\({{C}_{1}}\),再顺时针旋转角度\(\left\| ({{e}_{1}},{{e}_{2}}) \right\|\)至边\({{e}_{2}}\)的极角坐标\({{C}_{2}}\),依次类推,直至完成所有夹角的旋转,形成完整的极角坐标图。也可以换一个角度理解极角坐标图,它相当于把多边形上的每条边看成向量,将它们的起始位置移至顶点\({{V}_{0}}\)。显然,极角坐标将\(

spacer
浏览量:651

6.2. 多边形生成算法

本篇文章禁止用于任何商业目的,版权申明、版本说明等见《前言》。 PDF文档和源码下载地址:https://github.com/twinklingstar20/Programmers_Computational_Geometry 6.2. 多边形生成算法 6.2.1. 生成算法综述 随机多边形的生成主要有两个应用:a)测试算法的正确性;b)评估算法耗费的CPU时间。为了能评估算法的正确性,输入的数据应尽可能的分散,使得算法的每一个分支都得到执行,这也有利于算法效率的有效评估。但实际上,我们经常很难获得大量有效的输入数据来测试,因此随机多边形的生成算法就显得非常的必要。 给定一个点集,求由它们组成的均匀分布的简单多边形是一个NP难问题,至今还没有找到多项式级别的算法,但对某些特殊的多边形,存在有多项式级别的算法。我们也可以采用启发式的方法,在可以接受的时间范围内生成丰富多样的非均匀分布的简单多边形。这里先介绍下非均匀分布的概念,设存在\(n\)个点的点集,总共能生成\(m\)种简单多边形,均匀分布的简单多边形生成算法是指这\(m\)种简单多边形都会有一定概率被生成,但非均匀分布的生成算法,只能生成其中的\(k(k\prec m)\)种。 针对随机星状多边形的生成算法,早在1988就Linda&hute就提出了一种\(O({{n}^{5}})\)的生成算法,Sohler(1999)提出了另一种时间复杂度更低的生成算法,达到\(O({{n}^{2}}\log n)\),Auer& Held(1996)提出了两种星状多边形的生成算法,一个算法复杂度是\(\text{O(}{{\text{n}}^{5}}\log n)\),和前面两种算法类似,实现难度较大,另外一个算法简单易实现,但不能保证生成的星状多边形可能是非退化的,称它为快速星状生成算法,复杂度是\(O(n\log n)\),本节将会详细地描述快速星状生成算法。 针对随机单调多边形的生成算法,Zhu et al(1996)提出了一种通过上顶点链表和下顶点链表,生成随机的X单调多边形,算法的复杂度是\(O(n)\),但是需要\(O({{n}^{2}})\)的预处理时间。本小节将会详细地描述另外一种更简单的生成算法,可以生成任意直线方向上的单调多边形。 针对随机凸多边形的生成算法,一种很简单的方法,就是随机生成一组点,通过凸包算法,求出包围点集的凸多边形。但是,这种方法会造成的一个问题是:随机生成10000个点数据,最终得到的凸包可能只有100个顶点,甚至于更少。Devillers et al(2014)提出了一种生成在同一个圆盘上的凸多边形,本节将介绍一种更简单的基于圆盘的凸多边形生成算法。 针对随机简单多边形的生成算法,由于无法在多项式时间内生成均匀分布的简单多边形,但是我们可以通过启发式的方法,生成非均匀分布的简单多边形。Auer&Held(1996)提出了多种启发式的方法,包括稳定增长法(Steady Growth)、空间分割法(Space Partition)、两步移动法(2-opt Moves),复杂度分别是\(O({{n}^{2}})\)、\(O(n\log n)\)和\(\text{O(}{{\text{n}}^{4}}logn)\)。此外,Dailey& Whitfield(2008)提出了一种\(O({{n}^{2}}\log n)\),类似于Koth曲线的构造,使用到多边形三角剖分算法。本节将介绍稳定增长法、两步移动法、和空间分割生成算法。 6.2.2. 星状多边形的生成算法 问题描述:随机生成不重合的\(n\)个点的点集\(S=\left\{ {{P}_{0}},{{P}_{1}},\cdots ,{{P}_{n-1}} \right\}\),由该点集生成一个逆时针顺序的星状多边形。 随机确定一个点\(P\),要求点\(P\)在点集\(S\)所确定的凸包内,可知点集\(S\)的中心,一定在凸包内,即 \

spacer
浏览量:110

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}}\)是凸(凹)点;顺时针顺序排列,则相反。 图6.1 多边形和非多边形,(a)多边形,(b)有曲线,(c)没有形成密闭区域 内角都不大于180。的简单多边形,称为凸多边形,即不存在凹点。它的任意一条边所在的直线都可以把平面分成两个半平面,凸多边形的顶点都在同一个半平面上,而且连接任意两个顶点的线段都在多边形内部或者边界上。 相邻边不相交的多边形称为简单多边形,与它相对应的是复杂多边形。至少存在一个内角大于180。的简单多边形,称为凹多边形,即至少存在一个凹点的简单多边形。凹多边形上至少存在一条边,它所在的直线把平面分成两个半平面,使得凹多边形上的点不在同一个半平面上。 图6.2 几种多边形,(a)凸多边形,(b)凹多边形,(c)复杂多边形 本章只涉及不带洞的简单多边形,显然,多边形把平面分成三部分:内部、边界和外部。如图6.2所示的几种多边形,(a)是凸多边形,(b)是凹多边形,(a)和(b)都是简单多边形,而(c)是复杂多边形。内部指的是灰色部分所示的区域,除去灰色区域和边界就是多边形的外部。 图6.3 对于给定直线的单调多边形和非单调多边形 若给定一条直线\(L\),任意一条与\(L\)垂直的直线与多边形最多相交两次,称这样的多边形称为单调多边形。若任意一个与\(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)\)的复杂度。判定一个多边形是否是单调多边形只需要\(O(n)\)的复杂度,因此,若能提前能判定一个多边形是单调的,那么它的三角剖分就可以在线性时间内完成。   图6.4 星状多边形 若一个多边形内存在一点,使得多边形的每条边界对该点可见,称这样的多边形为星状多边形,如图6.4的左侧多边形所示,点\(Z\)对多边形的所有边界可见。也就是说,多边形内存在点\(Z\),使得对于多边形内的所有点与点\(Z\)构成在线段都在多边形内。由满足这个性质的点\(Z\)构成的区域,称为多边形的核,如图1.4的右侧多边形所示,若核的面积为零(点或者线段),称这样的星状多边形是退化的,相反,面积不为零的情况,就是非退化的。显然,核不为空的多边形才能称得上星状多边形,它的核一定是由多边形的边形成的半平面的交。星状多边形也是简单多边形,用一个数学形式来表示几种多边形间的关系为:凸多边形\(\subset \)星状多边形\(\subset \)简单多边形。如果需要判断一个简单多边形是否是星状的,只需要判断多边形的核是否为空,Lee&Preparata(1973)提出一种线性复杂度计算多边形核的算法,周(2000)简化了该算法,只处理凹点的情况。  

spacer