前回に引き続きドロネー図行ってみましょう。こんにちは。ムーチョです。
今回は面を塗りつぶします。
前回同様にOpenCVのソースに含まれるサンプルをもとに作成しました。
おおまかな流れはこんな感じです。

1.空のドロネー空間を作成
2.座標をドロネー空間に追加
3.面の座標３点を取得
4.描画

1.2.は前回と全く一緒なので飛ばして3.へ。
さすがはOpenCV！あっさり３点が取れる関数が平然と用意されてるッ！
そこにシビれる！あこがれるゥ！
って展開を思い切り期待していましたが、そんなことはありませんでした・・・。

サンプルをみる限り、線の時とほぼ同じで、
まずは１辺を取り、右隣の接する辺を取得してそれで３点にたどり着くという手法。
そこだけ抜粋するとこんな感じです。

[code lang="cpp"]
	CvSeqReader  reader;
	cvStartReadSeq( (CvSeq*)(subdiv->edges), &reader, 0 );

// 線の時と同じ形でなぜか総当たり
	for( i = 0; i < total; i++ ){
		CvQuadEdge2D* edge = (CvQuadEdge2D*)(reader.ptr);
		if( CV_IS_SET_ELEM( edge )){

// 辺から２点を取得
			pt0 = cvSubdiv2DEdgeOrg((CvSubdiv2DEdge)edge);
			pt1 = cvSubdiv2DEdgeDst((CvSubdiv2DEdge)edge);

// 右隣の辺を取得
			t = cvSubdiv2DGetEdge((CvSubdiv2DEdge)edge, CV_NEXT_AROUND_LEFT );
			pt2 = cvSubdiv2DEdgeDst(t);

		}
		CV_NEXT_SEQ_ELEM( elem_size, reader );
	}

[/code]

その３点からTriMeshを作成して塗りつぶし。
とりあえずアルファ10%で塗ってみたところ、あれ？

これはこれでありか？いやいや。

という訳で塗れてない面やら何度も塗ってる面やらバラバラ。
サンプルをよくよく見直してみると、1辺から二つの面を取得してました。
という訳で以下を追加してたところ・・・

[code lang="cpp"]
// 基準にしてる辺を反転
			e = cvSubdiv2DRotateEdge( (CvSubdiv2DEdge)edge, 2 );
// 辺から２点を取得
			pt0 = cvSubdiv2DEdgeOrg(e);
			pt1 = cvSubdiv2DEdgeDst(e);
// 反転させた辺の右隣の辺を取得
			t = cvSubdiv2DGetEdge(e, CV_NEXT_AROUND_LEFT );
			pt2 = cvSubdiv2DEdgeDst(t);

[/code]

均質にはなったが、なんか濃いです・・・。

当然ながら辺総当たりなので、面１つにたいして辺が３つあるため
３倍塗ってるご様子。
どうもサンプルソースもそれっぽい。
そこでやや強引ですが、重複を削除することを決意。
C++初心者のムーチョはここでハマりまくり。

単純にソート＆ユニーク化は効果なし・・・。
↓
ソート時に比較しやすいように座標で持つのをあきらめ、
前回追加してたflagを３点のIDとして持った構造体に変更。
アンド、ID(int)３点の大小でソートできるように比較関数を用意。
↓
比較関数がコンパイル時にエラーはきまくり。クラスにすることで回避。
↓
と思ったのもつかの間、それ用に定義した構造体を渡すと、比較関数がエラー。
構造体をあきらめ、配列にするもエラー。C++の配列ってホント使いにくい。
↓
vectorにしたら無事動くがややもっさり。
やっぱり構造体的なものの方がいいのか？と
省力化を兼ねてCinderが元々持ってるVec3iに３点のIDを格納しちゃえと変更。
↓
再びエラーで動かなくなる。Vec3iをVec3fに変更。
もうかなりやけっぱち。後々わかりにくくなりそうだけど、エコですよ。エコ。
↓
これでどうにか動くように。vectorを使ってた時より少し速くもなりました。
基本がないってつらいですね。

[code lang="cpp"]

// まずは並べ替え
	polys.sort(comparePolyKey());

// 重複を削除
	list<Vec3f>::iterator last_it = unique(polys.begin(), polys.end());
	polys.erase(last_it, polys.end());

// 並べ替え用のクラス
class comparePolyKey {
public:
	bool operator()(const Vec3f&amp; left, const Vec3f&amp; right)
	{
		return (left.x < right.x)
		 || (left.x == right.x &amp;&amp; left.y < right.y)
		 || (left.x == right.x &amp;&amp; left.y == right.y &amp;&amp; left.z < right.z);
	}
};

[/code]

そんなこんなでようやくキレイに塗れました。

ぱっと見が退屈なのが非常に残念。

おまけにソートとユニーク化をかける前より高速化したので、
面倒でしたがこちらの方がいいですね。
そもそも3倍まわさないようにしたいのですが、
どう書くのがいいのか思いつかず・・・。
かなりいっぱいいっぱいなドロネー図でした。

さらに画像を解析して分割・塗りつぶしをしようと思っていましたが、
リアルタイムでは処理落ちしそうです。