一种凹多边形凸分解的全局剖分算法

《一种凹多边形凸分解的全局剖分算法》由会员上传分享，免费在线阅读，更多相关内容在学术论文-天天文库。

1、第29卷第3期2011年6月中国民航大学学报JOURNALOFCIVILAVIATIoNUNIVERSITYOFCHINAV01．29No．3June2011一种凹多边形凸分解的全局剖分算法贺怀清，杨鹏(中国民航大学计算机科学与技术学院。天津300300)摘要：提出了一种凹多边形凸分解的全局剖分算法。首先对局部剖分算法的原理及存在的问题进行了阐述，并对基于正负法搜索可视点串的算法进行了更正和改进。然后利用改进的权函数从全局剖分的角度选择最优的剖分点进行剖分。同局部剖分算法相比，提高了剖分后所得的多边形形态质量。该算法主要作为轮廓偏置算法的前期处理算法．对

2、原轮廓进行分解，提高了原轮廓多边形进行轮廓偏置算法的运行效率。关键词：凹多边形；凸分解；全局剖分；局部剖分；正负法；轮廓偏置中图分类号：TP391．72文献标识码：A文章编号：1674—5590(2011)03—0052—04GlobalSubdivisionAlgorithmonConvexDecompositionofConcavePolygonHEHuai-qing，YANGPe昭(CollegeofComputerScienceandTechnology，CAUC，Tianjin300300，China)Abstract：Proposedaglo

3、balsubdivisionalgorithmontheconvexdecompositionofconcavepolygon．First，theprincipleoflocalsubdivisionalgorithmandtheexistedproblemsweredescribed；Thenitcorrectedandimprovedthesearchvisualpointstringalgorithmbasedonpositiveandnegativemethod；last，chosetheoptimalsplitpointstosubdivide

4、concavepolygonbyusingtheimprovedweightfunctionfromanoverallperspective．Comparedwiththelocalsubdivisionalgorithm，itimprovedpolygonshapequalityaftersubdivision．Asamainp陀一processingalgorithmofcontouroffset，itdecomposedtheoriginalcontourandimprovedtheefficiencyofcontouroffsetalgorith

5、mtotheoriginalcontourpolygon．Keywords：concavepolygon；convexdecomposition；globalsubdivision；localsubdivision；positiveandnegativemethod：contouroffset在现有的较为成熟的扫描算法当中，轮廓偏置扫描算法【-1由于不需要频繁开关激光器，且扫描中不断改变方向，能够获得较好的精度。但是由于在偏置的过程中，要不断地检查环自交、环相交等情况，因此算法效率不高。对此，不少学者提出结合计算几何当中的凹多边形凸分解算法12-51将多

6、边形Iq分解为多个凸多边形，再分别对每个凸多边形进行轮廓偏置的算法。文献[21q，通过对凹点进行分类及编码，有效地减少了简单多边形的个数，但是编码较为复杂；文献【3】对文献【2】进行了改进，提出了在凹点的可视点对之间通过权函数来进行剖分；文献[4】在Rogers．F．David提出的经典算法之上提出了基于顶点可见性的剖分算法，根据当前凹点的权函数来进行剖分，结果不够全面；文献【5】提出了一种较为简化的可视点串求取算法，并在改进了的权函数基础之上进行剖分，效果较好。本文首先对局部剖分算法的原理及存在的问题进行了阐述，并对基于正负法搜索可视点串的算法进行了更

7、正和改进，然后利用改进的权函数从全局剖分的角度选择最优的剖分点进行剖分，优化了简单多边形的形态质量。通过在各个子轮廓上进行轮廓偏置扫描，得到了较好的实验结果。1基本概念与定义定义1简单多边形16J：设平面上n个点P。、P：、收稿日期：2011-ol埘作者简介：贺怀清(1969一)，女，吉林白山人。教授，博士，研究方向为图形图像与可视化技术．第29卷第3期贺怀清，杨鹏：一种凹多边形凸分解的全局剖分算法一53一⋯、p。按循环排序方法逆时针排列，P。在P。之后，又设e，=石瓦，e：=云i，⋯，e。=云百是连接点的n条线段，那么这些线段界限一个简单多边形：①循环

8、排序中相邻线段对的交是它们间共有的单个点：e；f3eⅢ=pm；②不相邻的线段不相