基于Delaunay算法的子彈散布均勻性檢驗(yàn)方法研究

宮會(huì)元，宋艾平

(63850部隊(duì)，吉林 白城 137001)

0 引言

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

1 Delaunay三角剖分

三角剖分(triangulation)是計(jì)算幾何領(lǐng)域中最主要的內(nèi)容,是數(shù)值分析(有限元等)、信息可視化、計(jì)算機(jī)圖形學(xué)等領(lǐng)域一項(xiàng)極為重要的預(yù)處理技術(shù)。Delaunay三角剖分由俄國(guó)數(shù)學(xué)家B.Delaunay于1934年提出,它是Voronoi 圖的集合對(duì)偶圖,具有嚴(yán)格的數(shù)學(xué)定義和完備的理論基礎(chǔ)。Delaunay三角網(wǎng)因其具有優(yōu)良的幾何特性,如空外圓性質(zhì)、最小角最大的性質(zhì)等,是公認(rèn)的最優(yōu)三角網(wǎng)[1-2], 應(yīng)用領(lǐng)域極為廣泛,如:GIS、計(jì)算機(jī)仿真、地質(zhì)學(xué)、計(jì)算機(jī)圖形學(xué)及虛擬現(xiàn)實(shí)等。

1.1 Voronoi 圖

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

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

(1)

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

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

圖1 Voronoi圖Fig.1 Voronoi ketch chart

1.2 Delaunay 三角剖分

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

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

2)復(fù)形的底空間是點(diǎn)集U的凸包C(U)。

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

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

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

2 均勻性檢驗(yàn)方法

單發(fā)子母彈的子彈藥落點(diǎn)集合為P,其對(duì)應(yīng)的二維區(qū)域?yàn)樽訌椝幍穆潼c(diǎn)散布區(qū)域。對(duì)散布區(qū)域進(jìn)行Voronoi劃分后,確定集合P中所有落點(diǎn)間的鄰近關(guān)系,如圖1中P2的鄰近點(diǎn)為P1,P3,P4,P5,P6,P7。繼續(xù)對(duì)點(diǎn)集P進(jìn)行Delaunay三角剖分,剖分后的所有Delaunay邊長(zhǎng)構(gòu)成的集合X,即為所有落點(diǎn)與其鄰近點(diǎn)的距離的集合,其散布可以表征點(diǎn)集P在散布區(qū)域內(nèi)分布的均勻性。

根據(jù)Delaunay三角剖分性質(zhì),一個(gè)點(diǎn)集的Delaunay三角剖分唯一確定,可以避免原有檢驗(yàn)方法中對(duì)區(qū)域劃分的主觀性對(duì)結(jié)果帶來(lái)的影響,提高了檢驗(yàn)結(jié)果的可信性。且每個(gè)相鄰點(diǎn)的距離均計(jì)入統(tǒng)計(jì),能實(shí)現(xiàn)對(duì)全區(qū)域內(nèi)的分布均勻性進(jìn)行檢驗(yàn),杜絕了檢驗(yàn)盲區(qū)。同時(shí),該方法對(duì)樣本數(shù)量無(wú)要求、對(duì)不規(guī)則邊界區(qū)域適應(yīng)性好。

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

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

(2)

其中:

(3)

(4)

2.1 檢驗(yàn)?zāi)Ｐ?/h3>

根據(jù)以上分析,建立均勻性檢驗(yàn)步驟如圖3所示。

圖3 均勻性檢驗(yàn)步驟Fig.3 Uniformity inspection steps

2.2 均勻性檢驗(yàn)的算法實(shí)現(xiàn)

目前主流的Delaunay三角形剖分算法[5-9]有貪心算法、漸進(jìn)插入算法、Tsung-pao Fang和Les.pieg算法,其中貪心算法的時(shí)間復(fù)雜度較高、漸進(jìn)插入算法復(fù)雜度適中但對(duì)有約束情況適應(yīng)性較差,Tsung-pao Fang和Les.pieg算法復(fù)雜度最低,但算法容易出現(xiàn)退化。因?yàn)樽幽笍椡鈬鷧^(qū)域處理方法采用凸多邊形法,外圍約束符合Delaunay剖分特點(diǎn),因此選用計(jì)算復(fù)雜度較小的漸進(jìn)插入算法。則均勻性檢驗(yàn)算法步驟為:

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

3 變異系數(shù)的仿真分析和閾值確定

3.1 變異系數(shù)理論分析

若集合L內(nèi)Delaunay邊長(zhǎng)均相等,即L1=L2=…=Lk,意味著此點(diǎn)集P的元素在分布區(qū)域內(nèi)服從絕對(duì)的均勻分布,此時(shí)每3個(gè)相鄰的落點(diǎn)均構(gòu)成正三角形,此時(shí)變異系數(shù)Cv=0。

構(gòu)造一組分布較為極端的數(shù)據(jù),分布范圍為100 m×80 m,子彈落點(diǎn)數(shù)量nm=90。所有數(shù)據(jù)分成3部分,每30個(gè)落點(diǎn)集中在一起,范圍小于1 m×1 m,經(jīng)計(jì)算,此時(shí)Cv=1.745。

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

3.2 仿真分析

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

3.3 均勻性檢驗(yàn)閾值

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

原假設(shè):Cv>Cv0,備擇假設(shè):Cv≤Cv0

4 試驗(yàn)應(yīng)用

以坐標(biāo)觀測(cè)值為例,進(jìn)行試驗(yàn)驗(yàn)證,典型計(jì)算Delaunay剖分結(jié)果如圖4所示,給定顯著性水平α=0.1,計(jì)算得Cv0=0.494,可判定當(dāng)Cv=0.49時(shí)分布較均勻,當(dāng)Cv=0.80時(shí)分布不均勻。

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

由Delaunay三角形剖分圖可見(jiàn),變異系數(shù)隨散布均勻性而單調(diào)變化,其值偏小時(shí)子彈散布相對(duì)均勻,偏大時(shí)存在局部聚集、散布區(qū)域內(nèi)存在盲區(qū)的情況,根據(jù)變異系數(shù)能夠直觀判定均勻性。

5 結(jié)論

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