Bézier样条曲线的近似弧长参数化方法

Bézier样条曲线的近似弧长参数化方法 Bézier样条曲线的近似弧长参数化方法 第24卷第10期 2007年10月 计算机应用与软件 ComputerApplicationsandSoftware Vo1.24No.10 Oct.2007 B6zier样条曲线的近似弧长参数化方法 白鸿武叶正麟 (西北工业大学理学院陕西西安710072) 石茂王树勋 (陕西师范大学数学系陕西西安710062) 摘要提出了B6zier样条曲线近似弧长参数化的方法及相应的算法.通过求出曲线近似二分之一弧长的点及其相应的参数 值,可将曲线分割为两条B6zier样条曲线.这两条曲线的弧长近似相等,因此让它们带有相同的权1.对新生成的B6zier样条曲线 不断重复上述工作,最终得到一条由多条B6zier样条曲线所构成的新的曲线.将这多条B6zier样条曲线合并为一条B6zier样条曲 线,进而通过节点插入技术将其转化为B样条形式的曲线以便得到全局参数,其中各段B6zier曲线在全局参数域中所占子区间的长 度与它们所具有的权成比例,这样便得到一条近似弧长参数化曲线. 关键词参数化算法B6zier曲线B6zier样条曲线 ANAPPRoXIMATEARC.LENGTHPARAMETERIZATIoN METHoDFoRB6ZIERSPLINECURVES BaiHongwuYeZhenglinShiMao?WangShuxun (FacultyofScience,NorthwesternPolytechnicalUniversity,Xi’an710072,Shaanxi,China) .(DepartmentofMathematicsandInformationScience,ShaanxiNormalUniversity,Xi’an710062,Shaanxi,China) AbstractAmethodofapproximatearc—lengthparameterizationforB6ziers plinecurvesandthecorrespondingalgorithmareproposed.The pointofapproximatelyhalf&re—lengthofthecurveisfound,andthecur veissubdividedatthecorrespondingparametervalue.ThustwoB6zier splinecurves&reobtained.Thetwocurveshaveapproximatelyequal&re—length,andweight1isassignedtoeachofthem.Repeatedworkis doneonthenewlygeneratedB6ziersplinecurves,andfinallyanewcurveconsistingofseveralB6ziersplinecurvesisobtained.TheseB6zier splinecurves&remergedintoone,andbymeansofknotinsertingtechnique,itisconvertedintoacurveofB—splineform.Thenewcurvehas aglobalparameter,inwhicheachB6ziercurvehasaparametersub—intervalo flengthproportionaltoitsweight.Thus,acurvewithapproximate &re—lengthparameterizationiSobtained. KeywordsP&rameterizationAlgorithmB6ziercurvesB6ziersplinecu rves 0引言 曲线参数化是CAGD中的重要问题之一.walker于1978 年提出了代数曲线可以有理参数化的充要条件,之后不断有 新的有理曲线的各种算法”出现.另一方面,要得到插值于 给定数据点的参数曲线,也要涉及对数据点的参数化问题.这 方面也已经有了大量的工作.上边提到的参数化方法尽管 努力向弧长参数化靠拢,但毕竟与真正意义上的弧长参数化还 有相当的距离.然而弧长参数化往往是十分困难的,甚至是不 可能的.因此,采用近似弧长参数化就不失为一种很好的替代 方法,而近似弧长参数化需要一个衡量近似程度的标准.为使 这种状况有所改善,Farouki曾提出了最优参数化的标准,并 试图按这个标准对曲线的参数化进行优化.然而,不论是上述 的参数化方法,还是对参数化的优化方法都不能对参数化的质 量——也就是所采用的参数化与弧长参数化之间的差异进行人 为的控制.由于这个原因,文献[11]给出了改善B6zier曲线参 数化效果的一种算法,以便对参数化的效果进行控制.这种算 法仅适用于B6zier曲线,但人们通常是用分段B6zier曲线而很 少用一条B6zier曲线来表示一条曲线,因而考虑B6zier样条曲 线的情形具有实际的意义.下面我们就来讨论如何对B6zier样 条曲线进行近似弧长参数化. 1参数化方法的 分析 定性数据统计分析pdf销售业绩分析模板建筑结构震害分析销售进度分析表京东商城竞争战略分析 及算法 设计 领导形象设计圆作业设计ao工艺污水处理厂设计附属工程施工组织设计清扫机器人结构设计 设r(t)=((t),Y(t),(t)),t?[0,1]是一条空间参数曲 线,0=t.<t,<…<t=1为区间[0,1]的一个等距划分.周知t 是弧长参数当且仅当(t)l;1.如果lr(t)IC,只需令 P(t)=r(t)/C即可得到lP(t)l;1.因此,可以用lr(t)I c来作为参数域中均匀分布的点对应于参数曲线上均匀分布的 点的等价条件.因而可以此作为参数化的出发点,而把…r 收稿日期:2006—11—13.基金项目:陕西省教育厅专项科研计划 项目(05JK309).白鸿武,副教授,主研领域:CAGD. 54计算机应用与软件2007年 (?)I—c=max(t)I—cI?作为参数化的一个准则. 现在,我们考虑这样一种参数化方法.假设r(t)是一条 B6zier样条曲线,它依次由B6zier曲线(t),r:(t),…,(t)组 成.对B6zier曲线r(t)用过其上的点的折线的长度近似代 替曲线r(t)的长度,用诸的和近似代替B6zier样条曲线的 长度;对B6zier曲线r(t)赋予权加=L/L.视[0,1]为B6zier 样条曲线的全局参数域,而诸r(t)依次在[0,1]中占有各自的 子区间,其长度与它所具有的权相同.将参数域[0,1]作2等 分,以连接B6zier样条曲线上相应分点的折线的长度近似代 替曲线的弧长S;从构成折线的第一条线段的长度开始逐次累 加,直至其和最接近L/2为止;记此时对应的参数分点为t;搜 索t.所属的与权加相对应的[0,1]的子区间一,s];令to= (t.,s)/(s一s【.1),对参数域[0,1]作2等分,以连接B6zier 曲线r(t)上相应分点的折线的长度近似代替曲线r(t)的弧 长S;从构成折线的第一条线段的长度开始逐次累加,直至参数 域中的分点t最接近,为止,记这个和为L;对曲线r(t)于 参数值f处进行分割,得两段B6zier曲线r(t)与(t).这 样,B6zier曲线rI(t)就变成了由r(t)与(t)构成的分段 B6zier曲线;让(t)具有权加fl=加L/L,让rl(t)具有权加 =加一加记由r(t),…,r一(t),r(t)构成的B6zier样条曲线 为r(t),记由(t),r…(t),…,(t)构成的B6zier样条曲线为 r(t);记r(t)的各条B6zier曲线的权和为加.,加=1一加;让r (t)的各条B6zier曲线的权除以加作为相应B6zier曲线的新 权.同样,让r(t)的各条B6zier曲线的权除以作为它们相 应B6zier曲线的新权;对r(t)与r(t)重复对r(t)的上述操作, 但对它们各自的局部参数域[0,1]作2等分,以便每一层次 的分割具有一致的尺度.反复进行上述的操作,直至满意为止. 如此便将原来的一条B6zier样条曲线变成了由多条B6zier样条 曲线所组成的曲线;将这多条B6zier样条曲线合并成一条 B6zier样条曲线R(t);由于R(t)中的各条B6zier曲线的权与它 们的近似弧长成比例,因此为了得到全局参数,若通过节点插入 技术将最终得到的B6zier样条曲线转化为B样条形式的曲线, 使其具有规范参数域[0,1],并使R(t)中的各条B6zier曲线在 新的全局参数域[0,1]中所占子区间的长度与他们各自的权成 比例,从而便得到了一条近似弧长参数化曲线.这种近似弧长 参数化方法的合理性与文献[11]中的情况是类似的. 现在根据上述B6zier样条曲线的重新参数化方法,给出相 应的参数化算法: B~zier样条曲线重新参数化算法 stepl(预处理)对B6zier样条曲线r(t)的每条B6zier曲 线计算其在整条B6zier样条曲线中的权(按照近似弧长进行分 配),得如下带权B6zier曲线: ((t),加1),(r2(t),加2),…,((t),加) 其中各条B6zier曲线的权和为1; step2若lev=0则转向stepl1(这里表示欲进行分割的 层数); ‘ step3让s0=0,s=加,.让B6zier曲线r(,)在整体参 数域[0,1]中对应于子区间一.,s]; step4均匀的取全局参数域[0,1]中n+1个点0=t.<t1 <?<t=1,这里=2; stel~计算B6zier样条曲线r(t)上与以上参数值对应的 点q0,q--,q,记lqiiqI=6,相应折线的长为; step6对诸6,从=1开始进行累加,直至其和大于L/2为 止.此时的记为i..;而第+1层中第r+1段中相应的记为 i; step7搜索,所属的子区间[s,s],对相应的Bezier曲 线r(t)于参数点to=(,_-)/(s一s一)处进行两段分割, 得B&ier曲线r1(t)与(t); stel~对参数域[0,1]作2等分,计算B6zier曲线r(t)上 过相应分点的折线的长度L;从构成折线的第一条线段的长度 开始逐次累加,直至参数域中的分点t最接近,为止,记这个 和为Ln;记加n=加Lil/L,加=加f一加?让r1(t)具有权, 让(t)具有权加&;现记由r(t),…,r(t),r(t)构成的 B6zier样条曲线为r(t),记由(t),r…(t),…,(t)构成的 B6zier样条曲线为r(t);记r(t)的各条B6zier曲线的权和为 加,记=1一加;让r(t)的各条B6zier曲线的权除以作为 相应B~zier曲线的新权.同样,让r()的各条B~zier曲线的权 除以作为它们相应B6zier曲线的新权; step9lev一1jlev.一1j: stepl0对r(t)与r(t)重复step2,stepl0的工作; stepll将以上各步所得的多条B6zier样条曲线顺次连接 成一条B6zier样条曲线; stepl2对stepl1所得的Bezier样条曲线通过节点插入技 术将其转化为B样条形式的曲线.并使其具有规范参数域 [0,1]. 由于上述算法只是对曲线进行了分割操作,因此从几何上 看曲线没有发生任何变化,仍然是原来的曲线.故曲线的几何连 续性没有发生变化.而且.曲线的次数与原曲线相同.但是,重 新参数化后.曲线的参数连续性显然发生了变化. 2应用实例 我们考虑由三条三次B6zier曲线顺次相接而成的平面 B6zier样条曲线.这三条B6zier曲线的控制顶点依次为:, 第一条:(0,一22.2),(1.5,一11.1),(3,一7.77),(4.1, 一 24.4): 第二条:(4.1,一24.4),(4.65,一32.7),(6,一32.2),(8, 一 27.7); 第三条:(8,一27.7),(11,一21.1),(16,一25.5),(19, 一 16.6). 按照上一节的算法,我们对 其进行近似弧长参数化.图1 中绘制了该B6zier样条曲线以 及经过五层分割后Ir(t)I的情 况,其中横坐标表示参数t,纵坐 标表示Ir(t)I.这里实线表示 分割之前的Ir(t)I,而虚线则表 示分割之后的Ir(t)I.可以看 出,分割之后的Ir(t)I已经非常 接近于一个恒定的常数.图2 图1分割前后Ir(t)I的情况 和图3则分别绘制了曲线参数化前后的情况. 第l0期白鸿武等:B6zier样条曲线的近似弧长参数化方法55 图2参数化前曲线的情况图3参数化后曲线的情况 3结论 可以看出,我们的方法具有以下的一些优点: (1)重新参数化前后,曲线的性质没有实质性的变化.由 于原来曲线为B6zier样条曲线,它实际上是分段多项式性质的, 而参数化后的曲线是B样条形式的曲线,其本质仍是分段多项 式曲线. (2)由于使用了B6zier曲线的分割技术,使得这种方法算 法非常简单,运算效率较高. (3)通过分割层数的选择,参数化的效果可以进行人为的控制. [7] [8] [9] [10] 参考文献 WalkerRJ.AlgebraicCurve[M].Berlin:Springer,1978. SendraJ,WinklerF.Parameterizationofalgebraiccurvesoveroptimal fieldextension[J].JournalofSymbolicComputation,1997,23(2/3): 557—576. VanHoeijM.Rationalparameterizationsofalgebraiccurvesusingca— nonicaldivisors[J].JournalofSymbolicComputation,1997,23(2/3): 209—227. GutierrezJ,RubioR,SchichoJ.Polynomialparametefizationofcurves withoutaaffinesingularities[J].ComputerAidedGeometricDesign, 2002,19(3):223—234. MorkenK,SchererK.Ageneralframeworkforhigh?accuracyparamet— ricinterpolation[J].MathematicsonComputation,1997,66(217): 237—260. SchabackR.OptimalgeometricHermiteinterpolationofcurves,in MathematicalmethodsforcurvesandsurfacesII[C].DahlenM,Lyche T,SchumakerLL(eds.).Nashville:VanderbihUniversityPress, 1998:417—428. SurazhskyT,SurazhskyY.Samplingplanarcurvesusingcurvature— basedshapeanalysis,inMathematicalmethodsforcurvesandsurfaces [C].Tromso2004.DahlenM,MorkenK,SchumakerLL(eds.). Brentwood:NashboroPress,2005:339—350. FloaterMS,SchurazhskyT.Parameterizationforcurveinterpolation [EB/OL].,tess/publications/curve— survey.pdf,2005. MaW,KruthJ.Parameterizationofrandomlymeasuredpointsforleast squaresfittingofB-splinecurvesandsurfaces[J].ComputerAided— 675. Design,1995,27(9):663— RidaTFarouki.Optimalparameterization[J].Computer—AidedDe— sign,1997,14(2):153—168. 白鸿武,叶正麟,张书玲.B~zier曲线的近似弧长参数化方法[J]. 计算机辅助设计与图形学,2006,18(8):1165—1168. (上接第43页) 棵R树的平均时间为(?t)/10,i?[1..10],如图1所示.针 对每棵R树随机产生10个查询窗口,窗口大小为每棵R树包 含对象所占区域的1/16,共进行100次查询,求平均值作为结 果,如图2所示. ×10 图1建立R树操作平均耗费时间图2查询操作平均耗费时间 图1表明建立R树的平均耗费时间,采用C.Linear分裂算 法要少于采用Quadratic分裂算法.原因在于C—Linear是线性 分裂,而Quadratic是二次分裂,前者一次分裂时间要比后者少, 当数据量比较大时,结点可能要进行数百次甚至上千次分裂,从 而C—Linear分裂算法在较大数据量的条件下,分裂时间要好于 Quadratic分裂算法. 图2中,采用C—Linear分裂算法的R树平均查询时间要比 采用Quadratic分裂算法的R树平均查询时间少17%左右.这 是因为C—Linear分裂算法运用分割聚类技术将地理空间中位置 相邻的对象尽可能地组织到同一个R树结点中,减少了无效查 询的次数.而Quadratic分裂算法选择一对分裂后不可能在同 一 组中出现的两个矩形作为种子矩形进行结点分裂,在数据量 较大时不能在地理空间上保证位置相邻的矩形对象被分配到同 一 结点中,从而降低了查询效率. 4结束语 本文分析了R树索引机制结点分裂 方案 气瓶 现场处置方案 .pdf气瓶 现场处置方案 .doc见习基地管理方案.doc关于群访事件的化解方案建筑工地扬尘治理专项方案下载 存在的不足,考虑到 结点分裂算法在索引过程中起着关键『生的作用,提出了基于分割聚 类技术的R树结点线性分裂方案(CLinear分裂算法).在进行R 树的操作过程中,当有结点溢出时,采用聚类分割技术进行索引项 的分配.最后从定『生和定量两个方面对结点的分裂算法进行了分 析和测试,结果表明C—Linear分裂算法具有较好的性能,在数据量 较大的GIS数据库的检索中具有很好的应用前景. 参考文献 [1]GuttmanR—trees:adynamicindexstructureforspatialsearching[C]. InProceedingsoftheACMSIGMODConferenceonManagementofDa— ta,1984:47—57. [2]BeckmannN,KriegelHP,SchneiderR,SeegerB.TheR一tree:Anef- fieientandrobustaccessmethodforpointsandrectangles[C].In:Pro— ceedingsofSIGMOD,AtlanticCity,NewJersey,1990:322—331. tree:AnImprovedR—treeUsingFractals [3]KamelC,FaloutsosHilbe~R— [C].InProceedingsofthe20ConferenceonVeryLargeDataBases (VLDB),1994:500—509. [4]HuangPW,LinHY,LinPL.OptimizingStorageUtilizationinR—tree DynamicIndexStructureforSpatialDatabases[J].TheJournalofSys— ternsandSoftware,2001,55(3):291—299. 15JBrakatsoulasS,PfoserD,TheodoridisY.RevisitingR?treeConstruction Pronciples[C].Inproceedingsof6ADBIS,2002:149—162. [6]HanJ,KamberM.DataMining:ConceptsandTechniques[M].Morgan Kaufmann,2001. [7]UniversityofCalifornia.RiversideDeoartmentofComputerScienceand Engineering.,marioh/spatialindex/[OL]. Sourcecodev0.83b.2005—06—22. 123456 rirLrLrL