Mathématiques appliquées à la photo numérique.

[Anonyme]

Bonjour à tous,

J'ai un problème très concret, et je voudrais être sûr d'avoir la
meilleure solution.
Voici les données :

J'aimerai imprimer 11 photos (chacune de résolution 1600*1200, soit à
titre indicatif 16,93*22,58cm) sur une seule feuille A4 (21*29,7cm) de
telle sorte qu'il y ait le moins de blanc possible sur la feuille
imprimée.

J'ai commencé à modéliser le problème de la façon suivante :
L'aire de la feuille A4 est de 21*29.7= 623.7 cm²
Soit Y l'aire des 11 photos.
Soit Z l'espace blanc restant sur la feuille. Z= 623.7 - Y.

BUT : Trouver, tel que Z soit minimal :
1) la taille optimale des photos (tout en respectant leur proportion).
2) La disposition idéale sur la feuille

D'avance, merci de votre aide, je serai très curieux de connaître la
solution !

[Anonyme]

Le 08/09/2004 20:56, Cl-point-d'interrogation-ment a écrit :
>
> J'aimerai[s] imprimer 11 photos (chacune de résolution 1600*1200, soit à
> titre indicatif 16,93*22,58cm) sur une seule feuille A4 (21*29,7cm) [...]

1) Je suppose puisque tu ne l'as pas précisé que les photos sont toutes
les onze dans le même sens (portrait ou paysage). Est-ce que la feuille
A4 a la même orientation que les photos, est-ce qu'au contraire elle a
l'autre orientation, ou bien est-ce que les deux choix sont possibles,
selon ce qui économise le plus d'espace ?

> [...]
>
> BUT : Trouver, tel que Z soit minimal :
> 1) la taille optimale des photos (tout en respectant leur proportion).

2) Les onze photos doivent-elles avoir la même taille, ou bien peut-on
en avoir certaines plus grandes que d'autres ?

> 2) La disposition idéale sur la feuille
>
> D'avance, merci de votre aide, je serai très curieux de connaître la
> solution !

Si la réponse à ma deuxième question est « toutes de la même taille »,
alors je pense que si tu peux mettre 11 photos tu pourras aussi bien en
mettre 12, vraisemblablement en 4 rangées de 3 ou en 3 rangées de 4.

Les dimensions des photos sont proportionnelles à 4x3 (4*400 x 3*400).
Selon que tu en mettes 3 ou 4 par rangée, cela tient donc soit dans un
carré (12 x 12), soit dans un rectangle au format 16 x 9.

Or ta feuille a comme proportions 21 x 21.sqrt(2). Le carré peut être
étendu jusqu'à 21 cm de côté, ce qui fait une surface perdue de 21 fois
21.(sqrt(2) - 1), soit 21 fois 8,7 donc environ 183 cm². Quant au
rectangle 16 sur 9, puisque 16/9 est plus grand que sqrt(2), c'est le 16
qui doit être étendu jusqu'à 21.sqrt(2). Dans ce cas, la place perdue
vaut 21¹x(sqrt(2) - 9/8), soit 127,54.

Dans les deux cas, il faut bien sûr rajouter la place perdue par
l'absence de 12e photo, mais cela ne change rien au fait que le format
16 sur 9 est préférable au format carré.

[Anonyme]

Salut à tous, salut Olivier,

Merci pour ta réponse. J'aurais effectivement opté intuitivement pour
le format paysage.
Pour répondre plus précisément aux questions que tu poses, je pensais
découper les photos ensuite. Donc, peu importe le format portrait ou
paysage des photos, et l'orientation de la feuille A4 est bien un
élément clé à déterminer, et donc pas fixé d'avance. Tous les choix
sont donc possible (même pourquoi pas mettre une photo en diagonale
sur la feuille).
Les onzes photos doivent aussi avoir toutes la même taille.

Cela dit, -tu vas me trouver exichiant, mais on est dans un forum de
maths, non ? - il ne me semble pas que ce que tu proposes soit une
démonstration (dans le sens fort) que c'est bien la solution optimale.
Qu'est-ce qui m'assure qu'une configuration "bizarre", avec des photos
en diagonale par exemple, ne pourrait pas être meilleure ?

Merci encore et à bientôt,
Clément.


Olivier Miakinen wrote in message news:...
> Le 08/09/2004 20:56, Cl-point-d'interrogation-ment a écrit :[color=green]
> >
> > J'aimerai[s] imprimer 11 photos (chacune de résolution 1600*1200, soit à
> > titre indicatif 16,93*22,58cm) sur une seule feuille A4 (21*29,7cm) [...]
>
> 1) Je suppose puisque tu ne l'as pas précisé que les photos sont toutes
> les onze dans le même sens (portrait ou paysage). Est-ce que la feuille
> A4 a la même orientation que les photos, est-ce qu'au contraire elle a
> l'autre orientation, ou bien est-ce que les deux choix sont possibles,
> selon ce qui économise le plus d'espace ?
>
> > [...]
> >
> > BUT : Trouver, tel que Z soit minimal :
> > 1) la taille optimale des photos (tout en respectant leur proportion).
>
> 2) Les onze photos doivent-elles avoir la même taille, ou bien peut-on
> en avoir certaines plus grandes que d'autres ?
>
> > 2) La disposition idéale sur la feuille
> >
> > D'avance, merci de votre aide, je serai très curieux de connaître la
> > solution !
>
> Si la réponse à ma deuxième question est « toutes de la même taille »,
> alors je pense que si tu peux mettre 11 photos tu pourras aussi bien en
> mettre 12, vraisemblablement en 4 rangées de 3 ou en 3 rangées de 4.
>
> Les dimensions des photos sont proportionnelles à 4x3 (4*400 x 3*400).
> Selon que tu en mettes 3 ou 4 par rangée, cela tient donc soit dans un
> carré (12 x 12), soit dans un rectangle au format 16 x 9.
>
> Or ta feuille a comme proportions 21 x 21.sqrt(2). Le carré peut être
> étendu jusqu'à 21 cm de côté, ce qui fait une surface perdue de 21 fois
> 21.(sqrt(2) - 1), soit 21 fois 8,7 donc environ 183 cm². Quant au
> rectangle 16 sur 9, puisque 16/9 est plus grand que sqrt(2), c'est le 16
> qui doit être étendu jusqu'à 21.sqrt(2). Dans ce cas, la place perdue
> vaut 21¹x(sqrt(2) - 9/8), soit 127,54.
>
> Dans les deux cas, il faut bien sûr rajouter la place perdue par
> l'absence de 12e photo, mais cela ne change rien au fait que le format
> 16 sur 9 est préférable au format carré.[/color]

[Anonyme]

Le 09/09/2004 20:27, Cl?ment a écrit :
>
> Pour répondre plus précisément aux questions que tu poses, je pensais
> découper les photos ensuite. Donc, peu importe le format portrait ou
> paysage des photos, et l'orientation de la feuille A4 est bien un
> élément clé à déterminer, et donc pas fixé d'avance. Tous les choix
> sont donc possibles

En effet, cela augmente les possibilités. Par exemple, en prenant 3x4
comme dimensions des photos, j'avais déjà proposé de les disposer dans
un carré 12x12 ou dans un rectangle 16x9, avec un rectangle de 3x4 de
perdu. Mais si tu peux en mettre trois dans un sens, et deux rangées de
quatre dans l'autre, tout tient dans un rectangle de 12x11, sans perte.

Je vais chercher dans cette voie, et je te tiens au courant.

> (même pourquoi pas mettre une photo en diagonale
> sur la feuille).

Mathématiquement, pourquoi pas ? Mais au niveau de la résolution de la
photo, je crains que tu y perdes.

> Cela dit, -tu vas me trouver exichiant, mais on est dans un forum de
> maths, non ? - il ne me semble pas que ce que tu proposes soit une
> démonstration (dans le sens fort) que c'est bien la solution optimale.
> Qu'est-ce qui m'assure qu'une configuration "bizarre", avec des photos
> en diagonale par exemple, ne pourrait pas être meilleure ?

En effet, ce n'était pas une démonstration, quoique si tu imposes que
toutes les photos aies la même orientation (ce qui n'est pas le cas, je
m'en rends compte maintenant), eh bien cette démonstration n'est pas
très difficile.

En revanche, en acceptant des positions en diagonale, le problème
général est suffisamment complexe pour que l'on ne sache pas le
résoudre, même pour des carrés dans un carré. Voir par exemple
. Coïncidence, pour des
nombres de carrés compris entre 1 et 25, celui dont la solution est la
plus complexe est avec 11 carrés (nécessite la résolution d'une équation
du 4e degré).

> Merci encore et à bientôt,
[ suivi par l'intégralité de mon article ]

Il serait sympa d'apprendre à alléger un peu tes articles, en supprimant
les choses inutiles. D'excellents conseils se trouvent sur la page
suivante:

--
Olivier

[Anonyme]

Le 10/09/2004 00:07, Olivier Miakinen a écrit :
>
> En revanche, en acceptant des positions en diagonale, le problème
> général est suffisamment complexe pour que l'on ne sache pas le
> résoudre, même pour des carrés dans un carré. Voir par exemple
> .

Voir aussi

[Anonyme]

Le 09/09/2004 20:27, Cl?ment a écrit :
>
> Cela dit, -tu vas me trouver exichiant, mais on est dans un forum de
> maths, non ? - il ne me semble pas que ce que tu proposes soit une
> démonstration (dans le sens fort) que c'est bien la solution optimale.
> Qu'est-ce qui m'assure qu'une configuration "bizarre", avec des photos
> en diagonale par exemple, ne pourrait pas être meilleure ?

Bien, je vais essayer d'être le plus précis possible dans mes
démonstrations mathématiques. Allons-y, je commence...

-+-+-+-

Tes photos sont de résolution 1600x1200, elles sont donc constituées
d'un rectangle de 4x3 carrés de résolution 400x400. Soit u l'unité de
longueur d'un de ces carrés de 400x400 pixels : on cherche à maximiser u
en organisant au mieux les photos.

On peut déjà donner un maximum absolu pour u, en constatant que les 11
photos ne peuvent pas couvrir une surface supérieure à celle de la
feuille de 21 cm sur 29,7 (= 21.sqrt(2)) cm.
11 photos * (4*3) * u² l). Dans un premier temps, on considèrera
que L et l ne sont pas forcément des nombres entiers.

Comme je l'écrivais dans un précédent article, la résolution de ce genre
de problème est très difficile si on accepte que les bords des photos ne
soient pas parallèles aux côtés du rectangle. J'ajoutais que la qualité
des photos risquait de s'en ressentir. Comme par ailleurs cela ne
pourrait pas faire gagner plus de 2,8 mm sur la longueur des photos
(comparer le maximum absolu avec la solution finalement trouvée), je
considère qu'on peut ignorer le cas des photos en diagonale.

-+-+-+-

Prouvons maintenant que l'on peut se limiter au cas où L et l sont
entiers. Pour cela, imaginons que l'on trace, à partir du coin en bas à
droite du rectangle Lxl, une grille de lignes horizontales et verticales
espacées de la longueur u.

Supposons qu'il existe au moins une photo dont le bord gauche ne
coïncide pas avec une des lignes de la grille. Soit la plus à gauche de
ces photos (ou l'une des plus à gauche s'il y en a plusieurs). Puisque
aucune photo non-alignée n'est plus à gauche que celle-ci, c'est qu'il y
a un espace vide à gauche de cette photo, et qu'on peut la déplacer vers
la gauche jusqu'à ce qu'elle soit alignée sur la grille, sans changer
les dimensions du rectangle Lxl.

Tant qu'il existe encore au moins une photo non alignée à gauche, on
recommence la manip. Il arrive un moment (après au maximum onze
déplacements) où toutes les photos sont alignées à gauche (et par
conséquent à droite aussi).

Maintenant on fait la même chose, mais en déplaçant *vers le bas* les
photos qui ne seraient pas alignées sur les lignes horizontales de la
grille.

Au final, si L et l n'étaient pas des nombres entiers, on peut les
réduire jusqu'au nombre entier inférieur, les photos restant à
l'intérieur du rectangle.

-+-+-+-

Récapitulons : nous devons trouver un rectangle de côtés entiers L et l
dans lequel placer onze photos de dimensions 4x3, chaque photo occupant
exactement 12 petits carrés *entiers* de la grille rectangulaire Lxl.

Ce rectangle étant agrandi au maximum, soit il s'étend sur toute la
largeur de la feuille, auquel cas on a l.u = 21 cm, soit il s'étend sur
toute la longueur, auquel cas on a L.u = 21.sqrt(2) cm.

On veut donc maximiser :
u = min(21/l, 21.sqrt(2)/L)
= 21.sqrt(2) . min( 1/L, 1/(l.sqrt(2)) )
= 21.sqrt(2) / max(L, l.sqrt(2))

Il faut soit minimiser L tout en le gardant supérieur à l.sqrt(2), soit
minimiser l tout en gardant l.sqrt(2) supérieur à L. Bien sûr, on a
comme contrainte supplémentaire que L*l est supérieur ou égal à 132
(11 photos de 12 u²).

-+-+-+-

Premier cas : L > l.sqrt(2)
Le plus petit L possible vaut 15, l pouvant valoir 9 ou 10. On peut
d'ailleurs trouver une façon de placer les 11 photos 4x3 dans un
rectangle 15x9 (*). Dans ce cas, on a u = 21.sqrt(2)/15 = 1,98 cm.

Deuxième cas : l.sqrt(2) > L
Le plus petit l possible vaut 10, L valant obligatoirement 14. Là encore
on peut trouver une façon de placer les 11 photos 4x3 dans un rectangle
14x10 (*). Dans ce cas, on a u = 21/10 = 2,1 cm, ce qui est le meilleur
résultat annoncé au début de cet article.

(*) Je te laisse retrouver toi-même les dispositions de 11 rectangles
4x3 dans un rectangle de dimensions 15x9 ou 14x10 respectivement. Cela
m'évitera de devoir tenter de l'art ASCII dans cet article.

-+-+-+-

Voilà, c'est tout, sauf si tu as des questions à poser. Merci pour cet
intéressant problème : tu reviens quand tu veux !

--
Olivier Miakinen

[Anonyme]

Le 10/09/2004 15:17, Olivier Miakinen a écrit :
>
> Voilà, c'est tout, sauf si tu as des questions à poser. Merci pour cet
> intéressant problème : tu reviens quand tu veux !

J'allais oublier... deux choses :

1) Avant de répondre à mon très long article, merci de *vraiment* lire
la page que je t'ai
déjà signalée. Si tu cites la totalité sans faire de coupures, ou bien
si au contraire tu ne cites rien, pas même mon nom, alors c'est sûr que
je vais faire la gueule : pense que la lecture de cette page te prendra
beaucoup moins de temps que celui que j'ai passé à répondre à ta question.

2) Pourquoi avoir mis un point d'interrogation à la place du « é » de
ton prénom ? Si tu as peur de problèmes d'encodage, autant mettre un
« e » sans accent, mais sinon le « é » sera correctement interprêté par
la plupart des logiciels de news actuels.

Cordialement,
--
Olivier Miakinen
Oh la belle bleue ! Oh la belle verte ! Oh la belle signature !

[Anonyme]

google@philosophons.com (Cl?ment) wrote in message news:...
> Salut à tous, salut Olivier,
>
> Merci pour ta réponse. J'aurais effectivement opté intuitivement pour
> le format paysage.
> Pour répondre plus précisément aux questions que tu poses, je pensais
> découper les photos ensuite. Donc, peu importe le format portrait ou
> paysage des photos, et l'orientation de la feuille A4 est bien un
> élément clé à déterminer, et donc pas fixé d'avance. Tous les choix
> sont donc possible (même pourquoi pas mettre une photo en diagonale
> sur la feuille).
> Les onzes photos doivent aussi avoir toutes la même taille.
>
> Cela dit, -tu vas me trouver exichiant, mais on est dans un forum de
> maths, non ? - il ne me semble pas que ce que tu proposes soit une
> démonstration (dans le sens fort) que c'est bien la solution optimale.
> Qu'est-ce qui m'assure qu'une configuration "bizarre", avec des photos
> en diagonale par exemple, ne pourrait pas être meilleure ?
>
> Merci encore et à bientôt,
> Clément.
>

Puisque tu vas découper les photos après, l'orientation ne rentre pas
en compte dans l'arrangement des photos. Il me semble que la meilleure
solution est la suivante : pour une feuille A4 format portrait,
positionner 9 photos format portrait en 3*3 et positionner les deux
dernières photos en dessous des 9 autres, au format paysage. Si la
feuille est de taille (21, 21*sqrt(2)) et les photos de taille (t,
4/3*t) alors pour faire rentrer les photos il faut que 3*t <= 21 et
que 5*t <= 21*sqrt(2) (3 largeurs de photos dans la largeur de la
feuille et 3 hauteurs et une largeur dans la hauteur de la feuille).
La 2ème inégalité est la plus contraignante; on obtient donc t =
21*sqrt(2)/5, soit t = 5,94 cm environ. Avec cette config les photos
couvrent 83% de la surface de la feuille, ce qui n'est pas trop mal;
cependant je ne sais pas si c'est la configuration optimale.

Laurent

[Anonyme]

Le 10/09/2004 16:34, Laurent Leconte a écrit :
>
> [...] pour une feuille A4 format portrait, positionner 9 photos
> format portrait en 3*3 et positionner les deux dernières photos en
> dessous des 9 autres, au format paysage. [...]

C'est le premier des deux cas que j'envisageais dans mon article.

> Avec cette config les photos couvrent 83% de la surface de la
> feuille, ce qui n'est pas trop mal; cependant je ne sais pas si c'est
> la configuration optimale.

Elle n'est pas optimale, puisque le deuxième cas envisagé dans mon
article fait mieux : dans cette autre configuration, les photos
couvrent 93 % de la surface de la feuille.

[Anonyme]

Bonjour Olivier,

Merci pour tous ces liens, c'est fort intéressant. Je ne pensais pas
tomber sur un problème aussi difficile, c'est passionnant !

En ce qui concerne les photos en diagonale, je ne vois pas pour quelle
raison cela changerait la résolution de la photo.

> Mais si tu peux en mettre trois dans un sens, et deux rangées de
> quatre dans l'autre, tout tient dans un rectangle de 12x11, sans perte.
> Je vais chercher dans cette voie, et je te tiens au courant.

C'est une idée qui permet effectivement de gagner de la place... mais
pratiquement, elle n'est pas mieux que la solution qui consiste à
mettre 2 rangées de 4 et 1 rangée de 3 (quand nous disposons d'une
feuille A4). Ca rend simplement l'espace libre "plus propre".


> si tu imposes que toutes les photos aies la même orientation
> (ce qui n'est pas le cas, je m'en rends compte maintenant),
> eh bien cette démonstration n'est pas très difficile.

Je serais tout de même intéressé de voir cette démonstration, pour
voir plus précisément comment on modélise le problème entièrement, et
surtout comment on prouve que la solution est optimale. Cela dit, si
tu y arrives aussi en autorisant les photos à avoir 2 orientations
(paysage ou portrait), je suis aussi preneur

Salutations,
Clément.

P.S. : Je constate que je ne suis pas le seul à semer un peu
l'anarchie dans les messages de ce newsgroup, mais je vais faire des
effort . Mon post a été divisé en 2, sans doute à cause de problèmes
d'accents...

P.S.2: J'ai bien envie de parler de tout ça à Jean-Paul Delahaye, je
suis sûr que ça l'amuserait de faire un petit article là-dessus dans
un Pour la Science

[Anonyme]

Olivier Miakinen wrote in message news:

> Bien, je vais essayer d'être le plus précis possible dans mes
> démonstrations mathématiques. Allons-y, je commence...
[...]
> Voilà, c'est tout, sauf si tu as des questions à poser. Merci pour cet
> intéressant problème : tu reviens quand tu veux !

Nos messages se sont croisés ne tiens donc pas forcément compte de ma
dernière réponse. En tous cas, merci beaucoup pour tout ce
développement. Je vais essayer de le comprendre, et je ne manquerai
pas de reposter un message si j'ai des questions.

Salutations,
Clément.

[Anonyme]

Le 10/09/2004 20:03, Cl?ment a écrit :
>
> [...] Je vais essayer de le comprendre, et je ne manquerai
> pas de reposter un message si j'ai des questions.

N'hésite pas non plus à publier un message de conclusion si tu n'as plus
de question, juste pour dire que le fil est clos.

Par ailleurs, je voulais te remercier pour ta façon de citer : c'est
beaucoup plus agréable ainsi.