Find if two areas intersect given the polygons` edges

Question

This problem has been puzzling me for some time now. I did find a solution where I can find every point in each polygon, then check for intersections. However, this is computationally expensive, and not practical at all.

There are four lines in the following image; two red and two blue lines. I would like to check if the area between the two red lines intersects with the area between the two blue lines.

The following variables are known:

1. The point where each line starts
2. Angle of each line
3. Where the line ends (always at image's edge)

I was thinking about using the slope's formula to check where does the origin point of the red lines falls in relation to each blue line. But I'm not sure if this was the best approach.

Thanks in advance.

Answer 1

There are principally two approaches to this problem:

1. Linear programming

Express the problem as a system of linear inequalities and solve it as a linear programming problem as described here: Solve a system of linear equations and linear inequalities. In your case the inequalities will be of the form (x - ox[i])*sin(a[i]) - (y - oy[i])*cos(a[i]) > 0 or (x - ox[i])*sin(a[i]) - (y - oy[i])*cos(a[i]) < 0 depending on how you define the angle a[i] of the i-th line and at which side of the line lays the polygon. (ox[i], oy[i]) are coordinates of the i-th vertex. If the inequalities are strict or not, that depends on how you want to treat boundary cases where the polygons touch with a vertex or an edge. This is a good easily generalizable approach, but it may be slow.

2. Intersection testing

In the general case (no vertices and edges coincide) there are 4 possibilities: (1) some edges intersect; (2) polygon 1 is inside polygon 2; (3) polygon 2 is inside polygon 1; (4) polygons do not intersect. You need to test for the first 3 cases.

For case 1 you need to implement a segment intersection test as described here How can I check if two segments intersect? and try to intersect each edge of polygon 1 with each edge of polygon 2, which is not a problem in your case because there will be at most 2*2 = 4 tests. If you detect at least one intersection, you are done.

For cases 2 and 3 you need to test if the vertex of polygon 1 is inside polygon 2 and vice versa. This may be done using the same tests IsOnLeft and IsOnRight described in How can I check if two segments intersect?: if a point is at the left of the right line and at the right of the left one, it is inside.

In any case you should pay special attention to degenerate and boundary cases: what if edges of a polygon coincide, or a vertex of one polygon lays on an edge of the other, or edges of different polygons coincide. You may detect and treat such cases differently depending on your particular purposes.

Answer 2

The concept

One simple way of detecting if intersections of shapes exist in an image, given that every shape must be a different color, you can define a mask for every color, and with the image's colors all masked out except for the shape with its, detect the amount of contours found for the outline of the shape.

If more than one contour (of an area greater than a specified amount to filter out noise) is found, that means that another shape's outline intersected the shape's outline, leaving gaps in its outline and thus resulting in multiple contours.

The code

import cv2
import numpy as np

def intersected(img, masks):
    img_hsv = cv2.cvtColor(img, cv2.COLOR_BGR2HSV)
    for lower, upper in masks:
        mask = cv2.inRange(img_hsv, np.array(lower), np.array(upper))
        blur = cv2.GaussianBlur(mask, (5, 5), 0)
        canny = cv2.Canny(blur, 0, 0)
        contours, _ = cv2.findContours(canny, cv2.RETR_EXTERNAL, cv2.CHAIN_APPROX_NONE)
        count = 0
        for cnt in contours:
            if cv2.contourArea(cnt) > 50:
                cv2.drawContours(img, [cnt], -1, (0, 255, 0), 1)
                cv2.imshow("Test", img)
                count += 1
                if count == 2:
                    return True

img = cv2.imread("shapes.png")

blue_mask = [1, 0, 0], [178, 255, 255]
red_mask = [0, 1, 0], [179, 254, 255]

if intersected(img, (blue_mask, red_mask)):
    print("Intersection detected!")
else:
    print("No intersection detected.")

The output

Intersection detected!

---

The explanation

1. Import the necessary libraries:

import cv2
import numpy as np

2. Define a function that will take in 2 arguments; the image of which we will be detecting if there are shape intersections, and an array of the HSV masks of the color of each shape:

def intersected(img, masks):

3. Get the image in its HSV form, and loop through each of the HSV masks:

    img_hsv = cv2.cvtColor(img, cv2.COLOR_BGR2HSV)
    for lower, upper in masks:
        mask = cv2.inRange(img_hsv, np.array(lower), np.array(upper))

4. Blur the mask to remove noise, detect it edges using the canny edge detector, and find the contours of the canny edges:

        blur = cv2.GaussianBlur(mask, (5, 5), 0)
        canny = cv2.Canny(blur, 0, 0)
        contours, _ = cv2.findContours(canny, cv2.RETR_EXTERNAL, cv2.CHAIN_APPROX_NONE)

5. Define a variable, count, to store the amount of contours with area greater than, say 50, found so far. If the count variable reaches 2, we'll know that at least one intersection have been found, and that is enough to confirm that there are intersections in the image:

        count = 0
        for cnt in contours:
            if cv2.contourArea(cnt) > 50:
                cv2.drawContours(img, [cnt], -1, (0, 255, 0), 1)
                cv2.imshow("Test", img)
                count += 1
                if count == 2:
                    return True

6. Finally, we can utilize the function on the image:

img = cv2.imread("shapes.png")

blue_mask = [1, 0, 0], [178, 255, 255]
red_mask = [0, 1, 0], [179, 254, 255]

if intersected(img, (blue_mask, red_mask)):
    print("Intersection detected!")
else:
    print("No intersection detected.")

Answer 3

This is an example using a small one channel image 10x10 pixel.

basic_img = np.zeros([10, 10], dtype=np.uint8)

Once you have the coordinates of the points, lets say:

pts_red = np.array([(9, 0), (9, 6), (4, 2), (4, 0)], dtype=np.int32)
pts_blue = np.array([(9, 0), (9, 1), (0, 8), (6, 0)], dtype=np.int32)

You can use fillPoly to draw the poligons contained between the lines:

red_poly = basic_img.copy()
cv2.fillPoly(red_poly, [pts_red], 1)
# plt.imshow(red_poly)

and

blue_poly = basic_img.copy()
cv2.fillPoly(blue_poly, [pts_blue], 1)
# plt.imshow(blue_poly)

Then use Numpy logical operations to get the intersection:

intersection = np.logical_and(red_poly, blue_poly)
# plt.imshow(intersection)

Finally, check for any True value to get the bool result:

np.any(intersection) #=> True

---

Here the plotted images of this example.

The blue poly

The red poly

The intersection

Answer 4

Here's a Pillow only version of my answer using OpenCV and NumPy, incorporating the same idea. Nevertheless, this version is limited to the two colors. Adding more colors (or polygons) would require additional work (basically, some looping).

from PIL import Image, ImageChops, ImageDraw

# Set up image
w, h = (400, 300)
img = Image.new('RGB', (w, h), (255, 255, 255))
draw_img = ImageDraw.Draw(img)

# Set up colors
colors = {
    'Red': (0, 0, 255),
    'Blue': (255, 0, 0)
}

# Set up lines per color, first element is the point in common
lines = {
    'Red': [((200, 150), (380, 0)), ((200, 150), (200, 0))],
    'Blue': [((100, 100), (399, 100)), ((100, 100), (300, 0))]
}

# Set up masks per color
masks = {
    'Red': Image.new('L', (w, h), 0),
    'Blue': Image.new('L', (w, h), 0)
}

# For each color...
for c in ['Red', 'Blue']:
    draw_mask = ImageDraw.Draw(masks[c])
    for line in lines[c]:

        # ... draw colored line in image, ...
        draw_img.line(line, colors[c], 2)

        # ... draw white line in mask, ...
        draw_mask.line(line, 255, 1)

    # ... find mid point between both end points, and ...
    mid = (int(sum([line[1][0] for line in lines[c]]) / len(lines[c])),
           int(sum([line[1][1] for line in lines[c]]) / len(lines[c])))

    # ... flood fill mask with the mid point as seed point
    ImageDraw.floodfill(masks[c], mid, 255)

# Logical and all masks, and check for at least one pixel overlap
inter = ImageChops.multiply(masks['Red'], masks['Blue'])
print('Is intersection: ', inter.getextrema()[1] > 0)

# Outputs
img.show()
masks['Red'].show()
masks['Blue'].show()
inter.show()

Outputs are identical to the OpenCV version.

----------------------------------------
System information
----------------------------------------
Platform:      Windows-10-10.0.16299-SP0
Python:        3.9.1
PyCharm:       2021.1
Pillow:        8.2.0
----------------------------------------

Answer 5

If you have two lines for each color with a common start point, and different end points at the image borders, you can simply create a mask, draw these lines, calculate the mid point between both end points, and use this mid point as seed point for some flood filling. Since you have a closed polygon, that mid point is guaranteed to be located inside the polygon. From that two masks, determine the intersection (logical and), and check for at least one pixel overlap.

Here's some code using OpenCV and NumPy:

import cv2
import numpy as np

# Set up image
w, h = (400, 300)
img = np.ones((h, w, 3), np.uint8) * 255

# Set up colors
colors = {
    'Red': (0, 0, 255),
    'Blue': (255, 0, 0)
}

# Set up lines per color, first element is the point in common
lines = {
    'Red': [((200, 150), (380, 0)), ((200, 150), (200, 0))],
    'Blue': [((100, 100), (399, 100)), ((100, 100), (300, 0))]
}

# Set up masks per color
masks = {
    'Red': np.zeros((h, w), np.uint8),
    'Blue': np.zeros((h, w), np.uint8)
}

# For each color...
for c in ['Red', 'Blue']:
    for line in lines[c]:

        # ... draw colored line in image, ...
        img = cv2.line(img, line[0], line[1], colors[c], 2)

        # ... draw white line in mask, ...
        masks[c] = cv2.line(masks[c], line[0], line[1], 255, 1)

    # ... find mid point between both end points, and ...
    mid = tuple(np.int0(np.sum(np.array(lines[c])[:, 1, :], axis=0) / 2))

    # ... flood fill mask with the mid point as seed point
    masks[c] = cv2.floodFill(masks[c], None, mid, 255)[1]

# Logical and all masks, and check for at least one pixel overlap
inter = np.all(np.array(list(masks.values())), axis=0).astype(np.uint8) * 255
print('Is intersection: ', inter.max() > 0)

# Outputs
cv2.imshow('Image', img)
cv2.imshow('Red mask', masks['Red'])
cv2.imshow('Blue mask', masks['Blue'])
cv2.imshow('Intersection', inter)
cv2.waitKey(0)
cv2.destroyAllWindows()

Image:

Red mask:

Blue mask:

Intersection:

Decision:

Is intersection:  True

The code can be easily generalized to add even more colors (or polygons).

----------------------------------------
System information
----------------------------------------
Platform:      Windows-10-10.0.16299-SP0
Python:        3.9.1
PyCharm:       2021.1
NumPy:         1.20.2
OpenCV:        4.5.1
----------------------------------------