Насколько перекрываются два прямоугольника?

Question

У меня есть два прямоугольника a и b, стороны которых параллельны осям системы координат.У меня есть их координаты x1, y1, x2, y2.

Я пытаюсь определить, не только они перекрываются, но СКОЛЬКО они перекрываются?Я пытаюсь выяснить, дают ли они действительно один и тот же прямоугольник или занимают немного места для маневра.Значит, их площадь 95% одинакова?

Любая помощь в расчете% перекрытия?

Answer 1

Вычислите площадь пересечения, которая также является прямоугольником:

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

Answer 2

Формула для пересечения будет

SI= Max(0, Min(XA2, XB2) - Max(XA1, XB1)) * Max(0, Min(YA2, YB2) - Max(YA1, YB1))

, тогда объединение будет S=SA+SB-SI

И, наконец, соотношение будет SI / S.

Answer 3

Я недавно столкнулся с этой проблемой и применил ответ Ивса, но каким-то образом это привело к неправильному размеру области, поэтому я переписал его.

Предполагая два прямоугольника 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

Answer 4

Хотя принятый ответ является правильным, я думаю, что стоит изучить этот ответ таким образом, чтобы обоснование ответа было совершенно очевидным.Это слишком распространенный алгоритм, чтобы иметь неполный (или, что еще хуже, противоречивый) ответ.Кроме того, лишь мельком взглянув на данную формулу, вы можете упустить красоту и расширяемость алгоритма, а также неявные решения, которые принимаются.

Во-первых, рассмотрим один из способов определения двумерного прямоугольника с помощью:

• (x, y) для верхней левой точки
• (x, y)для нижней правой точки

Это может выглядеть следующим образом:

Я указываю верхний левый с треугольником ивнизу справа с кружком.Это сделано для того, чтобы избежать непрозрачного синтаксиса, такого как 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)

Answer 5

Просто исправляем предыдущие ответы, чтобы соотношение было между 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

Answer 6

Предполагая, что прямоугольник должен быть параллелен оси 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

Answer 7

[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

Answer 8

@ 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

Answer 9

Ответ @ user3025064 - правильный ответ. Принятый ответ непреднамеренно переворачивает внутренние вызовы MAX и MIN. Нам также не нужно сначала проверять, пересекаются ли они или нет, если мы используем представленную формулу MAX (0, x), а не ABS (x). Если они не пересекаются, MAX (0, x) возвращает ноль, что делает область пересечения 0 (т.е. не пересекающейся).

Я полагаю, что @ Ив Дауст исправит свой ответ, потому что это принятый ответ, который появляется у всех, кто ищет эту проблему. Еще раз, вот правильная формула для пересечения:

SI = Max(0, Min(XA2, XB2) - Max(XA1, XB1)) * Max(0, Min(YA2, YB2) - Max(YA1, YB1))

Остальное как обычно. Союз:

SU = SA + SB - SI

и соотношение:

SI/SU

Answer 10

Протестировал ответ @ 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.