我有一个矩形的坐标,包括
x1
, y1
, x2
, y2
,以及其他矩形的坐标列表。我想比较已有矩形与其他矩形的重叠情况,判断它们是否与原始矩形的重叠面积超过50%。我查看了其他资源,但仍然无法理解。以下是相关资源链接:
x1
, y1
, x2
, y2
,以及其他矩形的坐标列表。我想比较已有矩形与其他矩形的重叠情况,判断它们是否与原始矩形的重叠面积超过50%。我查看了其他资源,但仍然无法理解。以下是相关资源链接:
首先,让我们把你的问题简化为一个维度:
你有一个区间 A = [a0, a1]
,想知道另一个区间 B = [b0, b1]
与它相交的程度。我会用 =
表示 A
,用 -
表示 B
。
有6种可能的情况:
A
contains B
, intersection = b1 - b0
a0 b0 b1 a1
==============
------
B
contains A
, intersection = a1 - a0
b0 a0 a1 b1
======
--------------
B
intersects A
from the left, intersection = b1 - a0
b0 a0 b1 a1
==========
----------
B
intersects A
from the right, intersection = a1 - b0
a0 b0 a1 b1
==========
----------
B
is to the left of A
, intersection = 0
b0 b1 a0 a1
======
------
B
is to the right of A
, intersection = 0
a0 a1 b0 b1
======
------
A = [a0, a1]
和 B = [b0, b1]
,返回它们相交的部分大小:def calculateIntersection(a0, a1, b0, b1):
if a0 >= b0 and a1 <= b1: # Contained
intersection = a1 - a0
elif a0 < b0 and a1 > b1: # Contains
intersection = b1 - b0
elif a0 < b0 and a1 > b0: # Intersects right
intersection = a1 - b0
elif a1 > b1 and a0 < b1: # Intersects left
intersection = b1 - a0
else: # No intersection (either side)
intersection = 0
return intersection
X
和Y
轴上执行此函数,并将这些数量相乘即可:# The rectangle against which you are going to test the rest and its area:
X0, Y0, X1, Y1, = [0, 0, 10, 10]
AREA = float((X1 - X0) * (Y1 - Y0))
# Rectangles to check
rectangles = [[15, 0, 20, 10], [0, 15, 10, 20], [0, 0, 5, 5], [0, 0, 5, 10], [0, 5, 10, 100], [0, 0, 100, 100]]
# Intersecting rectangles:
intersecting = []
for x0, y0, x1, y1 in rectangles:
width = calculateIntersection(x0, x1, X0, X1)
height = calculateIntersection(y0, y1, Y0, Y1)
area = width * height
percent = area / AREA
if (percent >= 0.5):
intersecting.append([x0, y0, x1, y1])
[15, 0, 20, 10]
在X轴上没有交集,因此 width = 0
。[0, 15, 10, 20]
在Y轴上没有交集,因此 height = 0
。[0, 0, 5, 5]
只有 25%
的交集。[0, 0, 5, 10]
有 50%
的交集,将添加到 intersecting
中。[0, 5, 10, 100]
有 50%
的交集,将添加到 intersecting
中。[0, 0, 100, 100]
有 100%
的交集,将添加到 intersecting
中。重叠区域是重叠宽度和重叠高度的乘积。
要找到矩形XY
和xy
的宽度重叠,取左边缘最右侧和右边缘最左侧。数值上,为max(X1, x1)
和min(X2, x2)
。因此,重叠宽度为min(X2, x2) - max(X1, x1)
。如果这个值为负数,则没有重叠。重复以上步骤计算高度。
因此,重叠面积可以用一个公式表示:
max(0, min(X2, x2) - max(X1, x1)) . max(0, min(Y2, y2) - max(Y1, y1))
[总成本:六次比较,两次减法,一次乘法(加上一次与目标区域的比较)]
作为微观优化,如果您可以立即得出“否定”结论,则可以立即得出“否定”结论。
min(X2, x2) - max(X1, x1) < 50% (X2 - X1)
[有一定的概率,成本将降低到三次比较和一次减法。]