ドロネイ三角形の作成

Delaunay.cpp

#include "opencv\cv.h"
#include "opencv\highgui.h"

#if CV_MAJOR_VERSION > 1
#include <opencv2/legacy/legacy.hpp>
#endif

//============================================================================
bool IsEdgeIn(int ind1, int ind2,
	const std::vector<std::vector<int> > &edges)
{
	for (size_t i = 0; i < edges.size(); i++)
	{
		if ((edges[i][0] == ind1 && edges[i][1] == ind2) ||
			(edges[i][0] == ind2 && edges[i][1] == ind1))
			return true;
	}

	return false;
}

//============================================================================
bool IsTriangleNotIn(const std::vector<int>& one_tri,
	const std::vector<std::vector<int> > &tris)
{
	std::set<int> tTriangle;
	std::set<int> sTriangle;

	for (size_t i = 0; i < tris.size(); i++)
	{
		tTriangle.clear();
		sTriangle.clear();
		for (int j = 0; j < 3; j++)
		{
			tTriangle.insert(tris[i][j]);
			sTriangle.insert(one_tri[j]);
		}
		if (tTriangle == sTriangle)    return false;
	}

	return true;
}

//============================================================================
void Delaunay(
	const CvSubdiv2D* Subdiv,
	const CvMat* ConvexHull,
	int __n,
	std::vector<std::vector<int> > &__tri,
	std::vector<CvPoint2D32f>& __point)
{
	// firstly we build edges
	size_t i;
	CvSeqReader  reader;
	CvQuadEdge2D* edge;
	CvPoint2D32f org, dst;
	CvSubdiv2DPoint* org_pt, *dst_pt;
	std::vector<std::vector<int> > edges;
	std::vector<int> one_edge;     one_edge.resize(2);
	std::vector<int> one_tri;	one_tri.resize(3);
	int ind1, ind2;

	cvStartReadSeq((CvSeq*)(Subdiv->edges), &reader, 0);
	for (i = 0; i < (size_t)Subdiv->edges->total; i++)
	{
		edge = (CvQuadEdge2D*)(reader.ptr);
		if (CV_IS_SET_ELEM(edge)){
			org_pt = cvSubdiv2DEdgeOrg((CvSubdiv2DEdge)edge);
			dst_pt = cvSubdiv2DEdgeDst((CvSubdiv2DEdge)edge);

			if (org_pt && dst_pt){
				org = org_pt->pt;
				dst = dst_pt->pt;
				if (cvPointPolygonTest(ConvexHull, org, 0) >= 0 &&
					cvPointPolygonTest(ConvexHull, dst, 0) >= 0){
					for (int j = 0; j < __n; j++){
						if (fabs(org.x - __point[j].x)<1e-6 &&
							fabs(org.y - __point[j].y)<1e-6)
						{
							for (int k = 0; k < __n; k++)
							{
								if (fabs(dst.x - __point[k].x)<1e-6
									&&fabs(dst.y - __point[k].y)<1e-6)
								{
									one_edge[0] = j;
									one_edge[1] = k;
									edges.push_back(one_edge);
								}
							}
						}
					}
				}
			}
		}

		CV_NEXT_SEQ_ELEM(Subdiv->edges->elem_size, reader);
	}

	// secondly we start to build triangles
	for (i = 0; i < edges.size(); i++)
	{
		ind1 = edges[i][0];
		ind2 = edges[i][1];

		for (int j = 0; j < __n; j++)
		{
			// At most, there are only 2 triangles that can be added 
			if (IsEdgeIn(ind1, j, edges) && IsEdgeIn(ind2, j, edges))
			{
				one_tri[0] = ind1;
				one_tri[1] = ind2;
				one_tri[2] = j;
				if (IsTriangleNotIn(one_tri, __tri))
				{
					__tri.push_back(one_tri);
				}
			}
		}
	}

	//OK, up to now, we have already builded the triangles!
}


void Train(
	std::vector<CvPoint2D32f>& __point,
	std::vector<std::vector<int> >& tri)
{
	CvMat* Points = cvCreateMat(1, __point.size(), CV_32FC2);
	CvMemStorage* Storage = cvCreateMemStorage(0);

	int __n = Points->cols;

	for (int i = 0; i < __n; i++)
		CV_MAT_ELEM(*Points, CvPoint2D32f, 0, i) = __point[i];

	CvMat* ConvexHull = cvCreateMat(1, __n, CV_32FC2);
	cvConvexHull2(Points, ConvexHull, CV_CLOCKWISE, 0);

	CvRect rect = cvBoundingRect(ConvexHull, 0);
	CvSubdiv2D* Subdiv = cvCreateSubdivDelaunay2D(rect, Storage);
	for (int ii = 0; ii < __n; ii++)
		cvSubdivDelaunay2DInsert(Subdiv, __point[ii]);

	Delaunay(Subdiv, ConvexHull , __n , tri , __point);
}

int main()
{

	std::vector<CvPoint2D32f> point;

	CvPoint2D32f pv[] =
	{
		{ 1, 0 },
		{ -1, 0 },
		{ 0, 1 },
		{ 0, -1 },
	};
	for ( auto p : pv )
	{
		point.push_back(p);
	}

	std::vector<std::vector<int> > tri;

	Train( point , tri );


	
}