Принципиально есть два подхода к этой проблеме:

1. Линейное программирование

Выразите проблему как систему линейных неравенств и решите ее как задачу линейного программирования, как описано здесь: Решите систему линейных уравнений и линейных неравенств. В вашем случае неравенства будут иметь форму (x - ox[i])*sin(a[i]) - (y - oy[i])*cos(a[i]) > 0 или (x - ox[i])*sin(a[i]) - (y - oy[i])*cos(a[i]) < 0 в зависимости от того, как вы определяете угол a[i] i-й линии и с какой стороны линии лежит многоугольник. (ox[i], oy[i]) - координаты i-й вершины. Если неравенства строгие или нет, это зависит от того, как вы хотите обрабатывать граничные случаи, когда многоугольники соприкасаются с вершиной или ребром. Это хороший, легко обобщаемый подход, но он может быть медленным.

2. Испытания на перекрестках

В общем случае (никакие вершины и ребра не совпадают) есть 4 возможности: (1) некоторые ребра пересекаются; (2) многоугольник 1 находится внутри многоугольника 2; (3) многоугольник 2 находится внутри многоугольника 1; (4) многоугольники не пересекаются. Вам нужно проверить первые 3 случая.

Для случая 1 вам необходимо реализовать тест пересечения сегментов, как описано здесь Как можно Я проверяю, пересекаются ли два сегмента? и пытаюсь пересечь каждый край многоугольника 1 с каждым краем многоугольника 2, что не является проблемой в вашем случае, поскольку будет проведено не более 2*2 = 4 тестов. Если вы обнаружите хотя бы один перекресток, все готово.

Для случаев 2 и 3 вам нужно проверить, находится ли вершина многоугольника 1 внутри многоугольника 2 и наоборот. Это можно сделать с помощью тех же тестов IsOnLeft и IsOnRight, описанных в Как я могу проверить, пересекаются ли два отрезка?: если точка находится слева от правой линии и справа от левой, то она внутри.

В любом случае следует обратить особое внимание на вырожденные и граничные случаи: что, если ребра многоугольника совпадают, или вершина одного многоугольника лежит на ребре другого, или ребра разных многоугольников совпадают. Вы можете выявлять и лечить такие случаи по-разному в зависимости от ваших конкретных целей.

Концепт

Один простой способ определить, существуют ли пересечения фигур на изображении, учитывая, что каждая форма должна быть разного цвета, вы можете определить маску для каждого цвета, а все цвета изображения замаскированы, за исключением формы с ее, определить количество контуров, найденных для контура формы.

Если обнаружено более одного контура (области, превышающей заданное значение для фильтрации шума), это означает, что контур другой фигуры пересек контур фигуры, оставляя зазоры в его контуре и, таким образом, приводя к нескольким контуры.

Код

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.")

Выход

Intersection detected!

Объяснение

1. Импортируйте необходимые библиотеки:

import cv2
import numpy as np

2. Определите функцию, которая будет принимать 2 аргумента; изображение, которое мы будем определять, есть ли пересечения форм, и массив масок HSV цвета каждой формы:

def intersected(img, masks):

3. Получите изображение в его форме HSV и пропустите каждую из масок HSV:

    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 = cv2.GaussianBlur(mask, (5, 5), 0)
        canny = cv2.Canny(blur, 0, 0)
        contours, _ = cv2.findContours(canny, cv2.RETR_EXTERNAL, cv2.CHAIN_APPROX_NONE)

5. Задайте переменную count для хранения количества контуров с площадью больше, чем, скажем, 50, найденных на данный момент. Если переменная count достигнет 2, мы узнаем, что было найдено хотя бы одно пересечение, и этого достаточно, чтобы подтвердить наличие пересечений на изображении:

        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. Наконец, мы можем использовать функцию на изображении:

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.")

Вот версия только для подушки, моего ответа с использованием OpenCV и NumPy, включающая ту же идею. Тем не менее, эта версия ограничена двумя цветами. Добавление большего количества цветов (или многоугольников) потребует дополнительной работы (в основном, некоторого зацикливания).

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

Выходы идентичны версии OpenCV.

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

Это пример использования небольшого одноканального изображения размером 10x10 пикселей.

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

Когда у вас есть координаты точек, скажем:

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)

Вы можете использовать fillPoly между линии:

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

и

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

Затем используйте числовые логические операции, чтобы получить пересечение:

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

Наконец, проверьте любое значение True, чтобы получить результат типа bool:

np.any(intersection) #=> True

Вот изображения этого примера.

Синий поли

Красный поли

Пересечение

Если у вас есть две линии для каждого цвета с общей начальной точкой и разными конечными точками на границах изображения, вы можете просто создать маску, нарисовать эти линии, вычислить среднюю точку между обеими конечными точками и использовать эту среднюю точку в качестве начального значения. точка для заливки некоторого флуда. Поскольку у вас замкнутый многоугольник, эта средняя точка гарантированно находится внутри многоугольника. По этим двум маскам определите пересечение (логическое и) и проверьте, нет ли перекрытия хотя бы на один пиксель.

Вот код с использованием OpenCV и 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()

Изображение:

Красная маска:

Синяя маска:

Пересечение:

Решение:

Is intersection:  True

Код можно легко обобщить, чтобы добавить еще больше цветов (или многоугольников).

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