Check if two contours intersect?

Question

I have 2 contours (cont1 and cont2) received from cv2.findContours(). How do I know if they intersect or not? I don't need coordinates, I only need a boolean True or False.

I have attempted different ways and already tried to do a check with

if ((cont1 & cont2).area() > 0):

... but got the error that the array has no method "Area()"

...
cont1array = cv2.findContours(binary1, cv2.RETR_LIST, cv2.CHAIN_APPROX_SIMPLE)[0]
cont2array = cv2.findContours(binary2, cv2.RETR_LIST, cv2.CHAIN_APPROX_SIMPLE)[0]
...

for cont1 in cont1array:
  for cont2 in cont2array:
    print("cont1")
    print(cont1)
    print(type(cont1))
    print("cont2")
    print(cont2)
    print(type(cont2))
>   if cont1 and cont2 intersect: #i dont know how check intersect
      print("yes they intersect")
    else:
      print("no they do not intersect")

# cont1
# [[172 302]
#  [261 301]
#  [262 390]
#  [173 391]]
# <class 'numpy.ndarray'>
# cont2
# [[  0   0]
#  [  0 699]
#  [499 699]
#  [499   0]]
# <class 'numpy.ndarray'>

Answer 1

Once you have the two contours from cv2.findContours(), you can use a bitwise AND operation to detect intersection. Specifically, we can use np.logical_and(). The idea is to create two separate images for each contour and then use the logical AND operation on them. Any points that have a positive value (1 or True) will be points of intersection. So since you're only looking to obtain a boolean value of whether there is intersection, we can check the intersected image to see if there is a single positive value. Essentially, if the entire array is False then there was no intersection between the contours. But if there is a single True, then the contours touched and thus intersect.

def contourIntersect(original_image, contour1, contour2):
    # Two separate contours trying to check intersection on
    contours = [contour1, contour2]

    # Create image filled with zeros the same size of original image
    blank = np.zeros(original_image.shape[0:2])

    # Copy each contour into its own image and fill it with '1'
    image1 = cv2.drawContours(blank.copy(), contours, 0, 1)
    image2 = cv2.drawContours(blank.copy(), contours, 1, 1)

    # Use the logical AND operation on the two images
    # Since the two images had bitwise and applied to it,
    # there should be a '1' or 'True' where there was intersection
    # and a '0' or 'False' where it didnt intersect
    intersection = np.logical_and(image1, image2)

    # Check if there was a '1' in the intersection
    return intersection.any()

Example

Original Image

Detected Contour

We now pass the two detected contours to the function and obtain this intersection array:

[[False False False ... False False False]
 [False False False ... False False False]
 [False False False ... False False False]
 ...
 [False False False ... False False False]
 [False False False ... False False False]
 [False False False ... False False False]]

We check the intersection array to see if True exists. We will obtain a True or 1 where the contours intersect and False or 0 where they do not.

return intersection.any()

Thus we obtain

False

Full code

import cv2
import numpy as np

def contourIntersect(original_image, contour1, contour2):
    # Two separate contours trying to check intersection on
    contours = [contour1, contour2]

    # Create image filled with zeros the same size of original image
    blank = np.zeros(original_image.shape[0:2])

    # Copy each contour into its own image and fill it with '1'
    image1 = cv2.drawContours(blank.copy(), contours, 0, 1)
    image2 = cv2.drawContours(blank.copy(), contours, 1, 1)

    # Use the logical AND operation on the two images
    # Since the two images had bitwise AND applied to it,
    # there should be a '1' or 'True' where there was intersection
    # and a '0' or 'False' where it didnt intersect
    intersection = np.logical_and(image1, image2)

    # Check if there was a '1' in the intersection array
    return intersection.any()

original_image = cv2.imread("base.png")
image = original_image.copy()

cv2.imshow("original", image)
gray = cv2.cvtColor(image, cv2.COLOR_BGR2GRAY)
cv2.imshow("gray", gray)
blurred = cv2.GaussianBlur(gray, (5,5), 0)
cv2.imshow("blur", blurred)
threshold = cv2.threshold(blurred, 60, 255, cv2.THRESH_BINARY)[1]
cv2.imshow("thresh", threshold)

contours = cv2.findContours(threshold.copy(), cv2.RETR_EXTERNAL, cv2.CHAIN_APPROX_SIMPLE)
# Depending on OpenCV version, number of arguments return by cv.findContours 
# is either 2 or 3
contours = contours[1] if len(contours) == 3 else contours[0]

contour_list = []
for c in contours:
    contour_list.append(c)
    cv2.drawContours(image, [c], 0, (0,255,0), 2)

print(contourIntersect(original_image, contour_list[0], contour_list[1]))
cv2.imshow("contour", image)
cv2.waitKey(0)

Answer 2

The answer by nathancy works, but suffers on the performance side where as in the example creates 3 copies of the image to draw the contours thus, is sluggish when it comes to execution time.

My alternative answer is as below;

def contour_intersect(cnt_ref,cnt_query, edges_only = True):
    
    intersecting_pts = []
    
    ## Loop through all points in the contour
    for pt in cnt_query:
        x,y = pt[0]

        ## find point that intersect the ref contour
        ## edges_only flag check if the intersection to detect is only at the edges of the contour
        
        if edges_only and (cv2.pointPolygonTest(cnt_ref,(x,y),True) == 0):
            intersecting_pts.append(pt[0])
        elif not(edges_only) and (cv2.pointPolygonTest(cnt_ref,(x,y),True) >= 0):
            intersecting_pts.append(pt[0])
            
    if len(intersecting_pts) > 0:
        return True
    else:
        return False

EDIT!!

After testing this code, realized that this check fails when there are no two similar points of a contour. Thus, I've rewritten the algorithm which checks of two contour lines intersect.

def ccw(A,B,C):
    return (C[1]-A[1]) * (B[0]-A[0]) > (B[1]-A[1]) * (C[0]-A[0])

def contour_intersect(cnt_ref,cnt_query):

    ## Contour is a list of points
    ## Connect each point to the following point to get a line
    ## If any of the lines intersect, then break

    for ref_idx in range(len(cnt_ref)-1):
    ## Create reference line_ref with point AB
        A = cnt_ref[ref_idx][0]
        B = cnt_ref[ref_idx+1][0] 
    
        for query_idx in range(len(cnt_query)-1):
            ## Create query line_query with point CD
            C = cnt_query[query_idx][0]
            D = cnt_query[query_idx+1][0]
        
            ## Check if line intersect
            if ccw(A,C,D) != ccw(B,C,D) and ccw(A,B,C) != ccw(A,B,D):
                ## If true, break loop earlier
                return True

    return False

Answer 3

To handle the case where one contour contains another, we can replace

image1 = cv2.drawContours(blank.copy(), contours, 0, 1)
image2 = cv2.drawContours(blank.copy(), contours, 1, 1)

of Nathancy's answer with

image1 = cv2.fillPoly(blank.copy(), [contour1], 1)
image2 = cv2.fillPoly(blank.copy(), [contour2], 1)

Answer 4

@Ivans and @nathancys answers are the best ones I saw here. However, drawing lines is still compute intensive, especially if there are many points in your contours, while computing bitwise ands directly can harm performance, especially if your canvas is large. A simple way to improve performance is to first check for bbox intersections; if you see that bboxes dont intersect, you know the contours dont. If your bboxes do intersect, just draw the smallest filled (or outline) ROI for both contours and compute a simple bitwise and. I have found this to provide significant speedups compared to the other techniques listed here, and prevents issues with large, complex contours on a large canvas. I use torch to compute bbox ious for simplicity/legibility.

import cv2
import numpy as np
import torchvision.ops.boxes as bops

def contour_intersect(cnt_ref, cnt_query):
    ## Contours are both an np array of points
    ## Check for bbox intersection, then check pixel intersection if bboxes intersect

    # first check if it is possible that any of the contours intersect
    x1, y1, w1, h1 = cv2.boundingRect(cnt_ref)
    x2, y2, w2, h2 = cv2.boundingRect(cnt_query)
    # get contour areas
    area_ref = cv2.contourArea(cnt_ref)
    area_query = cv2.contourArea(cnt_query)
    # get coordinates as tensors
    box1 = torch.tensor([[x1, y1, x1 + w1, y1 + h1]], dtype=torch.float)
    box2 = torch.tensor([[x2, y2, x2 + w2, y2 + h2]], dtype=torch.float)
    # get bbox iou
    iou = bops.box_iou(box1, box2)

    if iou == 0:
        # bboxes dont intersect, so contours dont either
        return False
    else:
        # bboxes intersect, now check pixels
        # get the height, width, x, and y of the smaller contour
        if area_ref >= area_query:
            h = h2
            w = w2
            x = x2
            y = y2
        else:
            h = h1
            w = w1
            x = x1
            y = y1

        # get a canvas to draw the small contour and subspace of the large contour
        contour_canvas_ref = np.zeros((h, w), dtype='uint8')
        contour_canvas_query = np.zeros((h, w), dtype='uint8')
        # draw the pixels areas, filled (can also be outline)
        cv2.drawContours(contour_canvas_ref, [cnt_ref], -1, 255, thickness=cv2.FILLED,
                         offset=(-x, -y))
        cv2.drawContours(contour_canvas_query, [cnt_query], -1, 255, thickness=cv2.FILLED,
                         offset=(-x, -y))

        # check for any pixel overlap
        return np.any(np.bitwise_and(contour_canvas_ref, contour_canvas_query))