Algorithme pour maximiser la couverture de la zone rectangulaire avec des carreaux de mise à l'échelle

Je réalise que c'est un vieux fil, mais j'ai récemment résolu ce problème de manière à ce que je pense soit efficace et donne toujours la bonne réponse. Il est conçu pour maintenir un rapport d'aspect donné. Si vous souhaitez que les enfants (boutons dans ce cas) soient carrés, utilisez simplement un rapport de format de 1. Je suis actuellement en train d'utiliser cet algorithme dans quelques endroits et cela fonctionne bien.

        double VerticalScale; // for the vertical scalar: uses the lowbound number of columns
        double HorizontalScale;// horizontal scalar: uses the highbound number of columns
        double numColumns; // the exact number of columns that would maximize area
        double highNumRows; // number of rows calculated using the upper bound columns
        double lowNumRows; // number of rows calculated using the lower bound columns
        double lowBoundColumns; // floor value of the estimated number of columns found
        double highBoundColumns; // ceiling value of the the estimated number of columns found


        Size rectangleSize = new Size(); // rectangle size will be used as a default value that is the exact aspect ratio desired.
        //
        // Aspect Ratio = h / w
        // where h is the height of the child and w is the width
        //
        // the numerator will be the aspect ratio and the denominator will always be one
        // if you want it to be square just use an aspect ratio of 1
        rectangleSize.Width = desiredAspectRatio;
        rectangleSize.Height = 1;

        // estimate of the number of columns useing the formula:
        //                          n * W * h       
        //  columns = SquareRoot(  -------------  )
        //                            H * w          
        //
        // Where n is the number of items, W is the width of the parent, H is the height of the parent,
        // h is the height of the child, and w is the width of the child
        numColumns = Math.Sqrt( (numRectangles * rectangleSize.Height * parentSize.Width) / (parentSize.Height * rectangleSize.Width) );

        lowBoundColumns = Math.Floor(numColumns);
        highBoundColumns = Math.Ceiling(numColumns);

        // The number of rows is determined by finding the floor of the number of children divided by the columns
        lowNumRows = Math.Ceiling(numRectangles / lowBoundColumns);
        highNumRows = Math.Ceiling(numRectangles / highBoundColumns);

        // Vertical Scale is what you multiply the vertical size of the child to find the expected area if you were to find
        // the size of the rectangle by maximizing by rows
        //
        //                      H
        // Vertical Scale = ----------
        //                    R * h
        //
        // Where H is the height of the parent, R is the number of rows, and h is the height of the child
        //
        VerticalScale = parentSize.Height / lowNumRows * rectangleSize.Height;

        //Horizontal Scale is what you multiply the horizintale size of the child to find the expected area if you were to find
        // the size of the rectangle by maximizing by columns
        //
        //                      W
        // Vertical Scale = ----------
        //                    c * w
        //
        //Where W is the width of the parent, c is the number of columns, and w is the width of the child
        HorizontalScale = parentSize.Width / (highBoundColumns * rectangleSize.Width);

        // The Max areas are what is used to determine if we should maximize over rows or columns
        //  The areas are found by multiplying the scale by the appropriate height or width and finding the area after the scale
        //                      
        // Horizontal Area =  Sh * w * ( (Sh * w) / A )
        //                     
        // where Sh is the horizontal scale, w is the width of the child, and A is the aspect ratio of the child
        //
        double MaxHorizontalArea = (HorizontalScale * rectangleSize.Width) * ((HorizontalScale * rectangleSize.Width) / desiredAspectRatio);
        //
        //                       
        // Vertical Area =   Sv * h * (Sv * h) * A
        // Where Sv isthe vertical scale, h is the height of the child, and A is the aspect ratio of the child
        //
        double MaxVerticalArea = (VerticalScale * rectangleSize.Height) * ((VerticalScale * rectangleSize.Height) * desiredAspectRatio);


        if (MaxHorizontalArea >= MaxVerticalArea ) // the horizontal are is greater than the max area then we maximize by columns
        {
            // the width is determined by dividing the parent's width by the estimated number of columns
            // this calculation will work for NEARLY all of the horizontal cases with only a few exceptions
            newSize.Width = parentSize.Width / highBoundColumns; // we use highBoundColumns because that's what is used for the Horizontal
            newSize.Height = newSize.Width / desiredAspectRatio; // A = w/h or h= w/A

            // In the cases that is doesnt work it is because the height of the new items is greater than the 
            // height of the parents. this only happens when transitioning to putting all the objects into
            // only one row
            if (newSize.Height * Math.Ceiling(numRectangles / highBoundColumns) > parentSize.Height)
            {
                //in this case the best solution is usually to maximize by rows instead
                double newHeight = parentSize.Height / highNumRows;
                double newWidth = newHeight * desiredAspectRatio;

                // However this doesn't always work because in one specific case the number of rows is more than actually needed
                // and the width of the objects end up being smaller than the size of the parent because we don't have enough
                // columns
                if (newWidth * numRectangles < parentSize.Width)
                {
                    //When this is the case the best idea is to maximize over columns again but increment the columns by one
                    //This takes care of it for most cases for when this happens.
                    newWidth = parentSize.Width / Math.Ceiling(numColumns++);
                    newHeight = newWidth / desiredAspectRatio;

                    // in order to make sure the rectangles don't go over bounds we
                    // increment the number of columns until it is under bounds again.
                    while (newWidth * numRectangles > parentSize.Width)
                    {
                        newWidth = parentSize.Width / Math.Ceiling(numColumns++);
                        newHeight = newWidth / desiredAspectRatio;
                    }

                    // however after doing this it is possible to have the height too small.
                    // this will only happen if there is one row of objects. so the solution is to make the objects'
                    // height equal to the height of their parent
                    if (newHeight > parentSize.Height)
                    {
                        newHeight = parentSize.Height;
                        newWidth = newHeight * desiredAspectRatio;
                    }
                }

                // if we have a lot of added items occaisionally the previous checks will come very close to maximizing both columns and rows
                // what happens in this case is that neither end up maximized

                // because we don't know what set of rows and columns were used to get us to where we are
                // we must recalculate them with the current measurements
                double currentCols = Math.Floor(parentSize.Width / newWidth); 
                double currentRows = Math.Ceiling(numRectangles/currentCols);
                // now we check and see if neither the rows or columns are maximized
                if ( (newWidth * currentCols ) < parentSize.Width && ( newHeight * Math.Ceiling(numRectangles/currentCols) ) < parentSize.Height)
                {
                    // maximize by columns first
                    newWidth = parentSize.Width / currentCols;
                    newHeight = newSize.Width / desiredAspectRatio;

                    // if the columns are over their bounds, then maximized by the columns instead
                    if (newHeight * Math.Ceiling(numRectangles / currentCols) > parentSize.Height)
                    {
                        newHeight = parentSize.Height / currentRows;
                        newWidth = newHeight * desiredAspectRatio;
                    }
                }

                // finally we have the height of the objects as maximized using columns
                newSize.Height = newHeight;
                newSize.Width = newWidth;

            }

        }
        else
        {
            //Here we use the vertical scale. We determine the height of the objects based upong
            // the estimated number of rows.
            // This work for all known cases
            newSize.Height = parentSize.Height / lowNumRows; 
            newSize.Width = newSize.Height * desiredAspectRatio;
        }