单圆弧样条保形插值算法

该文以插值具有偶数个点的闭多边形为例提出了一种新的圆弧样条插值算法。这种算法具有以下3个特点：（1）生成的圆弧样条曲线具有保形的特点；（2）圆弧样条中圆弧的段数与型值点个数相同。（3）圆弧段之间的连接点不一定在插值的型值点上，这样就能用更多的自由度来控制拟合曲线的形状。同此文中还提出了一个优化的算法来得到光顺的插值曲线，同时还给出了几个例子加以说明。     

约束双圆弧插值

提出一种构造C-型双圆弧和S-型双圆弧的算法,该双圆弧的2个端点为给定的点,在端点处的2个切向量为给定的切向量,且完全位于一条给定直线的一侧.对于C-型双圆弧,分12种情况给出不等式直接判断双圆弧是否满足位于给定直线一侧的约束条件.如果存在多个同时满足插值条件和直线约束条件的双圆弧,则通过求解一个最小值问题选出最优的双圆弧;否则,通过添加一个额外的点构造2段双圆弧.对于S-型双圆弧也给出一些带直线约束的插值结果.     

R3中的双圆弧样条

本文主要结果是将平面R3中的双圆弧样条拓广成空间R3中的双圆弧样条,得到了给定空间R3中的两点及其单位矢量的双圆弧形式,并且当给定点与其单位切矢共面时,空间双圆弧自动退化为平面双圆弧.在求得型值点处导矢进行双圆弧拟合时,我们采用了拓广的空间转轴三次样条和局部的方法.最后给出双圆弧逼近计算的实例.     

基于误差控制的自适应3次B样条曲线插值

针对现有曲线插值算法不能有效压缩型值点的缺陷,研究了一种自适应三次B样条曲线插值算法。从型值点序列中选用最少的点插值一条初始曲线,基于提出的点到曲线的最小距离计算方法,分别计算各非插值点对应的插值误差,并从中提取最大插值误差。若最大误差大于给定的误差阈值,则将其对应的型值点加入插值型值点序列,重新插值曲线,直到最大插值误差满足误差要求。与现有曲线插值算法相比,该算法可以在保证插值精度的前提下有效压缩数据量。     

改进的Kasa算法及其在圆拟合中的精度分析

Kasa算法是应用最为广泛的代数圆拟合方法之一,但在短圆弧采样条件下拟合结果不够理想,且拟合精度随圆半径的减小而变差.在Kasa代数算法的基础上,提出RS约束算法.通过坐标旋转使采样点具有对称性,以横坐标最大值作为半径约束条件修正拟合算法.仿真测试验证了RS约束算法具备更强的鲁棒性,能够消除半径变化对拟合精度的影响,在短圆弧情况下该算法的拟合精度远优于Ka-sa算法.     

圆渐开线平面插值样条及其应用

利用拼接的圆渐开线实现对平面上的数据点及其切向的插值,通过解决两点及其切向的圆渐开线插值,以及在各种不同情况下的插值处理方法,提供了圆渐开线平面插值样条的生成算法,由于圆渐开线为凸曲线,其曲率与弧长成反比,因此其样条曲线对插值曲线的形状控制是有利的,并可作为圆弧样条插值方法的一种扩展。     

特征点的B样条曲线逼近技术

为了构造逼近稠密有序点列的初始曲线,提出一种B样条曲线逼近的节点配置算法.以初始曲线的曲率极值点和点列的2个端点作为特征点的种子点,利用最小二乘法构造逼近种子点的B样条曲线,并根据B样条曲线段的复杂度进行特征点的细分和节点矢量的更新;重复这一过程,直到逼近的误差小于给定的阈值,实现B样条曲线的精确逼近.实例结果表明,在相同的给定阈值条件下,文中算法可比Park算法、Piegl算法和Li算法减少更多的控制顶点,逼近曲线的控制顶点数等于细分后的特征点数,且逼近曲线的节点分布合理.     

二次均匀B样条曲线的双圆弧逼近方法*

提出了一种用双圆弧对二次均匀B样条曲线的分段逼近方法。首先,对一条具有n 1个控制顶点的二次均匀B样条曲线按照相邻两节点界定的区间分成n-1段只有三个控制顶点的二次均匀B样条曲线段;然后对每一曲线段构造一条双圆弧进行逼近。所构造的双圆弧满足端点及端点切向量条件,即双圆弧的两个端点分别是所逼近的曲线段的端点,而且双圆弧在两个端点处的切向量是所逼近的曲线段在端点处的单位切向量。同时,双圆弧的连接点是双圆弧连接点轨迹圆与其所逼近的曲线段的交点。这些新构造出来的双圆弧连接在一起构成了一条圆弧样条曲线,即二次均匀B样条曲线的逼近曲线。另外给出了逼近误差分析和实例说明。     

数据点加权最小二乘渐进迭代逼近及其B样条曲线拟合

为了使B样条拟合曲线插值部分数据点且逼近其余数据点,提出数据点加权的最小二乘渐进迭代逼近(DW-LSPIA)算法,证明了其收敛性并以它为基础提出一种B样条曲线拟合算法.首先赋初始权重于每个数据点,用DW-LSPIA算法生成初始拟合曲线;然后根据待插值点与拟合曲线上对应点的误差调整待插值点的权重,并重新运用DW-LSPIA算法生成新的拟合曲线;如此迭代,直至拟合曲线达到插值要求.实例结果表明,该拟合算法鲁棒、高效,也可使拟合曲线保形.     

圆弧曲线的三次NURBS表示

本文首次提出三次ＮＵＲＢＳ曲线精确地表示圆弧的充要条件，解决了两方面的问题：一是已知三次ＮＵＲＢＳ曲线，如何判断它是否是圆弧，二是已知一圆弧曲线，怎样用三次ＮＵＲＢＳ曲线精确地表示，给出了圆弧曲线的三次ＮＵＲＢＳ表示的几何构造算法，均匀有理Ｂ样条曲线和有理Ｂｅｚｉｅｒ曲线精确地表示圆弧曲线的充要条件可作为ＮＵＲＢＳ曲线的特殊情形得到，这些研究结果为ＮＵＲＢＳ应用于ＣＡＧＤ，ＣＡＤ／ＣＡＭ提供了一个     

曲线插值的一种保凸细分方法

为了弥补以四点插值细分方法为代表的线性细分方法在形状控制方面的缺陷,提出一种基于几何的插值型保凸细分方法.细分过程每一步中,每条边所对应的新控制顶点由原控制顶点及其切向共同确定;每点处的切向由其邻近的点所确定,并且随细分过程逐步调整.理论分析表明,该方法的极限曲线是G1连续的保凸曲线.如果所有的初始点取自圆弧段,则极限曲线就是该圆弧段.数值实例表明,采用文中方法得到的曲线较为光顺.     

布氏硬度自动测量中多圆检测方法

圆检测应用广泛,是布氏硬度自动测量的关键。针对圆检测中存在圆分裂、多个圆、不完整圆的情况,提出一种基于交叉圆合并、凸包点迭代纯化最小二乘拟合的圆检测方法。首先对图像进行纹理增强并二值化,其次提取有效区域的最小外接矩形,并得到圆弧与最小外接矩形的三个切点,得到初始圆,然后合并有交叉的圆。最后求合并圆的轮廓点与其凸包的交集,进行迭代纯化最小二乘拟合,最终得到亚像素级的圆半径值。最后通过实际应用测试,验证了论文方法的有效性。     

Correct Delaunay Triangulation in the Presence of Inexact Inputs and Arithmetic

The construction of the Delaunay triangulation depends on the correct determination of whether or not a fourth point is inside the circle determined by three other points. By modeling the data points as disks and examining the associated mutual tangent circles, we show how to construct an incircle test that is reliable and sharp, one that is not corrupted by round-off error, one that can deal with inexact input data, avoids rational and big integer arithmetic, and brings geometry to the forefront instead of error analysis or arithmetic.     

Curve fitting and fairing using conic splines

We present an efficient geometric algorithm for conic spline curve fitting and fairing through conic arc scaling. Given a set of planar points, we first construct a tangent continuous conic spline by interpolating the points with a quadratic Bézier spline curve or fitting the data with a smooth arc spline. The arc spline can be represented as a piecewise quadratic rational Bézier spline curve. For parts of the G¹ conic spline without an inflection, we can obtain a curvature continuous conic spline by adjusting the tangent direction at the joint point and scaling the weights for every two adjacent rational Bézier curves. The unwanted curvature extrema within conic segments or at some joint points can be removed efficiently by scaling the weights of the conic segments or moving the joint points along the normal direction of the curve at the point. In the end, a fair conic spline curve is obtained that is G² continuous at convex or concave parts and G¹ continuous at inflection points. The main advantages of the method lies in two aspects, one advantage is that we can construct a curvature continuous conic spline by a local algorithm, the other one is that the curvature plot of the conic spline can be controlled efficiently. The method can be used in the field where fair shape is desired by interpolating or approximating a given point set. Numerical examples from simulated and real data are presented to show the efficiency of the new method.     

Determining Digital Circularity Using Integer Intervals

Digital circularity is a well-researched topic for its real-world practicality to circularity measure, estimation of discrete curvature, circular arc segmentation, etc. The proposed work reveals a novel technique to determine whether a digital curve segment is digitally circular using the correspondence of its constituent runs with the square numbers in integer intervals. The notion of radii nesting is used to successively analyze these runs of digital points. Two algorithms have been proposed along with their demonstrations and detailed analysis, and a simple-yet-effective solution has been provided to expedite them using infimum circle and supremum circles that bound the initial range of radii. We have also shown how the proposed technique can be used for segmentation of an arbitrary digital curve segment into a sequence of circular arcs. Experimental results have been given to demonstrate the efficiency and elegance of the proposed technique.     

基于遗传算法的以线段和圆弧为基元的曲线拟合

采用线段和圆弧作逼近基元是数字曲线拟合中的一个难点。文中给出一种基于改进遗传算法的拟合方法。通过对点列进行二进制编码，以拟合段数较少和拟合误差较小为优化目标，变异概率和交叉概率自适应生成，并根据相关知识控制分界点间隙，所得最优解中值为1的基因对应数字曲线的分界点，对线段与圆弧相交和相切以及具有噪声等多种情况进行检测，可同时提取尖点和切点，还可得到逼近基元及其之间关系。较好地解决了用线段和圆弧拟合曲线问题。     

基于切线段匹配的快速圆弧检测算法

针对目前工程图纸矢量化过程中圆弧检测准确率不高、检测时间过长等问题,提出一种基于切线段匹配的快速圆弧检测算法。首先,该方法找出可能位于圆外边界上八方向(0,π/4,π/2,…,7π/4)与圆相切的线段,并记录在切线集合中;然后,对已找到的切线段进行两两配对,估算圆心半径范围,得到候选圆集合;最后,对获取的候选圆集合进行数据合并,对合并后的每一个候选圆进行跟踪检测,最终确定它是一个圆还是一个弧。在切线段寻找过程中进行匹配,对已确定为圆的候选圆,在切线段集合中去除与该圆相对应切线段,有效减少了匹配次数。在对比实验中,所提算法的平均识别率达到了97.250%,平均检测时间为12.290 s, 比随机抽样一致性(RANSAC)算法和有效投票算法(EVM)的平均识别率更高,平均检测时间更短。实验结果表明,所提算法能够有效地对低噪声图像中弧长大于1/8圆周长的圆弧进行检测,同时能提高检测准确率、缩短检测时间。     

A note on planar minimax arc splines

Arc splines are planar, tangent continuous, piecewise curves made of circular arcs and straight line segments. They are important because they can be used as the cutting paths for numerically controlled cutting machinery. This paper presents an algorithm for finding an arc spline that is a minimax approximation to discrete data.