ドロネー三角形を作りたかったので、ひさびさに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個ですけど、点が千個以上でもラクラクです。