どのようなサイズのn個の長方形にも対応できるアルゴリズムが必要です。面積を最小限に抑えた大きなサイズの長方形にするには

Question

nの長方形のアルゴリズムを必要とします。面積が最小になるように、また、すべての小さな四角形の位置を返します。

私が実装し、これを必要とする特定のタスクは、個別のPNGファイルを取ると、それにすべての画像を持つ大規模なPNGになるだろうスプライトシートコンパイラでは、その個々のフレームは、実行時にこの表面からをブリットすることができています時間。

特長は、指定された幅/高さの特定の比率を目指すことですが、必須ではありません。

私は別の言語に移植できるシンプルな汎用コードを好むでしょう。

Answer 1

Petruza、

私はこの記事で開始します： http://www.codeproject.com/KB/web-image/rectanglepacker.aspx#basic

それは問題空間の偉大な説明を持っているあなたの具体的な使用（スプライトパッキン）に適用されます。アルゴリズムについても詳しく説明しており、記事の最後にサンプルのC＃コードがあります。

ハッピーコーディング。

Answer 2

これは自分の必要に合わせてまとめたものです。 Tパラメータは、結果に関連付けたいオブジェクト（Tagプロパティのように考える）です。サイズのリストを取得し、整列されたRectのリストを返します。

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))) }; 
    } 
}