平面代数曲线间最近距离的计算

Seediscussions,stats,andauthorprofilesforthispublicationat:https://www.researchgate.net/publication/46284312ComputingtheminimumdistancebetweentwoplanaralgebraiccurvesArticleinJisuanjiFuzhuShejiYuTuxingxueXuebao/JournalofComputer-AidedDesignandComputerGraphics·April2008Source:OAICITATIONSREADS2563authors,including:Xiao-DiaoChenJun-HaiYongHangzhouDianziUniversityTsinghuaUniversity44PUBLICATIONS293CITATIONS106PUBLICATIONS1,160CITATIONSSEEPROFILESEEPROFILESomeoftheauthorsofthispublicationarealsoworkingontheserelatedprojects:SolidModelingViewprojectgeometricmethodforsolvingnon-linearequationsystemViewprojectAllcontentfollowingthispagewasuploadedbyXiao-DiaoChenon22October2015.Theuserhasrequestedenhancementofthedownloadedfile. 第20卷第4期计算机辅助设计与图形学学报Vol120,No142008年4月JOURNALOFCOMPUTER2AIDEDDESIGN&COMPUTERGRAPHICSApr1,2008平面代数曲线间最近距离的计算1)2)3)陈小雕雍俊海汪国昭1)(杭州电子科技大学计算机学院杭州310018)2)(清华大学软件学院北京100084)3)(浙江大学数学系计算机图象图形研究所杭州310027)(xiaodiao@nit.zju.edu.cn)摘要通过几何观察,指出一条曲线上的最近点是另一条曲线的等距曲线与该曲线的切点这一事实,同时提出基于等距思想的方法来求解2条平面代数曲线间的最近距离1该方法几何意义明显,可同时用来计算代数曲线P参数曲线间的最近距离1对于平面二次曲线,采用文中方法得到的单变量多项式方程次数比已有类似方法中结果方程的次数更低,从而可以降低方程求解的计算复杂度或提高求解的稳定性1关键词最近距离;平面代数曲线;等距方法中图法分类号TP391172ComputingtheMinimumDistancebetweenTwoPlanarAlgebraicCurves1)2)3)ChenXiaodiaoYongJunhaiWangGuozhao1)(CollegeofComputer,HangzhouDianziUniversity,Hangzhou310018)2)(SchoolofSoftware,TsinghuaUniversity,Beijing100084)3)(InstituteofComputerGraphicandImageProcessing,DepartmentofMathematics,ZhejiangUniversity,Hangzhou310027)AbstractThroughgeometricobservation,itisfoundthatthenearestpointonacurveisatangentpointbetweenthecurveandanoffsetcurveoftheothercurve1Basedonthisobservation,anoffsetmethodispresentedforcomputingtheminimumdistancebetweentwoplanaralgebraiccurves1Thenewmethodisgeometricallyinstructive,andcanbeusedforcomputingtheminimumdistancebetweenanalgebraiccurveandaparametriconeonthesameplane1Forplanarquadraticcurves,thedegreeoftheresultingunivariatepolynomialequationbyourmethodismuchlowerthanthatoftheequationsinpreviouscomparablemethods,whichmayleadtolowercomputationcomplexityorhigherrobustnessofthesolutions1Keywordsminimumdistance;planaralgebraiccurves;offsetmethod2最近距离的计算问题有很多应用1如在机器人近距离1由于一次消多元方法的限制,在R空间中运动规划中,距离信息被用来计算物体间的相互作代数曲线的情形下,采用这些代数曲面情形中的方[1]用力以及惩罚系数;在CADPCAM中,距离信息法得到的最终结果可能会存在较大的差异1例如,[2]被用于碰撞干涉检测;计算机图形学中的碰撞检对于一个2次曲面f(x,y,z)=0和一个3次曲面测与动画模拟,也经常需要用到物体间的距离信g(x,y,z)=0间的最近距离,采用文献[3]中的方[325]息1法不容易直接求解x,y,z关于其他2个变量的表3文献[3,627]讨论了R空间中2次曲面间的最达式,从而影响最终消元后得到单变量多项式方程收稿日期:2007-09-28;修回日期:2008-01-081基金项目:国家“九七三”重点基础研究发展规划项目(2004CB318000,2004CB719403);国家自然科学基金(60625202,60533070,60473130);宁波市自然科学基金(1140157B703)1陈小雕,男,1976年生,博士,讲师,主要研究方向为计算机图形学、几何造型1雍俊海,男,1973年生,博士,教授,博士生导师,主要研究方向为CAGD,CAD&CG1汪国昭,男,1944年生,教授,博士生导师,主要研究方向为CAGD,CAD&CG1©1994-2008ChinaAcademicJournalElectronicPublishingHouse.Allrightsreserved.http://www.cnki.net 460计算机辅助设计与图形学学报2008年的次数;而同样对于一个2次曲线F(x,y)=0和一曲线间的最近距离1假设给定的2条平面代数曲线个3次曲线G(x,y)=0间的最近距离,采用本文不相交,其方程分别为C1:f(x,y)=0和C2:方法可以直接给出x,y关于另外2个变量的表达g(x,y)=01若点p=(x0,y0)T为曲线C1上的最式,提高了消元的效率,最终的结果也优于类似的已近点,最近距离为d1如图1所示,曲线C1位移为有方法1本文仅讨论平面物体间的最近距离1d的等距线刚好与曲线C2相切于点q,则点q是曲椭圆、抛物线等平面代数曲线经常被用于在各线C2上对应的最近点,且有种平面造型系统中表示平面物体1如AutoCAD中,q=(x(x)Pk,y(x)Pk)T0+dfx0,y00+dfy0,y0经常要计算2条曲线之间最近距离的信息1通过将(1)曲线离散成若干条直线段,2条曲线间的最近距离22其中k=fx(x0,y0)+fy(x0,y0)1点p和q也可以转化为若干条直线段间的最近距离问题1直的连线方向既是曲线C1在点p处的法向,也是曲线段间的最近距离容易求解,因此在高精度要求下,线C2在点q处的法向1综上所述,令α=dPk,有曲线可能需要被分解成很多条直线段,但这时对应f(x0,y0)=0的计算量比较大,可能无法满足实时计算的要求,需g(x0+αfx(x0,y0),y0+要曲线间最近距离的直接求解方法1αfy(x0,y0))=0若2条代数曲线相交,则相应的最近距离为0,它们之间的任何一个交点,都可以当作相应的最近gx(x0+αfx(x0,y0),y0+(2)点1关于2条曲线间的求交问题,可以参考文献[82αfy(x0,y0))+μfx(x0,y0)=012],本文不再详细讨论求交方法的细节1假设2条gy(x0+αfx(x0,y0),y0+代数曲线不相交,它们的最近距离计算问题往往被αfy(x0,y0))+μfy(x0,y0)=0转化为一个多项式方程组的求解,或一个次数较高其中fx,fy,gx和gy分别为f和g关于x和y的偏[627]的单变量多项式方程的求根问题12002年,导数1Lennerz等提出了基于Langrange乘子法的方法,讨[6]论了二次曲线曲面间最近距离的计算问题1该方法可以得到2个双变量的多项式方程,或一个次数相对较高的单变量多项式方程1为了防止涉及的矩阵出现奇异性,文献[6]的方法需要区分是否中心曲线,以便分别讨论求解1Sohn等基于直线几何的方法讨论二次曲面、圆环面间的最近距离计算问[7]题,用来求解二次曲线间的最近距离,但需要事图1曲线S的等距曲线O1,O2与曲线C相切于P和Q先计算出曲线法向一致性所满足的方程,不同类型的曲线对应的方程需要分别计算1采用文献[7]方式(2)中共有4个多项式方程和4个变量x0,法得到2个双变量的多项式方程,其次数甚至比文y0,α和μ,消去其中3个变量x0,y0和μ,得到一个[3]献[6]中方程相应的次数更高1关于单变量α的多项式方程1从理论上来说,文献本文提出一种基于等距思想的计算方法,可以[13214]中的结式理论可以用来消去多项式方程组统一地计算2条平面代数曲线间的最近距离,并得的任意多个变量,单变量多项式方程的求解见文献到2个双变量的方程,或一个单变量的方程1采用[12],本文不作详细讨论1求解出α后,将其代入式本文方法理论上也适用于计算平面上一条代数曲线(2)中,可解出x0,y0和μ,进而求解出最近距离和一条参数曲线间的最近距离1对于2条二次曲线d=αk1相应地,另一个最近点可由式(1)得到1间的最近距离计算问题,采用本文方法得到的单变若第一条曲线f(x,y)=0为参数曲线C(t)=T量多项式方程的次数低于文献[627]方法得到的单(X(t),Y(t)),则在式(2)中将第一个方程去除,T变量多项式方程的相应次数1同时将代数曲线的法向(fx(x,y),fy(x,y))替换T成参数曲线的法向表示式(Y′(t),-X′(t)),可以1最近距离计算的等距方法得到3个关于t,α和μ的方程1类似地,消去2个变量t和μ,得到一个关于单变量α的多项式方程;本文的等距方法理论上可以用来解决2条代数然后,同样可以求解出最近距离以及相应的最近点1©1994-2008ChinaAcademicJournalElectronicPublishingHouse.Allrightsreserved.http://www.cnki.net 4期陈小雕等:平面代数曲线间最近距离的计算461x0=-(BD+Cpμ-CE)P(BA+2BAα+2平面二次曲线间的最近距离Bμ-C2-2C2α),22y0=β2P(BA+2BAα+Bμ-C-2Cα);一般平面二次曲线的方程为2其中β2=CD+2CDα+2ABpα+4ABpα+2Bpαμ-22g(x,y)=Ax+By+2Cxy+2Dx+2Ey+F=02222αpC-4pαC-EA-2AEα-Eμ+Apμ+2Apα+(3)2pμ,将其代入到式(5)中,整理后,得到2个关于α211椭圆P双曲线与一般平面二次曲线间的最近距离和μ的多项式方程1消去变量μ,得到H(α)=设椭圆或双曲线的方程可以表示为f(x,y)=422h3(α)h4(α),其中h3(α)和h4(α)分别表示关于xPm+yPn-1=0,一般平面二次曲线由式(3)确α的次数至多为1次和8次的单变量多项式方程1定,则式(2)变为0=x22213抛物线与抛物线间的最近距离0Pm+y0Pn-122222设抛物线的方程可以表示为f(x,y)=x-0=A(1+2αPm)x0+B(1+2αPn)y0+22py,第2条抛物线方程由(Ax+By+C)+(Dx+2C(1+2αPm)(1+2αPn)x0y0+Ey+F)=0确定,则式(2)变为2D(1+2αPm)x0+2E(1+2αPn)y0+F20=x0-2py00=2A(1+2αPm)x0+2C(1+2αPn)y0+20=(A(x0+2αx0)+B(y0-2αp)+C)+2D+2μx0PmD(x0+2αx0)+E(y0-2αp)+F0=2B(1+2αPn)y0+2C(1+2αPm)x0+0=2A(A(x0+2αx0)+B(y0-2αp)+C)+D+2μx02E+2μy0Pn0=2B(A(x0+2αx0)+B(y0-2αp)+C)+E-2μp(4)(6)其中第3,4个方程是关于x0和y0的线性方程,求其中第3,4个方程是关于x0和y0的线性方程,求解得到解得到x0=-m(-nCE+nBD+μD-2CEα+2BDα)Pβ1,x0=-(BD-AE+2Apμ)P(2Bμ),y0=-n(-mCD+mAE+μE-2CDα+2AEα)Pβ1;2其中β2y0=β3P(2Bμ);1=2nABα+nBμ-nCm+nABm+2μAα-2222其中β2=ABD-A2E+2A2μp+2ABDα-2αA2E+2Cαm-4Cα+Amμ+2BαAm+4ABα+2α+μ24αA2μp-2BCμ-Eμ+2pμ2+4B2pμα,将其代入到2Bαμ-2nC,将其代入到式(4)中,整理后,得到2个关于α和μ的多项式方程1消去变量μ,式(6)中,整理后,得到2个关于α和μ的多项式方4程1消去变量μ,得到一个关于α的次数至多为5得到h(α)=h1(α)h2(α),其中h1(α)和h2(α)分别表示关于α的次数至多为1次和12次的单变量次的多项式方程1多项式方程1214直线与一般平面二次曲线间的最近距离212抛物线与一般平面二次曲线间的最近距离设直线的方程可以表示为f(x,y)=ax+by+2设抛物线的方程可以表示为f(x,y)=x-c,一般平面二次曲线由式(3)确定,则式(2)变为2py,一般平面二次曲线由式(3)确定,则式(2)变为0=ax0+by0+c0=x2220-2py00=A(x0+aα)+B(y0+αb)+220=A(x0+2αx0)+B(y0-2αp)+2C(x0+aα)(y0+αb)+2C(x0+2αx0)(y0-2αp)+2D(x0+aα)+2E(y0+αb)+F(5)2D(x0+2αx0)+2E(y0-2αp)+F0=A(x0+aα)+2C(y0+αb)+2D+μa0=2A(x0+2αx0)+2C(y0-2αp)+2D+2μx00=2B(y0+αb)+2C(x0+aα)+2E+μb0=2B(y0-2αp)+2C(x0+2αx0)+2E-2μp(7)其中第3,4个方程是关于x0和y0的线性方程,求其中第3,4个方程是关于x0和y0的线性方程,求解得到解得到©1994-2008ChinaAcademicJournalElectronicPublishingHouse.Allrightsreserved.http://www.cnki.net 462计算机辅助设计与图形学学报2008年222x0=(2BD+2aABα-2aCα-0=x0+2y0-12CE-Cbμ+aBμ)P(2(C2-AB)),220=2(x0+2αx0-10)+(y0+4αy0-2)-1;y0=(2CD-2bABα-2AE-Abμ+0=4x0+8αx0-40+2μx0222bCα+aCμ)P(2(AB-C));0=2y0+8αy0-4+4μy0将x0,y0代入到式(7)中,整理后,得到2个关于α由第3,4个方程求解出x0和y0,并代入第1,2个和μ的多项式方程1消去变量μ,得到一个关于α方程中,得到2个关于α和μ的方程1利用结式理的次数至多为2次的多项式方程1论消去μ,得到关于α的16次多项式h(α)=4215直线与抛物线间的最近距离40960000(4α+3)h2(α),其中设直线的方程可以表示为f(x,y)=ax+by+h2(α)=68569798833+1041198915888α+c,抛物线的方程表示为f(x,y)=x2-2py,则式235932203099600α+14865544006272α+(2)变为12891063802432α4-3323267602432α5-0=ax0+by0+c671387171545088α+186626736128α+20=(x0+aα)-2p(y0+αb)89(8)51195183104α-3747086336α-0=2(x0+aα)+μa101112764411904α+25165824α+4194304α10=-2p+μb22例21给定椭圆x+2y-1=0和4次曲线求解第3,4个方程得到x0=-a(bα+p)Pb,代入(x-3)4+(y-5)4-1=01得到方程组式(8)的第1,2个方程,得到0=x220+2y0-120=-a(αb+p)Pb+by0+c220=(x0+2αx0-3)+(y0+4αy0-5)-1;0=(-a(αb+p)Pb+αa)2-2p(y;0+αb)30=4(x0+2αx0-3)+2μx0将上式消去变量y0,得到一个关于α的次数为1次30=4(y0+4αy0-5)+4μy0232的多项式方程(2ba+2b)α+pa-2bc=01利用结式理论消去变量x0,y0和μ,得到一个关于表1中综合了上述平面二次曲线各种情形的结α的50次单变量多项式方程1果,其中,M1[6]表示文献[6]中的方法,M2表示本本文提出一种基于等距思想的最近距离计算方文的等距方法,表中的数字表示得到的单变量多项法,可以统一直接求解2条不相交的平面代数曲线式方程中所有因子多项式的最高次数1从表1中可间的最近距离1对于平面二次曲线间的最近距离,以看出,除直线P直线情形2个方法的次数均为1采用本文方法得到的单变量多项式方程的次数比文外,本文方法得到的单变量方程次数均低于文献[6]献[627]中方法得到的多项式的相应次数都要低,从中相应方程的次数1而可以降低求解方程过程中的计算复杂度或提高求表1最高次数的比较结果解的稳定性1理论上,本文方法也适用于求解平面上一条代数曲线与一条参数曲线间的最近距离1椭圆P双曲线抛物线直线M1[6]M2M1[6]M2M1[6]M2椭圆P双曲线161212842参考文献抛物线1289531直线423111[1]LatombeJC1Robotmotionplanning[M]1Boston:KluwerAcademicPublishers,1991[2]KimK2J1Minimumdistancebetweenacanalsurfaceanda3例子与结论simplesurface[J]1Computer2AidedDesign,2003,35(10):871-879下面以椭圆为例[3]ChenXD,YongJH,ZhengGQ,etal1Computingminimum,说明本文的等距方法1本文distancebetweentwoimplicitalgebraicsurfaces[J]1Computer2的例子都用Maple软件实现1AidedDesign,2006,38(10):1053-106122例11给定2个椭圆x+2y-1=0和2(x-[4]JiménezP,ThomasF,TorrasC13Dcollisiondetection:a2210)+(y-2)-1=01式(4)变为survey[J]1Computers&Graphics,2001,25(2):269-285©1994-2008ChinaAcademicJournalElectronicPublishingHouse.Allrightsreserved.http://www.cnki.net 4期陈小雕等:平面代数曲线间最近距离的计算463[5]JohnsonDE,CohenE1Aframeworkforefficientminimum[9]DupontL,LazardD,LazardS,etal1Near2optimaldistancecomputations[C]PPProceedingsofthe1998IEEEparameterizationoftheintersectionofquadrics[C]PPInternationalConferenceonRobotics&Automation,Leuven,Proceedingsofthe9thAnnualSymposiumonComputational1998:3678-3684Geometry,SanDiego,California,2003:246-255[6]LennerzC,SchÊmerE1Efficientdistancecomputationfor[10]KrishnanS,ManochaD1Anefficientsurfaceintersectionquadraticcurvesandsurfaces[C]PPProceedingsofGeometricalgorithmbasedonthelower2dimensionalformulation[J]1ACMModelingandProcessing1NewYork:IEEEComputerSocietyTransactionsonGraphics,1997,16(1):74-106Press,2002:60-69[11]PatrikalakisNM1Surface2to2surfaceintersections[J]1IEEE[7]SohnK2A,JüttlerB,KimM2S,etal1ComputingdistancesComputerGraphicsandApplications,1993,13(1):89-95betweensurfacesusinglinegeometry[C]PPProceedingsofthe[12]PatrikalakisN,MaekawaT1Shapeinterrogationforcomputer10thPacificConferenceonComputerGraphicsandApplications,aideddesignandmanufacturing[M]1Berlin:Springer2Verlag,NewYork,2002:236-2452002[8]ChenXiaodiao,YongJunhai,ZhengGuoqin,etal1TorusP[13]WeeC,GoldmanR1EliminationandresultantsPart1:sphereintersectionalgorithm[J]1JournalofComputer2Aidedeliminationandbivariateresultants[J]1IEEEComputerDesign&ComputerGraphics,2005,17(6):1202-1206(inGraphicsandApplications,1995,15(1):69-77Chinese)[14]WeeC,GoldmanR1EliminationsandresultantsPart2:(陈小雕,雍俊海,郑国勤,等1圆环面P球面求交算法[J]1multivariateresultants[J]1IEEEComputerGraphicsand计算机辅助设计与图形学学报,2005,17(6):1202-1206)Applications,1995,15(2):60-69©1994-2008ChinaAcademicJournalElectronicPublishingHouse.Allrightsreserved.http://www.cnki.netViewpublicationstats