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.

Answer 2

You will have to use:

    CvSeq* cvConvexityDefects(
const CvArr* contour,
const CvArr* convexhull,
CvMemStorage* storage = NULL
);

This will return a sequence(CvSeq) of CvConvexityDefect and not CvPoint or anything else like the CvSeq that you are probably used to.

You can go trough the defects in a loop, like this:

CvSeq* defects =  cvConvexityDefects(.....);
for (i = 0; i < defects->total; i++)
{
CvConvexityDefect* def = (CvConvexityDefect*)cvGetSeqElem(defects, i);
//do something with them
}

A defect has the following structure:

    typedef struct CvConvexityDefect {
// point of the contour where the defect begins
CvPoint* start;
// point of the contour where the defect ends
CvPoint* end;
// point within the defect farthest from the convex hull
CvPoint* depth_point;
// distance between the farthest point and the convex hull
float depth;
} CvConvexityDefect;

So after getting each defect you can build a CvSeq of points from them and use cvPointPolygonTest on the centroids of the triangles to see if they are inside of them. If they are inside the defects, then it means that they are outside the main contour.

Hope this is what you need and that it helps.