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'>

you could use bounding rects as a first coarse and cheap step and refine afterwards. I would draw each contour filled on an individual mask image and compute the mask intersection, but that might be too slow. — Micka, Apr 11 '19 at 21:39
In the real world, two different contours can never intersect (see, e.g. https://socratic.org/questions/why-do-contour-lines-never-cross-on-a-topographic-map). In an approximation in a computer, some contours could intersect but the usefulness of that would depend on the circumstances. Could you say a bit more about the underlying problem that you are trying to solve, which might let people provide more helpful answers? — Simon, Apr 11 '19 at 21:45
There is a picture of a child's game (like a lotto grid). During the game they put chopsticks on the picture (like ice cream sticks). I need to determine which cells are under the sticks. cont1 is my contours of all the cells of this game grid (before they were put on sticks). cont2 is my contours from all the sticks in the picture. In the code I do a check: if the contour of the cell crosses the contour of the sticks, then the cell is closed by the stick. Therefore, I need to know how to establish the fact of intersection of two contours. — , Apr 11 '19 at 22:04
Since each contour, in this context, is just a vector of points, can you just find the intersection of the two vectors of points after turning them into sets (e.g. as described in https://stackoverflow.com/questions/3697432/how-to-find-list-intersection/33067553)? — Simon, Apr 11 '19 at 22:13

Ivan · Answer 1 · 2021-04-05T06:39:22.207

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

I would recommend this answer over the selected answer just becasue of the huge performance gain. — Neeraj Gulia, Aug 15 '20 at 13:56
This only works if a `cnt_query` corner is inside `cnt_ref` area. Must use `cv2.CHAIN_APPROX_NONE` parameter in cnt_query for this to work. — Justas, Oct 29 '20 at 08:28
@justas Would suggest using cv2.CHAIN_APPROX_SIMPLE to have less memory footprint of working with contours as highlighted in this post https://docs.opencv.org/3.4/d4/d73/tutorial_py_contours_begin.html — Ivan, Apr 05 '21 at 08:51
nice but i wish your code was simple to use like @nathancy , so can u tell what is this `cnt_query` in it ? in accepted answer we can see 3 input image cnt1 and cnt2 which is understandable — user889030, Mar 23 '22 at 13:07

score 10 · Accepted Answer · edited Feb 05 '23 at 18:59

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]], 0, 1)
    image2 = cv2.drawContours(blank.copy(), [contours[1]], 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)

you could just `return True in intersection` or even more simply `return intersection.any()` — alkasm, Apr 12 '19 at 04:31
Thanks, it seems to work, but if one circuit is located inside the other, then I get a false — , Apr 12 '19 at 09:15

Pietro Cicalese · Answer 3 · 2022-04-22T19:37:54.180

@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))

This works perfectly for me with the very low computational time! Thanks — Samuel Thudi, Sep 23 '22 at 06:32

score 0 · Answer 4 · answered Mar 22 '22 at 06:18

0

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)

answered Mar 22 '22 at 06:18

Haoyu Xu

9
1

This is poorly explained. – TheCodeNovice Dec 13 '22 at 23:55

Check if two contours intersect?

4 Answers4

Linked

Related