Power图扫描生成算法研究

2013-07-19弓小影张有会王丹丹

中国科技信息 2013年21期

弓小影张有会王丹丹

1. 石家庄经济学院数理学院, 河北石家庄 050031

2. 河北师范大学数学与信息科学学院, 河北石家庄 050016

引言

Voronoi图[1]是计算几何的一个重要分支，它是针对一个有限点集，以点作为生成元(或母点)按照一定规则将平面分割成若干小区域，这种分割图形在表达点与点之间的位置关系以及点的影响区域等空间信息时很有优势。考虑到生成元会具有不同的性质，因此有必要考虑给生成元加权。Power图就是对每个生成元加权，并且将欧式距离推广为Power距离[2]而生成的Voronoi图。

Power图的传统构造方法有正则三角化构造法[2]和近些年提出的离散生成法[3]等.这些算法均对构造Power图做出过历史性的贡献，但它们在程序设计思路或数据结构等方面还略显复杂。因此，我们力求寻找一种程序设计思路简洁，辅助数据结构简单，且能保证图形效果的算法，下面就给出Power的扫描生成算法。

1 Power图的定义 [4]

图1 Power图

Power图有许多良好性质，具体参见文献[3]及[5]，不再赘述。

2 Power图的扫描生成算法

2.1 算法的基本思想

由Power图的定义，关键将生成元的Power边画出来即可，如果将到相邻两个母点(生成元)的Power距离相等的点逐个画出，就可以直接画出Power边，进而生成Power图.该算法具体描述为：任意取屏幕上的像素点，计算点到个生成元的Power距离，从这个距离数值中找出两个最小距离和次最小距离记录下来，如果次最小距离和最小距离之差小于事先指定的某阈值，则画出点，否则就不画，继续判断屏幕上下一个像素点是否符合上述条件.当扫描完屏幕上的所有像素点后，便可以生成Power图。

2.2 扫描生成算法的具体描述

算法具体如下；

2.3 算法中的关键技术：考虑相邻生成元间的距离对Power图的影响

下面证明：两个相邻生成元之间的距离大小会影响到Power边上的任意一点到这两个生成元的Power距离差。

图2

图3

图4 生成元距离对Power图的影响

图5 考虑M因素后生成的Power图

上述已经证明两相邻生成元间的距离在生成Power图时，对Power图会产生影响，因此，设置的阈值应与相邻两个生成元之间的距离有关，具体做法如下：

2.4 作图实例（用VC＋＋6.0实现）

在Visual C++6.0[6]环境下，本文提供的算法已经编程实现，图6就是由该算法生成Power图的过程图例，其中各生成元的坐标由随机产生，权重由随机产生。

图6 扫描法生成Power图的过程图

3 Power图的应用实例[7][8][9][10]

下面以石家庄市东南区域公园分布为例，以公园作为生成元，赋予不同的权值，利用扫描生成算法构造Power图，通过Power模型分析每个公园控制区域。

图7是石家庄电子地图（2012年版）的一部分，图中标示出了石家庄市东南区域有五个公园。

图7 石家庄东南部公园分布图

随着人们生活水平的提高，保健意识的增强，公园日益成为人们生活离不开的场所，去公园遛弯、锻炼一般会选择平面距离比较近的，因此，平面欧氏距离会影响公园的影响区域。同时，公园的环境、锻炼器材、服务设施等也会影响居民的选择，将这些因素综合考虑作为公园的影响能力，用不同的权值代表，这样就可以将公园抽象为点生成元，进而构造出Power图，结果如图8所示，图中黑点代表公园，数字代表每个公园不同的权值。

图8 以公园为生成元生成的Power图

由Power图理论，权值较大的生成元的覆盖区域应较大，但由图8可见，希望绿洲公园权值较大(因该公园设施较全、环境很好、附近居民区很多，故用较大的权值来代表这些因素)，但它的覆盖区域却较小，这样就造成了附近居民比如想去那的健身器材锻炼，会出现人较多，需要等待，或者去那遛弯人很多，难于找到地方休息等等局面的出现，或者要去较远的公园，从这个意义上来说，现有公园的布局不能满足人们的生活需求，在东南角区域应再增加公园。好在现在市政府已经意识到这一问题，修建了或正在筹建公园、绿地满足居民的需求，同时提高人民的生活质量。