基于满意度移动模型的点军标显示自动避让方法

黄亚锋，张航峰

(南京电子技术研究所，南京 210039)

0 引 言

基于数据自动生成要图是要图标绘的发展趋势。基于数据自动生成要图涉及一对基本矛盾，即有限的要图表示空间与可以无限细致划分的战场空间信息的矛盾。体现这对矛盾的一个典型案例是点军标显示占位冲突，即在要图表达空间不变的前提下，当点军标显示过于密集时将产生符号间间隔小于视觉可辨间隔甚至符号间相互叠置等现象。而解决点军标显示占位冲突的有效途径之一是采用避让标绘方式，将冲突军标移位在附近图面空白区域并用指引线指向配置位置。

由于军标避让标绘方法的重要性，在态势智能化显示领域，该问题的研究一直是研究热点问题。在概念层次上，文献［1］指出军标自动避让是态势智能显示的关键技术，是实现态势图无极缩放的技术基础。在算法层次上，文献［2］提出了基于模拟退火的军标自动避让算法，该算法将军标位置重叠度作为评价军标备选位置的优劣的评价函数，通过随机寻优的方式寻求优化解。文献［3］提出了基于密度方法的军标聚类方法，该算法基本思路是寻找大于密度阈值的空间冲突军标群，利用新的军标继承被代替存在冲突的标号。

以上点状军标自动避让算法重点考虑了军标覆盖面积、分布密度对点军标避让方案选择的影响。然而点状军标自动避让是个复杂空间思维过程，它需要通过尽可能小的点军标移动达到最少的军标重叠区域的目标，如何对这一个复杂的问题建模值得进一步研究。在总结点军标标绘规则基础上，借鉴社会活动中的满意度移动模型，将点军标自动避让当作空间竞争问题求解，以军标重叠区域大小为军标满意度主要判断依据，并综合考虑点军标移动距离、配置位置对避让方案的影响，通过多次迭代导出最终标绘结果。

1 点状军标避让标绘原则

点军标标绘原则是人工制图经验的总结，也是计算机环境下自动避让标绘算法设计时需要遵循的规则。在总结文献［2 ～4］工作基础上，将点军标避让标绘原则总结如下。

①点军标标绘尺寸视觉可辨;

②点军标显示不相互重叠;

③点军标间隔大于视觉可辨最小距离;

④当多个点军标显示存在占位冲突时，将点军标移位至附近图面空白区域并用指引线指向配置位置。

分析以上标绘规则，原则①可以看作点军标避让标绘预处理环节，可通过以点坐标定位点为不变点的仿射变换实现，暂不讨论。原则②、③是点军标应用避让方法的适用条件的总结。利用形式化方式进行描述，对于态势图任一点军标集合S = {JB1，JB2，……，JBn}，n 为点军标的个数，将点军标JBi、JBj(i，j≤n)间最短距离记作dis(JBi，JBj)，点军标JBi、JBj(i，j≤n)间覆盖面积记作lap(JBi，JBj)，若d为点军标间视觉可辨最小间隔，则点军标避让的适用条件为

原则④是具体避让标绘方法的总结。点军标JBi移位配置后对应点军标记作JBi′，将点军标JBi的定位点记作ZJBi，点军标避让标绘后满足点军标移位最小、军标间无冲突的要求即

2 基于满意度的点军标显示避让模型

在对点军标集合进行避让条件判断后(即判断是否满足式(1)的条件)，如何将点军标的避让过程建模，使避让后军标集合满足式(2)的要求是其中难点问题，它需要在一定模型基础上定量给出各点军标可选配置位置及各可选位置点军标冲突程度，并综合考虑以上因素导出最优的点军标避让标绘方法。通过借鉴社会活动中的满意度移动模型，在该模型基础上给出军标个体满意度、军标群满意度定义，经过多次点军标移动达到点军标满意度最大、位移最小的目标。

满意度模型［5］由Dewdney 观察人群内部活动得到社会动力学模型。该模型认为不同的人与人之间的吸引力或排斥力是不相同的，在进行例如聚会等局限于一定固定封闭空间内部的社会活动时，每个参加聚会的个体都在试图寻求他在聚会人群中的合理定位，寻求他与其他个体间的最佳距离。为了达到满意度最大的目标，个体总在他的附近不停寻找可选位置，以接近他所喜欢的个体(具有吸引力的个体)，远离他所厌恶的个体(具有排斥力的个体)。在算法层次上，满意度移动模型利用规则格网对聚会进行的封闭空间进行划分，由个体与其他个体距离矩阵确定其满意度大小，将个体所处3 ×3 矩阵作为个体移位备选位置，依次考虑每个个体满意度并将该个体移位至其满意度最高的备选位置，经过数次迭代后，每个聚会的个体都会需要找一个达到他满意度最大的位置，使整个聚会空间达到稳定的状态。

满意度移动模型是进行多个目标移位操作的有力工具，该模型已应用至社会活动建模、地图综合等多个领域［5，6］。满意度移动模型与其他移动方法相比，具有计算效率高、鲁棒性强等优点。这里，应用满意度模型解决点军标避让标绘问题，将避让标绘可以看作是在一定封闭的地图空间内，点军标相互空间竞争、寻求最佳位置的过程。

下面从点军标显示满意度、可选移动位置、避让流程和参数设置等方面介绍基于满意度移动模型的点军标自动避让算法。

(1)点军标显示满意度

定义点军标个体的满意度是基于满意度的点军标避让算法的基础。在避让标绘问题中，点军标的满意度越高就意味着点军标与其他军标的冲突越小。同时结合式(1)给出的点军标冲突定义，可推论出点军标的满意度与点军标间最短距离、点军标间覆盖面积有关。然而需要注意的是，由于点军标内部几何图形通常较为复杂，计算大量的复杂几何图形间覆盖面积与最短距离的计算代价很高，因此从计算效率角度看式(1)的直接定义无法直接定义点军标的满意度。

为解决上述问题，考虑到点军标外接矩形是对点军标外形的一种概括，将点军标满意度定义为点军标外接矩形覆盖面积和的反比。对于任一军标JBi，其外接矩形为MBR(JBi)，则JBi的满意度Happiness(JBi)，

式中，i，j≤n;ε 为常数。

(2)点军标配置位置

在避让标绘问题中，首先点军标的备选配置受标绘图幅大小的限制，点军标避让标绘位置不能位于地图图幅之外;再次点军标的备选配置要顾及读图者阅读习惯的影响;其次点军标备选配置数目的多少对避让算法运算效率有直接影响，算法需要依次计算图幅各军标各备选位置的满意度，故算法效率与备选位置数目呈反比关系。

综合考虑上述因素，将点军标原有配置位置及离点军标原有位置距离r 处的四方向邻域(右上、左上、左下、右下)位置作为点军标移位的备选位置如图1所示，图1(a)所示的军标1 含有1 －5 的备选位置。地图图廓线附近的点军标移位位置为图幅范围内的邻域位置，图1(b)所示的右上图廓附近的军标1 备选位置为1、2。另外，在各点军标满意度相同的情况下，各备选位置的优先级是不尽相同的，从避让标绘习惯看存在这从中间、右上、左上、左下、右下优先级逐步递减的规律，图1 中用数字标绘方式给出各位置的配置优先级，图中数字越小该位置优先级越高。

图1 点军标可选配置位置

(3)避让标绘流程

基于满意度模型的点军标避让标绘问题中，系统初始输入条件为存在空间冲突的点军标集合，系统为集合内部各点军标元素依次在可选配置位置集合中寻找最优配置位置，通过多次迭代后当每个军标的满意度都不能再增加时，系统达到稳定状态，系统的输出为移位后具有稳定状态的点军标集合。

基于满意度模型的点军标避让标绘的详细流程如下。

①系统输入初始军标集合S0= {JB1、JB2、……、JBn}，计算集合S0各军标满意度用Happiness(S0)表示，Happiness(S0)={Happiness(JB1)、Happiness(JB2)、……、Happiness(JBn)}。

②对集合内军标进行满意度移位，由下列过程组成:

a)为集合内军标设置移位标志位flag(JBi)，flag(JBi)=0;

b)选取flag(JBi)=0 而且满意度最小的军标为待移位军标JBM;

c)计算JBM的备选配置位置，将其移动至满意度最高且配置优先级最高的备选位置;

d)flag(JBM)=1，更新军标集状态，判断集合状态若满足条件∀flag(JBi)=1，则转至步骤③，否则转至步骤②a)。

③军标集状态由Sn变更为Sn+1，计算Happiness(Sn+1)，若条件Happiness(Sn+1)= Happiness(Sn)存在则转至步骤④，否则转至步骤②;

④Sn+1为避让后的军标集合，输出军标集合Sn+1。

某次迭代过程中军标JB1的避让过程如图2 所示，图2(a)为初始点军标集合，点军标JB1与JB2、JB3间存在占位冲突，图2(b)为利用最小外接矩形计算JB1满意度的过程，其中矩形重叠部分Ⅰ、Ⅱ、Ⅲ为冲突部分，分别计算军标JB1的五个备选配置的满意度，通过计算可知左上方位的满意度最大，图2(c)为将左上位置作为移位位置后的避让标绘结果。

图2 军标JB1 的自动避让过程

(4)参数设置

3 实验与讨论

基于上述方法采用模拟数据进行实验如图5 所示。图5(a)为实验数据，包含点军标42 个，其中后方指挥所、专项指挥所各21 个;图5(b)为采用基于满意度移位模型的军标结果，模型移位参数r 设置为军标外接矩形短半径的1/4，所需迭代次数为4。采用目视判别的方法对实验结果进行比照分析，发现该避让方法的结果图5(b)能够较好地解决图5(a)中A、B、C 等处点军标占位矛盾。然而分析图5(b)，发现算法在有效解决点军标的占位矛盾的同时也使点军标分布密度趋于一致，也就是无法有效保持各区域点军标分布密度的对比情况(如图5(a)A、D 处在避让前A 处明显大于D 处，而在避让后的A、D 处点军标分布密度相差不大)。这是本算法存在的不足之处。

图5 基于满意度移位的军标避让算法

为解决上述不足，基于满意度移动模型的避让算法的改进可从如下方面进行:①改进军标满意度计算模型，综合考虑点军标分布密度对比对军标避让操作的影响;②当军标分布过于密集时，结合选择/删除操作、避让移位、同类军标聚合等多种操作解决点军标冲突。多种操作的集成涉及到何种条件下对何处目标选择何种操作，并实施到何种操作程度问题，这属于高层次的空间决策问题。后继研究将着手解决该问题。

［1］曾军，王飞. 计算机辅助标图发展研究［J］.测绘学院学报，2000，17(3):224-231.

［2］陈文凯，曹泽文.基于模拟退火算法的部署图点军标自动避让［J］.兵工自动化，2009，28(3):35-37.

［3］赵恩来，郝文宁，赵水宁，韩宪勇.改进的基于密度方法的态势聚类显示算法［J］.计算机工程，2010，36(18):35-37.

［4］夏仕保.实用要图标绘［M］.北京:军事科学出版社，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.