On the Approximation Order of Tangent Estimators G Albrecht

Gudrun Albrecht

Description

Niveau: Supérieur, Doctorat, Bac+8
On the Approximation Order of Tangent Estimators G. Albrecht ENSIAME - LAMAV/CGAO J.–P. Becar IUT - LAMAV/CGAO Universite de Valenciennes et du Hainaut–Cambresis Le Mont Houy F-59313 Valenciennes Cedex 9 G. Farin D. Hansford Department of Computer Science Arizona State University Tempe, AZ 85287-8809 February 2, 2007 Abstract A classic problem in geometric modelling is curve interpolation to data points. Some of the existing interpolation schemes only require point data, whereas others, require higher order information, such as tangents or curvature values, in the data points. Since the given, mea- sured data usually lack this information, estimation of these quantities becomes necessary. Several tangent estimation methods for planar data points exist, usually yielding different results for the same given point data. The present paper thoroughly analyses some of these meth- ods with respect to their approximation order. Among the considered methods are the classical schemes FMILL, Bessel, and Akima as well as a recently presented conic precision tangent estimator. The ap- proximation order for each of the methods is theoretically derived by distinguishing purely convex point configurations and configurations with inflections. The approximation orders vary between one and four 1

• tangent vector


• x4y22 ?


• conic based


• l¯12 ?


• akima's method


• most popular schemes


• geometric modelling


• there exist


• farin farin

Sujets

• Hansford
• Albrecht
• Tangent vector
• Computer-aided design
• Existential quantification

Informations

• Publié par: profil-zyak-2012
• Nombre de lectures: 28
• Langue: English

Extrait

OntheApproximationOrderofTangentEstimators G.Albrecht [e-mail] ENSIAME-LAMAV/CGAO J.–P.Be´car [e-mail] IUT-LAMAV/CGAO Universite´deValenciennesetduHainaut–Cambre´sis LeMontHouy F-59313ValenciennesCedex9 G.Farin [e-mail] D.Hansford [e-mail] DepartmentofComputerScience ArizonaStateUniversity Tempe,AZ85287-8809 February2,2007 Abstract Aclassicproblemingeometricmodellingiscurveinterpolationto datapoints.Someoftheexistinginterpolationschemesonlyrequire pointdata,whereasothers,requirehigherorderinformation,suchas tangentsorcurvaturevalues,inthedatapoints.Sincethegiven,mea- sureddatausuallylackthisinformation,estimationofthesequantities becomesnecessary.Severaltangentestimationmethodsforplanar datapointsexist,usuallyyieldingdifferentresultsforthesamegiven pointdata.Thepresentpaperthoroughlyanalysessomeofthesemeth- odswithrespecttotheirapproximationorder.Amongtheconsidered methodsaretheclassicalschemesFMILL,Bessel,andAkimaaswell asarecentlypresentedconicprecisiontangentestimator.Theap- proximationorderforeachofthemethodsistheoreticallyderivedby distinguishingpurelyconvexpointconfigurationsandconfigurations withinflections.Theapproximationordersvarybetweenoneandfour 1

forthedifferentmethods.Numericalexamplesillustratethetheoreti- calresults. 1Introduction Aclassicproblemingeometricmodellingiscurveinterpolationtodata points.Differentinterpolationschemesexist,see,e.g.,[4].Someofthem onlyrequirethepointdata,whereasothers,especiallythepiecewisein- terpolationschemes,requirehigherorderinformation,suchastangentsor curvaturevalues,inthedatapoints.Sincethegiven,measureddatausually lackthisinformation,estimationofthesequantitiesbecomesnecessary. Thispaperdealswiththeproblemofestimatingtangentsingivenpla- nardatapoints.Thereexistdifferentmethodsforthispurpose.Wecom- parefiveschemes,thatarepopularintheCAGDarea,firstwithrespectto theirpracticalperformance,andthenwethoroughlyinvestigatetheirrespec- tiveapproximationorders.TheconsideredtangentestimatorsareFMILL’s method,Bessel’sandAkima’smethod,see[4],aswellasacirclebasedanda generalconicbasedmethod.Conicbasedtangentestimatorsare,e.g.,used in[8,5,6]. FMILL’s,Bessel’sandthecirclebasedmethodtakethreeconsecutive pointsasinputdata,andthetangentisestimatedinthemiddlepoint. FMILLsimplyproducesalineparalleltotheonejoiningthefirstandthe thirdpoint,Besseltakesthetangenttoaparametricparabolainterpolating thethreepoints,andthecirclebasedmethodusesthetangenttothecircle interpolatingthethreedatapoints.Akima’smethodandtheconicbased methodtakefiveconsecutivepointsestimatingthetangentinthethird point.AsBessel’smethodalsoAkima’smethodneedsparametervaluesin thedatapointstobeestimated,andobtainsthetangentvectorbyacertain weightedcombinationofthefivedatapoints.Themorerecentconicbased method[1]producesthetangenttotheinterpolatingconicofthegivenfive points.Itusesasimplealgorithmthatisbasedonatheoremfromclassical projectivegeometry,so–calledPascal’stheorem,andthusnecessitatesvery fewcomputationstoachievethistangentwithconicprecision,incontrast tocomputingtheimplicitconic. Regardingthecomparisonofthesefivemethods,experimentsclearly illustrateabetterperformanceoftheconicbasedmethodwithrespectto theotherschemesshowingahighsuitabilityforapplicationsinthearea ofconvexitypreservinginterpolation.Inasubsequenttheoreticalstudywe determinetheapproximationordersofallfiveconsideredtangentestimation methods,andthusprovethatforconvexconfigurationstheconicbased methodisofapproximationorderfour,whereasthecirclebasedmethodhas approximationordertwo,andFMILL’s,Bessel’sandAkima’singeneral onlyhaveapproximationorderone.Inthecaseofinflectionpointswe 2