У меня есть два прямоугольника a и b со своими сторонами, параллельными осям системы координат. У меня есть их координаты как x1, y1, x2, y2.
Я пытаюсь определить, они не только перекрываются, но и как они перекрывают друг друга? Я пытаюсь выяснить, действительно ли они представляют собой один и тот же прямоугольник, или взять немного комнаты для маневра. Так же их область равна 95%?
Любая помощь при вычислении% перекрытия?
Вычислите площадь пересечения, которая также является прямоугольником:
SI = Max(0, Min(XA2, XB2) - Max(XA1, XB1)) * Max(0, Min(YA2, YB2) - Max(YA1, YB1))
Оттуда вы вычисляете площадь объединения:
SU = SA + SB - SI
И вы можете рассмотреть соотношение
SI / SU
(100% в случае идеального перекрытия, до 0%).
Формула для пересечения будет
SI= Max(0, Min(XA2, XB2) - Max(XA1, XB1)) * Max(0, Min(YA2, YB2) - Max(YA1, YB1))
то объединение будет S=SA+SB-SI
И, наконец, отношение будет SI / S.
Недавно я столкнулся с этой проблемой и применил ответ Ив, но почему-то это привело к неправильному размеру области, поэтому я переписал ее.
Предполагая два прямоугольника A и B, выясните, насколько они перекрываются, и если да, верните размер области:
IF A.right < B.left OR A.left > B.right
OR A.bottom < B.top OR A.top > B.bottom THEN RETURN 0
width := IF A.right > B.right THEN B.right - A.left ELSE A.right - B.left
height := IF A.bottom > B.bottom THEN B.bottom - A.top ELSE A.bottom - B.top
RETURN width * height
Хотя принятый ответ является правильным, я думаю, что стоит изучить этот ответ таким образом, чтобы обоснование ответа было совершенно очевидным. Это слишком распространенный алгоритм, чтобы иметь неполный (или, что еще хуже, противоречивый) ответ. Кроме того, лишь мельком взглянув на данную формулу, вы можете упустить красоту и расширяемость алгоритма, а также неявные решения, которые принимаются.
Во-первых, рассмотрим один из способов определения двумерного блока с помощью:
Это может выглядеть так:
Я обозначаю верхний левый треугольником, а нижний правый - кружком. Это позволяет избежать непрозрачного синтаксиса, такого как x1, x2 для этого примера.
Два перекрывающихся прямоугольника могут выглядеть так:
Обратите внимание: чтобы найти совпадение, вы ищете место, где сталкиваются оранжевый и синий:
Как только вы это узнаете, становится очевидным, что перекрытие - это результат нахождения и умножения этих двух затемненных линий:
Длина каждой линии - это минимальное значение точек окружности за вычетом максимального значения точек треугольника.
Здесь я использую двухцветную форму, чтобы показать, что сравниваются оранжевая и синяя точки. Маленькая буква после двухцветной формы указывает на то, что треугольники сравниваются вдоль этой оси (x или y).
Например, чтобы найти длину затемненной синей линии, вы можете увидеть, что оранжевый и синий треугольники сравниваются, чтобы найти максимальное значение между ними. Атрибут, который сравнивается, является атрибутом x. Максимальное значение x между оранжевым и синим треугольниками составляет 210.
Другой способ сказать то же самое: длина новой линии, которая соответствует обеим линиям, которые мы сравниваем, определяется путем вычитания ближайшей точки на самой длинной стороне линии из самой дальней точки на ближайшей стороне линия.
Поиск этих линий дает полную информацию о перекрывающихся областях.
Если у вас есть это, найти процент перекрытия тривиально:
Но подождите, если оранжевый прямоугольник не пересекается с синим, у вас возникнет проблема:
В этом примере вы получаете -850 для нашей области перекрытия, что не может быть правильным. Еще хуже, если обнаружение не пересекается ни с одним измерением (ни по оси x, ни по оси y), тогда вы все равно получите положительное число, потому что оба измерения отрицательны. Вот почему вы видите Max(0,...) * Max(0,...) как часть решения; это гарантирует, что если любое из перекрытий будет отрицательным, вы получите 0 обратно от вашей функции.
Окончательная формула соответствует нашей символике:
Стоит отметить, что использование функции max(0,...) может не потребоваться. Возможно, вы захотите узнать, перекрывает ли что-то одно из своих измерений, а не все; если вы используете max, вы уничтожите эту информацию. По этой причине подумайте, как вы хотите работать с неперекрывающимися изображениями. Обычно функцию max можно использовать, но стоит знать, что она делает.
Наконец, обратите внимание, что, поскольку это сравнение касается только линейных измерений, его можно масштабировать до произвольных измерений или произвольных перекрывающихся четырехугольников.
Подвести итоги:
intersecting_area =
max(0, min(orange.circle.x, blue.circle.x) - max(orange.triangle.x, blue.triangle.x)) * max(0, min(orange.circle.y, blue.circle.y) - max(orange.triangle.y, blue.triangle.y))
percent_coverage = intersecting_area/(orange_area + blue_area - intersecting_area)
Просто фиксируйте предыдущие ответы, чтобы соотношение находилось между 0 и 1 (с использованием Python):
# (x1,y1) top-left coord, (x2,y2) bottom-right coord, (w,h) size
A = {'x1': 0, 'y1': 0, 'x2': 99, 'y2': 99, 'w': 100, 'h': 100}
B = {'x1': 0, 'y1': 0, 'x2': 49, 'y2': 49, 'w': 50, 'h': 50}
# overlap between A and B
SA = A['w']*A['h']
SB = B['w']*B['h']
SI = np.max([ 0, 1 + np.min([A['x2'],B['x2']]) - np.max([A['x1'],B['x1']]) ]) * np.max([ 0, 1 + np.min([A['y2'],B['y2']]) - np.max([A['y1'],B['y1']]) ])
SU = SA + SB - SI
overlap_AB = float(SI) / float(SU)
print 'overlap between A and B: %f' % overlap_AB
# overlap between A and A
B = A
SB = B['w']*B['h']
SI = np.max([ 0, 1 + np.min([A['x2'],B['x2']]) - np.max([A['x1'],B['x1']]) ]) * np.max([ 0, 1 + np.min([A['y2'],B['y2']]) - np.max([A['y1'],B['y1']]) ])
SU = SA + SB - SI
overlap_AA = float(SI) / float(SU)
print 'overlap between A and A: %f' % overlap_AA
Выход будет:
overlap between A and B: 0.250000
overlap between A and A: 1.000000
Предполагая, что прямоугольник должен быть параллелен оси x и y, поскольку это кажется ситуацией из предыдущих комментариев и ответов.
Я еще не могу опубликовать комментарий, но я хотел бы отметить, что оба предыдущих ответа, похоже, игнорируют случай, когда один боковой прямоугольник полностью находится в стороне от другого прямоугольника. Пожалуйста, поправьте меня, если я ошибаюсь.
Рассмотрим случай
a: (1,1), (4,4)
b: (2,2), (5,3)
В этом случае мы видим, что для пересечения высота должна быть bTop - bBottom, потому что вертикальная часть b полностью содержится в a.
Нам просто нужно добавить несколько случаев следующим образом: (Код можно закоротить, если вы обрабатываете верх и низ как то же самое, что и правое и левое, так что вам не нужно дважды дублировать условный фрагмент, но это должно делаем.)
if aRight <= bLeft or bRight <= aLeft or aTop <= bBottom or bTop <= aBottom:
# There is no intersection in these cases
return 0
else:
# There is some intersection
if aRight >= bRight and aLeft <= bLeft:
# From x axis point of view, b is wholly contained in a
width = bRight - bLeft
elif bRight >= aRight and bLeft <= aLeft:
# From x axis point of view, a is wholly contained in b
width = aRight - aLeft
elif aRight >= bRight:
width = bRight - aLeft
else:
width = aRight - bLeft
if aTop >= bTop and aBottom <= bBottom:
# From y axis point of view, b is wholly contained in a
height = bTop - bBottom
elif bTop >= aTop and bBottom <= aBottom:
# From y axis point of view, a is wholly contained in b
height = aTop - aBottom
elif aTop >= bTop:
height = bTop - aBottom
else:
height = aTop - bBottom
return width * height
@User3025064 является правильным и является самым простым решением, однако исключительность должна быть проверена сначала для прямоугольников, которые не пересекаются, например, для прямоугольников A и B (в Visual Basic):
If A.Top =< B.Bottom or A.Bottom => B.Top or A.Right =< B.Left or A.Left => B.Right then
Exit sub 'No intersection
else
width = ABS(Min(XA2, XB2) - Max(XA1, XB1))
height = ABS(Min(YA2, YB2) - Max(YA1, YB1))
Area = width * height 'Total intersection area.
End if
[ymin_a, xmin_a, ymax_a, xmax_a] = list(bbox_a)
[ymin_b, xmin_b, ymax_b, xmax_b] = list(bbox_b)
x_intersection = min(xmax_a, xmax_b) - max(xmin_a, xmin_b) + 1
y_intersection = min(ymax_a, ymax_b) - max(ymin_a, ymin_b) + 1
if x_intersection <= 0 or y_intersection <= 0:
return 0
else:
return x_intersection * y_intersection
Ответ @user3025064 - правильный ответ. Принятый ответ непреднамеренно переворачивает внутренние MAX и MIN звонки. Нам также не нужно сначала проверять, пересекаются они или нет, если мы используем представленную формулу MAX (0, x) в отличие от ABS (x). Если они не пересекаются, MAX (0, x) возвращает ноль, что делает область пересечения 0 (то есть непересекающейся).
Я предлагаю, чтобы @Yves Daoust исправил его ответ, потому что он принят, который появляется всем, кто ищет эту проблему. Еще раз, вот правильная формула для пересечения:
SI = Max(0, Min(XA2, XB2) - Max(XA1, XB1)) * Max(0, Min(YA2, YB2) - Max(YA1, YB1))
Остальные как обычно. Союз:
SU = SA + SB - SI
и соотношение:
SI/SU
Протестировал ответ @user3025064, результаты были правильными для всех случаев, кроме случаев, когда прямоугольник полностью заключен в другой. Итак, после получения СИ вам необходимо рассчитать коэффициент следующим образом:
S=SA+SB-SI
ratio = SI / S
if SI == SA or SI == SB:
ratio = 1
return ratio*100
Это даст 100, когда один заключен внутри другого. Другой подход состоит в том, чтобы рассчитать SI/SA и SI/SB и проверить, равен ли один из них 1.