1

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.

5
  • IIRC, it is a hard problem (perhaps NP-hard). No efficient algorithm is known (in polynomial time). Dec 24, 2011 at 18:12
  • 1
    This isn't really a way to implement this, but the app Zwoptex already does this. It can be found here: zwoptexapp.com . You may want to give them a look before you try and build this yourself.
    – msgambel
    Dec 24, 2011 at 18:12
  • 1
  • Thanks, great answers, please make them into answers so I can vote them and mark one as the correct answer.
    – Petruza
    Dec 24, 2011 at 18:24
  • @MSgambel: actually Zwoptex is great and I use MacOS so it's the right tool for me, thanks!
    – Petruza
    Dec 24, 2011 at 21:37

1 Answer 1

0

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

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.