Триангуляция Делоне

[Smorodov 579]

Решил сделать обертку над OpenCV-шным триангулятором.

Лично для меня такая форма удобнее.

Хотя, конечно она не очень-то быстрая, надо посмотреть альтернативы.

#include "opencv2/highgui/highgui.hpp"

#include "opencv2/contrib/contrib.hpp"

#include "opencv2/video/tracking.hpp"

#include "opencv2/imgproc/imgproc.hpp"

#include "opencv2/features2d/features2d.hpp"

#include "opencv2/nonfree/nonfree.hpp"

#include "opencv2/calib3d/calib3d.hpp"

#include "opencv2/legacy/legacy.hpp"

#include <vector>

#include <string>

#include <fstream>

#include <iostream>

using namespace std;

using namespace cv;


//---------------------------------------------

// триангуляция. на входе вектор точек, на выходе вектор треугольников

//---------------------------------------------	

vector<vector<Point2f>> Triangulate(vector<Point2f>& pts)

{

	vector<vector<Point2f>> result;

	vector<Scalar>  val;

	cv::vector<int> hull;

	vector<Point2f> hull_pts;

	// Найдем выпуклую оболочку вокруг наших точек

	convexHull( pts, hull, false );


	// Перекинем точки оболочки в отдельный массив и найдем габарит этой оболочки

	// (нужно для инициализации триангулятора)

	Point2f top_left(FLT_MAX,FLT_MAX);			   // min_x min_y

	Point2f bottom_right(FLT_MIN,FLT_MIN);		   // max_x max_y


	for(int i=0;i<hull.size();i++)

	{

		Point2f p=pts[hull[i]];

		hull_pts.push_back(p);

		if(p.x<top_left.x){top_left.x=p.x;}

		if(p.y<top_left.y){top_left.y=p.y;}

		if(p.x>bottom_right.x){bottom_right.x=p.x;}

		if(p.y>bottom_right.y){bottom_right.y=p.y;}

	}

	// Немного раздвинем область

	top_left.x--;

	top_left.y--;

	bottom_right.x++;

	bottom_right.y++;

	// Габаритный прямоугольник наших точек, расширенный на 1 в каждую сторону

	Rect region(top_left, bottom_right);

	// Инициализируем триангулятор

	Subdiv2D subdiv(region);

	// Загружаем в него точки

        subdiv.insert(pts);


	vector<Vec6f> triangleList;

	subdiv.getTriangleList(triangleList);

	vector<Point2f> pt(3);

	for( size_t i = 0; i < triangleList.size(); i++ )

	{

		Vec6f t = triangleList[i];

                // 

		pt[0] = Point(t[0],t[1]);

		pt[1] = Point(t[2],t[3]);

		pt[2] = Point(t[4],t[5]);

		// нам нужна триангуляция выпуклого многогранника, а не всей области

		int p1=pointPolygonTest( hull_pts, pt[0], false );

		int p2=pointPolygonTest( hull_pts, pt[1], false );

		int p3=pointPolygonTest( hull_pts, pt[2], false );

		// если точки треугольника внутри выпуклой оболчки, то запоминаем треугольник 

		if(p1>-1 && p2 >-1 && p3>-1)

		{

			result.push_back(pt);

		}

	}


	return result;

}


//---------------------------------------------

// Испытаем функцию триангуляции

//---------------------------------------------	

int main( int, char** )

{	

	string win = "Delaunay Demo";

	namedWindow(win);

	Rect rect(0, 0, 600, 600);

	Mat img(600,600, CV_8UC3);

	img=0;

	// Вектор с точками

	vector<Point2f> pts;

	// Заполняем массив случайными точками

	for( int i = 0; i < 200; i++ )

	{

		Point2f fp( (float)(rand()%(rect.width-10)+5),(float)(rand()%(rect.height-10)+5));

		pts.push_back(fp);


	}

	// Массив треугольников, каждый содержит в себе по 3 точки

	vector<vector<Point2f>> triangles;

	// Проведем триангуляцию

	triangles=Triangulate(pts);

	// Нарисуем результат

	Scalar  delaunay_color(255,255,255);

	for( size_t i = 0; i < triangles.size(); i++ )

	{

		line(img, triangles[i][0], triangles[i][1], delaunay_color, 1, CV_AA, 0);

		line(img, triangles[i][1], triangles[i][2], delaunay_color, 1, CV_AA, 0);

		line(img, triangles[i][2], triangles[i][0], delaunay_color, 1, CV_AA, 0);

	}	

	imshow( win, img );

	waitKey(0);

	return 0;

}

[/code]

[Smorodov 579]

Хорошая презентация по теме:

http://graphics.stanford.edu/courses/cs368-06-spring/handouts/Delaunay_1.pdf

и статейка с исходниками

http://www.codeguru.com/cpp/cpp/algorithms/general/article.php/c8901/Delaunay-Triangles.htm

и вполне приличная библиотечка:

http://www.sintef.no/Projectweb/Geometry-Toolkits/TTL/

книжка (в которой ссылка на эту библиотечку):

"Triangulations and Applications (Mathematics and Visualization)" авторы: Øyvind Hjelle (Author), Morten Dæhlen.

Одна из самых быстрых реализаций: http://www.cs.cmu.edu/~quake/triangle.html

и

Реализация для CUDA: http://www.comp.nus.edu.sg/~tants/delaunay2DDownload.html

[Smorodov 579]

Прицепил библиотеку triangle, в примере функция получает вектор opencv-шных точек, а выдает вектор треугольников, каждый из треугольников состоит вектора индексов точек (а не из координат, за что не люблю opencv-шный триангулятор).

Все что надо для компиляции находится в архиве:

TriangulationExample(triangle_lib).rar