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

Question

Où irais-je chercher des algorithmes qui prennent une grille 2d de valeurs qui sont soit 0 ou 1 en entrée, puis identifient tous les rectangles possibles qui ne se chevauchent pas? Dans une explication plus pratique: je dessine une grille qui est représentée par un certain nombre de carrés, et je souhaite trouver un moyen de combiner autant de carrés adjacents en rectangles que possible, afin de réduire le temps dépensé pour faire du vélo à travers chaque carré et le dessiner.

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

Addendum: Apparemment, ce que je cherche semble être une technique appelée Tesselation. Maintenant, j'ai juste besoin de trouver une bonne description pour ce cas particulier.

Addendum 2: La limite des carrés "1" sera irrégulière et dans certains cas même pas connectée, car la distribution de "1" carrés sera complètement aléatoire. J'ai besoin que ces formes irrégulières soient identifiées et divisées en rectangles réguliers. Pour obtenir le meilleur équilibre entre vitesse et efficacité, il est optimal d'utiliser les données de la grille pour remplir un quad-tree avec chaque noeud ayant une valeur de statut vide/partiellement rempli/rempli.

Answer 1

J'ai fait quelque chose de similaire pour une visualisation voxel rapide et sale de boîtes 3d avec OpenGL. J'ai commencé à partir de la boîte en haut à gauche et stocké le drapeau vide/rempli. Ensuite, j'ai essayé d'étendre le rectangle vers la droite jusqu'à ce que je frappe une boîte avec un drapeau différent. J'ai fait la même chose dans le sens descendant.

Dessinez le rectangle s'il est rempli.

S'il y a des boîtes remaing, répéter récursivement la procédure pour les trois rectangles remaing induits par le dernier rectangle, qui sont à droite, en bas et en bas à droite:

xxxx 1111 
xxxx 1111 
xxxx 1111 

2222 3333 
2222 3333 
2222 3333 

Answer 2

Vous cherchez donc la limite rectangulaire des carrés «ON»?
Voulez-vous la limite intérieure ou extérieure?
ie. La limite doit-elle seulement avoir des carrés «ON» ou voulez-vous que le rectangle contienne tous les carrés «ON» d'un groupe?

Answer 3

Comme vous ne cherchez pas le nombre minimum de carrés, je suggère d'utiliser un compromis qui garde votre algorithme simple. La meilleure solution dépend de vos données, mais une simple alternative consiste simplement à collecter des boîtes le long d'une ligne. I.e.:

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

généreront:

skip 2 
draw 3 
skip 3 
draw 4 
skip 1 

Cela permettra de réduire le nombre d'appels à tirer case sans avoir besoin de la mise en cache (i.e. vous pouvez construire vos boîtes à la volée).

Si vous voulez créer des boîtes plus grandes, je suggère un algorithme de retour en arrière, vous trouverez le premier 1 et essayer d'élargir la boîte dans toutes les directions. Construis une liste de cases et efface les 1: s comme tu les as utilisées.

Answer 4

Jetez un oeil à this article from Dr Dobb's Portal sur la recherche d'un maximum rectangle dans votre situation. C'est une discussion très détaillée d'un algorithme extrêmement efficace, et je pense que le répéter de manière itérative pourrait résoudre votre problème.

Answer 5

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