Comment diviser une zone composée de petits carrés en de plus grands rectangles?

Question

Où irais-je chercher des algorithmes prenant une grille 2D de valeurs ayant la valeur 0 ou 1 en entrée, puis identifiant tous les rectangles possibles ne se chevauchant pas?

Pour une explication plus pratique: je dessine une grille représentée par un certain nombre de carrés et je souhaite trouver un moyen de combiner autant de carrés adjacents que possible en rectangles, afin de réduire le temps passé en parcourant chaque carré et en le dessinant.

L'efficacité maximale n'est pas nécessaire, la vitesse est plus importante.

Addendum: Apparemment, ce que je recherche semble être une technique appelée Tesselation. Maintenant, il ne me reste plus qu'à trouver une bonne description pour ce cas particulier.

Addendum 2: limite du "1" les carrés seront irréguliers et, dans certains cas, même pas connectés, comme la distribution de "1" les carrés seront complètement aléatoires. J'ai besoin que ces formes irrégulières soient identifiées et divisées en rectangles réguliers.

Réponse correcte: Pour obtenir le meilleur équilibre entre rapidité et efficacité, il est optimal d'utiliser les données de la grille pour remplir un arbre quadrilatère, chaque nœud ayant une valeur d'état vide ou partiellement remplie. rempli.

Answer 1

J'ai fait quelque chose de similaire pour une visualisation voxel rapide et sale des boîtes 3D avec OpenGL.

Je suis parti de la boîte en haut à gauche et j'ai stocké le drapeau vide / rempli. Ensuite, j'ai essayé d'élargir le rectangle vers la droite jusqu'à ce que je frappe une case avec un drapeau différent. J'ai fait la même chose dans la direction descendante.

Dessinez le rectangle, s'il est rempli.

S'il reste des cases, répétez la procédure de manière récurrente pour les trois rectangles restants induits par le dernier rectangle, à droite, en bas et en bas à droite:

xxxx   1111
xxxx   1111
xxxx   1111

2222   3333
2222   3333
2222   3333

Answer 2

Consultez cet article du portail du docteur Dobb sur la recherche d'un rectangle maximal dans votre situation. C’est une discussion très détaillée sur un algorithme extrêmement efficace, et je pense que le répéter de manière itérative résoudrait probablement votre problème.

Answer 3

Comme vous ne recherchez pas le nombre minimum de carrés, je vous conseillerais d'utiliser un compromis qui garde votre algorithme simple.

La meilleure solution dépend de vos données, mais une solution simple consiste à collecter des boîtes le long d'une ligne. I.e:

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

entraînera:

skip 2
draw 3
skip 3
draw 4
skip 1

Ceci réduira le nombre d'appels pour dessiner une boîte sans avoir besoin de la mettre en cache (c.-à-d. que vous pouvez construire vos boîtes à la volée).

Si vous voulez créer de plus grandes boîtes, je vous suggérerais un algorithme de retour en arrière. Vous trouverez le premier 1 et essayez d’élargir la boîte dans toutes les directions. Construisez une liste de boîtes et effacez le 1: s tel que vous les avez utilisé.

Answer 4

Vous recherchez donc la limite rectangulaire des carrés «ON»?
Voulez-vous la limite intérieure ou extérieure?
c'est à dire. La limite doit-elle uniquement comporter des carrés "ON" ou voulez-vous que le rectangle contienne tous les carrés "ON" d'un groupe?

Answer 5

Je devais résoudre un problème similaire, mon algorithme prend en charge les tableaux déchiquetés. Je l'ai lourdement testé et commenté, mais il est plus lent que la suggestion de joel-in-gö: https://stackoverflow.com/a/13802336