圆弧的四次Bézier曲线逼近

针对Bézier曲线不能精确表示圆弧,导致在基于Bézier曲线曲面造型的CAD系统中存在圆弧的Bézier曲线逼近问题,提出一种用四次Bézier曲线逼近圆弧的方法.根据圆弧与Bézier曲线都具有的对称性确定带待定参数的Bézier曲线的控制顶点;再由误差函数的零点分布情况确定待定参数,给出控制顶点的计算公式、误差的解析表达式和逼近阶.与采用已有方法得到的最好结果相比较,文中方法的逼近阶虽然也是8,但系数不到已有方法的一半,因而具有更好的逼近精度.     

双曲面片的高精度多项式逼近

用三次Bezier曲线逼近双曲线段，在端点保持GC^1插值，给出单边逼近的误差，并进行最优插值点的选择，得到最优的误差估计；在此基础上，用双三次Bezier多项式逼近单叶和双叶双曲面片，给出误差估计，逼近六到六阶精度。相邻的逼近片之间GC^1连续。     

Bézier曲线合并的区间逼近

从区域逼近的全新角度来研究几何逼近的核心问题之一:曲线的近似合并.给出了将两条或多条平面Bézier曲线合并为一条尽量细窄的区间Bézier曲线的两种方法:一是基于求已知Bézier样条曲线的上下边界直接得到区间控制顶点的值,从而诱导出一条区间合并Bézier曲线;二是基于最小二乘法求出原多段Bézier曲线合并结果的最佳一致逼近曲线作为区间Bézier曲线的中心曲线,再取区间Bézier点为常值域或变值域来得出两种误差曲线.给出大量实例来展示上述算法的逼近效果,并进行分析与比较.结果表明,算法在实现外形信息的几何逼近及数据转换方面有明显的应用前景,并可推广于空间Bézier曲线、圆域Bézier曲线、有理Bézier曲线的合并.     

Bézier曲线的等距曲线的同次多项式逼近

等距曲线广泛应用工数控机床加工过程、机器人行走路线、刺绣针法生成等工业领域中,与基曲线相比,其表示更为复杂,基本小能用有理曲线来精确表示.为了使等距曲线与CAD/CAM系统更好地相容,基于圆弧的Bézier多项式逼近,提出一种Bézier曲线的等距曲线的同次多项式逼近方法.首先利用Tchebyshev多项式逼近圆弧,并由此得到圆弧的任意次数的Bézier多项式逼近;然后利用上述圆弧逼近的方法去逼近等距曲线的基圆.进而推导出了一种Bézier曲线的等距曲线多项式逼近方法,得到等距逼近曲线是与基曲线次数相同的Bézier曲线.最后通过实例与其他基于圆弧逼近的等距曲线逼近方法进行了比较,结果表明,文中方法与其他方法具有相似的逼近效果,但大大降低了逼近次数.     

Bernstein多项式推广及其所生成的拟Bézier曲线

文章对Bernstein多项式进行推广,用函数f(t)代替变量t,所生成的拟Bézier曲线不仅拥有与Bézier曲线相类似的性质,而且能产生一些好的特性,如通过调节因子可以改变拟Bézier曲线的次数,使拟Bézier曲线拼接时有更大的自由度和灵活性,有一定的应用和研究价值。     

OR插值曲线构造及Bézier曲线逼近

根据平面多项式曲线的等距有理参数化条件,构造了具有不同连续阶的OR插值曲线.由于OR曲线可通过恰当的参数变换产生有理形式的等距线,因此根据给定B啨zier曲线离散端点条件,可构造特定连续阶的OR样条曲线来逼近该Bézier曲线,而将OR样条曲线的精确等距线作为B啨zier曲线的逼近等距线.     

圆弧的五次PH曲线等弧长逼近

针对圆弧多项式逼近中弧长不相等的问题,对给定圆弧在逼近多项式插值圆弧端点和端点切向量的条件下,结合PH曲线弧长可用多项式精确表示的性质,提出等弧长多项式逼近方法,并给出了五次PH多项式逼近圆弧的精确表示.最后通过实例说明了该方法的有效性.     

椭圆offset曲线的多项式逼近算法

首先对椭圆进行必要的细分,然后将每一段椭圆弧的offset曲线用一段Bézier曲线逼近,进而得到G1连续的分段Bézier曲线作为椭圆offset曲线的近似.该算法一方面给出了计算Bézier曲线段控制顶点的表达形式,计算简单;另一方面对offset曲线的逼近误差给出了整体估计,并且利用整体误差估计决定细分椭圆的段数,构造了满足给定容差的近似曲线.     

带双参数的Bézier型三角多项式曲线

给出了带有双参数的三角多项式曲线,称为λT-Bézier曲线.其不但具有Bézier曲线类似的性质,还可以表示二次曲线、超越曲线.对参数的不同设置使得曲线具有较强的可调性--λ1 λ2越大曲线越靠近控制多边形.在拼接时可达G3连续.实例给出了该类曲线的有效性.     

COMPUTING AREAS BOUNDED BYRATIONAL BEZIER CURVES

ＣＯＭＰＵＴＩＮＧＡＲＥＡＳＢＯＵＮＤＥＤＢＹＲＡＴＩＯＮＡＬＢＥＺＩＥＲＣＵＲＶＥＳＧｕｏｊｉｎＷａｎｇ；ＴｈｏｍａｓＷ．ＳｅｄｅｒｂｅｒｇＣＯＭＰＵＴＩＮＧＡＲＥＡＳＢＯＵＮＤＥＤＢＹＲＡＴＩＯＮＡＬＢＥＺＩＥＲＣＵＲＶＥＳ￥ＧｕｏｊｉｎＷａｎｇ...     

三向四次箱样条曲面与Bezier曲面的光滑拼接

以二元四次多项式在三角域和矩形域上的Bezier形式的Blossom为工具,给出了当给定一张三向四次箱样条曲面时,能与之C^0、C^1、C^2拼接的三边或矩形Bezier曲面的控制顶点所要满足的一个显式表示的充分条件。这一结果在使用三向四次箱样条曲面或Loop细分曲面造型,而又需要构造Bezier曲面与之拼接或补洞时,具有理论和实际应用价值。     

矩形孔径柱面镜面形拟合基底多项式研究

对矩形孔径柱面镜面形的拟合方法进行了研究,将矩形域的扩展Zernike多项式与Chebyshev多项式分别作为面形拟合基底,对导出面形数据进行波面复原,分析赛德像差与拟合基底的对应关系对比拟合结果,Chebyshev多项式较矩形域的扩展Zernike多项式有较好的像差分离能力。     

有理三次Bezier曲线表示圆弧的一种实用方法

在圆弧的标准型有理二次贝齐尔表示的基础上,给出了圆弧的带参数的标准型有理三次贝齐尔一种更实用的表示形式,通过调节参数的值,就可以得到同一圆弧不同的标准型有理三次贝齐尔表示。就参数对内控制点、两内权因子及肩点的影响进行了详细分析,从而对圆弧的标准型有理三次贝齐尔形式表示的内在性质有了更深入的了解。     

欧氏空间货郎担问题的一个多项式时间近似方案的改进与实现

货郎担问题的实例是给定n个结点和任意一对结点{i,j}之间的距离di,j,要求找出一条封闭的回路,该回路经过每个结点一次且仅一次,并且费用最小,这里的费用是指回路上相邻结点间的距离和.货郎担问题是NP难的组合优化问题,是计算机算法研究的热点之一.在过去几十年中,这一经典问题成为许多重要算法思想的测试平台,并促使一些研究领域的出现,如多面体理论和复杂性理论.欧氏空间上的货郎担问题,结点限制在欧氏空间,距离定义为欧氏距离.即使是这样,欧氏空间上的货郎担问题仍然是NP难的.1996年,Arora提出欧氏空间上货郎担问题的第1个多项式时间近似方案.对其中货郎担问题的算法进行了改进：提出一种新的构造方法,使应用于该算法的“补丁引理”结论由常数6改进到常数3,从而使算法的时间复杂度大幅减少;同时,编程实现了该算法,并对实验结果进行了分析.     

边缘识别的二维正交多项式拟合及结构变形检测

数字图像中边缘附近的灰度是沿边缘方向和跨边缘方向二维变化的,以前边缘识别的多项式拟合大多采用跨边缘方向的一维拟合。介绍一种采用二维正交多项式进行边缘识别的新方法,由于二维拟合更符合边缘附近小区域内像素灰度二维变化的实际,因此拟合结果优于一维拟合。在进行拟合时,利用正交多项式的正交性将优化方程对角化,避免求逆或解方程,没有多项式拟合优化方程的病态问题,采用高阶多项式拟合可以提高拟合精度。对生成图像的边缘识别结果表明,二维正交多项式拟合识别边缘的精度和稳定性较好。简支梁模型试验表明,采用正交多项式边缘拟合方法检测梁的静变形,图像变形检测精度在0.1像素之内,适当选择图像采集设备和采集范围,点检测精度与传统检测方法的精度相当,边缘检测属线状高密度检测,检测范围远大于传统方法。     

张量积Bézier曲面降多阶逼近

给出了一种基于最小二乘范数下的Bézier曲面降多阶逼近误差的矩阵计算公式。根据带角点高阶插值条件下原张量积Bézier曲面与降多阶张量积Bézier曲面的误差函数在[0,1]x[0,1]上取极小值,得到降多阶张量积Bézier曲面的控制顶点的矩阵表达式。通过数值例子显示采用该方法所得的降多阶曲面对原曲面有较好的逼近效果。将Bézier曲线降阶逼近的迭代方法推广到曲面,得到曲面降阶逼近的迭代方法,并给出了相应的数值实例。     

具有局部性质的球面插值样条曲线的构造

高维球面样条曲线拟合技术在计算机动画和惯性导航等领域都受到广泛地关注.实际中常需球面曲线插值给定的数据点,并要求曲线具有一定的连续性和良好的局部性质.此前的方法存在一定的局限性.为此,基于球面Bézier曲线,提出了一种仅利用插值点位置信息便可在任意维空间中构造C 2球面插值样条曲线的新方法.首先,通过映射拟合出了插值...     

代数曲线分段逼近的误差分析

针对代数曲线分段逼近的误差函数,展开深入的理论分析,给出了由误差公式确定误差界的一般算法。定义了一种新型误差,它具有几何意义直观、计算比较简单的特征。结合数值实例,验证了新型误差的实用价值。     

Polynomial time approximation algorithms for proportionate open‐shop scheduling

This paper deals with the presentation of polynomial time (approximation) algorithms for a variant of open‐shop scheduling, where the processing times are only machine‐dependent. This variant of scheduling is called proportionate scheduling and its applications are used in many real‐world environments. This paper develops three polynomial time algorithms for the problem. First, we present a polynomial time algorithm that solves the problem optimally if , where n and m denote the numbers of jobs and machines, respectively. If, on the other hand, , we develop a polynomial time approximation algorithm with a worst‐case performance ratio of that improves the bound existing for general open‐shops. Next, in the case of , we take into account the problem under consideration as a master problem and convert it into a simpler secondary approximation problem. Furthermore, we formulate both the master and secondary problems, and compare their complexity sizes. We finally present another polynomial time algorithm that provides optimal solution for a special case of the problem where .