一种圆度误差评估的计算几何方法

摘要

本发明涉及测试计量技术领域，且公开了一种圆度误差评估的计算几何方法，步骤一：首先利用格雷厄姆(Graham)方法求得平面点集P中位于其凸壳上的有序点集P

说明书

技术领域

本发明涉及测试计量技术领域，具体为一种圆度误差评估的计算几何方法。

背景技术

在测试计量领域，最小覆盖圆方法(简称3M法)是评定圆度误差的重要方法。

对于3M法的研究已有诸多报道，但是目前有效的方法并不多见，各类方法有自己的局限性。函数逼近的3M方法得到的是最小覆盖圆圆心与半径的近似值，严格地说所求并不是真正最小的覆盖圆。最优化的方法把圆心位置作为优化参数，把外接圆的半径作为优化目标，采用各种有效算法来搜寻最小覆盖圆的圆心，这种方法耗时长、效率较低，得到的也不是准确结果。另外，基于二次规划的3M法原理深奥，给使用者造成理解和编程困难，计算效率也不高。为此，提出一种圆度误差评估的计算几何方法。

发明内容

(一)解决的技术问题

针对现有技术的不足，本发明提供了一种圆度误差评估的计算几何方法，不仅能精确确定最小覆盖圆圆心位置和半径长度，而且方法的原理简单，解结构固定，计算效率高，容易编程实现，适合大规模并行计算和后续有需要严格分析的场合，解决了背景技术提出的问题。

(二)技术方案

为实现上述的目的，本发明提供如下技术方案：一种圆度误差评估的计算几何方法，步骤一：首先利用格雷厄姆(Graham)方法求得平面点集P中位于其凸壳上的有序点集P

ⅰ.将P中y坐标最小的点设为p

ⅱ.从p

①k＝4

②j＝2

③如果p

④j＝j+1，转到③，直到j＝k-1

⑤k＝k+1，转到②，直到k＝n+1(注意，因为节点编号随着节点的删除是在不断减少的，所以在算法过程中n也是在不断减少的)

经过以上删除过程后，剩下的有序点集记为P

步骤二：从点集P

步骤三：

在点集P

步骤四：Δp

进一步优选的，所述步骤1中的格雷厄姆方法的特点是除了位于相对基点(p

进一步优选的，所述步骤一到步骤四中，由于点集P有n个点，先看第一步的步骤ⅱ中转移到②的次数不会超过n，每一个顶点至多删去1次，删去顶点的个数也不可能超过n，因此第一步的步骤ⅱ是线性时间复杂度，第一步的步骤ⅰ很显然涉及到角度的排序问题，要计算n-1个夹角，并按夹角分类，计算每个夹角只需要常数时间，计算n-1个夹角耗费线性时间，分类需要时间O(n log n)，因此，第一步格雷厄姆算法部分总的时间复杂性为O(n logn)，第二步、第三步处理的集合点数相对原始集合P来说少的多，且为线性时间开销，第四步为常数时间，故所提计算方法总的时间复杂度近似为O(n log n)。

(三)有益效果

与现有技术相比，本发明提供了一种圆度误差评估的计算几何方法，具备以下有益效果：

该圆度误差评估的计算几何方法，基于计算几何思想给出了一种高效实用的圆度误差评估的方法，所提出的方法不仅能精确确定最小覆盖圆圆心位置和半径长度，而且方法的原理简单，解结构固定，计算效率高，容易编程实现，适合大规模并行计算和后续有需要严格分析的场合，适合于需要精确评估和大规模计算机械部件圆度误差的设备制造和在线检测场合。

附图说明

图1为本发明提出的第一种测试结构图；

图2为本发明提出的第二种测试结构图。

具体实施方式

下面将结合本发明实施例中的附图，对本发明实施例中的技术方案进行清楚、完整地描述，显然，所描述的实施例仅仅是本发明一部分实施例，而不是全部的实施例。基于本发明中的实施例，本领域普通技术人员在没有做出创造性劳动前提下所获得的所有其他实施例，都属于本发明保护的范围。

请参阅图1-2，一种圆度误差评估的计算几何方法，步骤一：首先利用格雷厄姆(Graham)方法求得平面点集P中位于其凸壳上的有序点集P

ⅰ.将P中y坐标最小的点设为p

ⅱ.从p

①k＝4

②j＝2

③如果p

④j＝j+1，转到③，直到j＝k-1

⑤k＝k+1，转到②，直到k＝n+1(注意，因为节点编号随着节点的删除是在不断减少的，所以在算法过程中n也是在不断减少的)

经过以上删除过程后，剩下的有序点集记为P

格雷厄姆方法的特点是除了位于相对基点(p

步骤二：从点集P

步骤三：

在点集P

步骤四：Δp

方法总的时间复杂性分析如下：由于点集P有n个点，先看第一步的步骤ⅱ中转移到②的次数不会超过n，每一个顶点至多删去1次，删去顶点的个数也不可能超过n，因此第一步的步骤ⅱ是线性时间复杂度，第一步的步骤ⅰ很显然涉及到角度的排序问题，要计算n-1个夹角，并按夹角分类，计算每个夹角只需要常数时间，计算n-1个夹角耗费线性时间，分类需要时间O(n log n)，因此，第一步格雷厄姆算法部分总的时间复杂性为O(n log n)，第二步、第三步处理的集合点数相对原始集合P来说少的多，且为线性时间开销，第四步为常数时间，故所提计算方法总的时间复杂度近似为O(n log n)。

方法应用：

通过平面一定区域内随机分布的20个样本点列对方法进行了测试，给出计算所得对应点列的三元组，最小覆盖圆的圆心和半径，同时测试时图形化显示平面点列分布和最小覆盖圆的相对位置关系，并用红色标记方法所找到的三点组。

测试1：

(4.437696,11.595508)(2.699973,3.339030)(-4.944914,2.619404)(6.819971,-6.028932)

(-29.203467,-23.920713)(-25.770135,-28.492996)(-10.516984,-28.861049)(-6.713767,3.931700)

(1.665395,12.456130)(-1.586657,-28.912320)(-24.083682,8.792077)(17.738884,-28.443556)

(16.343577,-23.223060)(20.919523,-1.714835)(7.979064,-12.040468)(-19.830012,-10.943632)

(14.217658,-8.445997)(-13.527329,9.275491)(6.869411,-23.737602)(1.116062,-18.127079)

测试1结果(如图1，图中三个箭头点的位置如下)

三点组：(-6.71377,23.93170)(17.73888,-28.44356)(-25.77013,-28.49300)

圆心：(-4.04034,-6.71593)

半径：30.764012。

测试2：

(7.942442,-18.837550)(-20.472732,-17.105319)(-18.180181,

-18.872341)(0.819422,17.416608)

(-21.728874,-8.770104)(-11.954405,-7.841731)(2.498550,27.253334)(-22.992340,5.984985)

(-19.062777,9.189428)(-26.083254,2.705466)(25.546739,-25.894650)(-6.107669,-18.423719)

(-23.572802,25.815912)(-15.649586,-7.470016)(-3.948790,26.698508)(11.643117,26.031983)

(-17.264626,-12.822352)(-23.226722,22.512589)(21.161229,-18.650777)(-14.794458,9.614246)

测试2结果(如图2，图中三个箭头点的位置如下)

三点组：(-23.57280,25.81591)(11.64312,26.03198)(25.54674,-25.89465)

圆心：(0.98697,-0.03937)

半径：35.660593。

综上，该圆度误差评估的计算几何方法，典型应用在一些具有柱状中空或外形的机械部件如气缸套、轴承杆等，在生产加工过程或实际使用过程中，因存在机械加工误差或意外磨损会产生不同程度的同轴圆度误差，将待检测的这类机械部件作与轴向垂直的n个截面，并投影到同一个截平面上，再用最小二乘法拟合n个截面投影圆，从而确定出n个圆心点，这n个平面点的最小覆盖圆半径即为该机械部件的同轴圆度误差；相同长度的机械部件，n越大，对该部件的圆度误差评估就越精细越全面，相应也会要求非常大的计算量，精确的误差评估方法也有利于保证圆度误差评估的有效性。

需要说明的是，术语“包括”或者其任何其他变体意在涵盖非排他性的包含，从而使得包括一系列要素的过程、方法、物品或者设备不仅包括那些要素，而且还包括没有明确列出的其他要素，或者是还包括为这种过程、方法、物品或者设备所固有的要素。在没有更多限制的情况下，由语句“包括一个……”限定的要素，并不排除在包括所述要素的过程、方法、物品或者设备中还存在另外的相同要素。

尽管已经示出和描述了本发明的实施例，对于本领域的普通技术人员而言，可以理解在不脱离本发明的原理和精神的情况下可以对这些实施例进行多种变化、修改、替换和变型，本发明的范围由所附权利要求及其等同物限定。