基于顶点可见性的凹多边形快速凸分解算法-Read.PDFVIP

第 36 卷 第 12 期 计 算 机 研 究 与 发 展 V o l36,N o 12 1999 年 12 月 JOU RNAL O F COM PU T ER R ESEA RCH D EV ELO PM EN T D ec. 1999 基于顶点可见性的凹多边形快速凸分解算法 金文华　饶上荣　唐卫清　刘慎权 ( 中国科学院计算技术研究所CAD 开放研究实验室　北京　100080) 摘　要　凹多边形的凸分解问题是计算几何的基本问题之一, 在许多领域均有应用. 现有算法大多为全局剖分算 法, 而局部剖分算法研究的很少. 全局方法由于耗时太多, 而不能满足所有工程应用的需要. 目前局部剖分算法中 最经典的是Rogers 算法, 但由于其存在许多缺陷而在实际应用中受到限制. 文中在多边形顶点可见性基础上, 提 出了新的局部剖分方法. 利用凹点的局部几何特性, 通过引入权函数从凹点的可见点串中选取适当的点引剖分线, 或者利用凹点夹角平分线与某两可见顶点所在边的交点引剖分线进行多边形分解. 文中算法已应用于工厂设计软 件 PD SO FT P ip ing 中, 实践证明效果很好. 关键词　简单多边形, 顶点可见性, 多边形分解, 计算几何 中图法分类号　 302. 4; 391. 72 T P T P A FAST POLY GON CONVEX D ECOM POSIT ION AL GOR ITHM BASED ON PO INT V ISIB IL ITY , , , J IN W en H ua RAO Shang Rong TAN G W ei Q ing and L IU Shen Q uan (CA D L aboratory , Institu te of Comp u ting T echnology , Ch inese A cad emy of S ciences, B eij ing 100080) Abstract　Po lygon convex decom po sition is one of the fundam en tal p rob lem s in com pu tational ge . . om etry It is u sed in m any fields M o st of the algo rithm s now availab le are global search ing . . ones L ocal search ing algo rithm s are rarely studied T he global search ing algo rithm s w aste so . m uch tim e that they canno t m eet the need of all the engineeri