给定多边形的边，判断两个区域是否相交
Find if two areas intersect given the polygons` edges
这个问题困扰我有一段时间了。
我确实找到了一个解决方案，我可以找到每个多边形中的每个点，然后检查交叉点。然而，这在计算上是昂贵的，而且根本不实用。
下图中有四行；两条红线和两条蓝线。我想检查两条红线之间的区域是否与两条蓝线之间的区域相交。
已知以下变量：
- 每行开始的点
- 每条线的角度
- 线条结束的地方（总是在图像的边缘）
我正在考虑使用斜率公式来检查红线的原点相对于每条蓝线的位置。但我不确定这是否是最好的方法。
提前致谢。
如果每种颜色都有两条线，起点相同，终点在图像边界处不同，则只需创建一个遮罩，绘制这些线，计算两端点之间的中点，然后使用这个中点作为一些洪水填充的种子点。由于您有一个封闭的多边形，因此可以保证该中点位于多边形内部。从这两个蒙版中，确定交集（逻辑与），并检查至少有一个像素重叠。
下面是一些使用 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
----------------------------------------
这个问题主要有两种方法：
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 的形式，具体取决于您如何定义第 i 条线的角度 a[i] 以及多边形位于该线的哪一侧。 (ox[i], oy[i])是第i个顶点的坐标。如果不等式严格或不严格，则取决于您要如何处理多边形与顶点或边接触的边界情况。这是一个很好的易于推广的方法，但它可能很慢。
2。路口测试
在一般情况下（没有顶点和边重合）有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 来完成：如果一个点位于右线的左侧和左线的右侧，则它在内部.
在任何情况下，您都应该特别注意退化和边界情况：如果多边形的边重合，或者一个多边形的顶点位于另一个多边形的边上，或者不同多边形的边重合怎么办。您可以根据您的特定目的以不同方式检测和处理此类情况。
这是一个使用 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 logical operations得到交集：
intersection = np.logical_and(red_poly, blue_poly)
# plt.imshow(intersection)
最后，检查任何真值以获得 bool 结果：
np.any(intersection) #=> True
这里是这个例子的打印图像。
蓝色聚
红色聚
路口
这是 的 Pillow only 版本，结合了相同的想法。尽管如此，此版本仅限于两种颜色。添加更多颜色（或多边形）需要额外的工作（基本上，一些循环）。
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
----------------------------------------
概念
检测图像中是否存在形状交集的一种简单方法，假设每个形状必须是不同的颜色，您可以为每种颜色定义一个遮罩，并且图像的所有颜色都被遮罩，除了形状使用它，检测为形状轮廓找到的轮廓数量。
如果找到多个轮廓（面积大于指定数量以滤除噪音），这意味着另一个形状的轮廓与形状的轮廓相交，留下间隙在其轮廓中，从而产生多个轮廓。
密码
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!
解释
- 导入必要的库：
import cv2
import numpy as np
- 定义一个接受两个参数的函数；我们将检测其是否存在形状交叉的图像，以及每个形状颜色的 HSV 掩码数组：
def intersected(img, masks):
- 获取 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))
- 模糊蒙版以去除噪声，使用 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)
- 定义一个变量，
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.")
这个问题困扰我有一段时间了。 我确实找到了一个解决方案，我可以找到每个多边形中的每个点，然后检查交叉点。然而，这在计算上是昂贵的，而且根本不实用。
下图中有四行；两条红线和两条蓝线。我想检查两条红线之间的区域是否与两条蓝线之间的区域相交。
已知以下变量：
- 每行开始的点
- 每条线的角度
- 线条结束的地方（总是在图像的边缘）
我正在考虑使用斜率公式来检查红线的原点相对于每条蓝线的位置。但我不确定这是否是最好的方法。
提前致谢。
如果每种颜色都有两条线，起点相同，终点在图像边界处不同，则只需创建一个遮罩，绘制这些线，计算两端点之间的中点，然后使用这个中点作为一些洪水填充的种子点。由于您有一个封闭的多边形，因此可以保证该中点位于多边形内部。从这两个蒙版中，确定交集（逻辑与），并检查至少有一个像素重叠。
下面是一些使用 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
----------------------------------------
这个问题主要有两种方法：
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 的形式，具体取决于您如何定义第 i 条线的角度 a[i] 以及多边形位于该线的哪一侧。 (ox[i], oy[i])是第i个顶点的坐标。如果不等式严格或不严格，则取决于您要如何处理多边形与顶点或边接触的边界情况。这是一个很好的易于推广的方法，但它可能很慢。
2。路口测试
在一般情况下（没有顶点和边重合）有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 来完成：如果一个点位于右线的左侧和左线的右侧，则它在内部.
在任何情况下，您都应该特别注意退化和边界情况：如果多边形的边重合，或者一个多边形的顶点位于另一个多边形的边上，或者不同多边形的边重合怎么办。您可以根据您的特定目的以不同方式检测和处理此类情况。
这是一个使用 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 logical operations得到交集：
intersection = np.logical_and(red_poly, blue_poly)
# plt.imshow(intersection)
最后，检查任何真值以获得 bool 结果：
np.any(intersection) #=> True
这里是这个例子的打印图像。
蓝色聚
红色聚
路口
这是
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
----------------------------------------
概念
检测图像中是否存在形状交集的一种简单方法，假设每个形状必须是不同的颜色，您可以为每种颜色定义一个遮罩，并且图像的所有颜色都被遮罩，除了形状使用它，检测为形状轮廓找到的轮廓数量。
如果找到多个轮廓（面积大于指定数量以滤除噪音），这意味着另一个形状的轮廓与形状的轮廓相交，留下间隙在其轮廓中，从而产生多个轮廓。
密码
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!
解释
- 导入必要的库：
import cv2
import numpy as np
- 定义一个接受两个参数的函数；我们将检测其是否存在形状交叉的图像，以及每个形状颜色的 HSV 掩码数组：
def intersected(img, masks):
- 获取 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))
- 模糊蒙版以去除噪声，使用 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)
- 定义一个变量，
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.")