既定水池供水区划的Voronoi模型及其算法

Voronoi model and algorithm of water supply division for a given pool location

山区供水规划常利用山头高地布设水池,针对这种既定水池位置的供水范围区划问题,提出一种基于Voronoi图的空间区域划分模型及算法.以贵州省纳雍县供水工程管网布置为研究对象,首先根据该工程地形确定水池位置,并将水池移入相对坐标中.然后采用Matlab编程语言得到供水区划的Voronoi模型,构建用水点到水池的最短取水路径.最后根据点定位的分层方法,用O(n2)的时间和空间复杂度作预处理,花费O(logn)时间便可定位任意用水点所属的Voronoi区域,实现任意用水点的优化查询.结果表明,将Voronoi模型应用到既定水池供水区划中,能实现既定水池供水范围优化划分,且能达到成本效益管理要求.

Water supply planning of the mountains often use laying pool at mountain highlands. In light of the problem of division for a given pool location, a spatial zoning model and its algorithm are proposed based on Voronoi diagram. Taking the layout of water supply pipe network in Nayong County of Guizhou Province as abject, firstly, according to the given pool which is determined by the terrain of Nayong County, and then the pool is removed into the relative coordinates. Secondly, using Matlab programming language to get the Voronoi model of the division for water supply area, the shortest path from water supply points to the pool water is determined. Finally, according to a layered approach of point positioning problem , using the temporospatial complexity of O（n^2） for pretreatment, spending O（logn）time can locate any Voronoi region which the water using point belongs to, the optimizing query of any water using point can be achieved. The results show that the Voronoi model used to the water supply division for a given pool, can make the water supply coverage of the pool to realize optimizing division and to achieve management requirements of cost-effectiveness.