Méthode efficace pour trouver les coordonnées rectangle dans les tableaux 0-1

Question

Disons que j'ai une matrice MxN de 0 et 1. Il peut ou peut ne pas être clairsemé.

Je veux une fonction de trouver efficacement des rectangles dans le tableau, où par le rectangle que je veux dire:

un ensemble de 4 éléments qui sont tous des 1 qui créent les 4 coins d'un rectangle , de sorte que la les côtés du rectangle sont orthogonaux aux axes du tableau . En d'autres termes, un rectangle est un ensemble de 4 1 avec des coordonnées [indice de ligne, index de colonne] comme suit: [r1, c1], [r1, c2], [r2, c2], [r2, c1] .

E.g. cette configuration a un rectangle:

0 0 0 1 0 1 0 
0 0 0 0 0 0 0 
0 1 0 0 0 0 0 
1 0 0 1 0 1 0 
0 0 0 0 0 0 0 
0 0 0 1 0 0 1 

Pour une matrice MxN donné, je veux une fonction Python F (A) qui renvoie un L de matrice de sous-réseaux, où chaque sous-réseau est la paire de coordonnées de l'angle d'un rectangle (et inclut tous les 4 coins du rectangle). Dans le cas où le même élément du tableau est le coin de plusieurs rectangles, il est correct de dupliquer ces coordonnées.

---

Ma pensée à ce jour est:

1) trouver les coordonnées du sommet de chaque triangle dans le tableau

2) vérifier chaque sommet du triangle de coordonnées pour voir si elle fait partie d'un rectangle

L'étape 1) peut être obtenue en trouvant les éléments qui sont des 1 et qui sont dans une colonne avec une somme de colonnes> = 2, et dans une rangée avec une somme de lignes> = 2.

L'étape 2) passerait ensuite par chaque coordonnée déterminée comme étant le sommet d'un triangle rectangle. Pour une paire de coordonnées d'un triangle rectangle donnée, elle parcourrait cette colonne en regardant toutes les autres coordonnées du triangle rectangle de 1) qui se trouve dans cette colonne. Pour toute paire de 2 points de triangle rectangle dans une colonne, il vérifie ensuite quelle ligne a une somme de rang plus petite pour savoir quelle rangée serait la plus rapide à parcourir. Ensuite, il parcourrait toutes les coordonnées de la colonne du triangle droit dans cette rangée et verrait si l'autre rangée avait aussi un point de triangle rectangle dans cette colonne. Si c'est le cas, ces 4 points forment un rectangle.

Je pense que cela fonctionnera, mais il y aura des répétitions, et dans l'ensemble, cette procédure semble être raisonnablement intensive. Quels sont les meilleurs moyens de détecter les coins de rectangle dans les tableaux 0-1?

Answer 1

Ceci est du haut de ma tête et pendant 5 heures d'escale à LAX.Voici mon algorithme:

Étape 1: Rechercher toutes les lignes pour au moins deux plus

| 0 0 0 1 0 1 0 
| 0 0 0 0 0 0 0 
| 0 1 0 0 0 0 0 
\|/ 1 0 0 1 0 1 0 
    0 0 0 0 0 0 0 
    0 0 0 1 0 0 1 

Sortie:

-> 0 0 0 1 0 1 0 
    0 0 0 0 0 0 0 
    0 1 0 0 0 0 0 
-> 1 0 0 1 0 1 0 
    0 0 0 0 0 0 0 
-> 0 0 0 1 0 0 1 

Étape 2: Pour chaque paire de ceux à chaque rangée obtiennent l'index pour un dans la colonne correspondant à ceux, disons pour t il première ligne:

-> 0 0 0 1 0 1 0 

vous vérifiez les dans les colonnes suivantes:

 | | 
     \|/ \|/ 

0 0 0 1 0 1 0 
0 0 0 0 0 0 0 
0 1 0 0 0 0 0 
1 0 0 1 0 1 0 
0 0 0 0 0 0 0 
0 0 0 1 0 0 1 

Étape 3: Si les deux match de l'indice; retourner les indices de tous les quatre. Cela peut être facilement accessible car vous connaissez la rangée et l'index des uns à toutes les étapes. Dans notre cas, la recherche en colonnes 3, 5 vont revenir 3 en supposant que vous commencez à partir de l'index 0. Donc, nous obtenons les indicies pour les éléments suivants:

0 0 0 ->1 0 ->1 0 
0 0 0 0 0 0 0 
0 1 0 0 0 0 0 
1 0 0 ->1 0 ->1 0 
0 0 0 0 0 0 0 
0 0 0 1 0 0 1 

Étape 4: Répétez l'opération pour toutes les paires

Complexité de l'algorithme Je sais que vous devez rechercher columns * rows * number of pairs mais vous pouvez toujours utiliser des hashmaps pour optimiser la recherche O(1). Ce qui rendra la complexité liée au nombre de paires. N'hésitez pas à commenter pour toute question.

Answer 2

Voici une implémentation Python similaire à la solution @PseudoAj. Il traitera les lignes commençant par le haut tout en construisant un dict où les clés sont des coordonnées x et les valeurs sont des ensembles de coordonnées y respectives.

Pour chaque ligne les étapes suivantes sont effectuées:

1. générons une liste de coordonnées x avec 1s de ligne courante
2. Si la longueur de la liste est inférieure à 2 déplacer à la ligne suivante
3. itérer sur toutes les paires de coordonnées left, right où left < right
4. Pour chaque paire de coordonnées take intersection de dict contenant des lignes traitées
5. Pour chaque coordonnée y à l'intersection ajouter rectangle pour entraîner
6. Enfin mettre à jour dict avec des coordonnées de ligne courante

code:

from collections import defaultdict 
from itertools import combinations 

arr = [ 
    [0, 0, 0, 1, 0, 1, 0], 
    [0, 0, 0, 0, 0, 0, 0], 
    [0, 1, 0, 0, 0, 0, 0], 
    [1, 0, 0, 1, 0, 1, 0], 
    [0, 0, 0, 0, 0, 0, 0], 
    [0, 0, 0, 1, 0, 0, 1] 
] 

# List corner coords 
result = [] 

# Dict {x: set(y1, y2, ...)} of 1s in processed rows 
d = defaultdict(set) 

for y, row in enumerate(arr): 
    # Find indexes of 1 from current row 
    coords = [i for i, x in enumerate(row) if x] 

    # Move to next row if less than two points 
    if len(coords) < 2: 
     continue 

    # For every pair on this row find all pairs on previous rows 
    for left, right in combinations(coords, 2): 
     for top in d[left] & d[right]: 
      result.append(((top, left), (top, right), (y, left), (y, right))) 

    # Add coordinates on this row to processed rows 
    for x in coords: 
     d[x].add(y) 

print(result) 

sortie:

[((0, 3), (0, 5), (3, 3), (3, 5))]