1 引 言

点群综合的目的是在点数目减少的情况下尽量正确表达点群的整体信息，即采用一定的模型或算法从原始的点群中抽取出含有一定数量点的子集合。当制图对象的质量、数量特征过于详细时，就要采取聚类和扩差措施进行概括，减少其质量和数量特征的差别，以达到地物类别清楚、层次分明的效果^[1]。

许多学者对点群目标的综合选取进行了不同方法的试验与研究。目前，基本方法是首先对点的重要性进行判断，然后以取舍方式进行点群综合。该方法存在一定的弊端，例如点状居民地选取算法不能很好地处理拓扑信息，而基于Voronoi图的综合算法又没有考虑到点的重要性程度^{[2, 3, 4, 5, 6, 7]}。基于以上考虑，本文结合聚类方法提取聚类中心点，并用层次Voronoi图结构逐步细化地表达聚类中心点，进而实现点群由繁到简综合。通过采取逐层次的聚类中心点概括，更加便于点群分布表达与拓扑几何信息计算，而且可以有效实现类簇点的图形化，优化点群综合过程。

2 层次Voronoi图 2.1 空间点群权重值分配

空间点的权重值反映了该空间点在空间点群整体中的个体重要程度。集合P={p₁，p₂，…，p_n}代表二维空间的点群整体，其中，空间点p_i∈P描述为平面坐标(x_i，y_i)形式。集合P中共有n个空间点，采用欧氏距离作为权重度量确定点群中各点的权重值^[8]。使用n×n形式的距离矩阵D表达空间点群中点之间的距离关系

距离矩阵D是对角线元素为0的对称矩阵，即D=D^T，d_ii=0，d_ij=d_ji。其中d_ij表示点p_i到点p_j的欧氏距离。dis(·)为欧氏距离算子，d_ij计算如式(2) 点p_i与点群P中各点的距离之和等价于行向量μ_i的各元素之和 根据式(3)，点群P中各点之间所构成的距离总和为 以点p_i距离和与点群P的距离总和之比为权重，点p_i的权重值w_i描述为式(5) 此处，因各点的权重值均为与点群P的距离总和之比，所以，满足归一化条件，即各点权重值之和为1。

2.2 空间点群聚类

点群聚类将点群划分为簇(cluster)的过程，使得位于不同簇中的点之间差别较大，而处于同一簇中的点之间具有较小的差异。点群聚类算法多数是以距离为基础的簇识别过程，最为典型的是k-means算法^[9]。本文采用戴维斯·鲍尔丁指数(Davies Bouldin index，DBI)^[10]来判定当前聚类结果是否达到最优。DBI指数的物理意义是簇内之间距离之和与簇外之间距离之比，能够有效地使k-means算法得到整体最优解。空间点群聚类算法过程如下：

输入：空间点群集合P。

输出：空间类簇集合R。

(1) 对于任意∀p_i∈P，根据式(1)计算距离矩阵D并得出行向量μ_i，将行向量μ_i的元素按降序排列，取前两个值与其对应的两个点p₁、p₂，作为初始聚类中心o₁←p₁、o₂←p₂，并将聚类中心置于数组clusterArray←o₁、o₂。

(2) 根据式(2)，对于任意∀p_i∈P，∀o_i∈clusterArray，分别计算出p_i到元素o_i的距离值，并以到聚类中心的距离最小为原则，将p_i分类，标记类别，并置于数组classArray←p_i。

(3) 根据文献^[10]，计算此时的classArray中的类簇最大相似度均值，置于currIndex。

(4) 遍历数组classArray：① 根据式(2)，计算p_i至各聚类中心的最小距离，并构成序列O(min(dis(o₁，p_i)，dis(o₂，p_i)，…，dis(o_n，p_i));② 取O中的最大值及其相关点o_i。

(5) 计算classArray中的类簇最大相似度均值，置于newIndex。

(6) 如果currIndex＜newIndex，将距离clusterArray中各聚类点最远的数据点o_i置入clusterArray，clusterArray←o_i，返回至步骤(2)。

(7) 如果currIndex≥newIndex，根据式(5)，计算各聚类中心点的权重值，输出聚类结果集R。

(8) 算法结束。

2.3 空间点群的层次Voronoi图

用Voronoi图数据结构进行空间点群的二维空间剖分。首先，点的Voronoi子区域为点的凸域(convex domain)表达，并且点与其凸域之间为一一对应关系；其次，Voronoi图是一种无缝隙无重叠的连续空间覆盖，可以消除层次结构边界的二义性；第三，可避免长、宽比率过高的子区域出现，能够更好地真实表达点群在空间上的形态分布。

定义1：普通Voronoi图^{[11, 12]}。点群P={p₁，p₂，…，p_n}(2≤n＜∞，p_i≠p_j)，对于p_i(x_i，y_i)∈P，式(6)描述p_i的Voronoi子区域

dis(·)为欧氏距离算子，同式(2)。由式(7)描述的图形结构称为点群P的普通Voronoi图

以点群聚类中心为支撑，可以有效地刻画点群层次性，即每一层次的聚类中心点可顺序地构成点群由总体粗略至局部细致的表达。以每一层聚类中心点构成的普通Voronoi图为基础，存在某一层次聚类中心点群C，并且，由C构成普通Voronoi图，vor(C)={vor(c₁)，vor(c₂)，…，vor(c_n)}。设每个聚类中心点的Voronoi子区域内存在聚类中心点群C′。给出层次Voronoi图的定义如下。

定义2:层次Voronoi图。存在上下连续两层次的聚类中心点群C与C′，对于∀c′₁，c′₂，…，c′_n∈C′，如果满足

则称由下式表达图形结构称为C与C′共同构成的层次Voronoi图

定义2中，式(8)说明上层某一聚类中心的Voronoi子区域包含下层聚类中心点群。与此同时，式(9)说明下层聚类中心点群的Voronoi子区域的并集等价于它们所对应的上层聚类中心点的Voronoi子区域。引入加权重距离(additively weighted distance，AWD)^{[13, 14, 15]}进一步描述聚类中心点的Voronoi子区域

式中，c_i为某一聚类中心点；w_i为根据式(8)得到c_i的类簇权重值，即c_i的Voronoi子区域所包含的下一层次聚类中心点的权重值之和。

普通Voronoi图(实心点群)与权重Voronoi图(空心点群)的示例，如图 1所示。

将每一层次的聚类中心点集合C表达为普通Voronoi图数据结构，进而将其描述为树结构的结点，结点的数据结构描述如下：

structure treeNode

{

 point _center;

 polygon _regions;

 integer _lev;

 double _wt;

 double _dis;

 double _rad;

 treeNodeArray _childs;

}

其中，_center为二维点类型〈id，x，y〉，用于存储当前的聚类中心点；_regions为二维面类型〈id，pointArray〉，用于存储聚类中心点的Voronoi子区域；_lev描述当前层节点位于树结构中的层次；_wt记录当前节点的权重值；_dis记录当前结点与其父节点的距离值；_rad记录当前节点与其父节点的角度值；_childs代表当前节点的叶子节点，为treeNode类型的数组。

根据以上定义与树结构结点描述，层次权重Voronoi图可描述为层次Voronoi图树结构(Voronoi hierarchical tree，VHT)，如图 2所示。需要说明的是，鉴于点群在空间分布上的不均匀性，VHT树结构整体表现为非平衡多叉树(non-balanced and multi-way tree)形式，即处于树结构同一层中的结点所包含的孩子节点数不相同，并且，各叶子结点的层数不相同。

3 层次Voronoi图的点群综合方法

点群是空间分布分析的主要对象，点群分布的定量特征主要由分布范围、排列方式和密度3个方面决定^{[16, 17, 18, 19, 20]}。

3.1 分布范围(scope)

由于空间点群分布的不规则性，需要一种能够根据点群的分布特点来实现点群分布范围表达的图形结构。根据上述基于聚类的权重层次Voronoi图结构，能够有效地描述点群分布趋势。在VHT树中，以父节点的权重值表示该点群的分布范围，通过权重Voronoi图将其分布范围以区域面积大小的形式表达并计算。设VHT树结构的当前层存在n个结点，并且当前结点为node，那么，node的分布范围大小由下式计算

式中，node〈w_i〉为当前结点的权重值；area(node)为当前结点的权重Voronoi子区域面积值。

3.2 排列方式(arrangement)

以正北方向为标准方向，按顺时针顺序，以父节点C为中心，其子节点与父节点的相对象限位置为横轴，子节点与父节点的相对方位角度为纵轴，抽象表达出点群的排列方式，如图 3—图 5所示。

从描绘的曲线图中可得出，图 3在整个象限上弧度值均有分配，全局上呈现出连续分布，据此推断出此点群的排列方式为中心环状分布。如果弧度值的分配集中于象限的两端，即弧度值在各自的象限边界处连续，如图 4所示，则此点群为按条带状分布排列。若点群的弧度值在整体范围内的某一局部区域内连续，则点群是按块状方式排列，如图 5所示。

通过点群方向的变差函数(γ^*)，可确定点群的排列方式以及空间点群间的拓扑邻近性

式中，φ为角度参数；Z(x)与Z(x+φ)为区域化变量；N(φ)为点对数目。

在层次权重Voronoi图中应用自适应聚类算法，可以确定点群类簇点的排列方式，进而确定其内部点的排列方式。通过聚类运算获得的类簇点坐标确定相对的位置和方向、通过构造的点群拓扑包含关系可确定点之间的拓扑关系。

3.3 密度控制(density)

点群综合的整体性特征要求是，在点群密集的区域综合后仍然保持相对密集，而稀疏区域仍然保持相对的稀疏。相对于VHT树的根节点，取树结构第2层中的最小权重值节点min(node_i)为基准，统计其Voronoi子区域中包含的点目标个数num，计算如下

式中，vor为结点的Voronoi子区域边界所包含的点；node_i(·)为结点Voronoi区域子区域范围所包含的点。考虑综合前后比例尺的变化，该节点下的综合目标点个数num(P′)需满足以下条件 式中，S为原始比例尺；S′为综合比例尺。根据该结点所包含的综合节点总数，计算该结点分支下需要剖分的层次数，即决定结点分枝树的层数。该层次中的其他节点与该最小权重值节点需满足以下条件 式中，min(·)代表层次中面积最小的Voronoi子区域。确定其节点的点群目标综合后的数据点个数相对于最小节点综合数据点的倍数 根据m值，进而确定其分支树的层次，以保证综合后的密度疏密程度和原始数据相一致。在式(16)与式(17)中，node_i^k为根节点下第k个权重子节点；m为当前层中面积最小的Voronoi子区域所包含的聚类中心数与当前层聚类中心点数之比；num(node_i^k)为结点node_i的Voronoi子区域所包含的数据点个数；num(node_i^k′)为点群综合后结点node_i的Voronoi子区包含的数据点个数。

4 算例与分析

算例由空间点群聚类、层次加权Voronoi图构建、VHT树构建与点群综合方法4个部分构成，相关数据结构与算法在Visual Studio 2010 C#、ESRI ArcGIS Engine 10环境实现。根据给定的点群数据，首先得到点群的最小外接矩形(minimum boundary rectangle，MBR)代表计算域，由聚类的类簇点建立权重Voronoi图，并在每个权重Voronoi图形中顺次调用聚类算法、权重点的层次Voronoi图剖分方法，建立VHT树结构，进而实现空间点群的不同层次综合。

如图 6所示，图 6(a)为1∶50 000比例尺云南省腾冲市居民地点群目标数据，共计1000个数据点；图 6(b)为第1次点群聚类与权重Voronoi图剖分结果，可以看出点群分布由4个聚类中心点表示；图 6(c)为对每个权重Voronoi子区域进行再次聚类、剖分，每个子区域内点数量增加，此时，由第1次的4个聚类中心点扩展到11个聚类中心点，由于具有层次性，因此，这11个点分别代表点群在4个Voronoi子区域内的分布趋势；图 6(d)是第3次Voronoi综合后的结果，可以看出，点群在第3层次被细化表达为49个聚类中心，且是第2层11个Voronoi子区域的细化，聚类中心与原始点群在点密度上、分布上趋于一致。

多数地理现象都具有空间相关特性，即距离越近的两事物越相似。在实际应用中，各向异性现象表现更为普遍，即将方向因素纳入考虑范畴时，有可能在某个方向距离更远的事物存在更大的相似性，这种现象被称为半变异和协方差分析中的方向效应。

如图 7—图 9所示，以提取出数据的东北—西南方向为例，获得点群对的半变异云图(semivariogram/covariance cloud)，其中纵坐标γ为变异函数值，横坐标h为点对之间的距离。

点群的范围、排列、密度与几何均值的参数统计如表 1所示。

试验表明，随着剖分层次的递增，对点群的表达会越来越详细。据此，可针对不同比例尺地图和实际需求提取不同程度的点群综合图，获得满足需求的比例尺地图要素，避免点取舍过程的繁琐判断。

5 结 论

本文通过在层次Voronoi图中应用本文的自适应聚类算法，实现了空间点群目标的制图综合。该方法不仅无需获得点群中点的重要性先验知识，而且可以表现出点群的空间范围特征、点群的空间排列，以及点群在不同概括程度上的分布状况。但具体的综合要求、算法精度以及不同类型空间目标之间的协调一致等问题还有待于作进一步的研究。此外，层次Voronoi图亦可作为空间索引与空间数据可视化的基础数据结构，如何构建多路平衡形式VHT树是非常值得关注的问题。