I need an algorithm that can fit n rectangles of a

2019-07-25 12:00发布

问题:

I need an algorithm that would take n rectangles of any sizes, and calculate a rectangle big enough to fit them all, minimizing its area so the wasted area is minimum, and also returning the position of all the smaller rectangles within.

The specific task I need this to implement on is in a sprite sheet compiler that would take individual PNG files and make a large PNG with all the images in it, so individual frames can be blitted from this surface at run time.

A nice to have feature would be that it aims to a specific given width/height ratio, but it's not mandatory.

I'd prefer simple, generic code I can port to another language.

回答1:

Petruza,

I would start with this article: http://www.codeproject.com/KB/web-image/rectanglepacker.aspx#basic

It has a great explanation of the problem space as applied to your specific usage (Sprite packing). It also describes the algorithm in detail, and there is sample C# code at the bottom of the article.

Happy coding.



回答2:

This is what I put together for my own needs. The T parameter is whatever object you want associated with the results (think of it like the Tag property). It takes a list of sizes and returns a list of Rects that are arranged

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