利用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時非空且非單點集，則……