En représentant le rectangle par (x, y, w), ou (x, y) est le point de base du rectangle, et w la largeur du rectangle, on obtient un ensemble de contraintes et une valeur à maximiser: w*w
Comme maximiser w*w (fonction strictement croissante) revient a maximiser w, le problèmes est un problème de programmation linéaire.
On doit donc pouvoir le résoudre avec l'algorithme du simplex.
Ca doit se trouver une lib qui implémente cet algo, non?
Bon, ça fait pas mal de temps que j'ai pas fait ce genre de choses, donc il y a peut-être des erreurs dans mon raisonnement...
# simplex?
Posté par パパフラクス . En réponse au message Algo / Determiner le plus grand rectangle d'une région. Évalué à 3.
Comme maximiser w*w (fonction strictement croissante) revient a maximiser w, le problèmes est un problème de programmation linéaire.
On doit donc pouvoir le résoudre avec l'algorithme du simplex.
Ca doit se trouver une lib qui implémente cet algo, non?
Bon, ça fait pas mal de temps que j'ai pas fait ce genre de choses, donc il y a peut-être des erreurs dans mon raisonnement...