2011.06.04 | 

先日、4時前に空が明るくなっててびっくりしました。
夏がまたやって来ますね。マサラ・ムーチョことムーチョです。こんばんは。
さてさて、Flash界では流行ともいえるドロネー図
Cinder+OpenCVで逆輸入してみました。
つたないソースですが、ソースコードも公開します。

座標群をドロネー三角形分割化し、出力するわけですが、
出力で必要なのは線だとつながる2点、面だと3点が必要になります。
今回は線の出力です。


おおおつながってるよ! 今回座標の数は2000。60fpsでもギュンギュン。


OpenCVでドロネー図を作る際、以下のような流れになります。
1.空のドロネー空間を作成
2.座標をドロネー空間に追加
3.線の座標を取得
4.描画
以下抜粋ソースです。



// 座標群
	for(int i = 0; i < points.size(); i++){
		float posx = 	Rand::randFloat()*Rand::randFloat(-1,1)*getWindowWidth()*0.5+getWindowWidth()*0.5;
		float posy = 	Rand::randFloat(-1,1)*Rand::randFloat(-1,1)*getWindowHeight()*0.5+getWindowHeight()*0.5;
		points[i]=Vec2f(posx,posy);
	}

// 1.空のドロネー空間を作成
	CvRect rect = { 0, 0, getWindowWidth(), getWindowHeight() };
	storage = cvCreateMemStorage(0);

	subdiv = cvCreateSubdiv2D( CV_SEQ_KIND_SUBDIV2D, sizeof(*subdiv),
														sizeof(CvSubdiv2DPoint),
														sizeof(CvQuadEdge2D),
														storage );
	cvInitSubdivDelaunay2D( subdiv, rect );

// 2.座標をドロネー空間に追加
	CvSubdiv2DPoint *p;
	for(int i = 0; i < points.size(); i++){
		p = cvSubdivDelaunay2DInsert( subdiv, toOcv(points[i]) );
		p->flags = i; //元座標とチェックするためにint追加
	}

// 3.線の座標を取得
	list lines;

	int i, org_id, dst_id;
	int total = subdiv->edges->total;
	int elem_size = subdiv->edges->elem_size;

	CvSubdiv2DPoint* org_pt;
	CvSubdiv2DPoint* dst_pt;
	Vec2f pos_org, pos_dst;
	CvPoint2D32f org, dst;

	CvSeqReader  reader;
	cvStartReadSeq( (CvSeq*)(subdiv->edges), &#038;reader, 0 );

	for( i = 0; i < total; i++ ){
		CvQuadEdge2D* edge = (CvQuadEdge2D*)(reader.ptr);

		if( CV_IS_SET_ELEM( edge )){
			org_pt = cvSubdiv2DEdgeOrg((CvSubdiv2DEdge)edge);
			dst_pt = cvSubdiv2DEdgeDst((CvSubdiv2DEdge)edge);
			if( org_pt &#038;& dst_pt ){
				org = org_pt->pt;
				dst = dst_pt->pt;
				pos_org = Vec2f(org.x, org.y); // 線の始点
				pos_dst = Vec2f(dst.x, dst.y); // 線の終点
				org_id = org_pt->flags;
				dst_id = dst_pt->flags;
				// 元座標と返された座標が一致するかチェック
				if(points[org_id] == pos_org &#038;& points[dst_id] == pos_dst){
					lines.push_back(LinePos(points[org_id], points[dst_id]));
				}
			}
		}

		CV_NEXT_SEQ_ELEM( elem_size, reader );
	}

// 4.描画
	for( list::iterator it = lines.begin(); it != lines.end(); ++it ){
		gl::drawLine(it->first, it->second);
	}


ちょっとした問題があって、というか私のやりたいことと
OpenCVの考えるドロネー分割にはちょっとした違いがありました。
私は座標同士だけを結ぶ線が欲しかったのですが、
OpenCVでは生成した空間を分割しようとします。
場合によってはそっちの方が正解かもしれませんが、
今回はその線を取り除くためにやっつけなひと手間を入れました。
そこを省略できるともっと高速になると思います。

ソースがこちらになります。
DelaunayLineApp.cpp

CinderとCinder-OpenCVが動く環境ならそのまま動くと思います。
あ、includeとlibへのパスは追加してください。
これが何気にめんどくさいんですが。
どうにかなりませんかね?このパスを通す作業って。