我需要一种算法，可以将任意大小的 n 个矩形放入一个较大的矩形中，并最小化其面积

Question

我需要一个算法，它需要 n 个任意大小的矩形，并计算一个足够大的矩形来容纳它们，最小化其面积，使浪费的面积最小，并返回所有较小的矩形的位置内的矩形。

我需要这个来实现的具体任务是在一个精灵表编译器中，它会获取单独的 PNG 文件并生成一个包含所有图像的大 PNG，因此可以从该表面blitted运行时间。

一个很好的功能是它针对特定的给定宽度/高度比，但这不是强制性的。

我更喜欢可以移植到另一种语言的简单、通用的代码。

Answer 1

这是我根据自己的需要整理的。 T 参数是您想要与结果关联的任何对象（将其视为 Tag 属性）。它接受一个大小列表并返回一个排列的矩形列表

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