J'ai besoin d'un algorithme qui peut adapter n rectangles de toute taille dans un plus grand minimisant sa zone

Question

J'ai besoin d'un algorithme qui prendrait n rectangles de toutes tailles, et calculer un rectangle assez grand pour les adapter tous, en minimisant son zone de sorte que la zone gaspillée est minimale, et aussi de retourner la position de tous les petits rectangles à l'intérieur.

La tâche spécifique je en ai besoin pour mettre en œuvre sur est dans un compilateur de feuille de sprite qui prendrait des fichiers PNG individuels et de faire un grand PNG avec toutes les images, donc des images individuelles peuvent être blittée de cette surface à l'exécution temps.

Une caractéristique intéressante serait qu'elle vise un rapport largeur/hauteur donné, mais ce n'est pas obligatoire.

Je préférerais un code générique simple que je peux transférer vers une autre langue.

Answer 1

Petruza,

Je commencerais par cet article: http://www.codeproject.com/KB/web-image/rectanglepacker.aspx#basic

Il a une grande explication de l'espace de problème tel qu'il est appliqué à votre utilisation spécifique (emballage Sprite). Il décrit également l'algorithme en détail, et il y a un exemple de code C# au bas de l'article.

Bonne codification.

Answer 2

C'est ce que j'ai mis ensemble pour mes propres besoins. Le paramètre T est l'objet que vous voulez associer aux résultats (pensez-y comme la propriété Tag). Il faut une liste de tailles et retourne une liste de Rects qui sont arrangés

static class LayoutHelper 
{ 

    /// <summary> 
    /// Determines the best fit of a List of Sizes, into the desired rectangle shape 
    /// </summary> 
    /// <typeparam name="T">Holder for an associated object (e.g., window, UserControl, etc.)</typeparam> 
    /// <param name="desiredWidthToHeightRatio">the target rectangle shape</param> 
    /// <param name="rectsToArrange">List of sizes that have to fit in the rectangle</param> 
    /// <param name="lossiness">1 = non-lossy (slow). Greater numbers improve speed, but miss some best fits</param> 
    /// <returns>list of arranged rects</returns> 
    static public List<Tuple<T, Rect>> BestFitRects<T>(double desiredWidthToHeightRatio, 
     List<Tuple<Size, T>> rectsToArrange, int lossiness = 10) 
    { 
     // helper anonymous function that tests for rectangle intersections or boundary violations 
     var CheckIfRectsIntersect = new Func<Rect, List<Rect>, double, bool>((one, list, containerHeight) => 
     { 
      if (one.Y + one.Height > containerHeight) return true; 
      return list.Any(two => 
      { 
       if ((one.Top > two.Bottom) || 
        (one.Bottom < two.Top) || 
        (one.Left > two.Right) || 
        (one.Right < two.Left)) return false; // no intersection 
       return true; // intersection found 
      }); 
     }); 

     // helper anonymous function for adding drop points 
     var AddNewPotentialDropPoints = new Action<SortedDictionary<Point, object>, Rect>(
      (potentialDropPoints, newRect) => 
      { 
       // Only two locations make sense for placing a new rectangle, underneath the 
       // bottom left corner or to the right of a top right corner 
       potentialDropPoints[new Point(newRect.X + newRect.Width + 1, 
        newRect.Y)] = null; 
       potentialDropPoints[new Point(newRect.X, 
        newRect.Y + newRect.Height + 1)] = null; 
      }); 

     var sync = new object(); 
     // the outer boundary that limits how high the rectangles can stack vertically 
     var containingRectHeight = Convert.ToInt32(rectsToArrange.Max(a => a.Item1.Height)); 
     // always try packing using the tallest rectangle first, working down in height 
     var largestToSmallest = rectsToArrange.OrderByDescending(a => a.Item1.Height).ToList(); 
     // find the maximum possible container height needed 
     var totalHeight = Convert.ToInt32(rectsToArrange.Sum(a => a.Item1.Height)); 
     List<Tuple<T, Rect>> bestResults = null; 
     // used to find the best packing arrangement that approximates the target container dimensions ratio 
     var bestResultsProximityToDesiredRatio = double.MaxValue; 
     // try all arrangements for all suitable container sizes 
     Parallel.For(0, ((totalHeight + 1) - containingRectHeight)/lossiness, 
      //new ParallelOptions() { MaxDegreeOfParallelism = 1}, 
      currentHeight => 
     { 
      var potentialDropPoints = new SortedDictionary<Point, object>(Comparer<Point>.Create((p1, p2) => 
      { 
       // choose the leftmost, then highest point as earlier in the sort order 
       if (p1.X != p2.X) return p1.X.CompareTo(p2.X); 
       return p1.Y.CompareTo(p2.Y); 
      })); 
      var localResults = new List<Tuple<T, Rect>>(); 
      // iterate through the rectangles from largest to smallest 
      largestToSmallest.ForEach(currentSize => 
      { 
       // check to see if the next rectangle fits in with the currently arranged rectangles 
       if (!potentialDropPoints.Any(dropPoint => 
       { 
        var workingPoint = dropPoint.Key; 
        Rect? lastFittingRect = null; 
        var lowY = workingPoint.Y; 
        var highY = workingPoint.Y - 1; 
        var boundaryFound = false; 
        // check if it fits in the current arrangement of rects 
        do 
        { 
         // create a positioned rectangle out of the size dimensions 
         var workingRect = new Rect(workingPoint, 
           new Point(workingPoint.X + currentSize.Item1.Width, 
           workingPoint.Y + currentSize.Item1.Height)); 
         // keep moving it up in binary search fashion until it bumps the higher rect 
         if (!CheckIfRectsIntersect(workingRect, localResults.Select(a => a.Item2).ToList(), 
          containingRectHeight + (currentHeight * lossiness))) 
         { 
          lastFittingRect = workingRect; 
          if (!boundaryFound) 
          { 
           highY = Math.Max(lowY - ((lowY - highY) * 2), 0); 
           if (highY == 0) boundaryFound = true; 
          } 
          else 
          { 
           lowY = workingPoint.Y; 
          } 
         } 
         else 
         { 
          boundaryFound = true; 
          highY = workingPoint.Y; 
         } 
         workingPoint = new Point(workingPoint.X, lowY - (lowY - highY)/2); 
        } while (lowY - highY > 1); 

        if (lastFittingRect.HasValue) // found the sweet spot for this rect 
        { 
         var newRect = lastFittingRect.Value; 
         potentialDropPoints.Remove(dropPoint.Key); 
         // successfully found the best location for the new rectangle, so add it to the pending results 
         localResults.Add(Tuple.Create(currentSize.Item2, newRect)); 
         AddNewPotentialDropPoints(potentialDropPoints, newRect); 
         return true; 
        } 
        return false; 
       })) 
       { 
        // this only occurs on the first square 
        var newRect = new Rect(0, 0, currentSize.Item1.Width, currentSize.Item1.Height); 
        localResults.Add(Tuple.Create(currentSize.Item2, newRect)); 
        AddNewPotentialDropPoints(potentialDropPoints, newRect); 
       } 
      }); 
      // layout is complete, now see if this layout is the best one found so far 
      var layoutHeight = localResults.Max(a => a.Item2.Y + a.Item2.Height); 
      var layoutWidth = localResults.Max(a => a.Item2.X + a.Item2.Width); 
      var widthMatchingDesiredRatio = desiredWidthToHeightRatio * layoutHeight; 
      double ratioProximity; 
      if (layoutWidth < widthMatchingDesiredRatio) 
       ratioProximity = widthMatchingDesiredRatio/layoutWidth; 
      else 
       ratioProximity = layoutWidth/widthMatchingDesiredRatio; 
      lock (sync) 
      { 
       if (ratioProximity < bestResultsProximityToDesiredRatio) 
       { 
        // this layout is the best approximation of the desired container dimensions, so far 
        bestResults = localResults; 
        bestResultsProximityToDesiredRatio = ratioProximity; 
       } 
      } 
     }); 
     return bestResults ?? new List<Tuple<T, Rect>>() {Tuple.Create(rectsToArrange[0].Item2, 
      new Rect(new Point(0, 0), new Point(rectsToArrange[0].Item1.Width, rectsToArrange[0].Item1.Height))) }; 
    } 
}