基于α-壳的圆度误差评定无关点删除算法

采用最小区域圆法进行圆度误差评定时,圆度误差的最终评定结果取决于位于最小区域圆上的采样点的坐标,而与其它点无关。删除圆度误差测量中的这些无关点可有效降低圆度评定算法的计算复杂度。将计算几何中α-壳的概念应用于圆度误差评定过程中;提出了一种在保证评定结果正确的前提下圆度评定中无关点的删除准则和删除算法;实验证明,本文提出的方法可有效删除圆度评定过程中的无关点。

圆度误差评定中α-壳的删点效率分析

为了解决在圆度误差评定中,当采样点数增多时,计算效率低的问题,提出了删点技术.在计算圆度误差前有效地删除那些不会对评定结果产生影响的无关点,以达到减小计算复杂度的目的.提出了α-壳删点技术,使α-内外壳的半径接近评定圆,并将该技术应用在最小外接圆(MCC)、最大内接圆(MIC)、最小区域圆(MZC)的评定过程中.针对采样得到的同一组数据进行算法的验证及比较.验证结果表明,采用本算法进行删点后得到的点数分别是前人的44.3%和87.5%.由此得出,本算法具有更高的效率.

无线传感器网络中基于α-壳的射频攻击定位

传感器网络的特殊性使之易受到射频干扰攻击等各种攻击,为了下一步安全机制的实施和部署,确定攻击者的位置,利用α-壳概念及其性质提出基于α-壳的射频攻击定位算法。当1/α与最小包容圆半径相等时,节点集合的α-壳顶点可达到共圆,进而依据α-壳顶点的数目,计算最小包容圆半径。该定位算法实现了最小包容圆半径的求解和圆心位置的确定,从而实现了对射频攻击者的定位。模拟实验表明,与已有的增量算法相比较,基于α-壳的射频攻击定位算法定位误差小,且随着网络节点密度等度量值的变化,时间消耗也不会呈指数级增长,而只呈线性的略微增长。

一种基于计算几何方法的最小包容圆求解算法

为实现点集最小包容圆(最小外接圆)的求解,将计算几何中的α-壳的概念应用到最小包容圆的计算过程,提出了一种精确有效的最小包容圆求解算法。根据α-壳定义及最小包容圆性质,证明当1/α等于最小包容圆半径时点集的α-壳顶点共圆,1/α小于最小包容圆半径时α-壳不存在,1/α大于最小包容圆半径时随着1/α减小α-壳顶点数逐渐减小的规律。将α-壳顶点数目作为搜索最小包容圆半径的依据,实现了最小包容圆半径的搜索和最小包容圆的求解。