How to check if one contour is nested/embedded in opencv

Question

I have two contours and I want to check the relation between them (if one of them is nested). Normally, I would use the findContours function with CV_RETR_TREE retrieval mode. However, I obtained the contours from a different source (using MSER method). I actually not only have the contours, but also the region mask if that helps. For example, lets say I want to segment the letter 'O', then I would have the following masks or contours:

1)

0 0 0 0 0 0
0 1 1 1 1 0
0 1 0 0 1 0
0 1 0 0 1 0
0 1 1 1 1 0
0 0 0 0 0 0 

2)

0 0 0 0 0 0
0 0 0 0 0 0
0 0 1 1 0 0
0 0 1 1 0 0
0 0 0 0 0 0
0 0 0 0 0 0 

How can I easily check that the second one is inside the first contour? I thought about checking the relation between the bounding boxes, but this doesn't cover all possible cases.

Answer 1

Use cv::pointPolygonTest(InputArray contour, Point2f pt, bool measureDist) to know whether a point from a contour is inside the other.

You have to check for border cases (the first point you pick is common to both polygons, etc)

if(pointPolygonTest(contour, pointFromOtherContour, false) > 0)
{
    // it is inside
}

The function determines whether the point is inside a contour, outside, or lies on an edge (or coincides with a vertex). It returns positive (inside), negative (outside), or zero (on an edge) value, correspondingly.

When measureDist=false , the return value is +1, -1, and 0, respectively. Otherwise, the return value is a signed distance between the point and the nearest contour edge.

Answer 2

If you know that the contours are closed (in a 4-connected sense), then you can probably use the ray-to-infinity test, which is more commonly used to test whether points are inside closed polygons. (Also assuming the contours don't cross over, which presumably they can't.)

Take any point on the candidate contour, and proceed from there to 'infinity' in any direction (pick an axis aligned one, for ease of implementation): if you get all the way to the edge of your image and cross the outside contour an odd number of times then the contour you started on is inside that contour.

'crossing' the outer contour is actually slightly tricky, for example:

  . 1 1 1 1 1 1 1
  . 1 . . X X X 1
  . 1 . . X . X 1
<-.-1-1-.-X X X 1 : here a naiive implementation counts two crossings
  . . 1 1 1 1 1 1

So to test if a ray is 'crossing' a contour at a point you really need to consider the 3x3 neighbouring points. I think you'll end up with a set of cases that look something like this:

  . . .
<-1-1 1 // not crossing
  . . .

  1 . 1
<-1-1 1 // not crossing
  . . .

  . . 1
<-1-1 1 // crossing
  . . .

  1 . .
<-1-1 1 // crossing
  . . .

I'm not 100% sure that it's possible to build a consistent test for crossings a 4-connected contour based on 3x3 neighbourhoods, but it seems likely that it is.

This all relies on the outer contour being closed, of course.