查找给定多边形的边缘，确定两个区域是否相交。

Question

这个问题已经困扰我有一段时间了。我找到了一个解决方案，可以找到每个多边形中的每个点，然后检查交点。但是，这样的计算成本很高，根本不实用。

下面的图片中有四条线：两条红线和两条蓝线。我想检查两条红线之间的区域是否与两条蓝线之间的区域相交。

以下变量已知：

1. 每条线开始的点
2. 每条线的角度
3. 线的结束位置（始终在图像边缘）

我在考虑使用斜率公式来检查红色线的起点相对于每条蓝色线的位置。但我不确定这是否是最佳方法。

提前致谢。

- Abdulaziz Al-Mojil

---

这指的是在编程中使用的“this”关键字。它是一个引用当前对象的关键字，可以用于访问该对象的属性和方法。在面向对象编程中，每个对象都有自己的状态和行为，因此使用“this”关键字可以确保正确地访问当前对象的成员。 - Mark Setchell

你可以使用凸多边形相交算法。这在O（N）的时间内可以实现。一个更简单的解决方案是分离轴定理。复杂度为O（N²）。与填充相比，这仍然是相当合理的。 - user1196549

Answer 1

解决这个问题主要有两种方法：

1. 线性规划

将问题表达为线性不等式系统，并按照此处所述的线性规划问题进行求解：Solve a system of linear equations and linear inequalities。在您的情况下，不等式将采用以下形式：(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，具体取决于您如何定义第i条线的角度a[i]以及多边形位于线的哪一侧。 (ox[i], oy[i])是第i个顶点的坐标。如果不等式是严格的或不严格的，则取决于您如何处理多边形与顶点或边相接触的边界情况。这是一种通用性好的方法，但可能速度较慢。

2. 相交测试

在一般情况下（没有顶点和边重合），有4种可能性：（1）某些边相交；（2）多边形1在多边形2内部；（3）多边形2在多边形1内部；（4）多边形不相交。您需要测试前三种情况。

对于情况1，您需要实现一个线段相交测试，如此处所述：How can I check if two segments intersect?，并尝试将多边形1的每条边与多边形2的每条边相交，这在您的情况下不是问题，因为最多会进行2*2 = 4次测试。如果检测到至少一个相交，则完成。

对于情况2和3，您需要测试多边形1的顶点是否在多边形2内部，反之亦然。可以使用How can I check if two segments intersect?中描述的相同测试IsOnLeft和IsOnRight：如果一个点在右侧线的左侧且在左侧线的右侧，则它在内部。

无论如何，您都应特别注意退化和边界情况：如果多边形的边重合，或者一个多边形的顶点位于另一个多边形的边上，或者不同多边形的边重合。您可以根据特定目的检测并以不同方式处理这些情况。

- aparpara

Answer 2

概念

一种简单的检测图像中形状相交的方法是，假设每个形状都有不同的颜色，你可以为每个颜色定义一个掩码，并且使用图像的颜色进行掩蔽，除了具有其颜色的形状之外，检测该形状轮廓的轮廓数量。

如果发现多个轮廓（面积大于指定量以过滤噪声），那么意味着另一个形状的轮廓与该形状的轮廓相交，留下了空隙导致出现多个轮廓。

代码

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

定义一个函数，它将接受两个参数：我们将检测是否存在形状交集的图像，以及每个形状颜色的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. 模糊掩模以消除噪声，使用Canny边缘检测器检测其边缘，并找到Canny边缘的轮廓：

        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

最后，我们可以在图像上使用该函数：

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

- Ann Zen

Answer 3

这是一个仅使用Pillow的版本，包含了与我的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
----------------------------------------

- HansHirse

Answer 4

这是一个使用小型单通道图像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)

然后使用 Numpy 逻辑运算 获取交集：

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

最后，检查是否有任何True值以获取布尔结果：

np.any(intersection) #=> True

---

这是此示例的绘图图像。

蓝色多边形

红色的多边形

交叉点

- iGian

Answer 5

如果您有每种颜色的两条线，具有共同的起点和图像边界处不同的终点，则可以简单地创建一个掩码，绘制这些线，计算两个端点之间的中点，并使用此中点作为某些洪水填充的种子点。由于您有一个封闭的多边形，因此保证该中点位于多边形内部。从这两个掩码中确定交集（逻辑与），并检查至少有一个像素重叠。

以下是使用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
----------------------------------------

- HansHirse