C++-ObjC OpenCV Constrained Delaunay

Question

I succesfully implemented a Delaunay triangulation of a contour in OpenCV 2.3.1.

With cvPointPolygonTest I can get all the triangles in the convex hull, then I tried to perform another cvPointPolygonTest on triangles centroid to know if they are in the main contour or not, so I can have the constrained triangulation of the contour.

But, it doesn't work well, as some triangles are (eg. with a walking man who has his two legs distant) 'over' a hole.

Does anyone know a way to perform a constrained triangulation. I thought about convexityDefects, but can't manage to understand how to begin with this.

Thanks in advance !

Ben

---

In fact, it is not a Convex Hull defects problem, but a triangulation one. This image will show you the trouble :

Particularly in the bottom of the triangulated hull, you can see that the triangulation is in AND out of the contour, because OpenCV is triangulating the convex hull. I would like to find a way to triangulate the contour itself.

I found some ideas about adding Steiner Points in the contour itself, but can't find where to begin with OpenCV.

My idea was to :

• test if the triangle is in AND out of the contour ;
• if true : get the intersection point ;
• and add it to the cvSubdiv2D.

Am I right with this ?

Thanks for your patience and your answers !

Answer 1

Finally I implemented the poly2tri library in my program.

Here is the result (OpenCV to get the contours, then poly2tri to perform triangulation) :

// -------------------- poly2tri --------------------


NSMutableArray* temp = [[NSMutableArray alloc] init];

vector<p2t::Triangle*> triangles;
vector< vector<p2t::Point*> > polylines;
vector<p2t::Point*> polyline;

for(int i = 0; i < contour32->total; i++ ) {
    CvPoint2D32f* pt32 = CV_GET_SEQ_ELEM(CvPoint2D32f, contour32, i);
    polyline.push_back(new p2t::Point((double)pt32->x, (double)pt32->y));
}

polylines.push_back(polyline);


p2t::CDT* cdt = new p2t::CDT(polyline);



// TODO -> holes with CV_RETR_TREE

// Triangulation !
cdt->Triangulate();

// On exporte nos triangles
triangles = cdt->GetTriangles();

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

    p2t::Triangle& t = *triangles[i];
    p2t::Point& a = *t.GetPoint(0);
    p2t::Point& b = *t.GetPoint(1);
    p2t::Point& c = *t.GetPoint(2);

    double x1 = (width / rWidth * (double)a.x) - (width / 2.f);
    double y1 = (height / rHeight * (double)a.y) - (height / 2.f);                   
    double x2 = (width / rWidth * (double)b.x) - (width / 2.f);
    double y2 = (height / rHeight * (double)b.y) - (height / 2.f);
    double x3 = (width / rWidth * (double)c.x) - (width / 2.f);
    double y3 = (height / rHeight * (double)c.y) - (height / 2.f);

    [temp addObject:[[NSArray arrayWithObjects:
                      [NSArray arrayWithObjects:
                       [NSNumber numberWithDouble:x1],
                       [NSNumber numberWithDouble:y1],
                       [NSNumber numberWithDouble:0.],
                       nil], 
                      [NSArray arrayWithObjects:
                       [NSNumber numberWithDouble:x2],
                       [NSNumber numberWithDouble:y2],
                       [NSNumber numberWithDouble:0.],
                       nil], 
                      [NSArray arrayWithObjects:
                       [NSNumber numberWithDouble:x3],
                       [NSNumber numberWithDouble:y3],
                       [NSNumber numberWithDouble:0.],
                       nil], 
                      nil] autorelease]];

}

[outDelaunay addObject:temp];                       

where contour32 is your OpenCV contour found with cvFindContours, then converted to float32.