ドロネー三角形を作りたかったので、ひさびさにOpenCVで遊んでみました。
ドロネー三角形(ドロネー図)というのは、適当な点のリストを線でつないで、適当な三角形を作ること、です。
ドロネー図 – Wikipedia
OpenCVライブラリはインテルが配布している、無料の画像処理ライブラリ。これを使うと、点のリストを渡すだけで、簡単にドロネー図を作成してくれます。
詳しい使用方法やインスコ方法などの解説は
http://opencv.jp/tips
平面細分割¶
をごらんください
今回はこちらのwindows用バイナリをインストールしました
http://sourceforge.net/projects/opencvlibrary/files/opencv-win/2.1/OpenCV-2.1.0-win32-vs2008.exe/download
OpenCVに付属のサンプル delaunay.py は少しややこしいので、必要最低限の関数にまとめることに。
今回は点をつなぐ線が欲しいだけなので、比較的簡単にできました。
delaunay_simple.py
#!/usr/bin/python # -*- coding: cp932 -*- import cv def delaunay_simple(pxy_list): u"ドロネー三角形" storage = cv.CreateMemStorage(0); xlist=[p[0] for p in pxy_list] ylist=[p[1] for p in pxy_list] rect=(min(xlist)-1,min(ylist)-1,max(xlist)+1,max(ylist)+1) subdiv = cv.CreateSubdivDelaunay2D( rect, storage ); pdict=dict() for idx,pxy in enumerate(pxy_list): p =cv.SubdivDelaunay2DInsert( subdiv, pxy ) pdict[p.pt]=idx next_dict=dict() for k in pdict: pass for edge in subdiv.edges: p0= cv.Subdiv2DEdgeOrg(edge).pt p1= cv.Subdiv2DEdgeDst(edge).pt if not p0 in pdict or not p1 in pdict: continue i0=pdict[p0] i1=pdict[p1] if not i0 in next_dict: next_dict[i0]=[] if not i1 in next_dict: next_dict[i1]=[] if not i1 in next_dict[i0] : next_dict[i0].append(i1) if not i0 in next_dict[i1] : next_dict[i1].append(i0) for k in next_dict: next_dict[k].sort() return next_dict #テストコード if __name__ == '__main__': #点のリストの作成 from random import random from math import sqrt idx=0 plist=[] while idx>10: px,py= 1.*random(),1.*random() for x,y in plist: if sqrt( (x-px)**2+(y-py)**2)>.1 : break else : plist.append( (px,py)) idx+=1 #plist=list(set(plist)) for p in plist: print p print "***" #作図に必要なのは 下の一行だけ。 #点のxy座標ペアの入ったリストを渡すと、 #点ごとに、どの点と線でつながっているのか辞書に #格納されて返ってきます。 next_dict=delaunay_simple(plist) print next_dict #ここからはグラフィックで表示するためのルーチン W,H=500,500 img = cv.CreateImage( (W,H), 8, 3 ); line_color = cv.RGB(0,0,0); point_color = cv.RGB(255,0,0); bg_color = cv.RGB(255,255,255); cv.Set( img, bg_color ) for k in next_dict: px0,py0=plist[k] px0*=W py0*=H for j in next_dict[k]: px1,py1=plist[j] px1*=W py1*=H pt1=(int(px0),int(py0)) pt2=(int(px1),int(py1)) cv.Line(img,pt1,pt2,line_color) for px,py in plist: px*=W py*=H pt1=(int(px-2),int(py-2)) pt2=(int(px+2),int(py+2)) cv.Rectangle(img,pt1,pt2,point_color) cv.SaveImage("delaunay.png",img) winname="delaunay" cv.NamedWindow(winname) cv.ShowImage(winname,img) cv.WaitKey(0); cv.DestroyWindow( winname );
今回はデモなので10個ですけど、点が千個以上でもラクラクです。