百度百科
泰森多邊形又叫馮洛諾伊圖（Voronoi diagram），得名于Georgy Voronoi，是由一組由連接兩鄰點(diǎn)線段的垂直平分線組成的連續(xù)多邊形組成。 泰森多邊形是對(duì)空間平面的一種剖分，其特點(diǎn)是多邊形內(nèi)的任何位置離該多邊形的樣點(diǎn)（如居民點(diǎn)）的距離最近，離相鄰多邊形內(nèi)樣點(diǎn)的距離遠(yuǎn)，且每個(gè)多邊形內(nèi)含且僅包含一個(gè)樣點(diǎn)。由于泰森多邊形在空間剖分上的等分性特征，因此可用于解決最近點(diǎn)、最小封閉圓等問(wèn)題，以及許多空間分析問(wèn)題，如鄰接、接近度和可達(dá)性分析等。 特征：
泰森多邊形圖例：
詳細(xì)介紹見(jiàn)百度百科泰森多邊形
算法實(shí)現(xiàn)算法一：
算法二：算法二是基于算法一的優(yōu)化。本文將著重介紹算法二。 1）算法二同樣采用特征點(diǎn)以均勻的速度向外擴(kuò)張的方式進(jìn)行。既然我們速度一定，那我們不妨設(shè)置為1，那么諸多特征點(diǎn)同時(shí)同步地向外擴(kuò)張，說(shuō)明在相遇時(shí)，相遇的特征點(diǎn)是本著相同的速度，以相同的時(shí)間到達(dá)的相遇地點(diǎn)（在這里是相遇的單元格），那么根據(jù)大眾熟知的速度路程公式s=v*t，我們知道這兩個(gè)相遇的特征點(diǎn)距離該相遇點(diǎn)的路程是相等的，也就是距離一樣，說(shuō)明該相遇點(diǎn)是這兩個(gè)特征點(diǎn)兩線的中點(diǎn)。這就符合了泰森多邊形的定義（是由一組由連接兩鄰點(diǎn)線段的垂直平分線組成的連續(xù)多邊形組成） 2）擴(kuò)張的速度我們假定為1，基準(zhǔn)的核心點(diǎn)，我們?cè)O(shè)定為特征點(diǎn)所在像素單元的幾何中心。我們規(guī)定，在以該特征點(diǎn)為圓心的輻射區(qū)域內(nèi)的其他像素單元格的幾何中心距離該特征點(diǎn)所在的幾何中心的直線距離（根據(jù)勾股定理計(jì)算即可）小于或者等于某時(shí)間點(diǎn)該特征點(diǎn)以速度為1外擴(kuò)的半徑長(zhǎng)度（即路程）時(shí)（也就是該像素單元格的大部分面積都包含在該時(shí)間點(diǎn)特征點(diǎn)輻射半徑所劃的圓中的時(shí)候），將該像素單元格賦值為特征點(diǎn)外擴(kuò)運(yùn)動(dòng)中此時(shí)的時(shí)間點(diǎn)信息。 計(jì)算中心點(diǎn)：（其中紅色點(diǎn)為核心特征點(diǎn)，黑色點(diǎn)為其外擴(kuò)過(guò)程中的一個(gè)示例點(diǎn)）
模擬泰森多邊形由核心特征點(diǎn)外擴(kuò)：（單元格中數(shù)值代表外擴(kuò)到該單元格所用的時(shí)間）
3）以步驟2）中介紹的方式，我們對(duì)所有特征點(diǎn)進(jìn)行相應(yīng)外擴(kuò)，假設(shè)每個(gè)特征點(diǎn)都輻射滿整張矩形區(qū)域，共輻射出與特征點(diǎn)數(shù)量等量的矩形表數(shù)量。（其實(shí)可以在代碼中把這些特征點(diǎn)輻射的不同數(shù)值放在一個(gè)數(shù)組集合中）。 以其中一個(gè)特征點(diǎn)輻射滿全圖為例：（圖二是用數(shù)值填充滿整個(gè)矩陣區(qū)域后，輸出excel，在excel中使用查找替換將相同的數(shù)值單元附成相同顏色的背景色） （注意輸出excel時(shí)，要輸出為“.csv”格式而不是“.xsl”和“.xslx”格式，因?yàn)楹髢煞N格式有輸出行列不超過(guò)256的限制，如果你使用矩陣行列小于256，那么就可以使用后兩種格式了） （圖一，選中單元即為核心單元點(diǎn)）
（圖二，相關(guān)查找替換后的模擬圖表）
4）依據(jù)步驟3）中的操作，我們將所有特征值的輻射全圖都計(jì)算出后，現(xiàn)在我們依據(jù)步驟1）中的理論，當(dāng)所有的輻射全圖中的某個(gè)相同單元格中，所有的輻射全圖中該單元格賦值有兩個(gè)并且是最小值相同時(shí)，那我們就把它確定為泰森多邊形的邊界線。 為什么是最小呢？ 因?yàn)槿绻麅蓚€(gè)最近的特征點(diǎn)外延先相遇了，那么后期有人再在此處相遇，對(duì)于我們而言就沒(méi)有什么意義了。
5）現(xiàn)在我們?cè)敿?xì)說(shuō)一下步驟2）的某一個(gè)特征點(diǎn)擴(kuò)充到全圖的具體操作，回到前面看算法一中的描述，我們要在某特征值的周?chē)M(jìn)行無(wú)窮無(wú)盡的試探，以及對(duì)于邊界單元兩邊的各特征點(diǎn)外擴(kuò)部隊(duì)彼此試探，互通信息困難的問(wèn)題，我們對(duì)算法一進(jìn)行了優(yōu)化，也就是算法二，為了提高效率，也本著一次遍歷運(yùn)算完所有單元的原則，我們使用步驟2）中的理論也就是大眾熟知的“勾股定理”，對(duì)整個(gè)矩陣的單元格進(jìn)行遍歷（事先我們不是已經(jīng)知道特征點(diǎn)的坐標(biāo)了么，也就是矩陣中的行列號(hào)）。對(duì)于計(jì)算出來(lái)的當(dāng)前單元格中心到特征點(diǎn)中心的直線距離，我們進(jìn)行一下處理，如果是整數(shù)，我們就直接將此數(shù)附與該單元格；如果有小數(shù)部分，例如3.4，也就是說(shuō)時(shí)間為3的時(shí)候，輻射區(qū)域還未到此單元格，時(shí)間為4的時(shí)候已經(jīng)超越了該單元格中心點(diǎn)，那么我們就為該單元格附上4，也就是對(duì)于小數(shù)取整加一。 代碼實(shí)例（python）：小編拿到的初始特征點(diǎn)坐標(biāo)文件為“xsl”文件，如下：
共29個(gè)特征點(diǎn)。 我們用到的矩陣大小為533*401。 我們的目標(biāo)是對(duì)這些特征點(diǎn)進(jìn)行構(gòu)造泰森多邊形，輸出該泰森多邊形的excel表和圖像文件。 我們的大體流程就是：
#! /usr/bin/env python #coding=utf-8 #************************************輸出圖像和excel表 # pyexcel_xls 以 OrderedDict 結(jié)構(gòu)處理數(shù)據(jù) from collections import OrderedDict from pyexcel_xls import get_data from pyexcel_xls import save_data import cmath import numpy as np from PIL import Image import math def read_xls_file(): xls_data = get_data(r"C:\Users\123\Desktop\Voronoi\result.xlsx") # print("Get data type:", type(xls_data)) #for sheet_n in xls_data.keys(): #print(sheet_n, ":", xls_data[sheet_n]) # print(len(xls_data["Sheet1"])) # print(xls_data["Sheet1"][0]) # print(len(xls_data["Sheet1"][0])) # print(type(xls_data["Sheet1"][0][0])) # print(xls_data["Sheet1"][0][0]) # 獲取特征點(diǎn)行列號(hào) VList=[] for i in range(len(xls_data["Sheet1"])): if i==0: continue; list1=[] for j in range(len(xls_data["Sheet1"][i])): if j==0: list1.append(xls_data["Sheet1"][i][j]) if j==1: list1.append(xls_data["Sheet1"][i][j]) VList.append(list1) break; # 打印獲取的行列號(hào) # for i in range(len(VList)): # for j in range(len(VList[i])): # print(VList[i][j],end="\t") # print() # 建立柵格矩陣 VMatrix=[None]*533 for i in range(len(VMatrix)): VMatrix[i] = [0]*401 for j in range(401): VMatrix[i][j]=[0]*30 print(type(VMatrix[1][1])) # print(VMatrix) # for i in range(533): # for j in range(401): # VMatrix[i][j].append(0); # print(VMatrix[i][j],end="\t") # print() # 為柵格矩陣附上特征點(diǎn) sum=0; for i in range(len(VList)): VMatrix[VList[i][0]][VList[i][1]][0]=66666 sum=sum+1 print(sum) #打印一下，共29個(gè)點(diǎn) # VMatrix[col][row+v][1]=v;#右 # VMatrix[col][row-v][1]=v;#左 # VMatrix[col+v][row][1]=v;#下 # VMatrix[col-v][row][1]=v;#上 # 在該矩形區(qū)域內(nèi)進(jìn)行遍歷計(jì)算 # for i in range(col-1,col+1): # for j in range(row-1,row+1): # Value2=(i-col)*(i-col)+(j-row)*(j-row) # if i==col&j==row: # continue; # elif abs(cmath.sqrt(Value2))<=v: # VMatrix[i][j][1]=v; # 所謂相同速度不同時(shí)間，不就是路程么？計(jì)算每個(gè)單元距離核心單元的具體距離，以速度為1算。 # 若為整數(shù)則保留，若有余數(shù)，則舍掉，加一 for k in range(len(VList)): col=VList[k][0] row=VList[k][1] for i in range(len(VMatrix)): for j in range(len(VMatrix[i])): if i==col&j==row: continue; Value2=(i-col)*(i-col)+(j-row)*(j-row) distance=cmath.sqrt(abs(Value2)).real if isinstance(distance,int): VMatrix[i][j][k+1]=distance; else: VMatrix[i][j][k+1]=math.ceil(distance); # 單獨(dú)提取三維列表中的第三維的30個(gè)變量中的一個(gè)變量 # 該30個(gè)變量中，第一個(gè)表示特征點(diǎn)，余下29個(gè)為29個(gè)特征點(diǎn)以自己為核心勻速向外擴(kuò)展的層次矩陣 # 在某一個(gè)單元內(nèi)，29個(gè)特征點(diǎn)流過(guò)的路程值中，如果有最小值不止一個(gè)，就說(shuō)明此處為邊界上的一個(gè)點(diǎn) SingleVM=[None]*533 for i in range(len(SingleVM)): SingleVM[i] = [255]*401 for j in range(len(SingleVM)): for k1 in range(len(SingleVM[j])): count=0 #29個(gè)數(shù)中最小值的計(jì)數(shù) minV=999999 for k2 in range(len(VMatrix[j][k1])): if k2==0: continue;#要把第一個(gè)元素跳過(guò)去，因?yàn)榈谝粋€(gè)元素存儲(chǔ)的是特征值 # print(VMatrix[j][k1][k3],end="\t") if VMatrix[j][k1][k2]<minV: minV=VMatrix[j][k1][k2] count=1 elif VMatrix[j][k1][k2]==minV: count=count+1 if count>=2: SingleVM[j][k1]=0;#邊界矩陣 # print() for i in range(len(VList)): SingleVM[VList[i][0]][VList[i][1]]=0 # 保存到csv文件 data = OrderedDict() # 添加sheet表 data.update({u"Sheet1": SingleVM}) #打印矩陣 # 保存成xls文件 有256行的限制 # 故存成csv文件 addr=r"C:\Users\123\Desktop\Voronoi\ResultBorder2.csv" save_data(addr, data) #保存成圖像輸出 data_list=np.asarray(SingleVM) pic=Image.fromarray(data_list.astype(np.uint8)) pic.save(r"C:\Users\123\Desktop\Voronoi\Voronoi.tif") if __name__ == '__main__': read_xls_file()
結(jié)果：1）excel文件：（由于數(shù)值過(guò)多，此處只附上將邊界單元格替換成紅色背景后的一部分表格）
2)圖像文件：
驗(yàn)證代碼的正確性：下面代碼，大家可以替換掉開(kāi)始的VList數(shù)組進(jìn)行運(yùn)行生成新的泰森多邊形。 #! /usr/bin/env python #coding=utf-8 # pyexcel_xls 以 OrderedDict 結(jié)構(gòu)處理數(shù)據(jù) # 隨便點(diǎn)幾點(diǎn)試試 from collections import OrderedDict from pyexcel_xls import get_data from pyexcel_xls import save_data import cmath import numpy as np from PIL import Image import math def read_xls_file(): VList=[[300,200],[100,200],[350,90],[60,80],[150,400]] # 打印獲取的行列號(hào) # for i in range(len(VList)): # for j in range(len(VList[i])): # print(VList[i][j],end="\t") # print() # 建立柵格矩陣 VMatrix=[None]*533 for i in range(len(VMatrix)): VMatrix[i] = [0]*401 for j in range(401): VMatrix[i][j]=[0]*6 print(type(VMatrix[1][1])) # print(VMatrix) # for i in range(533): # for j in range(401): # VMatrix[i][j].append(0); # print(VMatrix[i][j],end="\t") # print() # 為柵格矩陣附上特征點(diǎn) sum=0; for i in range(len(VList)): VMatrix[VList[i][0]][VList[i][1]][0]=0 sum=sum+1 print(sum) #打印一下，共29個(gè)點(diǎn) # VMatrix[col][row+v][1]=v;#右 # VMatrix[col][row-v][1]=v;#左 # VMatrix[col+v][row][1]=v;#下 # VMatrix[col-v][row][1]=v;#上 # 在該矩形區(qū)域內(nèi)進(jìn)行遍歷計(jì)算 # for i in range(col-1,col+1): # for j in range(row-1,row+1): # Value2=(i-col)*(i-col)+(j-row)*(j-row) # if i==col&j==row: # continue; # elif abs(cmath.sqrt(Value2))<=v: # VMatrix[i][j][1]=v; # 所謂相同速度不同時(shí)間，不就是路程么？計(jì)算每個(gè)單元距離核心單元的具體距離，以速度為1算。 # 若為整數(shù)則保留，若有余數(shù)，則舍掉，加一 for k in range(len(VList)): col=VList[k][0] row=VList[k][1] for i in range(len(VMatrix)): for j in range(len(VMatrix[i])): if i==col&j==row: continue; Value2=(i-col)*(i-col)+(j-row)*(j-row) distance=cmath.sqrt(abs(Value2)).real if isinstance(distance,int): VMatrix[i][j][k+1]=distance; else: VMatrix[i][j][k+1]=math.ceil(distance); # 單獨(dú)提取三維列表中的第三維的30個(gè)變量中的一個(gè)變量 # 該30個(gè)變量中，第一個(gè)表示特征點(diǎn)，余下29個(gè)為29個(gè)特征點(diǎn)以自己為核心勻速向外擴(kuò)展的層次矩陣 # 在某一個(gè)單元內(nèi)，29個(gè)特征點(diǎn)流過(guò)的路程值中，如果有最小值不止一個(gè)，就說(shuō)明此處為邊界上的一個(gè)點(diǎn) SingleVM=[None]*533 for i in range(len(SingleVM)): SingleVM[i] = [255]*401 for i in range(len(VList)): SingleVM[VList[i][0]][VList[i][1]]=0 for j in range(len(SingleVM)): for k1 in range(len(SingleVM[j])): count=0 #29個(gè)數(shù)中最小值的計(jì)數(shù) minV=999999 for k2 in range(len(VMatrix[j][k1])): if k2==0: continue;#要把第一個(gè)元素跳過(guò)去，因?yàn)榈谝粋€(gè)元素存儲(chǔ)的是特征值 # print(VMatrix[j][k1][k3],end="\t") if VMatrix[j][k1][k2]<minV: minV=VMatrix[j][k1][k2] count=1 elif VMatrix[j][k1][k2]==minV: count=count+1 if count>=2: SingleVM[j][k1]=0;#邊界矩陣 # print() # 保存到csv文件 data = OrderedDict() # 添加sheet表 data.update({u"Sheet1": SingleVM}) #打印矩陣 # 保存成xls文件 有256行的限制 # 故存成csv文件 addr=r"C:\Users\123\Desktop\Voronoi\zzshishiBorder2.csv" save_data(addr, data) data_list=np.asarray(SingleVM) pic=Image.fromarray(data_list.astype(np.uint8)) pic.save(r"C:\Users\123\Desktop\Voronoi\zzshishiVoronoi.tif") if __name__ == '__main__': read_xls_file()
本測(cè)試代碼生成結(jié)果：
|
|
|
來(lái)自： 精品唯居 > 《待分類(lèi)》
