Smorodov 579 Жалоба Опубликовано August 18, 2012 Решил сделать обертку над 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 Жалоба Опубликовано August 19, 2012 Хорошая презентация по теме: 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 Жалоба Опубликовано April 20, 2013 Прицепил библиотеку triangle, в примере функция получает вектор opencv-шных точек, а выдает вектор треугольников, каждый из треугольников состоит вектора индексов точек (а не из координат, за что не люблю opencv-шный триангулятор). Все что надо для компиляции находится в архиве: TriangulationExample(triangle_lib).rar Поделиться сообщением Ссылка на сообщение Поделиться на других сайтах