资源描述：
《基于非线性规划理论的凸多面体最小平移距离算法》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。
1、第11卷第10期中国图象图形学报Vo.l11,No.102006年10月JournalofImageandGraphicsOct.,2006基于非线性规划理论的凸多面体最小平移距离算法周之平张少博吴介一张飒兵(东南大学CIMS中心,南京210096)摘要凸多面体的最小平移距离问题一直以来都成为计算机图形学的一个研究热点。目前已有的距离算法在稳定性、可实现性、精确度和实现效率这几方面或多或少都存在一定的缺陷。为此,从最小平移距离定义出发,引入广义分离平面概念,提出一种用非线性规划求解距离问题的新算法。
2、算法先定义一对最优广义分离平面以确定凸多面体最小平移距离;然后,将最优广义分离平面对的搜索问题等效变换为非线性规划问题;最后,用非线性优化工具软件对非线性规划问题进行求解,从而确定最小平移距离。实验结果表明:该算法能提供一个准确的距离值和实现向量,其性能优于其他同类算法;迭代次数与多面体的顶点数呈线性关系。此外,该算法只需提供顶点信息即可实现,求解过程中避免了死循环,故实现简单、可靠。因此,此算法是一种快速而有效的距离算法。关键词凸多面体最小平移距离分离平面实现向量非线性规划中图法分类号:TP391.4
3、1文献标识码:A文章编号:10068961(2006)10148707AMinimumTranslationalDistanceAlgorithmofConvexPolyhedraBasedonNonlinearProgrammingTheoryZHOUZhiping,ZHANGShaobo,WUJiey,iZHANGSabing(TheCIMSCenterofSoutheastUniversity,Nanjing210096)AbstractTheproblemofminimumtran
4、slationaldistance(MTDforshort)ofconvexpolyhedraisalwaysanactivesubfieldofcomputergraphics.Thecurrentdistancealgorithmsaredeficientinsuchrequirementsasstability,realizability,accuracyandefficiencymoreorless.Inordertoovercometheselimitations,thegeneralizedsepar
5、ableplaneisintroducedbasedonthedefinitionofMTDandanewalgorithmoftheMTDproblemusingnonlinearprogrammingispresentedinthepaper.Thisalgorithmiscarriedoutasfollow.Firstly,theMTDmeasureisdeterminedbydefiningtheoptimalgeneralizedseparableplanepair.Secondly,theprobl
6、emofsearchingtheoptimalplanepairisequivalentwithnonlinearprogrammingproblemundersometransforms.Finally,anonlinearoptimizationsoftwareisusedtosolvetheequivalentmode,landthereforeMTDmeasureisdeterminedbythesolution.Theresultsshowthattheproposedalgorithmperform
7、slinearlywiththesizeofmodelandovertheotheralgorithmsinmostofthetests.Besides,itcanprovidebothanaccuratemeasureandthewitnessvectorinafewiterations,whicharegentlylinearwiththevertexnumber.Inaddition,theimplementationissimpleandreliable,becauseonlytheinformation
8、ofvertexisrequiredandthecyclecanbeavoided.So,itisafastandefficientdistancealgorithm.Keywordsconvexpolyhedra,lminimumtranslationaldistance,separableplane,witnessvector,nonlinearprogrammin
