trouver la plus petite surface contenant tous les rectangles

Ceci est une question d’entrevue.
On nous donne les dimensions de différents rectangles, nous devons trouver l’aire (minimum) du rectangle qui peut les entourer? les rectangles peuvent aussi être tournés.

test case:- input: 3 //number of rectangles 8 8 4 3 3 4 output: 88 11x8: + - - - - - - + + - + | | | | | | | | | | + - + | | + - + | | | | | | | | + - - - - - - + + - + 

j’ai regardé une question similaire posée avant d’ installer des rectangles dans la plus petite surface possible
L’approche ci-dessus examine toutes les possibilités, les rotations et détermine le minimum pour toutes ces possibilités dans tous les cas de configuration.
ne pouvons-nous pas baser un algorithme dans lequel nous trouvons d’abord la sum de l’aire des rectangles, puis la longueur maximale, la largeur?

Il n’y a pas de solution absolue à ce problème, mais il existe plusieurs solutions approximatives, vous pouvez en lire quelques unes ici .

Emballage rectangle optimal sur des repères non carrés :

Étant donné un ensemble de rectangles, notre problème est de trouver tous les rectangles englobants d’aire minimale qui les contiendront sans chevauchement. Nous nous référons à un rectangle englobant comme une boîte englobante. Le problème d’optimisation est NP-difficile , alors que le problème consistant à décider si un ensemble de rectangles peut être emballé dans un cadre de sélection donné est NP-complet , via une réduction de l’empaquetage (bin) (Korf 2003).

Nouvelles améliorations dans l’emballage optimal du rectangle :

Korf [2003] a divisé le problème d’emballage du rectangle en deux sous-problèmes: le problème de la boîte d’encombrement minimale et le problème de confinement. Le premier trouve une boîte englobante de la plus petite surface pouvant contenir un ensemble donné de rectangles, tandis que le second essaie de regrouper les rectangles donnés dans une boîte englobante donnée. L’algorithme qui résout le problème minimal du cadre de sélection appelle l’algorithme qui résout le problème de confinement en tant que sous-programme.

Problème de la zone de délimitation minimale

Un moyen simple de résoudre le problème des boîtes d’encombrement minimales consiste à rechercher les zones minimales et maximales décrivant l’ensemble des boîtes d’encadrement réalisables et potentiellement optimales. Des boîtes englobantes de toutes les dimensions peuvent être générées avec des zones comsockets dans cette plage, puis testées dans un ordre de zone non décroissant jusqu’à ce que toutes les solutions possibles de la plus petite zone soient trouvées. La surface minimale est la sum des surfaces des rectangles donnés. La surface maximale est déterminée par le cadre de sélection d’une solution gloutonne trouvée en définissant la hauteur du cadre de sélection sur celle du rectangle le plus haut, puis en plaçant les rectangles à la première position disponible lors du balayage de gauche à droite. de bas en haut.

Voir aussi Optimal Rectangle Packing: New Results .

Tout d’abord, vous devriez vérifier si le rectangle englobant peut être pivoté ou non. Quoi qu’il en soit, vous pouvez ignorer la condition “rectangles” et résoudre la tâche en points. Vous avez un tableau de points (qui sont des sumts de rectangles). Votre tâche consiste à trouver un rectangle de délimitation avec une surface minimale. Si le rectangle englobant ne peut pas être pivoté, la solution est stupide et présente la complexité O (n).

Tableau généré de rectangles et faire tableau de points, qui sont des sumts de rectangles. Suivant est simple:

 long n; // Number of vertexes point arr[SIZE]; //Array of vertexes long minX = MAXNUMBER, minY = MAXNUMBER, maxX = -MAXNUMER, maxY = -MAXNUMBER; for (long i = 0; i < 4 * n; i++) { minX = MIN(minX, arr[i].x); minY = MIN(minY, arr[i].y); maxX = MIN(maxX, arr[i].x); maxY = MIN(maxY, arr[i].y); } long width = maxX - minX, height = maxY - minY; printf("%ddX%ld", width, height); 

Une autre tâche si le rectangle peut être pivoté. Alors vous devriez d'abord:

  1. Construire un polygone convexe minimum de tous les points du rectangle. Vous pouvez utiliser n'importe lequel des algorithmes existants. Complexité O (n log n). Comme exemple "Graham's Scan": http://en.wikipedia.org/wiki/Graham%27s_scan
  2. Utilisez un algorithme simple pour un polygone convexe. Lien: http://cgm.cs.mcgill.ca/~orm/maer.html

Lien vers votre tâche dans le wiki: http://en.wikipedia.org/wiki/Minimum_bounding_rectangle