找出给定多边形边的两个区域是否相交

Question

这个问题一直困扰着我一段时间了。 我确实找到了一个解决方案，我可以找到每个多边形中的每个点，然后检查交点。然而，这在计算上是昂贵的，而且根本不实用

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

已知以下变量：

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

我在考虑使用斜率公式来检查红线的原点相对于每条蓝线落在哪里。但我不确定这是否是最好的方法

提前谢谢

Answer 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个顶点的坐标。如果不等式严格与否，则取决于如何处理多边形与顶点或边接触的边界情况。这是一个很好的、易于推广的方法，但它可能很慢

二,。交叉测试

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

对于案例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来完成：如果一个点位于右线的左侧，而在左线的右侧，则该点位于内部

在任何情况下，都应该特别注意退化和边界情况：如果多边形的边重合，或者一个多边形的顶点位于另一个多边形的边上，或者不同多边形的边重合，该怎么办。根据您的特殊目的，您可能会以不同的方式检测和处理此类病例

Answer 2

这里有一个枕头版本的my answer using OpenCV and 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
----------------------------------------

Answer 3

概念

一种简单的检测图像中是否存在形状交叉点的方法，假设每个形状必须是不同的颜色，您可以为每种颜色定义一个遮罩，并且在图像的颜色都被遮罩（形状除外）的情况下，检测为形状轮廓找到的轮廓量

如果发现多个轮廓（大于过滤噪声的指定量的区域），这意味着另一个形状的轮廓与该形状的轮廓相交，在其轮廓中留下间隙，从而产生多个轮廓

代码

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

1. 定义一个包含2个参数的函数；我们将检测的图像是否存在形状交叉点，以及每个形状颜色的HSV遮罩阵列：

def intersected(img, masks):

1. 以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))

1. 模糊遮罩以去除噪声，使用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)

1. 定义一个变量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

1. 最后，我们可以利用图像上的功能：

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