基于python 凸包問(wèn)題的解決
最近在看python的算法書(shū),之前在年前買(mǎi)的書(shū),一直在工作間隙的時(shí)候,學(xué)習(xí)充電,終于看到這本書(shū),但是確實(shí)又有點(diǎn)難,感覺(jué)作者寫(xiě)的代碼太炫技 了,有時(shí)候注釋也不怎么能看懂,終于想到一個(gè)方法,就是里面說(shuō)的算法問(wèn)題,我就百度python解決他,覺(jué)得這個(gè)挺好。
下面是凸包問(wèn)題的一個(gè)代碼。
# -*- coding: utf-8 -*- import turtle import random import time f=open('point.txt','w') for i in range(100): x=random.randrange(-250,250,10) y=random.randrange(-200,200,10) f.write(str(x)+','+str(y)+'\n') f.close() point=[] f=open('point.txt') for i in f: try: temp=i.split(',') x=float(temp[0]); y=float(temp[1]) point.append((x,y)) except : print 'a err' f.close() point=list(set(point))#去除重復(fù)的點(diǎn) n=0 for i in range(len(point)): if point[n][1]>point[i][1]: n=i p0=point[n] point.pop(n) def compare(a,b): x=[a[0]-p0[0],a[1]-p0[1]] y=[b[0]-p0[0],b[1]-p0[1]] dx=(x[0]**2+x[1]**2)**0.5 dy=(y[0]**2+y[1]**2)**0.5 cosa=x[0]/dx cosb=y[0]/dy if cosa < cosb: return 1 elif cosa > cosb: return -1 else: if dx<dy: return -1 elif dx>dy: return 1 else: return 0 point.sort(compare) point.insert(0,p0) ep=point[:]#復(fù)制元素,操作ep不會(huì)對(duì)point產(chǎn)生影響 tag=0 while tag==0: tag=1 l=len(ep) for i in range(l): i1,i2,i3=(i,(i+1)%l,(i+2)%l) x,y,z=(ep[i1],ep[i2],ep[i3]) a1,a2=((y[0]-x[0],y[1]-x[1]),(z[0]-y[0],z[1]-y[1])) if a1[0]*a2[1]-a1[1]*a2[0] < 0: tag=0 ep.pop(i2) break elif a1[0]*a2[1]-a1[1]*a2[0]==0 and a1[0]*a2[0]<0: #==0應(yīng)改寫(xiě),360度的情況 tag=0 ep.pop(i2) break def drawpoint(point,color,line): p=turtle.getturtle() p.hideturtle() turtle.delay(1) if(line=='p'): p.speed(0) for i in point: p.pu() p.color(color) p.goto(i) p.pd() p.dot() elif(line=='l'): p.pu() p.speed(1) for i in point: p.color(color) p.goto(i) p.pd() p.dot() p.goto(point[0]) drawpoint(point,'black','p') drawpoint(ep,'red','l') time.sleep(1)
補(bǔ)充知識(shí):凸包問(wèn)題的蠻力算法及python實(shí)現(xiàn)
蠻力法的基本思想是先用排除法確定凸包的頂點(diǎn),然后按逆時(shí)針順序輸出這些頂點(diǎn)。在判斷點(diǎn)P是不是凸包上的頂點(diǎn)時(shí),有如下性質(zhì):
給定平面點(diǎn)集S,P,Pi,Pj,Pk是S中四個(gè)不同的點(diǎn),如果P位于Pi,Pj,Pk組成的三角形內(nèi)部或邊界上,則P不是S的凸包頂點(diǎn)。
那么如何判斷點(diǎn)P在三角形內(nèi)部或邊界上?給定平面兩點(diǎn)AB,直線方程g(A,B,P)=0時(shí),P位于直線上,g(A,B,P)>0和g(A,B,P)<0時(shí),P分別位于直線的兩側(cè)。
判斷點(diǎn)P在三角形內(nèi)部或邊界上只需依次檢查P和三角形的每個(gè)頂點(diǎn)是否位于三角形另外兩個(gè)頂點(diǎn)確定的直線的同一側(cè),即判斷:
t1=g(pj,pk,p)*g(pj,pk,pi)>=0 ,
t2=g(pi,pk,p)*g(pi,pk,pj)>=0,
t3=g(pj,pi,p)*g(pj,pi,pk)>=0
是否同時(shí)成立
凸包問(wèn)題的蠻力算法偽代碼如下:
BruteForce(S):
輸入:平面n個(gè)點(diǎn)的集合S
輸出:按逆時(shí)針順序輸出S的凸包的所有頂點(diǎn)
If n=3 Then 以逆時(shí)針順序輸出S的頂點(diǎn),算法結(jié)束 找到S中縱坐標(biāo)最小的點(diǎn)P,該點(diǎn)一定位于凸包上
For S中任意三點(diǎn)Pi,Pj,Pk Do If Pi,Pj,Pk 一點(diǎn)位于其他兩點(diǎn)與P構(gòu)成的三角形內(nèi) Then 刪除該點(diǎn)
找出S中橫坐標(biāo)最小的點(diǎn)A和橫坐標(biāo)最小的點(diǎn)B
將S劃分問(wèn)直線AB上方點(diǎn)集SU,直線AB下方點(diǎn)集SL,A,B兩點(diǎn)屬于SL
將SL按橫坐標(biāo)遞增排序,SU按橫坐標(biāo)遞減排序順序輸出SL,SU
首先隨機(jī)生成點(diǎn)集S
import random import itertools def generate_num(n): random_list = list(itertools.product(range(1, 100), range(1, 100))) lists=random.sample(random_list, n) return lists
判斷點(diǎn)P在三角形內(nèi)部或邊界上,即判斷點(diǎn)P是否在凸包上
在具體的判斷過(guò)程中,尤其時(shí)坐標(biāo)點(diǎn)比較密集的情況下,還有有三種比較特殊的情況
組成直線的兩點(diǎn)垂直于x軸
除點(diǎn)P外其余三點(diǎn)在一條直線上時(shí),不應(yīng)刪除點(diǎn)P,因?yàn)榇藭r(shí)點(diǎn)P可能時(shí)凸包上的點(diǎn)
除點(diǎn)P外其余三點(diǎn)在一條直線上且垂直于x軸時(shí),不應(yīng)刪除點(diǎn)P,因?yàn)榇藭r(shí)點(diǎn)P可能時(shí)凸包上的點(diǎn)
#判斷pi是否位于pj,pk,p0組成三角形內(nèi),返回t1,t2,t3三個(gè)變量 def isin(pi,pj,pk,p0): x1 = float(p0[0]) x2 = float(pj[0]) x3 = float(pi[0]) x4 = float(pk[0]) y1 = float(p0[1]) y2 = float(pj[1]) y3 = float(pi[1]) y4 = float(pk[1]) k_j0=0 b_j0=0 k_k0=0 b_k0=0 k_jk=0 b_jk=0 perpendicular1=False perpendicular2 = False perpendicular3 = False #pj,p0組成的直線,看pi,pk是否位于直線同一側(cè) if x2 - x1 == 0: #pj,p0組成直線垂直于X軸時(shí) t1=(x3-x2)*(x4-x2) perpendicular1=True else: k_j0 = (y2 - y1) / (x2 - x1) b_j0 = y1 - k_j0 * x1 t1 = (k_j0 * x3 - y3 + b_j0) * (k_j0 * x4 - y4 + b_j0) #pk,p0組成的直線,看pi,pj是否位于直線同一側(cè) if x4 - x1 == 0: #pk,p0組成直線垂直于X軸時(shí) t2=(x3-x1)*(x2-x1) perpendicular2=True else: k_k0 = (y4 - y1) / (x4 - x1) b_k0 = y1 - k_k0 * x1 t2 = (k_k0 * x3 - y3 + b_k0) * (k_k0 * x2 - y2 + b_k0) # pj,pk組成的直線,看pi,p0是否位于直線同一側(cè) if x4 - x2 == 0: # pj,pk組成直線垂直于X軸時(shí) t3=(x3-x2)*(x1-x2) perpendicular3 = True else: k_jk = (y4 - y2) / (x4 - x2) b_jk = y2 - k_jk * x2 t3 = (k_jk * x3 - y3 + b_jk) * (k_jk * x1 - y1 + b_jk) #如果pk,p0,pj,三點(diǎn)位于同一直線時(shí),不能將點(diǎn)刪除 if (k_j0 * x4 - y4 + b_j0)==0 and (k_k0 * x2 - y2 + b_k0)==0 and (k_jk * x1 - y1 + b_jk)==0 : t1=-1 #如果pk,p0,pj,三點(diǎn)位于同一直線時(shí)且垂直于X軸,不能將點(diǎn)刪除 if perpendicular1 and perpendicular2 and perpendicular3: t1=-1 return t1,t2,t3
接下來(lái)是實(shí)現(xiàn)算法主要部分,用來(lái)找出凸包上的點(diǎn)
import isintriangle def force(lis,n): #集合S中點(diǎn)個(gè)數(shù)為3時(shí),集合本身即為凸包集 if n==3: return lis else: #集合按縱坐標(biāo)排序,找出y最小的點(diǎn)p0 lis.sort(key=lambda x: x[1]) p0=lis[0] #除去p0的其余點(diǎn)集合lis_brute lis_brute=lis[1:] #temp是用來(lái)存放集合需要?jiǎng)h除的點(diǎn)在lis_brute內(nèi)的索引,四個(gè)點(diǎn)中如果有一個(gè)點(diǎn)在其余三個(gè)點(diǎn)組成的三角形內(nèi)部,則該點(diǎn)一定不是凸包上的點(diǎn) temp=[] #三重循環(huán)找到所有這樣在三角形內(nèi)的點(diǎn) for i in range(len(lis_brute)-2): pi=lis_brute[i] #如果索引i已經(jīng)在temp中,即pi一定不是凸包上的點(diǎn),跳過(guò)這次循環(huán) if i in temp: continue for j in range(i+1,len(lis_brute) - 1): pj=lis_brute[j] #如果索引j已經(jīng)在temp中,即pj一定不是凸包上的點(diǎn),跳過(guò)這次循環(huán) if j in temp: continue for k in range(j + 1, len(lis_brute)): pk=lis_brute[k] #如果索引k已經(jīng)在temp中,即pk一定不是凸包上的點(diǎn),跳過(guò)這次循環(huán) if k in temp: continue #判斷pi是否在pj,pk,p0構(gòu)成的三角形內(nèi) (it1,it2,it3)=isintriangle.isin(pi,pj,pk,p0) if it1>=0 and it2>=0 and it3>=0: if i not in temp: temp.append(i) # 判斷pj是否在pi,pk,p0構(gòu)成的三角形內(nèi) (jt1,jt2,jt3)=isintriangle.isin(pj,pi,pk,p0) if jt1>=0 and jt2>=0 and jt3>=0: if j not in temp: temp.append(j) # 判斷pk是否在pj,pi,p0構(gòu)成的三角形內(nèi) (kt1, kt2, kt3) = isintriangle.isin(pk, pi, pj, p0) if kt1 >= 0 and kt2 >= 0 and kt3 >= 0: if k not in temp: temp.append(k) #listlast是最終選出的凸包集合 lislast=[] for coor in lis_brute: loc = [i for i, x in enumerate(lis_brute) if x == coor] for x in loc: ploc = x if ploc not in temp: lislast.append(coor) #將p0加入凸包集合 lislast.append(p0) return lislast
最后將凸包集合輸出就不多說(shuō)了,按照偽碼上實(shí)現(xiàn)就可以,凸包蠻力算法在點(diǎn)集大小為1000時(shí)結(jié)果
以上這篇基于python 凸包問(wèn)題的解決就是小編分享給大家的全部?jī)?nèi)容了,希望能給大家一個(gè)參考,也希望大家多多支持腳本之家。
相關(guān)文章
基于Python編寫(xiě)一個(gè)計(jì)算器程序,實(shí)現(xiàn)簡(jiǎn)單的加減乘除和取余二元運(yùn)算
這篇文章主要介紹了基于Python編寫(xiě)一個(gè)計(jì)算器程序,實(shí)現(xiàn)簡(jiǎn)單的加減乘除和取余二元運(yùn)算,文中通過(guò)示例代碼介紹的非常詳細(xì),對(duì)大家的學(xué)習(xí)或者工作具有一定的參考學(xué)習(xí)價(jià)值,需要的朋友們下面隨著小編來(lái)一起學(xué)習(xí)學(xué)習(xí)吧2020-08-08Pytorch中torch.repeat_interleave()函數(shù)使用及說(shuō)明
這篇文章主要介紹了Pytorch中torch.repeat_interleave()函數(shù)使用及說(shuō)明,具有很好的參考價(jià)值,希望對(duì)大家有所幫助。如有錯(cuò)誤或未考慮完全的地方,望不吝賜教2023-01-01Python?中?threading.Thread.join()?的使用方法示例詳解
threading.Thread.join()用于阻塞當(dāng)前線程,直到調(diào)用它的線程對(duì)象執(zhí)行完成或者超時(shí),在Python中,想要充分利用多線程的優(yōu)勢(shì),就需要對(duì)threading模塊中的 Thread 類(lèi)了解,這里有一個(gè)非常簡(jiǎn)單的多線程程序,幫助理解 threading.Thread.join 方法,感興趣的朋友跟隨小編一起看看吧2024-06-06Python基礎(chǔ)進(jìn)階之海量表情包多線程爬蟲(chóng)功能的實(shí)現(xiàn)
這篇文章主要介紹了Python基礎(chǔ)進(jìn)階之海量表情包多線程爬蟲(chóng),本文通過(guò)實(shí)例代碼給大家介紹的非常詳細(xì),對(duì)大家的學(xué)習(xí)或工作具有一定的參考借鑒價(jià)值,需要的朋友可以參考下2020-12-12python實(shí)現(xiàn)字符串連接的三種方法及其效率、適用場(chǎng)景詳解
本篇文章主要介紹了python實(shí)現(xiàn)字符串連接的三種方法及其效率、適用場(chǎng)景詳解,具有一定的參考價(jià)值,感興趣的小伙伴們可以參考一下。2017-01-01對(duì)Pyhon實(shí)現(xiàn)靜態(tài)變量全局變量的方法詳解
今天小編就為大家分享一篇對(duì)Pyhon實(shí)現(xiàn)靜態(tài)變量全局變量的方法詳解,具有很好的參考價(jià)值,希望對(duì)大家有所幫助。一起跟隨小編過(guò)來(lái)看看吧2019-01-01