一种基于Voronoi图的点密度专题图制作方法

摘要

基于Voronoi图的点密度专题图制作方法，首先读取离散点数据，以离散点构建V图；然后对整个V图区域进行栅格化，并根据像元与V多边形的隶属关系及V多边形内部像元中心点距离散点的距离来计算像元的密度值。为使结果更加合理，本发明中对生成栅格进行了邻域均值平滑处理，并进行重分类，赋予不同的灰度值；最后，渲染所有栅格。基于离散点构建的V图通过基于最短距离约束的空间划分为每个离散点生成影响范围，在此范围内进行局部密度计算保证了各影响范围之间计算结果的可比性及可靠性；另外，本方法中考虑了影响范围内不同像元点密度的差异，在各点所在的V多边形内部采用了基于距离的密度值分配办法，使结果更加合理准确。

说明书

技术领域

本发明提出的是一种点密度专题地图的制作方法，属于计算几何、地图学 与地理信息系统(GIS)中Voronoi图应用技术的交叉领域。

背景技术

点密度的计算是指根据区域内点的分布估计其内任一点所在位置单位面积 的点数。在地学应用中，点密度的计算是对居民点密度计算、建筑物密度计算 等问题进行归纳与总结后的理论抽象，在人口密度分布、图像处理、聚类分析、 判别分析、独立成分分析(ICA)、计算机视觉等领域有着重要的应用。体现点 密度分布的最直接的方法就是通过绘制点密度图。点密度图是地图学中专题图 的一种，它用点(数)来表现与数据值对应的边界或域对象，一个域对象中点 的总个数代表了域对应的数据值。

目前，计算任意一点所在处点密度主要有两种常用方法。一种是简单点密 度计算方法，即根据落入每个栅格像元周围邻域内的点要素计算单位面积的量 级。从概念上讲，它以栅格像元为出发点，对每个栅格像元中心的周围都定义 了一个邻域，将邻域内点的数量相加，然后除以邻域面积，最终得到点要素的 密度。另一种是核密度估计的方法，它以点要素为出发点，计算点要素在其周 围邻域中的密度。该方法认为在每个点上方均覆盖着一个平滑曲面。在点所在 位置处表面值最高，随着与点的距离的增大表面值逐渐减小，在与点的距离等 于搜索半径的位置处表面值为零。核函数密度估计方法的搜索邻域仅允许使用 圆形，每个输出像元的密度均为叠加在栅格像元中心的所有核表面的值之和。

这两种方法在点密度计算中都有着广泛的应用，但是搜索邻域的大小对结 果有一定影响：当搜索半径参数值越大，生成的密度栅格越平滑且概化程度越 高；当参数值越小，生成的栅格所显示的信息越详细。此外，简单点密度计算 方法以统一大小的邻域统计离散点的个数，但忽略了邻域范围内点密度的差异； 而核密度估计方法以统一大小的圆作为搜索邻域，考虑了邻域内点密度的差异， 但忽略了不同离散点“影响范围”的不同。

发明内容

本发明要解决技术问题是：克服现有技术的上述不足，借助Voronoi图对 于空间划分的技术优势，提供一种基于Voronoi图的点密度专题图制作方法， 其以每个离散点所对应的Voronoi多边形为邻域，通过反距离权重分配的方法 实现邻域内点密度的差异赋值，能够快速、合理、准确的计算点密度并输出点 密度图。

为了解决以上技术问题，本发明提供的一种基于Voronoi图的点密度专题 图制作方法，包括以下步骤：

第一步、离散点读取——读取作为原始数据的离散点集，所述离散点具有 各自的序号和坐标数据；

第二步、构建Voronoi图——基于离散点集中的所有离散点构建Voronoi 图；

第三步、Voronoi图栅格化——根据Voronoi图左上角和右下角的坐标，以 及给定的划分栅格像元的行、列数，将整个Voronoi图区域划栅格化，生成若 干像元并确定每个像元的中心点坐标；

第四步、建立像元与Voronoi多边形的隶属关系——根据像元的中心点坐 标与Voronoi多边形的拓扑关系，判定像元与Voronoi多边形的隶属关系，当 像元的中心点落在某Voronoi多边形内，则判定该像元属于该Voronoi多边形；

第五步、计算像元的密度值——第i个Voronoi多边形V_i的总密度值为1/S_g， 将该总密度值1/S_g分摊给Voronoi多边形V_i的各像元，使Voronoi多边形V_i内所 有像元的密度值总和等于1/S_g，其中，S_g为单个像元的面积，1≤i≤n，n为Voronoi 图中Voronoi多边形的个数；

第六步、栅格平滑——采用空域平滑滤波的方法重新计算每个像元密度值；

第七步、像元密度值重分类——统计分析栅格图中所有像元的密度值大小， 据此将所有像元密度值重新分类，赋予不同灰度值；

第八步、绘制密度图——根据各像元的灰度值对栅格进行渲染获得密度图。

本发明的点密度专题图制作方法中，基于离散点构建的Voronoi图，使用 Voronoi多边形对区域进行分割，使每个Voronoi多边形内有且只有一个离散点 (发生元)，每个Voronoi多边形可视为相应离散点生成“影响范围”；Voronoi 多边形内各像元密度值的计算不与其他Voronoi多边形发生关联，因此Voronoi 多边形内像元密度值的计算受干扰程度低，Voronoi多边形内局部密度计算保证 了各Voronoi多边形之间计算结果的可比性及可靠性；并且Voronoi多边形的 总密度值分摊方式可以根据实际情况进行选择，可选择均分法，也可选择反距 离权重分配法，使用更加灵活；基于离散点所构建的Voronoi图具有唯一性， 因此本发明方案实现过程中主观因素更少，易于操作。

本发明提供了以下三种Voronoi多边形总密度值分摊方案：

方案一：

在前述方法的第二步中，建立离散点与其所属的Voronoi多边形之间的对 应关系；所述第五步中，采用反距离权重分配法分摊Voronoi多边形内的各像 元密度值，Voronoi多边形内像元的密度值与该像元中心点至该Voronoi多边形 所对应的离散点的距离成反比；Voronoi多边形V_i内的第j个像元的密度值为 其中R_ij、R_ik分别表示Voronoi多边形V_i中第j个和第k个像元 的中心点至Voronoi多边形V_i所对应的离散点P_i的距离，j≤m_i，k≤m_i，m_i为 Voronoi多边形V_i内的像元个数，i、j、k均为自然数。

方案二：

在前述方法的第二步中，建立离散点与其所属的Voronoi多边形之间的对 应关系；所述第五步中，采用反距离权重分配法分摊Voronoi多边形内的各像 元密度值，Voronoi多边形内像元的密度值与该像元中心点至该Voronoi多边形 所对应的离散点的距离的平方成反比；Voronoi多边形V_i内的第j个像元的密度 值为其中R_ij R_ik分别表示Voronoi多边形V_i中第j个和第k个 像元的中心点至Voronoi多边形V_i所对应的离散点P_i的距离，j≤m_i，k≤m_i，m_i为 Voronoi多边形V_i内的像元个数，i、j、k均为自然数。

方案三：

在前述方法的第五步中，采用均分法分摊Voronoi多边形内的各像元密度 值，Voronoi多边形V_i内第j个像元的密度值B_ij＝1/(S_g*m_i)，m_i为Voronoi多边形 V_i内的像元个数，j≤m_i，且j为自然数。

前述三种方案中，前两种方法采用的是反距离权重分配法，第三种采用的 是均分法。均分法计算更加简单，点密度的空间分布可从Voronoi多边形的大 小(Voronoi多边形包含像元的数量)上反映出来，Voronoi多边形面积越大， 则点密度值越低；反距离权重分配法则考虑了“影响范围”(Voronoi多边形) 内不同像元点密度的差异，各像元所在的Voronoi多边形内部采用了基于距离 的密度值分配办法，使结果更加合理准确。

其中，反距离权重分配法中，点密度的空间分布可从计算得到的Voronoi 多边形面积的大小上反映出来，在Voronoi多边形内部进一步考虑了距离因素， 将像元的密度值按距离的倒数(或倒数的平方)所占的比重分配到各个像元中， 使得计算结果更加合理。

附图说明

下面结合附图对本发明作进一步的说明。

图1为本发明方法流程图。

图2为离散点及其Voronoi图构建示意图。

图3为像元隶属关系及密度值计算示意图。

图4为栅格邻域均值平滑示意图。

图5为像元密度值重分类示意图。

具体实施方式

下面根据附图详细说明本发明，本发明的目的和效果将变得更加明显。

如图1所示为本发明基于Voronoi图的点密度专题图制作方法的流程图， 包括以下步骤：

第一步、离散点读取——读取作为原始数据的离散点集，所述离散点具有 各自的序号和坐标数据。

读取离散点的坐标，并根据屏幕坐标范围与离散点坐标范围的比例关系显 示每个点位置(图2左)。本例中将离散点编号作为离散点的属性数据进行存储。

第二步、构建Voronoi图——基于离散点集中的所有离散点构建Voronoi 图，建立离散点与其所属的Voronoi多边形之间的对应关系；

本例中，以离散点集中所有离散点为发生元，通过扫描线算法构建Voronoi 图，将离散点的编号值传递给Voronoi多边形的编号值，这样就建立了离散点 与其所属的Voronoi多边形之间的对应关系；同时建立发生元(离散点)与 Voronoi边、发生元(离散点)与Voronoi多边形间的拓扑关系，Voronoi边的 数据结构中记录构成该边的直线方程系数，构成该边的两个端点以及与该边关 联的两侧发生元(离散点)，Voronoi多边形的数据结构中记录该多边形的边集 合；采用这样的数据有利于下面第五步中像元密度值的计算。

第三步、Voronoi图栅格化——根据Voronoi图左上角和右下角的坐标，以 及给定的划分栅格像元的行、列数，将整个Voronoi图区域划栅格化，生成若 干像元并确定每个像元的中心点坐标。

对于划分的任一p*q的格网，设其整个区域左下角和右上角的坐标分别为 (A₁，B₁)和(A₂，B₂)，其中A₁＜A₂，B₁＜B₂。像元可以二维数组形式存储，排列方式 为从左向右，从上向下排列。对于任一像元a_ij其像元中心点坐标为 其中，0≤i≤p-1，0≤j≤q-1。

第四步、建立像元与Voronoi多边形的隶属关系——根据像元的中心点坐 标与Voronoi多边形的拓扑关系，判定像元与Voronoi多边形的隶属关系，当 像元的中心点落在某Voronoi多边形内，则判定该像元属于该Voronoi多边形。

本例中，像元与Voronoi多边形的隶属关系规定如下：若像元中心点落在 哪个Voronoi多边形内，则此像元就隶属于该Voronoi多边形；若像元中心点 落在某条Voronoi边上，则查找与该边关联的两个Voronoi多边形，规定该像 元隶属于发生元编号较小的Voronoi多边形；若像元中心恰好与某个Voronoi 顶点重合，则查找与该顶点相关联的三条Voronoi边，进而找到与该顶点相关 联的三个Voronoi多边形，规定该像元隶属于三个Voronoi多边形中发生元编 号最小者。图4中实线边框内的像元为隶属于该多边形的像元。对于像元中心 落在Voronoi多边形的Voronoi边及Voronoi多边形的顶点上的情况属于特例， 这些像元的隶属关系规则可人为定义，没有严格要求，因此本发明中并没有对 该部分内容进行限定和详细说明。

第五步、计算各像元的密度值——第i个Voronoi多边形V_i的总密度值为 1/S_g，将该总密度值1/S_g分摊给Voronoi多边形V_i的各像元，使Voronoi多边形 V_i内所有像元的密度值总和等于1/S_g，其中，S_g为单个像元的面积，1≤i≤n，n 为Voronoi图中Voronoi多边形的个数；

本例中，采用反距离权重分配法分摊Voronoi多边形内的各像元密度值， Voronoi多边形内像元的密度值与该像元中心点至该Voronoi多边形所对应的离 散点的距离成反比。

如图3所示为像元隶属关系及密度值计算示意图。像元具体密度值的计算 方法如下：

Voronoi多边形V_i内的第j个像元的密度值为其中R_ij、R_ik分别表示Voronoi多边形V_i中第j个和第k个像元的中心点至Voronoi多边形V_i所对应的离散点P_i的距离，S_g表示单个像元的面积，j≤m_i，k≤m_i，m_i为Voronoi 多边形V_i内的像元个数，i、j、k均为自然数。像元密度值计算的实质就是在一 个Voronoi多边形中，根据其隶属的每一个像元的几何中心到发生元的距离的 倒数占所有像元几何中心到发生元距离倒数之和的比例来分配“一个点”的份 额，再除以像元面积得到点密度。如图5所示，左侧栅格中的数据则为计算后 得到的像元密度值，接下来进行第六步栅格平滑。

第六步、栅格平滑——采用空域平滑滤波的方法重新计算每个像元密度值。

空域平滑滤波的方法可以为邻域均值平滑法、邻域中值平滑法、邻域极值 平滑法等。本例中采用领域平均法，即将格网中一个像元的密度值与周围邻近 像元的密度值相加，然后将求得的平均值作为新格网中该像元的密度值；另外 根据生成栅格像元数的多少，采用适宜大小的模板(如5*5，9*9，25*25 等)通过逐行遍历每个像元进行所求像元邻域内的矩阵相乘，如图4所示，本 例选用的是3*3大小的模板，平滑后的栅格中像元密度值见图5右侧。经过栅 格平滑后，基本可消除Voronoi边附近的“陡坡”现象。本实施例中，采用了 均值平滑法，不排除存在更合理有效的平滑方法。

第七步、像元密度值重分类——统计分析栅格图中所有像元的密度值大小， 据此将所有像元密度值重新分类，赋予不同灰度值。

重分类的实质是将像元密度值(属性值)进行重新归类或者把输入像元密 度值更改为替代值的方法(如图5所示)。首先，逐行遍历每个像元，统计分析 所有像元密度值的中最大值、最小值及其频率分布；其次，做出频率分布直方 图与频率变化曲线，并据此选择合理的间隔阈值按密度值从小到大的顺序将所 有像元分为若干类；最后，对分类后像元赋予不同的灰度值。密度越大，赋予 的灰度值越大。

第八步、绘制密度图——根据各像元的灰度值对栅格进行渲染获得密度图。

本实施例的第五步中，Voronoi多边形内像元的密度值与该像元中心点至该 Voronoi多边形所对应的离散点的距离成反比；除此之外，Voronoi多边形内像 元的密度值与该像元中心点至该Voronoi多边形所对应的离散点的距离的平方 成反比；Voronoi多边形V_i内的第j个像元的密度值为其中R_ijR_ik分别表示Voronoi多边形V_i中第j个和第k个像元的中心点至Voronoi多边形 V_i所对应的离散点P_i的距离，j≤m_i，k≤m_i，m_i为Voronoi多边形V_i内的像元个 数，i、j、k均为自然数。

在计算像元密度值时，也可采用均分法分摊Voronoi多边形内的各像元密 度值，Voronoi多边形V_i内第j个像元的密度值B_ij＝1/(S_g*m_i)，m_i为Voronoi多边 形V_i内的像元个数，j≤m_i，且j为自然数。

本实施例基于离散点构建的Voronoi图通过基于最短距离约束的空间划分 为每个离散点生成“影响范围”，在此范围内进行局部密度计算保证了各“影响 范围”(Voronoi多边形)之间计算结果的可比性及可靠性；另外，本方法中考 虑了“影响范围”内不同像元点密度的差异，在各点所在的Voronoi多边形内 部采用了基于距离的密度值分配办法，使结果更加合理准确。

除上述实施例外，本发明还可以有其他实施方式。凡采用等同替换或等效 变换形成的技术方案，均落在本发明要求的保护范围。