Algorithme de placement d'images multiples - Algorithme de collage

Question

Je crée une application pour afficher plusieurs vidéos simultanément (disons 2 à 10 vidéos). Je cherche fondamentalement un algorithme qui peut aider au placement des vidéos sur l'écran. Le problème auquel je suis confronté est que chaque vidéo peut avoir un rapport d'aspect différent, et je vais évidemment devoir redimensionner les vidéos pour les faire tenir à l'écran. Mais je veux les redimensionner et les ajuster de manière à maximiser l'utilisation de l'écran (et à minimiser la distorsion du rapport d'aspect). En outre, je souhaite que l'utilisateur puisse augmenter la taille d'une ou de plusieurs vidéos afin de prendre plus de place sur l'écran. L'algorithme devrait donc être stable, dans la mesure où l'agrandissement d'une vidéo ne fait pas sauter tous les emplacements.

Je pose cette question dans un langage agnostique, et le fait que j'utilise la vidéo n'est pas pertinent, ce problème s'applique également aux images fixes.

Est-ce que quelqu'un connaît un algorithme de placement?

Pour aider à clarifier voici un exemple. J'ai trois vidéos, avec les tailles suivantes. Je veux que la première vidéo occupe environ 50% de l'écran et que les deux dernières vidéos occupent environ 25% de l'écran.

(464, 336) 50% 
(624, 480) 25% 
(608, 336) 25% 

Comment les placer sur l'écran (1024x800) pour y parvenir? Je me suis dit que je diviserais d'abord l'écran en deux et que je correspondrais le mieux à la première vidéo de la moitié supérieure. Ensuite, je diviser la moitié inférieure en deux et adapter les deux vidéos restantes du mieux que je peux.

merci à l'avance

Answer 1

Ceci est une version du problème d'emballage bin http://en.wikipedia.org/wiki/Bin_packing_problem qui est NP-dur, de sorte que vous aurez envie de choisir une heuristique raisonnable.Si vous ne voulez pas que les vidéos sautent lorsque vous en redimensionnez une, vous devrez laisser un tas d'espace mort supplémentaire ou réduire automatiquement les autres.

Sauf si vous avez une bonne raison de l'autoriser, je suggère d'exiger que les rapports d'aspect restent fixes. Une suggestion: commencez par fixer la hauteur de toutes les vidéos, puis utilisez un premier algorithme glouton pour les intégrer. La hauteur initiale sera une fraction entière de la hauteur totale de l'écran. Si quelqu'un redimensionne une vidéo, tout le reste rétrécit de la même valeur de fraction et se déplace pour s'adapter.

Answer 2

racine carrée + logique basée sur l'arrondissement. Si le reste de sqrt est < 0.5, arrondissez le résultat vers le bas, utilisez le résultat en tant que lignes/cols et ajoutez 1 au nombre de lignes ou de colonnes; Si le reste de sqrt est> = 0.5, arrondissez le résultat et utilisez-le comme nombre de lignes/colonnes.

10 videos = 4x3 (3.16; rounded down, so add 1 row or col) 
9 videos = 3x3 (3; abs) 
8 videos = 3x3 (2.82; round up) 
7 videos = 3x3 (2.64; round up) 
6 videos = 3x2 (2.44; round down, so add 1 row or col) 
5 videos = 3x2 (2.23; round down, so add 1 row or col) 
4 videos = 2x2 (2; abs) 
3 videos = 2x2 (1.73; round up) 
2 videos = split screen in half vertically or horizontally (however you'd like) 
1 video = full screen 

Maintenant, c'est de faire toutes les vidéos « carrés », et probablement la meilleure option, car vous compte vraiment ne peut pas facilement les différentes résolutions/rapports qui existent là-bas (à moins qu'il soit statique pour vous). Donc, selon le rapport entre la résolution d'affichage et la résolution vidéo, il y aura de l'espace autour de la grille pour que vous puissiez centrer la grille. Cela dit, une option est pour vous de prendre cet espace "padding" et le diviser par le nombre de lignes (ou cols) et l'utiliser comme un tampon entre les vidéos. Une fois que vous avez le nombre de lignes/colonnes et en supposant que toutes les vidéos doivent être de la même taille, vous divisez simplement la largeur de l'écran par colonnes et la hauteur par lignes et vous avez vos dimensions vidéo. Ensuite, placez les vidéos sur l'écran - évidemment, dans certains cas, certains points de la grille peuvent être vides. Vous pouvez détecter les lignes et les cols couverts par l'espace sur la grille et centrer les vidéos sur cette ligne particulière.

Si vous souhaitez "optimiser" une vidéo, déterminez à l'avance la quantité de "maximisation" de l'espace. Ensuite, soustrayez cette empreinte de pixel de la résolution de l'écran avant de calculer la taille des autres vidéos. Si la maximisation signifie 50% de l'écran, vous soustrayez cette vidéo du nombre de vidéos dans la grille et soustrayez 50% de l'espace des pixels de la résolution d'affichage.

Answer 3

Je pense qu'un Treemap est ce que vous pourriez avoir besoin.

bonne description de l'histoire de l'algorithme here

quantique TreeMaps ALGs commandés, plus pertinents pour votre seach actuelle, here

HTH!