ejemplo visual

Considere un rectángulo completo (inicialmente la imagen completa) y elimine un cuadro excluido. Obtendrás 2x2x2x2=16 posibles subdivisiones rectangulares, por ejemplo esta.

 ┌────────────────────────┐ │ │ │ │ ├───────┬───────┬────────┤ │ │ exc │ │ │ │ lude │ │ │ ├───────┴────────┤ │ │ │ │ │ │ └───────┴────────────────┘

Para cada casilla de la subdivisión, retire la siguiente casilla excluida. Haz esto N veces y toma la caja más grande del paso final.

Suposición : desea que el cuadro más grande de su matriz cumpla con sus reglas, y no es el cuadro delimitador NUEVO más grande que cumple.

Este es un pseudocódigo, todavía tiene que completar los espacios en blanco

 int largestBoxIndex = -1; int largestBoxArea = -1; for (i=0; i<allBoxes[].length; i++) { box CurrentBox = allBoxes[i]; bool isComply = false; for (j=0; j<allBoxes[].length; j++) { isComply = false; if(i==j) break; ComparedBox = allBoxes[j] if (isIntersected(CurrentBox, ComparedBox)) break; if (isInside(CurrentBox, ComparedBox)) break; isComply = true; } if(isComply) if(Area(allBoxes[i]) > largestBoxArea) { largestBoxArea = Area(allBoxes[i]): largestBoxIndex =i; } } if(largestBoxIndex != -1) largestBoxIndex;//this is the largest box

Una solución matemática simple al problema.

Suponga que le dan 5 rectángulos como se muestra a continuación:

 rects = [[100, 100, 200, 200], [200, 200, 200, 200], [200, 500, 200, 200], [350, 50, 150, 200], [500, 400, 200, 300]]

Tenga en cuenta que el formato de estos rectángulos es: [x, y, ancho, alto] Donde, (x, y) es la coordenada de la esquina superior izquierda del rectángulo, y width y height son el ancho y alto del rectángulo respectivamente . Primero tendrá que convertir sus coordenadas en este formato.

3 de estos 5 se cruzan.

Ahora lo que haremos es iterar sobre estos rectángulos uno por uno, y para cada rectángulo, encontrar la intersección de este rectángulo con los otros rectángulos uno por uno. Si se encuentra que algún rectángulo se cruza con cualquiera de los otros rectángulos, estableceremos el valor de la flag para los dos rectángulos como 0 . Si se encuentra que un rectángulo no se cruza con ningún otro rectángulo, entonces su valor de flag se establecerá en 1 . (El valor predeterminado del indicador es -1 ). Finalmente, encontraremos el rectángulo de mayor área entre los rectángulos con bandera valor 1.

Veamos el código para encontrar el área de intersección de los dos rectángulos:

 # Rect : [x, y, w, h] def Intersection(Rect1, Rect2): x = max(Rect1[0], Rect2[0]) y = max(Rect1[1], Rect2[1]) w = min(Rect1[0] + Rect1[2], Rect2[0] + Rect2[2]) - x h = min(Rect1[1] + Rect1[3], Rect2[1] + Rect2[3]) - y if w < 0 or h < 0: return None return [x, y, w, h]

Esta función devolverá None si no hay un área de intersección entre estos rectángulos o devolverá las coordenadas del rectángulo de intersección (Ignore este valor para el problema actual. Esto podría ser útil en otros problemas).

Ahora, echemos un vistazo al algoritmo.

 n = len(rects) # -1 : Not determined # 0 : Intersects with some # 1 : No intersection flag = [-1]*n for i in range(n): if flag[i] == 0: continue isIntersecting = False for j in range(n): if i == j or flag[j] == 1: continue Int_Rect = Intersection(rects[i], rects[j]) if Int_Rect is not None: isIntersecting = True flag[j] = 0 flag[i] = 0 break if isIntersecting == False: flag[i] = 1 # Finding the maximum area rectangle without any intersection. maxRect = None maxArea = -1 for i in range(n): if flag[i] == 1: if rects[i][2] * rects[i][3] > maxArea: maxRect = rects[i] maxArea = rects[i][2] * rects[i][3] print(maxRect)

Nota: Agregue las coordenadas del rectángulo de "áreas excluidas" a la lista de rects y asigne su valor de flag como 0 para evitar que se seleccionen como el rectángulo de área máxima.

Esta solución no involucra ninguna imagen, por lo que será el algoritmo más rápido a menos que esté optimizado.

Puede usar el método cv2.boundingRect() para obtener x, y, w, h de cada cuadro delimitador, y con x, y, w, h de cada cuadro delimitador, puede usar la condición x2 + w2 > x1 > x2 - w1 and y2 + h2 > y1 > y2 - h1 para verificar si dos cuadros delimitadores se cruzan o están dentro de otros:

 import cv2 import numpy as np def intersect(b1, b2): x1, y1, w1, h1 = b1 x2, y2, w2, h2 = b2 return x2 + w2 > x1 > x2 - w1 and y2 + h2 > y1 > y2 - h1 # Here I am generating a random array of 10 boxes in the format [[x,y], [x,y], [x,y], [x,y]] np.random.seed(55) boxes = np.random.randint(10, 150, (10, 4, 2)) + np.random.randint(0, 300, (10, 1, 2)) bounds = [cv2.boundingRect(box) for box in boxes] valids = [b1 for b1 in bounds if not any(intersect(b1, b2) for b2 in bounds if b1 != b2)] if valids: x, y, w, h = max(valids, key=lambda b: b[2] * b[3]) print(f"x: {x} y: {y} w: {w} h: {h}") else: print("All boxes intersect.")

Producción:

 x: 75 y: 251 w: 62 h: 115

Para visualización:

 import cv2 import numpy as np def intersect(b1, b2): x1, y1, w1, h1 = b1 x2, y2, w2, h2 = b2 return x2 + w2 > x1 > x2 - w1 and y2 + h2 > y1 > y2 - h1 np.random.seed(55) boxes = np.random.randint(10, 150, (10, 4, 2)) + np.random.randint(0, 300, (10, 1, 2)) bounds = [cv2.boundingRect(box) for box in boxes] valids = [b1 for b1 in bounds if not any(intersect(b1, b2) for b2 in bounds if b1 != b2)] img = np.zeros((500, 500), "uint8") for x, y, w, h in bounds: cv2.rectangle(img, (x, y), (x + w, y + h), 255, 1) if valids: x, y, w, h = max(valids, key=lambda b: b[2] * b[3]) cv2.rectangle(img, (x, y), (x + w, y + h), 128, -1) cv2.imshow("IMAGE", img) cv2.waitKey(0)

Producción:

Encuentra el cuadrado más grande en una matriz numpy

¿Quizás esto ayudaría? Si conoce el tamaño de toda el área, puede calcular el cuadro más grande dentro de la matriz numpy. Si configura todos los cuadros dados en 1 y toda su área en 0, necesita encontrar el área más grande que sea única y no 1.

En otras palabras:

1. se excluyen los rectángulos que comparten puntos
2. de los rectángulos restantes, toma el más grande

¡No hay necesidad de contornos, centroides, cuadros delimitadores, máscaras o redibujar píxeles!

Como se indicó anteriormente, en el caso proporcionado, las coordenadas de los rectángulos contienen duplicados. Aquí, usamos una sola clase para almacenar los límites exteriores del rectángulo. El teorema del eje de separación de esta respuesta de @samgak se usa en un método intersects() .

 from __future__ import annotations # optional from dataclasses import dataclass # optional ? @dataclass class Rectangle: left: int top: int right: int bottom: int def __repr__(self): """String representation of the rectangle's coordinates.""" return f"⟔ {self.left},{self.top} ⟓ {self.right},{self.bottom}" def intersects(self, other: Rectangle): """Whether this Rectangle shares points with another Rectangle.""" h = self.right < other.left or self.left > other.right v = self.bottom < other.top or self.top > other.bottom return not h or not v def size(self): """An indicator of the Rectangle's size, equal to half the perimeter.""" return self.right - self.left + self.bottom - self.top main = Rectangle(100, 100, 325, 325) others = { 0: Rectangle(100, 100, 400, 400), 1: Rectangle(200, 200, 300, 300), 2: Rectangle(200, 300, 300, 500), 3: Rectangle(300, 300, 500, 500), 4: Rectangle(500, 500, 600, 600), 5: Rectangle(350, 350, 600, 600), } for i, r in others.items(): print(i, main.intersects(r), r.size())

En pocas palabras, h es True si el otro rectángulo está completamente a la izquierda oa la derecha; v es True si está en la parte superior o inferior. El método intersects() devuelve True si los rectángulos comparten puntos (incluso una esquina).

Producción:

 0 True 600 1 True 200 2 True 300 3 True 400 4 False 500 5 False 200

Entonces es trivial encontrar el mayor:

 valid = {r.size():i for i, r in others.items() if not main.intersects(r)} print('Largest:', valid[max(valid)], 'with size', max(valid))

Producción:

 Largest: 4 with size 500

Esta respuesta asume left < right y top < bottom para todos los rectángulos.

La siguiente función convierte las coordenadas del rectángulo proporcionadas al tipo utilizado por la clase Rectangle anterior. Esto supone que el orden es [[l, t], [r, t], [r, b], [l, b]] (un camino).

 def trim(coordinates): """Remove redundant coordinates in a path describing a rectangle.""" return coordinates[0][0], coordinates[1][1], coordinates[2][0], coordinates[3][1]

Finalmente, queremos hacer esto para todos los rectángulos, no solo uno "principal". Simplemente podemos hacer que cada rectángulo sea el principal por turnos. Use itertools.combinations() en un iterable como una list :

 itertools.combinations(rectangles, 2)

Esto asegurará que no comparemos dos rectángulos más de una vez.

Aquí hay una solución O (n ^ 2). find_maxbox toma una matriz de rectángulos y los convierte en objetos de Box y luego compara cada par de cuadros para eliminar los rectángulos no válidos. Esta solución asume que los lados de los rectángulos son paralelos a los ejes XY.

 class Box(): def __init__(self, coordinates): self.coordinates = tuple(sorted(coordinates)) self.original = coordinates self.height = abs(self.coordinates[0][1] - self.coordinates[3][1]) self.width = abs(self.coordinates[0][0] - self.coordinates[3][0]) self.excluded = False def __eq__(self, b2): return self.coordinates == b2.coordinates def get_area(self): return self.height * self.width def bounding_box(self, b2): maxX, maxY = map(max, zip(*self.coordinates, *b2.coordinates)) minX, minY = map(min, zip(*self.coordinates, *b2.coordinates)) return Box([(minX, minY), (maxX, minY), (minX, maxY), (maxX, maxY)]) def intersects(self, b2): box = self.bounding_box(b2) if box.height < self.height + b2.height and box.width < self.width + b2.width: return True else: return False def encloses(self, b2): return self == self.bounding_box(b2) def exclude(self): self.excluded = True def is_excluded(self): return self.excluded def __str__(self): return str(self.original) def __repr__(self): return str(self.original) # Pass array of rectangles as argument. def find_maxbox(boxes): boxes = sorted(map(Box, boxes), key=Box.get_area, reverse=True) _boxes = [] _boxes.append((boxes[0], boxes[0])) for b1 in boxes[1:]: b2, bb2 = _boxes[-1] bbox = b1.bounding_box(bb2) if not b1.intersects(bb2): _boxes.append((b1, bbox)) continue for (b2, bb2) in reversed(_boxes): if not b1.intersects(bb2): break if b1.intersects(b2): if b2.encloses(b1): b1.exclude() break b1.exclude() b2.exclude() _boxes.append((b1, bbox)) for box in boxes: if box.is_excluded(): continue else: return box.original return None