15

I have 2 contours A and B and I want to check if they intersect. Both A and B are vectors of type cv::Point and are of different sizes

To check for intersection, I was attempting to do a bitwise_and. This is throwing an exception because the inputs are of different size. How do I fix this ?

Edit:

The attached image should give a better idea about the issue. The car is tracked by a blue contour and the obstacle by a pink contour. I need to check for the intersection. enter image description here

Madman
  • 309
  • 1
  • 5
  • 10

4 Answers4

15

A simple but perhaps not the most efficient (??) way would be to use drawContours to create two images: one with the contour of the car and one with the contour of the obstacle.

Then and them together, and any point that is still positive will be points of intersection.

Some pseudocode (I use the Python interface so wouldn't get the C++ syntax right, but it should be simple enough for you to convert):

import numpy as np # just for matrix manipulation, C/C++ use cv::Mat
# find contours.
contours,h = findContours( img, mode=RETR_LIST, method=CHAIN_APPROX_SIMPLE )
# Suppose this has the contours of just the car and the obstacle.

# create an image filled with zeros, single-channel, same size as img.
blank = np.zeros( img.shape[0:2] )

# copy each of the contours (assuming there's just two) to its own image. 
# Just fill with a '1'.
img1 = drawContours( blank.copy(), contours, 0, 1 )
img2 = drawContours( blank.copy(), contours, 1, 1 )

# now AND the two together
intersection = np.logical_and( img1, img2 )

# OR we could just add img1 to img2 and pick all points that sum to 2 (1+1=2):
intersection2 = (img1+img2)==2

If I look at intersection I will get an image that is 1 where the contours intersect and 0 everywhere else.

Alternatively you could fill in the entire contour (not just the contour but fill in the inside too) with drawContours( blank.copy(), contours, 0, 1, thickness=-1 ) and then the intersection image will contain the area of intersection between the contours.

Kyle Hardinge
  • 85
  • 10
mathematical.coffee
  • 55,977
  • 11
  • 154
  • 194
  • How can we view the intersection using imshow(), when using imshow to display the intersection, obtaining a black image. But when printed the intersection, as described observed ones and zeros. Is there any work around to visualize the intersection – Sai krishna May 09 '19 at 10:53
  • 1
    @Saikrishna use the grayscale values. If it is for visualization, draw contours at say 20... which is visible but not saturated. The intersection will be brighter (at 40 or more) – Shravya Boggarapu Aug 02 '19 at 11:48
  • I think it's necessary to use 4-connected line instead of 8-connected when only the contour boundary is drawn, because otherwise some intersection point of 2 diagonals with some particular intersecting angle may be missed. – user202729 Aug 08 '19 at 16:40
  • Also the first solution will not detect the case when one contour contains another. – user202729 Aug 15 '19 at 07:46
  • Doesn't `drawContours` only fill the outline? So you will get intersections between outlines? I had to add `cv2.FILLED` as argument: `img2 = cv2.drawContours(blank.copy(), contours, 0, 1, cv2.FILLED)`. – Jeppe Mar 04 '20 at 09:52
0

If you first sort your vectors, using pretty much any consistent sorting criterion that you can come up with, then you can use std::set_intersection directly on the vectors. This may be faster than the accepted answer in case the contours are short compared to the image size.

Reunanen
  • 7,921
  • 2
  • 35
  • 57
  • 1
    This is wrong for "compressed" contour, two contours may intersect even when they have no common vertices. – user202729 Aug 08 '19 at 16:41
  • @user202729 True. And the same holds for non-compressed 8-connected contours. But not for 4-connected. – Reunanen Aug 11 '19 at 18:11
0

I have found the Clipper library quite useful for these kinds of purposes. (It's straightforward to transform vectors of cv::Point to Clipper Path objects.)

Reunanen
  • 7,921
  • 2
  • 35
  • 57
0

C++ tested code, based on mathematical.coffee's answer:

    vector< Point> merge_contours(vector <Point>& contour1, vector <Point>& contour2, int type){
    // get work area        
    Rect work_area = boundingRect( contour1 ) | boundingRect( contour2 );        
    
    Mat merged = Mat::zeros(work_area.size(), CV_8UC1);        
    Mat contour1_im = Mat::zeros(work_area.size(), CV_8UC1);
    Mat contour2_im = Mat::zeros(work_area.size(), CV_8UC1);
    
    //draw
    vector<vector<Point> > shifted1;
    shifted1.push_back(shift_contour(contour1, work_area.tl()));
    drawContours( contour1_im, shifted1, -1, 255, -1);
    vector<vector<Point> > shifted2;
    shifted2.push_back(shift_contour(contour2, work_area.tl()));
    drawContours( contour2_im, shifted2, -1, 255, -1);
    
    //imshow("contour1 debug", contour1_im);
    //imshow("contour2 debug", contour2_im);        
    
    if( type == 0 )
        // intersect
        bitwise_or( contour1_im, contour2_im, merged);
    else
        // unite
        bitwise_and( contour1_im, contour2_im, merged);        
    //imshow("merge contour debug", merged);
    
    // find
    vector<vector<Point> > contours;
    vector<Vec4i> hierarchy;
    findContours(merged,contours,hierarchy, RETR_TREE, CHAIN_APPROX_SIMPLE, Point(0, 0));
    
    if(contours.size() > 1){
        printf("Warn: merge_contours has output of more than one contours.");
    }
    
    return shift_contour(contours[0], work_area.tl() * -1);        
}
Strohkopf
  • 1
  • 1