资源描述：
《任意多边形顶点凸,凹性判别的简捷算法》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。
1、1000-9825/2002/13(07)1309-04©2002JournalofSoftware软件学报Vol.13,No.7任意多边形顶点凸、凹性判别的简捷算法Ã刘润涛(哈尔滨理工大学计算机应用技术研究所,黑龙江哈尔滨150080)E-mail:liurt@0451.comhttp://www.hrbust.edu.cn摘要:给出了一种确定任意多边形顶点凸、凹性的简捷算法.该算法只需要2n+4次乘法,5n+10次加、减法及2n+3次比较即可完成(n是多边形顶点的个数).同时,给出了任意简单多边形走向
2、的充要条件.关键词:多边形;凸凹性;算法;走向;充要条件中图法分类号:TP391文献标识码:A在模式识别、图像处理、曲面插值等方面常常遇到对多边形区域或离散点进行分割的问题,如能预先确定[2,3]每个多边形顶点的凸、凹性,就可使该问题的解决得到简化.对于判别任意多边形顶点的凸、凹性的问题,文22献[1]给出了一个算法,其时间复杂性为O(nlogn)次乘法和O(n)次比较.本文所给出的算法,其时间复杂度仅为2n+2次乘法,2n次加、减法及3n次比较,时间复杂度减少.本文首先给出几个相关的概念,然后讨论任意简
3、单多边形走向判别的充要条件.之后给出任意多边形顶点凸、凹性判别的算法.最后对该算法的时间复杂度进行分析.1基本概念为叙述方便,先给出几个相关的定义.定义1.设pi=(xi,yi),i=1,2,3,…,n,pn+1=p1是给定多边形的n个顶点,若对任意i,j(i≠j),i,j=1,2,3,…,n,线段pipi+1与pjpj+1或是相邻且相交于一端点或不相交,则称该多边形为简单多边形.定义2.设p1,…,pn,pn+1=p1是一个简单多边形.若线段pi−1pi与线段pipi+1所形成的内角(即由该多边形所围°
4、有界区域内所形成的角)是一个不超过180的角,则称顶点pi是凸的,否则,称pi是凹的.由此定义可知,对任意一个简单多边形,其每个顶点或是凸的,或是凹的.定义3.设p1,p2,…,pn,pn+1=p1是一个简单多边形.若沿p1→p2…pn→pn+1方向走,该简单多边形所围的有界区域总在左边,则称该多边形的走向是逆时针的;反之,称其走向是顺时针的.2简单多边形走向的充要条件给定一个简单多边形,其顶点为p1,p2,…,pn,pn+1=p1,它的走向是逆时针的还是顺时针的,对于判别每个顶点的凸、凹性是很重要的.如
5、何用较小的计算量解决这个问题是确定每个顶点的凸、凹性的一个关键步骤.解决该问题的思路是:先求出给定的多边形n个顶点的x值或y值最大或最小的点(称其为极值点),使该多边形落入由这些x值和y值最大或最小的点构成的矩形内(注意,一定有点落在4条边上),如图1所示.然后,依据该多边形在每个极值点处与相邻两顶点的位置关系,就可以确定该多边形的走向.下面以y值最大的点为例说明该方法的实现过程.Ã收稿日期:2000-11-29;修改日期:2001-04-26基金项目:国家自然科学基金资助项目(69705004,1017
6、1025);黑龙江省自然科学基金资助项目(F9706)作者简介:刘润涛(1961－),男,黑龙江东宁人,副研究员,主要研究领域为计算机辅助几何设计,计算机图形算法.1310JournalofSoftware软件学报2002,13(7)p1p3p5pi+1pip2p4p9pipi−1p7pi−1pi+1p8(a)(b)p6Fig.1Fig.2图1图2记pi为y值最大的点,即yi=max[yj],做辅助点pi′:当pi−1,pi,pi+1共线时,令pi′=pi−α(0,1)(α为任一正数,可取α=︱pi−1p
7、i︱).否则,令pi′=(pi−1+pi+1)/2.作以pi′为原点通过pi的射线l(注意,l是有方向的),则pi−1,pi+1位于l的两侧.易见,若pi−1位于l的左侧,则该多边形是顺时针的.反之亦然.因此,得到以下结论,该多边形走向是顺时针的⇔pi−1位于l的左侧.进行类似的讨论可得,该多边形走向是逆时针的⇔pi−1位于l的右侧.那么,如何判别pi−1是位于l的左侧还是右侧呢?xy1i−1i−1为此,引入函数S(pi−1,pi,pi+1)=xiyi1=∆pi−1pipi+1的有向面积的2倍.xy1i+
8、1i+1若pi−1在由pi经pi+1的射线的左侧,则∆pi−1pipi+1的有向面积为正,否则为负,如图2所示,图2(a)为pi−1在由pi经pi+1的射线的左侧,图2(b)为pi−1在由pi经pi+1的射线的右侧.经简单计算可得S(pi−1,pi,pi+1)=(xi−xi−1)(yi−yi+1)−(yi−yi−1)(xi−xi+1),因此,多边形走向是顺时针的⇔S(pi−1,pi′,pi+1)＞0,多边形走向是逆时针的⇔S(
