python 實(shí)現(xiàn)德洛內(nèi)三角剖分的操作
更新時(shí)間：2021年04月22日 14:16:56 作者：hpuhjl
這篇文章主要介紹了python 實(shí)現(xiàn)德洛內(nèi)三角剖分的操作，具有很好的參考價(jià)值，希望對(duì)大家有所幫助。一起跟隨小編過來看看吧
我也不知道這玩意主要是干啥用的
實(shí)現(xiàn)如下
我用剖分的三角形的三個(gè)頂點(diǎn)到中心點(diǎn)的距離和作為顏色， 結(jié)果顯示： 點(diǎn)越密集的地方， 圖片上的顏色越深。
from scipy.spatial import Delaunay
import numpy as np
import matplotlib.pyplot as plt
width = 80
height = 40
pointNumber = 50
points = np.zeros((pointNumber, 2))
points[:, 0] = np.random.randint(0, width, pointNumber)
points[:, 1] = np.random.randint(0, height, pointNumber)
tri = Delaunay(points)
center = np.sum(points[tri.simplices], axis=1)/3.0
'''
color = []
for sim in points[tri.simplices]:
x1, y1 = sim[0][0], sim[0][1]
x2, y2 = sim[1][0], sim[1][1]
x3, y3 = sim[2][0], sim[2][1]
s = ((x1-x2)**2+(y1-y2)**2)**0.5 + ((x1-x3)**2+(y1-y3)**2)**0.5 + ((x3-x2)**2+(y3-y2)**2)**0.5
color.append(s)
color = np.array(color)
'''
color = []
for index, sim in enumerate(points[tri.simplices]):
cx, cy = center[index][0], center[index][1]
x1, y1 = sim[0][0], sim[0][1]
x2, y2 = sim[1][0], sim[1][1]
x3, y3 = sim[2][0], sim[2][1]
s = ((x1-cx)**2+(y1-cy)**2)**0.5 + ((cx-x3)**2+(cy-y3)**2)**0.5 + ((cx-x2)**2+(cy-y2)**2)**0.5
color.append(s)
color = np.array(color)
plt.figure(figsize=(20, 10))
plt.tripcolor(points[:, 0], points[:, 1], tri.simplices.copy(), facecolors=color, edgecolors='k')
plt.tick_params(labelbottom='off', labelleft='off', left='off', right='off', bottom='off', top='off')
ax = plt.gca()
plt.scatter(points[:,0],points[:,1], color='r')
#plt.grid()
plt.savefig('Delaunay.png', transparent=True, dpi=600)
補(bǔ)充：生長(zhǎng)算法實(shí)現(xiàn)點(diǎn)集的三角剖分（ Python（Tkinter模塊））
關(guān)于三角剖分
假設(shè)V是二維實(shí)數(shù)域上的有限點(diǎn)集，邊e是由點(diǎn)集中的點(diǎn)作為端點(diǎn)構(gòu)成的封閉線段, E為e的集合。那么該點(diǎn)集V的一個(gè)三角剖分T=(V,E)是一個(gè)平面圖G，該平面圖滿足條件：
1.除了端點(diǎn)，平面圖中的邊不包含點(diǎn)集中的任何點(diǎn)。
2.沒有相交邊。
3.平面圖中所有的面都是三角面，且所有三角面的合集是散點(diǎn)集V的凸包。
在實(shí)際中運(yùn)用的最多的三角剖分是Delaunay三角剖分，它是一種特殊的三角剖分。
【定義】Delaunay邊：假設(shè)E中的一條邊e（兩個(gè)端點(diǎn)為a,b），e若滿足下列條件，則稱之為Delaunay邊：
存在一個(gè)圓經(jīng)過a,b兩點(diǎn)，圓內(nèi)(注意是圓內(nèi)，圓上最多三點(diǎn)共圓)不含點(diǎn)集V中任何其他的點(diǎn)，這一特性又稱空?qǐng)A特性。
【定義】Delaunay三角剖分：如果點(diǎn)集V的一個(gè)三角剖分T只包含Delaunay邊，那么該三角剖分稱為Delaunay三角剖分。
關(guān)于Delaunay三角剖分算法可以參考百度百科Delaunay三角剖分算法
我做三角剖分的目的——構(gòu)建TIN，不規(guī)則三角網(wǎng)
不規(guī)則三角網(wǎng)（TIN）是DEM的重要形式之一，相較于規(guī)則格網(wǎng)，其具有數(shù)據(jù)冗余小、細(xì)節(jié)丟失少的特點(diǎn)。
在分布不規(guī)則的高程點(diǎn)之間構(gòu)建出三角網(wǎng)，其關(guān)鍵技術(shù)就是三角剖分
算法步驟
1、首先任選一點(diǎn)，在點(diǎn)集中找出距離改點(diǎn)最近的點(diǎn)連成一條線，以該線為基線。
2、在所有點(diǎn)中尋找能與該基線構(gòu)成具有空?qǐng)A性三角形的點(diǎn)，并構(gòu)成三角形。
3、以新生成的邊為基線，重復(fù)第二步，直至點(diǎn)集構(gòu)網(wǎng)完成。
具體代碼如下
所使用的python版本為python3.6，編輯器為Pycharm2018.3.1
#-*- coding:utf-8 -*-
import tkinter
from tkinter import filedialog
import csv
#根據(jù)兩點(diǎn)坐標(biāo)計(jì)算距離
def caldis(x1,y1,x2,y2):
return ((x1-x2)**2+(y1-y2)**2)**0.5
#輸入三角形三個(gè)頂點(diǎn)，計(jì)算外接圓圓心及半徑
def calcenter(x1,y1,x2,y2,x3,y3):
y1=-y1 #計(jì)算公式是根據(jù)平面直角坐標(biāo)推算的，原點(diǎn)在左下角，但是計(jì)算機(jī)屏幕坐標(biāo)原點(diǎn)在右上角，所以計(jì)算式y(tǒng)坐標(biāo)取負(fù)
y2=-y2
y3=-y3
if (y1 != y3 and y1 != y2 and y2 != y3): #判斷是否有y坐標(biāo)相等，即三角形某邊斜率為0的情況，避免出現(xiàn)墳分母為0的錯(cuò)誤
if(((x3-x1)/(y3-y1))-((x2-x1)/(y2-y1)))==0:
x2=x2+1
x=(((y1+y3)/2)+((x1+x3)/2)*((x3-x1)/(y3-y1))-((y1+y2)/2)-((x1+x2)/2)*((x2-x1)/(y2-y1)))/(((x3-x1)/(y3-y1))-((x2-x1)/(y2-y1)))
y=-((x3-x1)/(y3-y1))*x+((y1+y3)/2)+(((x1+x3)/2)*((x3-x1)/(y3-y1)))
return (x, -y, caldis(x, y, x1, y1))
elif (y1 == y3 and y1 != y2 and y2 != y3):#若存在斜率為0的邊則計(jì)算可簡(jiǎn)化
x=(x1+x3)/2
y=-((x2-x1)/(y2-y1))*x+((y1+y2)/2)+((x2-x1)/(y2-y1))*((x1+x2)/2)
return (x, -y, caldis(x, y, x1, y1)) #返回值為元組（圓心橫坐標(biāo)x，圓心縱坐標(biāo)y，外接圓半徑r），計(jì)算出來的y值要返回屏幕坐標(biāo)所以再次取負(fù)
elif (y1 != y3 and y1 == y2 and y2 != y3):
x = (x1 + x2) / 2
y = -((x3 - x1) / (y3 - y1)) * x + ((y1 + y3) / 2) + ((x3 - x1) / (y3 - y1)) * ((x1 + x3) / 2)
return (x, -y, caldis(x, y, x1, y1))
elif (y1 != y3 and y1 != y2 and y2 == y3):
x = (x3 + x2) / 2
y = -((x3 - x1) / (y3 - y1)) * x + ((y1 + y3) / 2) + ((x3 - x1) / (y3 - y1)) * ((x1 + x3) / 2)
return (x, -y, caldis(x, y, x1, y1))
else:
return None
class getTIN: #定義窗口及操作類
def __init__(self):
self.path=str() #坐標(biāo)文件路徑
self.pointlist=[] #存放所有點(diǎn)坐標(biāo)的列表
self.linelist=[] #存放線的列表，每條線用兩個(gè)點(diǎn)號(hào)表示連線
self.tk=tkinter.Tk() #定義主窗口
self.tk.title('MyTIN')
self.tk.geometry('1200x720')
self.shengzhang=tkinter.Button(self.tk,text='生長(zhǎng)算法',width=15,command=self.drawTIN_shengzhang)
self.shengzhang.place(x=1050,y=100) #定義按鈕，關(guān)聯(lián)到生長(zhǎng)算法計(jì)算TIN的的函數(shù)
self.readin=tkinter.Button(self.tk,text='讀入坐標(biāo)文件',width=15,command=self.getfile)
self.readin.place(x=1050,y=50)
self.can=tkinter.Canvas(self.tk,width=950,height=620,bg='white')
self.can.place(x=50,y=50)
self.tk.mainloop()
def getfile(self): #選擇坐標(biāo)文件（*.csv），從文件中讀入坐標(biāo)存入pointlist列表并在繪圖區(qū)展示出來
self.path=filedialog.askopenfilename()
f=open(self.path,'r')
fd=csv.reader(f)
self.pointlist=list(fd)
for i in range(0,len(self.pointlist)):
self.can.create_oval(int(self.pointlist[i][0])-2,int(self.pointlist[i][1])-2,int(self.pointlist[i][0])+2,int(self.pointlist[i][1])+2,fill='black')
self.can.create_text(int(self.pointlist[i][0])+7,int(self.pointlist[i][1])-7,text=str(i))
def drawTIN_shengzhang(self):
j = 1
k = 0
mindis = ((int(self.pointlist[0][0]) - int(self.pointlist[1][0])) ** 2 + (int(self.pointlist[0][1]) - int(self.pointlist[1][1])) ** 2) ** 0.5
x = len(self.pointlist)
for i in range(1, x):
dis = ((int(self.pointlist[0][0]) - int(self.pointlist[i][0])) ** 2 + (int(self.pointlist[0][1]) - int(self.pointlist[i][1])) ** 2) ** 0.5
if dis < mindis:
mindis = dis
j = i
self.linelist.append((k,j)) #首先計(jì)算出距起始點(diǎn)（點(diǎn)號(hào)為0）距離最短的點(diǎn)，以這兩點(diǎn)的連線作為基線開始生長(zhǎng)
self.shengzhangjixian(k,j)
def drawTIN(self): #根據(jù)線文件在繪圖區(qū)繪制出TIN
for i in self.linelist:
self.can.create_line(self.pointlist[i[0]][0], self.pointlist[i[0]][1], self.pointlist[i[1]][0], self.pointlist[i[1]][1])
def shengzhangjixian(self,i,j): #根據(jù)某一基線開始生長(zhǎng)的函數(shù)
x = len(self.pointlist)
for k in range(0,x): #遍歷沒一個(gè)點(diǎn)，判斷是否與基線構(gòu)成D三角形
n = 0 #n用于統(tǒng)計(jì)外接圓內(nèi)的點(diǎn)數(shù)
if ((k,i) not in self.linelist) and ((i,k) not in self.linelist) and ((j,k) not in self.linelist) and ((k,j) not in self.linelist):
for y in range(0,x): #遍歷每一個(gè)點(diǎn)，判斷
if y==i or y==j or y==k:
continue
if(calcenter(int(self.pointlist[i][0]),int(self.pointlist[i][1]),int(self.pointlist[j][0]),int(self.pointlist[j][1]),int(self.pointlist[k][0]),int(self.pointlist[k][1]))==None):
continue
else:
xyr=calcenter(int(self.pointlist[i][0]),int(self.pointlist[i][1]),int(self.pointlist[j][0]),int(self.pointlist[j][1]),int(self.pointlist[k][0]),int(self.pointlist[k][1]))
if caldis(xyr[0],xyr[1],int(self.pointlist[y][0]),int(self.pointlist[y][1])) < xyr[2]: #判斷點(diǎn)是否在外接圓內(nèi)
n=n+1
else:
continue
else:continue
if n == 0: #判斷是否為D三角形
self.linelist.append((k,i)) #將新生成的邊的端點(diǎn)號(hào)加入線列表
self.drawTIN() #調(diào)用繪制函數(shù)繪制TIN
self.shengzhangjixian(k,i) #以生成的新邊作為基線，迭代計(jì)算
self.linelist.append((k,j))
self.drawTIN()
self.shengzhangjixian(k,j)
else:continue
if __name__ == '__main__':
MyTIN=getTIN()
通過如下代碼生成一組隨機(jī)的點(diǎn)并存入文件
import random
import csv
from tkinter import filedialog
path=filedialog.askopenfilename()
OutAddress=open(path,'a',newline='')
csv_write = csv.writer(OutAddress,dialect='excel')
for i in range(0,20):
x=random.randint(30,920)
y=random.randint(30,590)
out=(x,y)
print(out)
csv_write.writerow(out)
通過上面的程序我們得到一組坐標(biāo)如下
550,432 81,334 517,265 842,408 369,123 502,169 271,425 213,482 588,248 94,295 344,350 500,385 912,527 801,491 838,455 104,479 760,160 706,77 227,314 764,576
將以上的點(diǎn)在界面中展示出來
點(diǎn)擊生長(zhǎng)算法運(yùn)行得到結(jié)果
小結(jié)
生長(zhǎng)算法在三角剖分算法中并不是什么高效的算法，其特點(diǎn)在于算法簡(jiǎn)單易行，但是計(jì)算量大，并且對(duì)于新插入的點(diǎn)無法更新，必須重新計(jì)算。
相比之下，逐點(diǎn)插入算法雖然計(jì)算量仍然較大（似乎三角剖分計(jì)算量都不?。?，但是能實(shí)現(xiàn)對(duì)新插入點(diǎn)的更新而不用重頭計(jì)算。
注：文中部分圖片及介紹來自百度百科。
以上為個(gè)人經(jīng)驗(yàn)，希望能給大家一個(gè)參考，也希望大家多多支持腳本之家。如有錯(cuò)誤或未考慮完全的地方，望不吝賜教。
相關(guān)文章
Python多線程同步Lock、RLock、Semaphore、Event實(shí)例
這篇文章主要介紹了Python多線程同步Lock、RLock、Semaphore、Event實(shí)例,Lock & RLock 用來確保多線程多共享資源的訪問,Semaphore用來確保一定資源多線程訪問時(shí)的上限,Event是最簡(jiǎn)單的線程間通信的方式,需要的朋友可以參考下2014-11-11
pandas對(duì)dataFrame中某一個(gè)列的數(shù)據(jù)進(jìn)行處理的方法
這篇文章主要介紹了pandas對(duì)dataFrame中某一個(gè)列的數(shù)據(jù)進(jìn)行處理的方法，文中通過示例代碼介紹的非常詳細(xì)，對(duì)大家的學(xué)習(xí)或者工作具有一定的參考學(xué)習(xí)價(jià)值，需要的朋友們下面隨著小編來一起學(xué)習(xí)學(xué)習(xí)吧2019-07-07
matplotlib一維散點(diǎn)分布圖的實(shí)現(xiàn)
本文主要介紹了matplotlib一維散點(diǎn)分布圖的實(shí)現(xiàn)，文中通過示例代碼介紹的非常詳細(xì)，對(duì)大家的學(xué)習(xí)或者工作具有一定的參考學(xué)習(xí)價(jià)值，需要的朋友們下面隨著小編來一起學(xué)習(xí)學(xué)習(xí)吧2023-03-03
python opencv實(shí)現(xiàn)切變換 不裁減圖片
這篇文章主要為大家詳細(xì)介紹了python opencv實(shí)現(xiàn)切變換，不裁減圖片，具有一定的參考價(jià)值，感興趣的小伙伴們可以參考一下2018-07-07
今天小編就為大家分享一篇關(guān)于Python使用folium excel繪制point，小編覺得內(nèi)容挺不錯(cuò)的，現(xiàn)在分享給大家，具有很好的參考價(jià)值，需要的朋友一起跟隨小編來看看吧2019-01-01
詳解Python中的from..import絕對(duì)導(dǎo)入語(yǔ)句
絕對(duì)導(dǎo)入其實(shí)非常簡(jiǎn)單,即是用from語(yǔ)句在import前指明頂層package名,下面我們通過兩個(gè)例子來詳解Python中的from..import絕對(duì)導(dǎo)入語(yǔ)句2016-06-06
python下paramiko模塊實(shí)現(xiàn)ssh連接登錄Linux服務(wù)器
這篇文章主要介紹了python下paramiko模塊實(shí)現(xiàn)ssh連接登錄Linux服務(wù)器的方法,實(shí)例分析了paramiko模塊實(shí)現(xiàn)ssh連接的具體用法,需要的朋友可以參考下2015-06-06
PyCharm上安裝Package的實(shí)現(xiàn)(以pandas為例)
這篇文章主要介紹了PyCharm上安裝Package的實(shí)現(xiàn)(以pandas為例)，文中通過示例代碼介紹的非常詳細(xì)，對(duì)大家的學(xué)習(xí)或者工作具有一定的參考學(xué)習(xí)價(jià)值，需要的朋友們下面隨著小編來一起學(xué)習(xí)學(xué)習(xí)吧2020-09-09
Django入門優(yōu)缺點(diǎn)及環(huán)境搭建流程
這篇文章主要為大家介紹了Django入門優(yōu)缺點(diǎn)及環(huán)境搭建流程詳解,有需要的朋友可以借鑒參考下,希望能夠有所幫助,祝大家多多進(jìn)步,早日升職加薪2023-11-11
修改默認(rèn)的pip版本為對(duì)應(yīng)python2.7的方法
今天小編就為大家分享一篇修改默認(rèn)的pip版本為對(duì)應(yīng)python2.7的方法，具有很好的參考價(jià)值，希望對(duì)大家有所幫助。一起跟隨小編過來看看吧2018-11-11