algorithm - ¿Cuánto se superponen dos rectángulos?
math geometry (9)
Tengo dos rectángulos ayb con sus lados paralelos a los ejes del sistema de coordenadas. Tengo sus coordenadas como x1, y1, x2, y2.
Estoy tratando de determinar, no solo se superponen, ¿pero CUÁNTO se superponen? Estoy tratando de averiguar si realmente son el mismo rectángulo o me dan un poco de margen de maniobra. Entonces, ¿su área es un 95% la misma?
¿Alguna ayuda para calcular el% de superposición?
@ User3025064 es correcto y es la solución más simple, sin embargo, la exclusividad se debe verificar primero para rectángulos que no se cruzan, por ejemplo, para los rectángulos A y B (en 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
Calcule el área de la intersección, que también es un rectángulo:
SI = Max(0, Min(XA2, XB2) - Max(XA1, XB1)) * Max(0, Min(YA2, YB2) - Max(YA1, YB1))
A partir de ahí calcula el área de la unión:
SU = SA + SB - SI
Y puedes considerar la proporción
SI / SU
(100% en caso de superposición perfecta, hasta 0%).
La fórmula para la intersección será
SI= Max(0, Min(XA2, XB2) - Max(XA1, XB1)) * Max(0, Min(YA2, YB2) - Max(YA1, YB1))
entonces la unión será S=SA+SB-SI
Y finalmente, la relación será SI / S
La respuesta de @ user3025064 es la respuesta correcta. La respuesta aceptada inadvertidamente invierte las llamadas MAX y MIN internas. Tampoco necesitamos verificar primero si se cruzan o no si usamos la fórmula presentada, MAX (0, x) en oposición a ABS (x). Si no se cruzan, MAX (0, x) devuelve cero, lo que hace que el área de intersección sea 0 (es decir, disjunta).
Sugiero que @Yves Daoust corrija su respuesta porque es la más aceptada que aparece para cualquiera que busque ese problema. Una vez más, aquí está la fórmula correcta para la intersección:
SI = Max(0, Min(XA2, XB2) - Max(XA1, XB1)) * Max(0, Min(YA2, YB2) - Max(YA1, YB1))
El resto como de costumbre. Unión:
SU = SA + SB - SI
y proporción:
SI/SU
Recientemente me encontré también con este problema y apliqué la respuesta de Yves, pero de alguna manera eso me llevó a un tamaño de área incorrecto, así que lo reescribí.
Suponiendo dos rectángulos A y B, averigüe cuánto se superponen y, de ser así, devuelva el tamaño del área:
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
Si bien la respuesta aceptada es correcta, creo que vale la pena explorar esta respuesta de una manera que haga que la justificación de la respuesta sea completamente obvia. Esto es demasiado común de un algoritmo para tener una respuesta incompleta (o peor, controvertida). Además, con solo echar un vistazo a la fórmula dada, puede perderse la belleza, la extensibilidad y las decisiones que se toman.
En primer lugar, considere una forma de definir un cuadro bidimensional con:
- (x, y) para el punto superior izquierdo
- (x, y) para el punto inferior derecho
Esto podría verse así:
Indico la parte superior izquierda con un triángulo y la inferior derecha con un círculo. Esto es para evitar la sintaxis opaca como x1, x2 para este ejemplo.
Dos rectángulos superpuestos pueden verse así:
Observe que para encontrar la superposición busca el lugar donde colisionan el naranja y el azul:
Una vez que reconoce esto, resulta obvio que la superposición es el resultado de encontrar y multiplicar estas dos líneas oscuras:
La longitud de cada línea es el valor mínimo del punto del círculo entre las líneas que queremos comparar, menos el valor máximo de los puntos del triángulo.
En otras palabras, la longitud de la línea que puede caber en ambas líneas que estamos comparando se hace restando el punto más cercano en el lado más largo de la línea desde el punto más alejado en el lado más cercano de la línea.
Encontrar esas líneas brinda información completa de las áreas superpuestas.
Una vez que tenga esto, encontrar el porcentaje de superposición es trivial:
Pero espere, si el rectángulo naranja no se superpone con el azul, entonces tendrá un problema:
Con este ejemplo, obtienes un -850 para nuestra área de superposición, eso no puede ser correcto. Peor aún, si una detección no se superpone con ninguna de las dimensiones (ni en el eje x ni en el eje y), de todos modos obtendrá un número positivo porque ambas dimensiones son negativas. Es por eso que ve el Max(0, ...) * Max(0, ...) como parte de la solución; asegura que si alguna de las superposiciones es negativa, obtendrás un 0 de tu función.
La fórmula final de acuerdo con nuestra simbología:
Vale la pena señalar que el uso de la función max(0, ...) puede no ser necesario. Es posible que desee saber si algo se superpone a una de sus dimensiones en lugar de a todas; si usa max entonces borrará esa información. Por esa razón, considere cómo desea tratar con imágenes que no se superponen. Normalmente, la función máxima está bien para usar, pero vale la pena ser consciente de lo que está haciendo.
Finalmente, observe que dado que esta comparación solo se refiere a medidas lineales, se puede escalar a dimensiones arbitrarias o cuadriláteros superpuestos arbitrarios.
Para resumir:
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)
Simplemente arreglando las respuestas anteriores para que la proporción esté entre 0 y 1 (usando 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
El resultado será:
overlap between A and B: 0.250000
overlap between A and A: 1.000000
Suponiendo que el rectángulo debe ser paralelo a los ejes y , esa parece ser la situación de los comentarios y respuestas anteriores.
No puedo publicar comentarios todavía, pero me gustaría señalar que ambas respuestas anteriores parecen ignorar el caso cuando un rectángulo lateral está totalmente dentro del otro rectángulo. Por favor, corríjame si estoy equivocado.
Considera el caso
a: (1,1), (4,4)
b: (2,2), (5,3)
En este caso, vemos que para la intersección, la altura debe ser bTop - bBottom porque la parte vertical de b está totalmente contenida en a .
Solo tenemos que agregar más casos de la siguiente manera: (El código puede acortarse si se trata la parte superior e inferior como lo mismo que la derecha y la izquierda, de modo que no es necesario duplicar el fragmento condicional dos veces, pero debería hacerlo).
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
[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