利用Voronoi图解决城市绿化问题

庞 慧 王庆林

(河北建筑工程学院，河北张家口075024)

0 引言

计算几何是计算机科学领域中极有生命力的子领域.它是随着计算机的发展起来的一门学科.由于计算几何应用范围很广泛所以被越来越多的学者研究、推广、应用.该学科主要研究计算几何中的算法及其效率问题.其研究成果已在计算机图形学、化学、统计分析、模式识别、地理信息系统以及其他许多领域中得到了广泛的应用.Voronoi图是一种平面分割图，它的剖分结果能够很好地表达点与点之间的邻近关系以及点的影响范围等重要的空间信息.在计算几何中，Voronoi图理论上成功地解决了找最近点、求最大空圆、求最小树等问题.另外Voronoi图还被广泛地应用于计算机辅助设计、地理信息处理、计算机图形学、模式识别、机器人、生态研究、城市规划、最优配置、物理、化学等方面.如校区的合理划分问题;公交车站牌设置问题;移动设施服务点的最优配置、基站配置与信号测试点选址问题等等.而线段为生成元的加权Voronoi图在地理信息系统及城市规划等方面有着重要应用.如:绿化区域的划分，净化能力分析，交通道路规划等等.本文即利用线段加权Voronoi图来解决绿化带分布问题.

1 加权Voronoi图和线段加权voronoi图

加权Voronoi图是点生成元加权Voronoi图的简称.它的定义为定义1.1

定义1.1 设pi(i=1，2，…，n)为二维欧氏空间(平面)上的n个互不相同的点，λi(i=1，2，…，n)是给定的n个正实数，称

为点pi的权重为λi的Voronoi区域，其中d(p，pi)为p和pi间的Euclid距离.

如果i≠j时非空且非单点集，则称为pi和pj间的加权Voronoi边，其中是vn(pj，λj)的闭包.两条以上Voronoi边的交点，称为加权Voronoi点也就是加权 Voronoi区域的顶点.将vn(pi，λi)(i=1，2……，n)及其边界，称为以pi(i=1，2，……，n)为生成元，λi(i=1，2，……，n)为权重的点生成元上加权的Voronoi图，通常简称为加权Voronoi图.

将加权Voronoi图的生成元由点扩展为线段，就得到了线段加权Voronoi图.线段加权Voronoi图的定义

定义1.2 设Li(i=1，2，……，n)为二维欧氏空间(平面)上的n条互不相交的线段，λi(i=1，2，……，n)是给定的个正实数，称为L的权重为λ 的Voronoi多ij边形，其中为点p和p＇间的欧氏距离.称 λi为线段Li的权重.由vn(Li，λi)i(i=1，2，……n)确定的对平面的分割称为线段加权的Voronoi图.

2 线段加权voronoi图的离散生成

2.1 判断新添加的线段是否与已有线段相交

将生成元推广至线段后，首先遇到的问题就是如何生成互不相交的若干条线段生成元.那么具体函数的做法是:先画出两条线段来，判断其是否相交，相交则舍去，不相交则添加.再添加第三条线段时，用同样的方法可以判断出它是否与前两条相交，以此类推即可.可用下面方法来判断两条线段是否相交.

线段1经过已知点(x10，y10)，(x11，y11)其参数方程为

线段2经过已知点(x20，y20)，(x21，y21)其参数方程为

线段1和线段2解以x，y，t1，t2为参数的四元一次方程组并确定t1，t2的范围，如果t1∈［0，1］且t2∈［0，1］，那么两线段相交;如果t1∉［0，1］或t≠∉［0，1］或t1，t2∉［0，1］则两线段不相交.两线段可能平行，这时两条直线的斜率相等即，平行时又分为两种情况平行不重合时表示可以添加;两条直线重合时，舍去.这样我们就可以通过判断两条线段是否相交来添加若干条线段生成元.

2.2 线段加权Voronoi图离散生成法的基本思想

用离散生成法画线段加权Voronoi图的基本思想是:首先，对每一条线段生成元指定一种颜色，使不同线段生成元之间的颜色互不相同，并且给每条线段生成元赋以权重值;然后，在各个生成元的边界上选取具有代表性的点，称为母点，如图1所示.最后，对每个母点，以母点为圆心，用母点所在线段生成元的颜色，以各母点所在线段生成元的权重逐渐向外扩展画圆.同一线段生成元上母点的颜色以及扩展速度是相同的.当屏幕上所有的像素都画上了颜色时，结束.此时不同颜色区域的边界即为线段加权Voronoi图的近似曲线，如图2所示.当母点充分密集时，这种近似效果可达到很高的程度.

3 线段加权voronoi图权重的确定

当有多个因素来确定权值时需要用层次分析法来进行计算.我们以公园或绿化带的选址为例.每个绿化带空气净化影响区域受绿化带自身面积、植物类型、周边污染源污染程度影响，层次模型如图3所示.评估专家分别对四个参评绿化带的三个主要因素进行评分后，填写比较表，构成判断矩阵.

经过计算后五个影响因素的权重比例如表1所示

表1 各影响因素权重表

四个绿化带的各自权重如表2所示

表2 四个绿化带的权重表

4 线段加权Voronoi图在绿化带选址中的应用

根据层次分析法所得到的权值由于差距不大这样会造成在生成加权voronoi图时画圆速度差别不大.为使得这种差别体现得更为明显，表2中的权值分别乘以100作为每个绿化带的权重.图4中线段是将绿化带抽象为线段后的选址位置，以这个位置为生成元，以表2权值的100倍为权值，利用离散的方法生成线段加权Voronoi图的区域划分结果如图5所示

从图5的结果进行分析，voronoi点离绿化带远的区域是目前绿化带净化空气难以到达的区域.在将来进行绿化带选址时首先考虑的增加绿化设施的区域即是这些离目前绿化带远的这些区域.

5 结束语

本文首先对Voronoi图与线段加权Voronoi图的基本知识进行了简单介绍，然后给出了一种离散法实现线段加权Voronoi图.线段加权Voronoi的权重是综合多种因素而得到的权重，权重是利用层次分析法而确定的，权重值更为准确.线段加权Voronoi区域面积本身是更符合生活实际的面积.将绿化区域抽象为线段后作为生成元生成线段加权Voronoi，其绿化区域即为每个Voronoi区域，可以非常明确地看出那些区域需要加强新的绿化区域.这样可以使得规划部门有目的地进行新增绿化区域的选址.

［1］周培德，卢开澄.计算几何——算法分析与设计［M］.北京:清华大学出版社，广西科学技术出版社，2000

［2］赵晔，张有会等.关于一般图形 Voronoi图的离散构造法的研究［J］.计算机应用与软件.Vol 21 No.6，2004，6

［3］许树柏.层次分析法原理［M］.天津:天津出版社，1998

［4］董蕊，张有会等.线段加权Voronoi图的离散生成算法的研究与实现［J］.计算机应用与软件，2009，7

［5］赵志辉、张有会等.线段障碍Voronoi图的离散生成［J］.计算机应用与软件，2004

［6］陈军.Voronoi动态空间数据模型［M］.北京:测绘出版社，2002