董 雪，劉潤濤

(哈爾濱理工大學(xué)應(yīng)用科學(xué)學(xué)院，哈爾濱150080)

區(qū)域劃分在計算幾何、計算機(jī)圖形學(xué)以及地理信息系統(tǒng)等許多領(lǐng)域有著廣泛的應(yīng)用.區(qū)域劃分比較普遍的方法有兩種[1]:一是人機(jī)交互實現(xiàn)對區(qū)域劃分，需要人工將各個區(qū)域劃分輸出.二是通過圖形識別及智能化方法對區(qū)域劃分，這種方法也需要輸入?yún)^(qū)域邊界的相關(guān)數(shù)據(jù)，然后將劃分后的封閉的子區(qū)域輸出.由于第二種方法減少了許多人工的操作，而且輸出結(jié)果更加精確，因此得到了廣泛的研究.Voronoi圖[2-3]是一個重要的計算幾何分支，在計算幾何理論和應(yīng)用中起著非常重要的作用在計算幾何中，Voronoi圖的理論有效地來解決最近點的查找、求最大空圓、求最小樹、求n個平面點的凸包等問題.王新生等采用網(wǎng)絡(luò)Voronoi圖研究城市網(wǎng)點的市場區(qū)域劃分[4].王新生等用若干條折線將平面區(qū)域劃分成若干子區(qū)域，提出一種平面區(qū)域劃分的拓?fù)渌惴?，加快了算法的運(yùn)行速度.Tomasz對于空間劃分給予過分析，但沒有詳細(xì)的算法分析.本文就是利用Voronoi圖劃分空間區(qū)域，定義了一個單位覆蓋空間，并將分塊區(qū)域內(nèi)的點集標(biāo)記顏色，位于同一分塊內(nèi)的點有相同的特性，從而把平面或維空間劃分為有周期性或準(zhǔn)周期性的分塊[5].

1 基本概念

點的集合，將由

對平面進(jìn)行分割，稱為以pi(i=1，2，……，n)為生成元(或母點)的Voronoi圖，區(qū)域V(pi)被稱為pi的Voronoi區(qū)域，見圖1.

圖1 Voronoi圖

定義2:定義集合:N表示自然數(shù)集:N={1，2，3，…}，在本文N用來表示顏色數(shù)稱為顏色集.Z表示整數(shù)集.R表示實數(shù)集，有N?Z?R.其它集合用普通的集合符號表示.向量p的坐標(biāo)為，這里單位線段表示為

定義3:定義空間:

度量空間(Dn，d)中，Dn為線性空間，距離函數(shù)d∶，滿足下列條件.

1)d(p，q)≥0;

2)d(p，p)=0;

3)d(p，q)=d(q，p);

4)d(p，q)+d(q，r)≥d(p，r).

其中:p，q，r∈Dn.

歐式空間(Rn，d)，距離函數(shù)為d∶

單位覆蓋空間(In，d)，距離函數(shù)為

定義4:在(Dn，d)空間中，V(P，κ)為Voronoi劃分，其中可數(shù)點集P?{p(i)|p(i)∈Dn，i∈N}，顏色函數(shù)κ∶p→N，用κ(p)表示點p的顏色.

定義如下:

1)V(p)={s|?q∈Pd≤d(s，q)，s∈Dn}

表示Dn的點集中生成點p的最近鄰點;

3)Pk?P中k為顏色:

Pk={p|κ(p)=k，p∈P};

5)Vk的邊界:

若P中沒有顏色為k的點，則Vk是空集.

定義5:V內(nèi)單位元的相鄰圖G(V)=(C，E)，C為頂點集，E為邊界集

2 構(gòu)建顏色分塊劃分

首先有限集P0中m個不同的點P0={p(1)，p(2)，…，p(m)}?In，在單位覆蓋空間(In，d)中的顏色Voronoi劃分V0(P0，κ0)，這里(i))=i，所以中每個點都有惟一的顏色.

然后構(gòu)建Voronoi劃分序列Vh(Ph，κh)，其中

如果給出一些約束條件P0集，就能生成(I0，d)空間中覆蓋在環(huán)面單位元連續(xù)的分塊劃分.這個簡單的約束條件是G(V0)=G(V1)，這個條件將保證所有單位元是連續(xù)的.找到更困難的約束條件是保證至少有一個單位元是不連通集，見圖2.

圖2 在平面中以m=3為例，r=2，Voronoi劃分圖

3 生成算法

為了生成和形象化近似的分塊劃分T(n，r，m，P0)，我們用點替換規(guī)則，地圖上用P0中的每個點替換P1中沒覆蓋的點集.同樣的替換規(guī)則可以應(yīng)用到Pk-1生成Pk.在Vk(Pk，κk)中的分塊單元只要有足夠大的k就能較好的接近分塊劃分V∞.

下面介紹一下?p(i)∈P0的替換規(guī)則算法S(p(i))?Rn×N如下.

1)對?p(i)∈P0，S(p(i))為空集;

2)對于?a∈(0，1，…，r-1}n和p(i)∈P0有:

②滿足?s∈P0d(q，t)≤d(q，s)，κ(t)≤κ(s)利用距離函數(shù)d找到q的最近鄰點t∈P0;

③計算出q和t之間的差:

④(u，i)加入S(t).

生成Vk(Pk，κk)的算法，間隙為r規(guī)定指數(shù)c為p(c)∈P0的顏色.

1)Pk為空集;

2)對于?p(c)∈P0:稱為

3)在Rn中計算幾何的Voronoi圖為Pk.提取Vk(Pk，κk)分塊單位元的表面作為位于Voronoi單位元之間的用不同的顏色的表面.

程序Sub(i=iteration level，k=max.iteration，

4 算法復(fù)雜度分析

該算法僅提取Vk分塊單位元的表面還不是最理想的算法.由于Pk集是P0的周期，所以Pk的Voronoi圖只包含m個不同的單位元圖.因此我們可以計算Voronoi圖V0和計算每次迭代后替換的周期分塊.最好的方法是在迭代替換和計算最后的分塊單位元時，要忽略所有的Voronoi單位元和用相同顏色包圍Voronoi單位元的生成點.最理想的算法要求計算的次數(shù)與分塊單位元表面的輸出數(shù)成正比(或者Voronoi單位元的數(shù)量為不同顏色的相鄰單位元).

5 結(jié)語

利用Voronoi圖劃分空間和其他傳統(tǒng)區(qū)域劃分空間方法相比，通過選擇適合的數(shù)據(jù)結(jié)構(gòu)，運(yùn)用點替換規(guī)則和迭代法劃分空間，并將分塊區(qū)域內(nèi)的點集標(biāo)記顏色，從而把平面或維空間劃分為有周期性或準(zhǔn)周期性的分塊.我們提出分塊劃分區(qū)域的方法推廣到空間中有很廣泛的應(yīng)用.

[1]雷小鋒，高 韜，謝昆青，等.擴(kuò)展空間對象聚類問題的研究[J].計算機(jī)工程與應(yīng)用，2003(23):172-175.

[2]CANTOR.On the power of perfect sets of points(de la puissance des ensembles parfait de points)[J].Acta Mathematica，1884(4):381–392.

[3]駱劍承，周成虎，梁 怡，等.多尺度空間單元區(qū)域劃分方法[J].地理學(xué)報，2002，57(2):167-173.

[4]王新生，余瑞林，姜友華.基于道路網(wǎng)絡(luò)的商業(yè)網(wǎng)點市場域分析[J].地理研究，2008，27(1):85-92.

[5]李新運(yùn).城市空間數(shù)據(jù)挖掘方法與應(yīng)用[M].濟(jì)南:山東大學(xué)出版社，2005.