点群选取是地图综合的重要组成部分，指在地图比例尺缩小的过程中从原始点群中抽取含有一定数量点的子集合，其目的是在点数目减少的情况下尽量正确表达点群的整体信息^[1].

点群选取的相关算法已比较成熟，具有代表性的有基于Voronoi图及加权Voronoi图的点群选取算法^[2-4]. 以上算法利用普通Voronoi图或加权Voronoi图表示点群的辐射范围，并以此为依据计算点群的选取概率，进而进行点的取舍. 其中用到的Voronoi图均将平面视为均匀空间，并假设任意2点可以通过1条直线或曲线直接相连^{[1, 4-7]}. 但在实际地理空间中，各种地理要素之间的相互联系发生于网络路径，传统Voronoi图剖分忽略了点群之间的连接与通达是沿着道路网的路径距离的事实；不仅如此，已有算法均没有顾及相关道路对点群辐射范围的影响，而现实生活中，点群的辐射范围往往与其周边道路是紧密相关的，关联道路的通达程度及道路等级等都会影响点群的辐射范围.

网络加权Voronoi图在Voronoi图的基础上将均匀空间改为网络空间，两点之间用实际网络路径距离相连^[8]. 同时，其构建过程融入了道路等级及连通方向等因素. 与平面Voronoi图相比，网络Voronoi图无疑是划分点群辐射范围更为合理、精确的方法^[9-11]. 为此，本文将网络加权Voronoi图引入点群选取，以期得到更加符合实际地理空间特征的点群选取结果.

算法主要由两部分组成：1）构建原始点群的网络加权Voronoi图；2）以网络加权Voronoi图为基础，提出“同心圆”算法进行点的删除. 其主要流程如图1所示.

城市空间通达、连接是沿着道路网伸展的，在此基础上对网络空间进行Voronoi图划分，即构建网络加权Voronoi图，是分析点群辐射范围的重要步骤. 本研究参考Ai等^[12]提出的水流扩展思想构建点群的网络加权Voronoi图，下面对其构建过程进行描述.

平面运算缺乏有效的路径搜索策略，为了能够有效识别路网的位置形状等信息，先采用路径单元剖分法进行网络图栅格化. 如图2所示为路径单元剖分法与传统栅格剖分的区别，其步骤描述如下：1）将网络路径按其节点划分为不同的弧段，如图2（a）中弧段L₁ L₂等；2）借鉴平面栅格思想，对空间网络“弧段”加密剖分，以弧段的细分单元段作为网络模型组织中的栅格，从而建立网络栅格数据模型^[13-14]（见图2（c））.

网络道路栅格化以后，将点群按照就近原则投影到网络空间道路上，将其落入的栅格单元记为点实体，如图3点中P₂~P₆对应的栅格单元. 网络边经栅格化后，边上的栅格可以分为3种类型. 1）空闲栅格：未被发生元占用的栅格（图3中的栅格S₁）；2）扩展栅格：当前栅格已被发生元占用，但其邻域栅格中存在未被占用的栅格. 则称此栅格为扩展栅格（图3中的栅格S₂）；3）占有栅格：当前栅格及其邻域栅格均被发生元占用，则称当前栅格为占有栅格（图3中栅格S₃）.

在点群栅格化基础上，以原始点群对应的栅格单元集作为发生元，沿着实际道路走向进行扩展，使其周围邻域中符合一定条件的地物被包括到该点区域中. 其扩展操作过程如下：1）将原始点群投影后的栅格单元集作为初始发生元，如图3中的P₂~P₆对应的黑粗线段标注的栅格单元. 2）以初始发生元为源头，沿着栅格化后的道路网同步向外蔓延，遇到道路交叉口即分散为不同支流继续扩展，直至道路的尽头或与其他支流相遇时结束，扩展操作的过程如图4所示.

可以看出，图4是将点群及道路段权重均视为相同，且所有道路段均为双向行驶时的扩展结果. 但在实际地空间中，扩展要受到点群权重、道路段权重及道路方向的制约^[15]. 这些制约可以描述如下.

1）点的权重越大，以其为发生元的支流的扩展速度越快：

(1) ${L_{\rm B}} = k_1 \times W(p).$

式中：L_B为该支流方向上的扩展步长，k₁为权重为1的发生元在弧段上的扩展步长，W（p）表示该点的权重函数.

2）扩展过程中相应的弧段权重越高，其上经过的支流扩展速度越快：

(2) ${L_{\rm B}} = k_2 \times W(x).$

式中：k₂为权重为1的道路段上支流的扩展步长，W（x）表示该弧段所在道路段的权重函数.

3）扩展过程会受弧段方向的制约，表现为支流只能沿着弧段的方向扩展：

(3) ${L_{\rm B}} = k_3 \times F({P_1},{P_2}).$

式中：k₃表示栅格单元长度，F（P₁，P₂）为判断支流方向P₁与道路段通达方向P₂是否一致的函数（若一致，则此函数值为1；若否，则为0）.

综上所述，网络加权Voronoi图的生成步骤（见图5）如下.

1）网络图栅格化. 将道路网按照道路交叉点划分为不同的网络弧段，然后对弧段进行网络栅格化处理.

2）初始化发生元. 将距离点群距离最近的栅格单元定义为扩展操作的初始发生元.

3）网络扩展：以初始发生元为起始弧段，以点群权重、相关联弧段权重及弧段方向为依据，沿着对应的弧段方向向外扩展一定步长，并更新栅格标识属性.

4）判断当前发生元，若其为扩展栅格，则继续沿着对应方向向外扩展，直至发生元的所有邻近栅格均为占有栅格.

点群综合的关键在于综合后的点群能够较好地保持原始点群的各类信息. 为了在充分顾及点群权重的基础上，保证原始点群信息的正确传输，算法采取了如下策略.

1）统计信息：采用开方根定律确定因比例尺变化而综合后的点的数目^[16].

(4) $N' = {N_0}\sqrt {\frac{{{M_0}}}{{M'}}} .$

式中：N₀为原始点群数目；N′为综合后的点群数目；M₀为原始地图比例尺分母；M′为目标比例尺分母.

2）专题信息：将点的权值作为点群选取的基本依据. 通过分析，将以下2个因素设为点群重要性衡量指标，并将其作为点群权重衡量指标，即：

a）点群的网络Voronoi多边形面积. 通过扩展操作，以每个点为起始的若干条弧段将组成一个多边形区域，依据文献[17]的方法求得这些弧段的外围多边形，将其称为网络Voronoi多边形（如图6中点P₁对应的多边形S₁），在网络加权Voronoi图中代表点群的辐射范围，故将其面积作为点群权重衡量的一个重要依据：

(5) ${P_{i1}} = {A_i}{\left( {\sum\nolimits_{i = 1}^n \ {{A_i}} } \right)^{{{ - 1}}}}.$

式中：P_i1表示点在点群中的网络Voronoi多边形面积所占比，A_i为第i点的网络Voronoi多边形面积.

b）点群的扩展弧段总长度. 一方面，在网络扩展过程中，点及其相关道路网的权重决定了网络扩展速度，而网络扩展速度直接影响着扩展弧段总长度. 因此，点群对应的扩展弧段总长度可以在一定程度上反映点群及其相关道路网的重要性程度；另一方面，道路网局部密度也会对网络扩展结果产生影响，而这种局部密度差异也可以通过点的扩展弧段总长度反映出来. 如图6所示，点P₂所在局部区域道路网密度明显高于点P₁所在道路网局部密度，导致在同样的扩展速度下，点P₂对应的网络Voronoi多边形面积小于点P₁对应的网络Voronoi多边形面积，这种局部密度差异可以用“由点P₂扩展的弧段总长度大于点P₁”来表示. 点群的扩展弧段总长度不仅能够反映点群的重要性程度，还可以作为网络扩展过程中道路网局部密度差异的一种表现. 因此，将点群的扩展弧段总长度作为其权重衡量的另一指标：

(6) ${P_{i2}} = {l_i}{\left( {\sum\nolimits_{i = 1}^n {{l_i}} } \right)^{ - 1}}.$

式中：P_i2表示点在点群中的扩展弧段总长度所占比，l_i为第i点的扩展弧段总长度.

在以上2个点群权重衡量指标的基础上，算法遵循“网络Voronoi多边形面积越大或其扩展弧段总长度越长，其所对应的点越容易保留”的规则进行点群选取. 并将点群分为3种类型：高等级必须保留（Ⅰ型：对应的网络Voronoi多边形面积较大或者扩展弧段总长度较大）、低等级直接舍弃（Ⅱ型：对应的网络加权Voronoi图面积及扩展弧段总长度都较小）以及介于两者之间参与选取竞争（Ⅲ型）^[18].

3）在点群综合过程中，为了使点群的拓扑信息尽可能小地改变，算法遵循“尽量不同时删除网络 Voronoi多边形邻居点”的原则进行点群取舍^[19-20]. 具体表现为点群可能为以下3种状态之一：“自由”、“固定”和“删除”，设定每个初始点都是“自由”的；在欲删除某一点时，判断其网络Voronoi多边形邻居点是否均为“自由”，若是，则将此点标记为“删除”，同时将其网络Voronoi多边形邻居点进行“固定”；否则将“固定”点改为“自由”点，开始下一轮删除操作.

4）用点的局部相对密度和点群分布范围来控制点群综合中度量信息的保持程度^{[3, 20]}.

(7) ${m_i}^\prime = {m_i}\Big/\sum\nolimits_{k = 1}^n \ {{m_k}} .$

式中：m_i'为点i的相对密度，m_i为点i的绝对密度，m_i=1/A_i.

（1）根据式（1）开方根定律^[9]求得综合过程中预删除点的数目： $n = {N_0} - N'$.

（2）利用式（5）、（6）求得点群中所有点的P_i1及P_i2. 将其对应标示在以P_i1为横坐标，P_i2为纵坐标的平面直角坐标系中（见图7（a）），并将其称为权重值点. 此时权重值越小的点（Ⅱ型点）越靠近坐标原点，因此采用以原点为圆心作1/4同心圆的方法，依次选取权重值较小的点，对其进行邻近关系判断和删除操作，本文称其为“同心圆”法.

（3）以坐标原点为原点，以权重值点与坐标原点距离的最小值为初始半径在坐标系中画1/4圆，将位于圆弧上的权重值点对应的点标记为“删除”，并“固定”其多边形邻居点.

（4）以平面坐标系中权重值点之间的最小平面距离为增量，更新半径值，以原点为圆心在坐标系内作1/4同心圆（如图7（b）所示），对于其圆弧上以及其与前一次的同心圆构成的圆环内的“自由”点，若其所有邻居点均没有被标记为“删除”，则将其标记为“删除”并“固定”其所有邻居点. 比较n与被标记为“删除”的点的个数，若n值较大，则重复4）；若两者相同，则转至6）；否则转至5）.

（5）将4）中添加了 “删除”标记的点改为 “自由”，将这些点按照网络Voronoi多边形面积降序排序，依次对位于队列尾端的点进行判别并添加“删除”标记，并对其网络加权Voronoi多边形邻居添加“固定”标记，直至标记为“删除”的点的总个数等于n时转6）；

（6）在原始点群中删除被标记为“删除”的点，剩余点群则为选取后的结果，算法结束.

选取深圳市某区域96个教育机构进行实验，其中，按照规模大小将其分为一级教育机构63个，二级教育机构33个；参与分析的道路网络由3级共4 652条道路段组成，其中市区一级道路2 217段，市区二级道路1 765段，一般道路670段. 原始地图比例尺为1∶50 000（见图8（a）），目标比例尺为1∶100 000.

在图8（b）中，以同一个点作为起始点的扩展弧段被标注了同一种颜色，灰色的点表示在点群选取过程中欲删除的点；图8（c）为点群选取结果，分析可得如下规律：1）权重值较大的点在选取过程中被保留的概率较大（实验中一级教育机构被保留的比率为91.9%；二级教育机构被保留的概率为32.3%）；2）位于多条道路交叉处的点被保留的概率较大（如图8（c）中的点P₁、P₂等）；3）相关联的道路等级较高且为双向行驶的点被保留的概率较大（如图8（c）中的点P₃等）.

如图9所示为利用传统加权Voronoi图（multiplicatively weighted Voronoi diagram，MWVD）对同样的点群数据进行实验的结果.

算法对2组实验过程中原始点群各类信息的保持程度进行了计算，其中，各类信息的传输评价标准如下.

1）统计信息：

(8) $ D_{\rm s} = |{N_{\rm g}} - {N_{\rm o}}|. $

式中：N_g为综合后点的数目，N_o为按照开方根定律应该保留的点的数目，D_s越小，统计信息传输越好.

2）专题信息：

(9) $ {D_{\rm th}} = \overline {{W}}_{\rm g} - \overline {{W}}_{\rm o}. $

式中： $\overline {{W}}_{\rm g} $ 为综合后点群权重平均值， $\overline {{W}}_{\rm o} $ 为综合前点群权重平均值，D_th越大，证明高权重点保留越多，专题信息传输越好.

3）拓扑信息：

(10) $ {D_{\rm tp}} = \overline {{d}}_{\rm o} - \overline {{d}}_{\rm g} . $

式中： $\overline {{d}}_{\rm g} $ 为综合后的点的原始网络加权Voronoi多边形邻居个数的平均值， $\overline {{d}}_{\rm o} $ 为原始点群中点的网络加权Voronoi多边形邻居个数的平均值，D_tp越小，拓扑信息传输越好.

4）度量信息：

(11) $ D_{\rm m} = \left| {\left. {\frac{{{P_{\rm o}} - {P_{\rm g}}}}{{{P_{\rm o}}}}} \right|} \right.. $

其中，P_g为综合后的点群分布边界多边形面积，P_o为综合前的原始点群分布边界多边形面积，D_m越小，密度信息传输越好.

根据式（8）~（11），得到2组实验中各类信息的传输程度量化表示如表1所示.

根据以上实验及表1可以得出：

1）基于网络加权Voronoi图的选取算法，较好地保持了原始点群的各类信息，尤其是对于统计信息与专题信息的保持与传输明显优于传统算法；在点群拓扑信息的保持策略中，由于网络加权Voronoi多边形邻居点较Voronoi多边形邻居点更符合实际地理空间特征，提出的算法对于点群拓扑信息保持程度优于传统算法，但为了更好地展示算法，实验所选点群的分布比较均匀，空间拓扑关系比较简单，从表1可以看出，这种优势不太明显；在点群度量信息的传输中，由于采用了相对密度保持策略，而利用网络加权Voronoi图与Voronoi图对于相对密度的影响区别不大，提出的算法与传统算法在度量信息的保持程度上差别不大，但由于网络加权Voronoi多边形面积较Voronoi多边形面积更能代表点群的辐射范围大小，提出的算法更具现实意义.

2）将网络加权Voronoi多边形面积及扩展弧段总长度作为衡量点群权重的两大指标引入点群选取，充分顾及了点群重要性、相关道路网权重及道路网局部密度对点群选取结果的影响.

3）网络加权Voronoi图的引入，使得点群选取算法既考虑了地理实体的空间分布等几何属性，又顾及了相关道路等级等非几何属性，使得选取结果更加合理.

4）基于网络加权Voronoi图的算法顾及到了点群关联道路的连通性，使得连通性较好的道路相关联的点具有较大的辐射范围，与实际情况比较吻合.

5）提出的点群选取算法利用“同心圆”方法解决了点群删除过程中的多因子集成问题，算法思路简单，较好地解决了点群的取舍问题.

本文提出的基于网络加权Voronoi图的点群综合算法以网络路径代替传统的欧式距离，融入了相关道路段的权重、方向等因素；在点的删除过程中，综合了点对应的网络加权Voronoi多边形面积及扩展弧段总长度对点的重要性的影响；在此基础上，提出了“同心圆”方法，较好地解决了2种因子影响下的点群取舍问题. 综合后的点群较好地保持了原始点群的各类信息；较好地顾及了点群权重、点群分布位置及点群相关联道路属性特征，综合结果更加符合实际地理空间特征.