禄小敏，闫浩文，王中辉，甘治国

（1．兰州交通大学 测绘与地理信息学院，甘肃 兰州730070；2．甘肃省地理国情监测工程实验室，甘肃 兰州 730070；3．中国水利水电科学研究院，北京100044）

群组目标是由多个单目标因局部空间关联度高而形成的集合。在地理空间中，空间目标在许多情况下都是以群组的形式出现，如高程点、道路、河流、居民地、岛屿等。按照构成要素的不同几何属性，群组目标一般分为点群、线群与面群3类［1］。

群组目标的分布边界能够很好地描述群组目标的空间形态以及分布范围，在空间方向关系判断［2］、空间相似度计算［3］、地图自动综合［4］等领域有着重要的应用。目前，有关群组目标的分布边界计算主要是针对空间点群目标，提出的代表性方法有“剥皮”法［5］、外围点连接 法［6］、Voronoi图法［7］等。相比而言，对于空间线、面群组目标的分布边界计算问题却鲜有学者涉猎。

鉴于此，本文在约束Delaunay三角网的基础上，通过设定动态阈值，利用“剥皮”法提出一种针对空间线、面群组目标的分布边界求解算法。

1 算法描述

1．1 算法的主要过程

群组目标的分布边界是指能够准确表达群组目标空间形态和分布范围的多边形，如图1中的多边形abcdef a所示。

图1 面群的边界多边形

根据Gestalt心理学的邻近性原则，只有两点相距小于视觉邻近距离时，其连接才能充当群组目标的分布边界［5］。众所周知，Delaunay三角网是计算和分析空间邻近性问题的优秀工具［8］。因此，本文拟通过构建线、面群的约束Delaunay三角网，利用“剥皮”法删除两点距离大于视觉邻近距离的三角形边，得到线、面群的分布边界多边形。算法的主要过程如图2所示。

图2 算法的主要过程

1．2 数据结构

本文算法中用到的数据结构主要有边数据结构和三角形数据结构。其中，边数据结构的核心参数是left Triangle，right Triangle，分别表示边的左、右邻接三角形索引；三角形数据结构的核心参数是triangle A，triangle B，triangle C，分别表示三角形三个顶点A，B，C的对边的邻接三角形索引。

1．3 算法的详细描述

本文以线群目标为例介绍算法的详细步骤。

1．3．1 线群的约束Delaunay三角剖分

下面结合图3对线群的约束Delaunay三角剖分过程［9］进行描述。

Step 1 利用Watson算法 构建线群特征点集的初始Delaunay三角网（见图3（a）），并将三角网中所有的三角形存入三角形数组；

Step 2：线群特征边入网，具体方法如下：

1）在三角形数组中查找与线群的特征边相交的所有三角形，并建立由这些三角形中和特征边不相交的边与该特征边构成的边数组L，具体分两种情况：若此特征边恰好是三角形的一条边，这种情况不做任何处理；否则，按照下述方法构建边数组：

①见图3（a），从三角形数组中查找与线群特征边LiLj相交且其顶点为Li的首三角形T1；

②将当前三角形（如T1）中不与特征边LiLj相交的边ELi与LiA加入边数组，同时查找与T1相邻接且与LiLj相交的三角形T2，并从三角形数组中删除T1；将T2作为当前三角形，重复该过程，直到当前三角形为末三角形T5为止，并将T5中与特征边不相交的边CLj与LjD加入到边数组，同时从三角形数组中删除T5；

③将LiLj加入到边数组。

2）利用边数组构建特征边LiLj的影响多边形PL和PR，如图3（b）所示，并将它们的顶点按逆时针方向存储。

3）对影响多边形进行Delaunay三角剖分（以PR 为例）［11］，具体步骤如下：

①计算多边形每个顶点的凹凸性；

②将多边形顶点数组中的每个凸顶点（如图3（c）中的顶点A）与其前后顶点Li，B组成△LiAB，若此三角形不包含多边形的其它顶点，则将其保存到三角形数组中，并从多边形顶点数组中删除此凸顶点，重新计算受影响的顶点的凹凸性，重复该过程，直到多边形顶点数组为空时结束；

③按最大－最小内角准则，对三角网进行LOP（Local Opti mization Procedure）优化，结果如图3（c）所示。

1．3．2 利用动态阈值“剥皮”法计算线群的分布边界

“剥皮”即删除那些位于Delaunay三角网外围的非线群特征边的边长大于一定阈值的三角形。具体步骤如下：

Step1：设阈值d＝k×Avelength，其中，k为“剥皮”等级（文中取k＝2），Avelength为Delaunay三角网中各三角形边长的平均值，d的值在每次“剥皮”后动态更新；

图3 线群的约束Delaunay三角剖分

Step2：将线群的外围非特征边（即只有一个邻接三角形的边且其不是线群的特征边）依次与阈值d比较，若边长大于d，首先判断删除该边后所在三角形的其他两边能否与其他边构成三角形，若能，将该边删除后转Step3；否则保留该边，重复此步骤；

Step3：将被删除边所在三角形的其余两边设置为外围边，重新计算Avelengt h并更新d值，逐层向内侵蚀直到所有的外围非特征边边长均小于当前阈值d。

图3（c）中的线群“剥皮”结果如图4所示。

图4 线群的"剥皮"结果

1．3．3 构建线群的分布边界多边形

由于在“剥皮”之后，线群分布边界的顶点是无序存放的，因此，需要将它们进行调整（本文采用逆时针方向存储），从而构建出最终的线群分布边界多边形。下面以图5为例说明构建分布边界多边形的具体方法。

Step1：在三角形数组中查找任意一条外围边（如图5中的边ab），将其端点加入到多边形顶点数组。

Step2：将外围边ab的终点b作为起点查找多边形的下一个顶点，具体过程为：

①在边数组中查找以点b为起点的边（如bj，bc），依次判断它们是否为外围边，若是（如bc），则将其另一端点（如点c）加入到多边形顶点数组；

②以点c为起点重复该过程，直至回到初始端点a。

按照上述方法，图5中的多边形顶点数组P＝｛a，b，c，d，e，f，g，h，i，a｝。

图5 边界多边形的构建

2 实验与讨论

本文借助Visual C＋＋6．0平台，编程实现上述算法，并以shape格式的线群（河系）、面群（居民地群）为例进行实验，结果如图6～图9所示。其中，图6、图7是河系的分布边界多边形计算结果，图8、图9是居民地群的分布边界多边形计算结果。

群组目标的分布边界多边形需符合人们的空间认知习惯，为此，本文采用人群调查的方式对上述实验结果进行验证。其中，被调查者是50名具有不同专业背景的本科生，实验要求被调查者对图6～图9中的线、面群分布边界多边形回答“好”、“较好”、“一般”和“不好”4个答案之一。表1是对应的调查统计结果。

表1 人群调查统计表

图6 实验一

图7 实验二

图8 实验三

由表1可知，实验结果的最高认同率为88%，最低认同率为78%，平均认同率为83%，且认为边界多边形描述群组目标空间形态和分布范围不好的人数均为0。这表明利用本文算法所求得的线、面群分布边界多边形符合人们的空间认知习惯，较好地表达了空间线群、面群目标的空间形态和分布范围。

需要指出的是，剥皮的阈值d越大，剥皮的次数越少，得到的边界多边形越接近凸壳；d越小，剥皮的次数越多，得到的边界多边形就越接近线、面群的实际分布范围。其中，阈值d中“剥皮”等级k的大小可在具体计算群组目标的分布边界时根据实际情况进行调整。

图9 实验四

3 结 论

本文在约束Delaunay三角网的基础上，通过设定动态阈值，利用“剥皮”法实现空间线、面群组目标的分布边界求解。实验表明，该算法能够计算空间任意线、面群目标的分布边界多边形，得到的结果符合人们的空间认知习惯，较好地描述了线、面群目标的空间形态和分布范围。未来研究的重点是利用本文算法实现群组目标的空间方向关系判断和空间相似度计算。

［1］ 刘涛．空间群组目标相似关系及计算模型研究［D］．武汉：武汉大学，2011．

［2］ 王中辉，闫浩文．基于方向Voronoi图模型的群组目标空间方向关系计算［J］．武汉大学学报：信息科学版，2013，38（5）：584－588．

［3］ 刘涛，闫浩文．空间面群目标几何相似度计算模型［J］．地球信息科学学报，2013，15（5）：635－642．

［4］ 闫浩文，王家耀．地图群（组）目标描述与自动综合［M］．北京：科学出版社，2009．

［5］ 艾廷华，刘耀林．保持空间分布特征的群点化简方法［J］．测绘学报，2002，31（2）：175－181．

［6］ AHUJA N．Extraction of early perceptual str uct ure in dot patter ns：Integrating region，boundary and co mponent gestalt［J］．Co mputer Vision，Graphics and Image Processing，1989，48（3）：304－356．

［7］ 李玉龙，朱华华．应用Voronoi图的点群范围自动识别［J］．工程图学学报，2007（3）：73－77．

［8］ 姜志伟，王山东，王伶俐，等．基于格网和方向法索引的Delaunay三角网生成算法［J］．测绘工程，2014，23（2）：57－60．

［9］ 王中辉，闫浩文．带约束折线的平面散点集Delaunay三角剖分［J］．测绘与空间地理信息，2011，34（1）：46－47．

［10］ WATSON DF．Co mputing the n－di mension Delaunay Tessellation with Application to Voronoi Polytopes［J］．Co mputer Jour nal，1981，24（2）：167－172．

［11］马小虎，潘志庚，石教英．基于凹凸顶点判定的简单多边形Delaunay三角剖分［J］．计算机辅助设计与图形学学报，1999，11（1）：1－3．