Discussion :

[insane97]

Bonjour à tous,
Pour les besoins d'un projet personnel avec opengl, j'aurais besoin d'un algorithme pour me caser des carrés dans un rectangle, tel que le rectangle soit entierement rempli (de carré).
Je dispose donc d'un rectangle de dimensions H et L.
Je dispose tout aussi du nombre de carrée N à caser dans le rectangle (qui peut aussi être separée en nombre de carré sur la hauteur et la longeur (Nh et Nl) ?)
Ce nombre peut être variable, c'est à dire si le rectangle n'est pas rempli avec ce N la on peut en prendre un autre, et est bien evidemment entier.
Donc je cherche A, la longeur du cotée du carrée pour qu'il respecte la condition ?
Qq'un pourrait m'aiguiller ?
Cordialement.

[sologne]

Bonjour,

Voici quelques idées qui me viennent en lisant ton problème.
Tout d’abord on peu chercher le carré "théoriquement" bon en faisant :
c = racinecarre(L*H/n), sauf que tu ne pourras pas paver concrètement ton rectangle avec ce carré (hormis un coup de chance ...)

Pour que le pavage soit possible, il faut que le coté du carré soit un diviseur du pgcd de H et L.

Si ton rectangle fait L = 30 et H = 20 Alors
Liste des cotés possibles = {Pgcd(20,30) = 10 puis, 5,2,1)}
FinSi

Ainsi ton rectangle de 30 par 20 (600 unités carres) peux être pavé de :
6 carrés de 10 de coté (10*10*6 = 600) ou
24 carrés de 5 de coté (5*5*24 = 600) ou
150 carrés de 2 de coté (2*2*150 = 600) ou
600 carrés de 1 de coté (1*1*600 = 600) (cas trivial)

Si tu veux faire un pavage du rectangle avec des carrés qui ont tous la même taille alors il faut que ton N appartienne à la Liste des cotés possibles.

Le pavage doit-il être avec des carrés de taille identique ?
Le coté d'un carré doit-il être entier ? (approche proposée ici) ou peut-il être réel ?
Peut-il y avoir un "résidu" dans le pavage, je pense à la construction d'une suite convergente dont le coté diminue progressivement, ...
Existe-t-il une relation de taille entre les différents carrés (si taille variable ?)

J'espère t'apporter plus de réponses que je ne te pose de questions.

Bon Courage

[prgasp77]

Bonjour,

il va falloir quelques conditions sur H et L, car dans le cas quelconque, il n'est pas possible de paver un rectangle d'un nombre fini de carrés de même taille. En effet, si un tel pavage existe, c'est à dire tel que n carrés ( carrés sur la hauteur, et sur la longueur) de cotés c remplissent le rectangle en question, alors


Autrement dit, un tel pavage n'existe que si H et L sont tous deux rationnels ou tous deux irrationnels (enfin je crois). Il te faut donc faire des hypothèses sur ces nombres ; la résolution du problème viendra en fonction desdites hypothèses.

Cdlt,

[insane97]

Merci pour vos deux reponses.

Pour te répondre @sologne, oui les carrés ont tous la même dimension.
Le coté des carrés est un réel.
Et pour le pavage progressive, pourquoi pas ?

@prgasp77, j'ai pas tout capté (les maths et moi blabla.. ).
Si j'ai bien compris selon le nombre de carré que je voudrais, il devrait y avoir une relation entre L et H,
On ne pourrais pas obtenir les N (Nl et Nh) en fonction de L et H (cas d'une image).

En faite, pour vous donner plus d'elements, je souhaiterais reproduire ceci:
http://koalastothemax.com
Mais en opengl

[prgasp77]

Si j'ai bien compris selon le nombre de carré que je voudrais, il devrait y avoir une relation entre L et H,
On ne pourrais pas obtenir les N (Nl et Nh) en fonction de L et H (cas d'une image).

Raté ! Je dis que pour certains couples (H,L), il n'y a pas de solution.

En faite, pour vous donner plus d'elements, je souhaiterais reproduire ceci:
http://koalastothemax.com
Mais en opengl

Il dit qu'il voit pas le rapport. Ici on part d'un carré qu'on subdivise récursivement en quatre quarts égaux.