基于Delaunay算法的子彈散布均勻性檢驗方法研究

宮會元，宋艾平

(63850部隊，吉林 白城 137001)

0 引言

子彈藥散布均勻性是子母彈重要的性能,是子母彈鑒定、驗收等試驗中必須考核驗證的指標?，F有子彈藥地面散布均勻性評價方法主要有兩種:一種是對散布區域分區并對各分區內落點數量分布應用統計方法進行檢驗;另一種是將落點按坐標方向分解,并按一維坐標分別檢驗均勻性。這些算法存在以下缺點:1)分組區間的劃分方法主觀性強,其合理性對檢驗結果有很大影響,降低了評價結果的可信度;2)只適用于樣本數量足夠大的情況;3)對不規則邊界區域適應性差;4)忽略了分組區間內部均勻性等,制約了實際的應用。針對上述問題,文中引入Delaunay三角形剖分法,對子彈藥落點散布均勻性進行研究,以解決現有方法的諸多缺點。

1 Delaunay三角剖分

三角剖分(triangulation)是計算幾何領域中最主要的內容,是數值分析(有限元等)、信息可視化、計算機圖形學等領域一項極為重要的預處理技術。Delaunay三角剖分由俄國數學家B.Delaunay于1934年提出,它是Voronoi 圖的集合對偶圖,具有嚴格的數學定義和完備的理論基礎。Delaunay三角網因其具有優良的幾何特性,如空外圓性質、最小角最大的性質等,是公認的最優三角網[1-2], 應用領域極為廣泛,如:GIS、計算機仿真、地質學、計算機圖形學及虛擬現實等。

1.1 Voronoi 圖

定義1[1]:令d(x,Pi)表示x到Pi的歐式距離,則點Pi的鄰域Vi定義為:

Vi={x∈Rn|d(x,Pi)

(1)

式中:Rn為n維歐氏空間;i=1,2,…,n;j=1,2,…,n。

對于二維空間,Voronoi圖如圖1所示,圖中陰影區域內的任意點到P2的距離近于到其他點Pi(i≠2)的距離,V1,V2,V3,V4,V5,V6確定的六邊形稱為P2的鄰域,其邊界對應于點P2的Voronoi多邊形,它是由Pi與相鄰點連線的垂直平分線圍成的。二維Voronoi圖是平面點集所有點的鄰域多邊形的并集。Voronoi多邊形的數學期望為6[3]

圖1 Voronoi圖Fig.1 Voronoi ketch chart

1.2 Delaunay 三角剖分

定義2[1]:U為Ed空間的有限點集,點集U的Delaunay三角化定義為滿足以下條件的單純形單元復形D(U)[4]:

1)復形D(U)的0-單純形組成的集合(即D(U)的所有頂點的集合)是U的子集。

2)復形的底空間是點集U的凸包C(U)。

3)任意一個d-單純形ΔT∈D(U),|T|=k+1,滿足:任意q∈U-T,q在ΔT的外接球外。

Delaunay三角剖分與Voronoi圖為對偶圖,Voronoi邊(限有限長線段)的中垂線就是Delaunay邊。如圖2所示,虛線為Voronoi圖,實線為Delaunay三角部分。

圖2 Voronoi 圖和Delaunay 三角剖分Fig.2 Voronoi ketch chart and Delaunay triangulation

2 均勻性檢驗方法

單發子母彈的子彈藥落點集合為P,其對應的二維區域為子彈藥的落點散布區域。對散布區域進行Voronoi劃分后,確定集合P中所有落點間的鄰近關系,如圖1中P2的鄰近點為P1,P3,P4,P5,P6,P7。繼續對點集P進行Delaunay三角剖分,剖分后的所有Delaunay邊長構成的集合X,即為所有落點與其鄰近點的距離的集合,其散布可以表征點集P在散布區域內分布的均勻性。

根據Delaunay三角剖分性質,一個點集的Delaunay三角剖分唯一確定,可以避免原有檢驗方法中對區域劃分的主觀性對結果帶來的影響,提高了檢驗結果的可信性。且每個相鄰點的距離均計入統計,能實現對全區域內的分布均勻性進行檢驗,杜絕了檢驗盲區。同時,該方法對樣本數量無要求、對不規則邊界區域適應性好。

以變異系數作為衡量各觀測值離散程度的統計量,具有無量綱特性,不受計量單位和均值大小的影響,因此對于衡量不同彈藥種類的相鄰子彈間距離散布情況具有普適性。

若相鄰子彈間距為x={x1,x2,…,xn},變異系數[2]Cv的表達式為:

(2)

其中:

(3)

(4)

2.1 檢驗模型

根據以上分析,建立均勻性檢驗步驟如圖3所示。

圖3 均勻性檢驗步驟Fig.3 Uniformity inspection steps

2.2 均勻性檢驗的算法實現

目前主流的Delaunay三角形剖分算法[5-9]有貪心算法、漸進插入算法、Tsung-pao Fang和Les.pieg算法,其中貪心算法的時間復雜度較高、漸進插入算法復雜度適中但對有約束情況適應性較差,Tsung-pao Fang和Les.pieg算法復雜度最低,但算法容易出現退化。因為子母彈外圍區域處理方法采用凸多邊形法,外圍約束符合Delaunay剖分特點,因此選用計算復雜度較小的漸進插入算法。則均勻性檢驗算法步驟為:

1)輸入m枚子彈坐標點集P,P={Pk|k=1,…,m};2)定義一個包含點集P的超三角形,把它作為初始Delaunay三角;3)將點集內一個未處理點Pk插入已有的Delaunay三角網內;4)在三角網中找出包含Pk的三角形,把Pk與這個三角形的3個頂點相連,生成3個新的三角形;5)應用Lawson提出的局部優化算法,向外更新該步之前生成的所有三角形;6)重復步驟3)～5),直到所有的點都被插入;7)刪掉包含超三角頂點的所有三角形,完成三角形剖分;8)逐條計算Delaunay邊長;9)計算變異系數及其散布;10)給定置信水平,判定子彈散布是否均勻。

3 變異系數的仿真分析和閾值確定

3.1 變異系數理論分析

若集合L內Delaunay邊長均相等,即L1=L2=…=Lk,意味著此點集P的元素在分布區域內服從絕對的均勻分布,此時每3個相鄰的落點均構成正三角形,此時變異系數Cv=0。

構造一組分布較為極端的數據,分布范圍為100 m×80 m,子彈落點數量nm=90。所有數據分成3部分,每30個落點集中在一起,范圍小于1 m×1 m,經計算,此時Cv=1.745。

由此可知,實際Cv值的變化范圍為0～1.745。

3.2 仿真分析

設子彈落點散布半徑為r,構造1 000組符合二維均勻分布的數據,分別取r,nm的組合為[40,28],[200,28],[200,200],[40,500], 基本覆蓋常見子母彈數據范圍,采用2.2方法對數據進行檢驗,得到各種條件下下對應的變異系數Cv值,結果如圖5所示。經大量仿真結果顯示,其均值對r,n不敏感,標準差隨子彈數量增加有減小趨勢。一般均勻分布條件下變異系數Cv均值約為0.567。

3.3 均勻性檢驗閾值

變異系數服從正態分布,即Cv～N(0.567,S2),且變異系數越小均勻性越好,若Cv≤Cv0,其中Cv0為閾值,則分布均勻。為進行均勻性檢驗作假設:

原假設:Cv>Cv0,備擇假設:Cv≤Cv0

4 試驗應用

以坐標觀測值為例,進行試驗驗證,典型計算Delaunay剖分結果如圖4所示,給定顯著性水平α=0.1,計算得Cv0=0.494,可判定當Cv=0.49時分布較均勻,當Cv=0.80時分布不均勻。

圖4 子母彈典型Delaunay三角形剖分圖Fig.4 Typical Delaunay triangulation of a certain type of submunition

由Delaunay三角形剖分圖可見,變異系數隨散布均勻性而單調變化,其值偏小時子彈散布相對均勻,偏大時存在局部聚集、散布區域內存在盲區的情況,根據變異系數能夠直觀判定均勻性。

5 結論

基于Delaunay算法的子彈均勻性檢驗算法能夠滿足均勻性檢驗的唯一性、全局性、普適性要求,對子彈數量不敏感,避免了原有方法的不足,具有良好的可操作性。