黃亞鋒，張航峰

(南京電子技術(shù)研究所，南京 210039)

0 引 言

基于數(shù)據(jù)自動(dòng)生成要圖是要圖標(biāo)繪的發(fā)展趨勢(shì)?；跀?shù)據(jù)自動(dòng)生成要圖涉及一對(duì)基本矛盾，即有限的要圖表示空間與可以無(wú)限細(xì)致劃分的戰(zhàn)場(chǎng)空間信息的矛盾。體現(xiàn)這對(duì)矛盾的一個(gè)典型案例是點(diǎn)軍標(biāo)顯示占位沖突，即在要圖表達(dá)空間不變的前提下，當(dāng)點(diǎn)軍標(biāo)顯示過(guò)于密集時(shí)將產(chǎn)生符號(hào)間間隔小于視覺(jué)可辨間隔甚至符號(hào)間相互疊置等現(xiàn)象。而解決點(diǎn)軍標(biāo)顯示占位沖突的有效途徑之一是采用避讓標(biāo)繪方式，將沖突軍標(biāo)移位在附近圖面空白區(qū)域并用指引線指向配置位置。

由于軍標(biāo)避讓標(biāo)繪方法的重要性，在態(tài)勢(shì)智能化顯示領(lǐng)域，該問(wèn)題的研究一直是研究熱點(diǎn)問(wèn)題。在概念層次上，文獻(xiàn)［1］指出軍標(biāo)自動(dòng)避讓是態(tài)勢(shì)智能顯示的關(guān)鍵技術(shù)，是實(shí)現(xiàn)態(tài)勢(shì)圖無(wú)極縮放的技術(shù)基礎(chǔ)。在算法層次上，文獻(xiàn)［2］提出了基于模擬退火的軍標(biāo)自動(dòng)避讓算法，該算法將軍標(biāo)位置重疊度作為評(píng)價(jià)軍標(biāo)備選位置的優(yōu)劣的評(píng)價(jià)函數(shù)，通過(guò)隨機(jī)尋優(yōu)的方式尋求優(yōu)化解。文獻(xiàn)［3］提出了基于密度方法的軍標(biāo)聚類方法，該算法基本思路是尋找大于密度閾值的空間沖突軍標(biāo)群，利用新的軍標(biāo)繼承被代替存在沖突的標(biāo)號(hào)。

以上點(diǎn)狀軍標(biāo)自動(dòng)避讓算法重點(diǎn)考慮了軍標(biāo)覆蓋面積、分布密度對(duì)點(diǎn)軍標(biāo)避讓方案選擇的影響。然而點(diǎn)狀軍標(biāo)自動(dòng)避讓是個(gè)復(fù)雜空間思維過(guò)程，它需要通過(guò)盡可能小的點(diǎn)軍標(biāo)移動(dòng)達(dá)到最少的軍標(biāo)重疊區(qū)域的目標(biāo)，如何對(duì)這一個(gè)復(fù)雜的問(wèn)題建模值得進(jìn)一步研究。在總結(jié)點(diǎn)軍標(biāo)標(biāo)繪規(guī)則基礎(chǔ)上，借鑒社會(huì)活動(dòng)中的滿意度移動(dòng)模型，將點(diǎn)軍標(biāo)自動(dòng)避讓當(dāng)作空間競(jìng)爭(zhēng)問(wèn)題求解，以軍標(biāo)重疊區(qū)域大小為軍標(biāo)滿意度主要判斷依據(jù)，并綜合考慮點(diǎn)軍標(biāo)移動(dòng)距離、配置位置對(duì)避讓方案的影響，通過(guò)多次迭代導(dǎo)出最終標(biāo)繪結(jié)果。

1 點(diǎn)狀軍標(biāo)避讓標(biāo)繪原則

點(diǎn)軍標(biāo)標(biāo)繪原則是人工制圖經(jīng)驗(yàn)的總結(jié)，也是計(jì)算機(jī)環(huán)境下自動(dòng)避讓標(biāo)繪算法設(shè)計(jì)時(shí)需要遵循的規(guī)則。在總結(jié)文獻(xiàn)［2 ～4］工作基礎(chǔ)上，將點(diǎn)軍標(biāo)避讓標(biāo)繪原則總結(jié)如下。

①點(diǎn)軍標(biāo)標(biāo)繪尺寸視覺(jué)可辨;

②點(diǎn)軍標(biāo)顯示不相互重疊;

③點(diǎn)軍標(biāo)間隔大于視覺(jué)可辨最小距離;

④當(dāng)多個(gè)點(diǎn)軍標(biāo)顯示存在占位沖突時(shí)，將點(diǎn)軍標(biāo)移位至附近圖面空白區(qū)域并用指引線指向配置位置。

分析以上標(biāo)繪規(guī)則，原則①可以看作點(diǎn)軍標(biāo)避讓標(biāo)繪預(yù)處理環(huán)節(jié)，可通過(guò)以點(diǎn)坐標(biāo)定位點(diǎn)為不變點(diǎn)的仿射變換實(shí)現(xiàn)，暫不討論。原則②、③是點(diǎn)軍標(biāo)應(yīng)用避讓方法的適用條件的總結(jié)。利用形式化方式進(jìn)行描述，對(duì)于態(tài)勢(shì)圖任一點(diǎn)軍標(biāo)集合S = {JB1，JB2，……，JBn}，n 為點(diǎn)軍標(biāo)的個(gè)數(shù)，將點(diǎn)軍標(biāo)JBi、JBj(i，j≤n)間最短距離記作dis(JBi，JBj)，點(diǎn)軍標(biāo)JBi、JBj(i，j≤n)間覆蓋面積記作lap(JBi，JBj)，若d為點(diǎn)軍標(biāo)間視覺(jué)可辨最小間隔，則點(diǎn)軍標(biāo)避讓的適用條件為

原則④是具體避讓標(biāo)繪方法的總結(jié)。點(diǎn)軍標(biāo)JBi移位配置后對(duì)應(yīng)點(diǎn)軍標(biāo)記作JBi′，將點(diǎn)軍標(biāo)JBi的定位點(diǎn)記作ZJBi，點(diǎn)軍標(biāo)避讓標(biāo)繪后滿足點(diǎn)軍標(biāo)移位最小、軍標(biāo)間無(wú)沖突的要求即

2 基于滿意度的點(diǎn)軍標(biāo)顯示避讓模型

在對(duì)點(diǎn)軍標(biāo)集合進(jìn)行避讓條件判斷后(即判斷是否滿足式(1)的條件)，如何將點(diǎn)軍標(biāo)的避讓過(guò)程建模，使避讓后軍標(biāo)集合滿足式(2)的要求是其中難點(diǎn)問(wèn)題，它需要在一定模型基礎(chǔ)上定量給出各點(diǎn)軍標(biāo)可選配置位置及各可選位置點(diǎn)軍標(biāo)沖突程度，并綜合考慮以上因素導(dǎo)出最優(yōu)的點(diǎn)軍標(biāo)避讓標(biāo)繪方法。通過(guò)借鑒社會(huì)活動(dòng)中的滿意度移動(dòng)模型，在該模型基礎(chǔ)上給出軍標(biāo)個(gè)體滿意度、軍標(biāo)群滿意度定義，經(jīng)過(guò)多次點(diǎn)軍標(biāo)移動(dòng)達(dá)到點(diǎn)軍標(biāo)滿意度最大、位移最小的目標(biāo)。

滿意度模型［5］由Dewdney 觀察人群內(nèi)部活動(dòng)得到社會(huì)動(dòng)力學(xué)模型。該模型認(rèn)為不同的人與人之間的吸引力或排斥力是不相同的，在進(jìn)行例如聚會(huì)等局限于一定固定封閉空間內(nèi)部的社會(huì)活動(dòng)時(shí)，每個(gè)參加聚會(huì)的個(gè)體都在試圖尋求他在聚會(huì)人群中的合理定位，尋求他與其他個(gè)體間的最佳距離。為了達(dá)到滿意度最大的目標(biāo)，個(gè)體總在他的附近不停尋找可選位置，以接近他所喜歡的個(gè)體(具有吸引力的個(gè)體)，遠(yuǎn)離他所厭惡的個(gè)體(具有排斥力的個(gè)體)。在算法層次上，滿意度移動(dòng)模型利用規(guī)則格網(wǎng)對(duì)聚會(huì)進(jìn)行的封閉空間進(jìn)行劃分，由個(gè)體與其他個(gè)體距離矩陣確定其滿意度大小，將個(gè)體所處3 ×3 矩陣作為個(gè)體移位備選位置，依次考慮每個(gè)個(gè)體滿意度并將該個(gè)體移位至其滿意度最高的備選位置，經(jīng)過(guò)數(shù)次迭代后，每個(gè)聚會(huì)的個(gè)體都會(huì)需要找一個(gè)達(dá)到他滿意度最大的位置，使整個(gè)聚會(huì)空間達(dá)到穩(wěn)定的狀態(tài)。

滿意度移動(dòng)模型是進(jìn)行多個(gè)目標(biāo)移位操作的有力工具，該模型已應(yīng)用至社會(huì)活動(dòng)建模、地圖綜合等多個(gè)領(lǐng)域［5，6］。滿意度移動(dòng)模型與其他移動(dòng)方法相比，具有計(jì)算效率高、魯棒性強(qiáng)等優(yōu)點(diǎn)。這里，應(yīng)用滿意度模型解決點(diǎn)軍標(biāo)避讓標(biāo)繪問(wèn)題，將避讓標(biāo)繪可以看作是在一定封閉的地圖空間內(nèi)，點(diǎn)軍標(biāo)相互空間競(jìng)爭(zhēng)、尋求最佳位置的過(guò)程。

下面從點(diǎn)軍標(biāo)顯示滿意度、可選移動(dòng)位置、避讓流程和參數(shù)設(shè)置等方面介紹基于滿意度移動(dòng)模型的點(diǎn)軍標(biāo)自動(dòng)避讓算法。

(1)點(diǎn)軍標(biāo)顯示滿意度

定義點(diǎn)軍標(biāo)個(gè)體的滿意度是基于滿意度的點(diǎn)軍標(biāo)避讓算法的基礎(chǔ)。在避讓標(biāo)繪問(wèn)題中，點(diǎn)軍標(biāo)的滿意度越高就意味著點(diǎn)軍標(biāo)與其他軍標(biāo)的沖突越小。同時(shí)結(jié)合式(1)給出的點(diǎn)軍標(biāo)沖突定義，可推論出點(diǎn)軍標(biāo)的滿意度與點(diǎn)軍標(biāo)間最短距離、點(diǎn)軍標(biāo)間覆蓋面積有關(guān)。然而需要注意的是，由于點(diǎn)軍標(biāo)內(nèi)部幾何圖形通常較為復(fù)雜，計(jì)算大量的復(fù)雜幾何圖形間覆蓋面積與最短距離的計(jì)算代價(jià)很高，因此從計(jì)算效率角度看式(1)的直接定義無(wú)法直接定義點(diǎn)軍標(biāo)的滿意度。

為解決上述問(wèn)題，考慮到點(diǎn)軍標(biāo)外接矩形是對(duì)點(diǎn)軍標(biāo)外形的一種概括，將點(diǎn)軍標(biāo)滿意度定義為點(diǎn)軍標(biāo)外接矩形覆蓋面積和的反比。對(duì)于任一軍標(biāo)JBi，其外接矩形為MBR(JBi)，則JBi的滿意度Happiness(JBi)，

式中，i，j≤n;ε 為常數(shù)。

(2)點(diǎn)軍標(biāo)配置位置

在避讓標(biāo)繪問(wèn)題中，首先點(diǎn)軍標(biāo)的備選配置受標(biāo)繪圖幅大小的限制，點(diǎn)軍標(biāo)避讓標(biāo)繪位置不能位于地圖圖幅之外;再次點(diǎn)軍標(biāo)的備選配置要顧及讀圖者閱讀習(xí)慣的影響;其次點(diǎn)軍標(biāo)備選配置數(shù)目的多少對(duì)避讓算法運(yùn)算效率有直接影響，算法需要依次計(jì)算圖幅各軍標(biāo)各備選位置的滿意度，故算法效率與備選位置數(shù)目呈反比關(guān)系。

綜合考慮上述因素，將點(diǎn)軍標(biāo)原有配置位置及離點(diǎn)軍標(biāo)原有位置距離r 處的四方向鄰域(右上、左上、左下、右下)位置作為點(diǎn)軍標(biāo)移位的備選位置如圖1所示，圖1(a)所示的軍標(biāo)1 含有1 －5 的備選位置。地圖圖廓線附近的點(diǎn)軍標(biāo)移位位置為圖幅范圍內(nèi)的鄰域位置，圖1(b)所示的右上圖廓附近的軍標(biāo)1 備選位置為1、2。另外，在各點(diǎn)軍標(biāo)滿意度相同的情況下，各備選位置的優(yōu)先級(jí)是不盡相同的，從避讓標(biāo)繪習(xí)慣看存在這從中間、右上、左上、左下、右下優(yōu)先級(jí)逐步遞減的規(guī)律，圖1 中用數(shù)字標(biāo)繪方式給出各位置的配置優(yōu)先級(jí)，圖中數(shù)字越小該位置優(yōu)先級(jí)越高。

圖1 點(diǎn)軍標(biāo)可選配置位置

(3)避讓標(biāo)繪流程

基于滿意度模型的點(diǎn)軍標(biāo)避讓標(biāo)繪問(wèn)題中，系統(tǒng)初始輸入條件為存在空間沖突的點(diǎn)軍標(biāo)集合，系統(tǒng)為集合內(nèi)部各點(diǎn)軍標(biāo)元素依次在可選配置位置集合中尋找最優(yōu)配置位置，通過(guò)多次迭代后當(dāng)每個(gè)軍標(biāo)的滿意度都不能再增加時(shí)，系統(tǒng)達(dá)到穩(wěn)定狀態(tài)，系統(tǒng)的輸出為移位后具有穩(wěn)定狀態(tài)的點(diǎn)軍標(biāo)集合。

基于滿意度模型的點(diǎn)軍標(biāo)避讓標(biāo)繪的詳細(xì)流程如下。

①系統(tǒng)輸入初始軍標(biāo)集合S0= {JB1、JB2、……、JBn}，計(jì)算集合S0各軍標(biāo)滿意度用Happiness(S0)表示，Happiness(S0)={Happiness(JB1)、Happiness(JB2)、……、Happiness(JBn)}。

②對(duì)集合內(nèi)軍標(biāo)進(jìn)行滿意度移位，由下列過(guò)程組成:

a)為集合內(nèi)軍標(biāo)設(shè)置移位標(biāo)志位flag(JBi)，flag(JBi)=0;

b)選取flag(JBi)=0 而且滿意度最小的軍標(biāo)為待移位軍標(biāo)JBM;

c)計(jì)算JBM的備選配置位置，將其移動(dòng)至滿意度最高且配置優(yōu)先級(jí)最高的備選位置;

d)flag(JBM)=1，更新軍標(biāo)集狀態(tài)，判斷集合狀態(tài)若滿足條件?flag(JBi)=1，則轉(zhuǎn)至步驟③，否則轉(zhuǎn)至步驟②a)。

③軍標(biāo)集狀態(tài)由Sn變更為Sn+1，計(jì)算Happiness(Sn+1)，若條件Happiness(Sn+1)= Happiness(Sn)存在則轉(zhuǎn)至步驟④，否則轉(zhuǎn)至步驟②;

④Sn+1為避讓后的軍標(biāo)集合，輸出軍標(biāo)集合Sn+1。

某次迭代過(guò)程中軍標(biāo)JB1的避讓過(guò)程如圖2 所示，圖2(a)為初始點(diǎn)軍標(biāo)集合，點(diǎn)軍標(biāo)JB1與JB2、JB3間存在占位沖突，圖2(b)為利用最小外接矩形計(jì)算JB1滿意度的過(guò)程，其中矩形重疊部分Ⅰ、Ⅱ、Ⅲ為沖突部分，分別計(jì)算軍標(biāo)JB1的五個(gè)備選配置的滿意度，通過(guò)計(jì)算可知左上方位的滿意度最大，圖2(c)為將左上位置作為移位位置后的避讓標(biāo)繪結(jié)果。

圖2 軍標(biāo)JB1 的自動(dòng)避讓過(guò)程

(4)參數(shù)設(shè)置

3 實(shí)驗(yàn)與討論

基于上述方法采用模擬數(shù)據(jù)進(jìn)行實(shí)驗(yàn)如圖5 所示。圖5(a)為實(shí)驗(yàn)數(shù)據(jù)，包含點(diǎn)軍標(biāo)42 個(gè)，其中后方指揮所、專項(xiàng)指揮所各21 個(gè);圖5(b)為采用基于滿意度移位模型的軍標(biāo)結(jié)果，模型移位參數(shù)r 設(shè)置為軍標(biāo)外接矩形短半徑的1/4，所需迭代次數(shù)為4。采用目視判別的方法對(duì)實(shí)驗(yàn)結(jié)果進(jìn)行比照分析，發(fā)現(xiàn)該避讓方法的結(jié)果圖5(b)能夠較好地解決圖5(a)中A、B、C 等處點(diǎn)軍標(biāo)占位矛盾。然而分析圖5(b)，發(fā)現(xiàn)算法在有效解決點(diǎn)軍標(biāo)的占位矛盾的同時(shí)也使點(diǎn)軍標(biāo)分布密度趨于一致，也就是無(wú)法有效保持各區(qū)域點(diǎn)軍標(biāo)分布密度的對(duì)比情況(如圖5(a)A、D 處在避讓前A 處明顯大于D 處，而在避讓后的A、D 處點(diǎn)軍標(biāo)分布密度相差不大)。這是本算法存在的不足之處。

圖5 基于滿意度移位的軍標(biāo)避讓算法

為解決上述不足，基于滿意度移動(dòng)模型的避讓算法的改進(jìn)可從如下方面進(jìn)行:①改進(jìn)軍標(biāo)滿意度計(jì)算模型，綜合考慮點(diǎn)軍標(biāo)分布密度對(duì)比對(duì)軍標(biāo)避讓操作的影響;②當(dāng)軍標(biāo)分布過(guò)于密集時(shí)，結(jié)合選擇/刪除操作、避讓移位、同類軍標(biāo)聚合等多種操作解決點(diǎn)軍標(biāo)沖突。多種操作的集成涉及到何種條件下對(duì)何處目標(biāo)選擇何種操作，并實(shí)施到何種操作程度問(wèn)題，這屬于高層次的空間決策問(wèn)題。后繼研究將著手解決該問(wèn)題。

［1］曾軍，王飛. 計(jì)算機(jī)輔助標(biāo)圖發(fā)展研究［J］.測(cè)繪學(xué)院學(xué)報(bào)，2000，17(3):224-231.

［2］陳文凱，曹澤文.基于模擬退火算法的部署圖點(diǎn)軍標(biāo)自動(dòng)避讓［J］.兵工自動(dòng)化，2009，28(3):35-37.

［3］趙恩來(lái)，郝文寧，趙水寧，韓憲勇.改進(jìn)的基于密度方法的態(tài)勢(shì)聚類顯示算法［J］.計(jì)算機(jī)工程，2010，36(18):35-37.

［4］夏仕保.實(shí)用要圖標(biāo)繪［M］.北京:軍事科學(xué)出版社，2004.

［5］DEWDNEY A K. Computer Recreations:Diverse Personalities Search for Social Equilibrium at a Computer Party［J］. Scientific American，1987(9):104-107.

［6］ MACKANESS W A，PURVES R S. Automated Displacement for Large Numbers of Discrete Map Objects［J］.Algorithmica，2001(30):302-311.