Tile Scaling for Maximum Area Coverage Based Upon Aspect Ratio of Tiles

using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using System.Windows;
using System.Windows.Controls;
using System.Windows.Data;
using System.Windows.Documents;
using System.Windows.Input;
using System.Windows.Media;
using System.Windows.Media.Imaging;
using System.Windows.Navigation;
using System.Windows.Shapes;
using System.Diagnostics;

namespace ScalingTiles
{
    /// <summary>
    /// Interaction logic for MainWindow.xaml
    /// </summary>
    public partial class MainWindow : Window
    {
        public MainWindow()
        {
            InitializeComponent();
        }

        private void Refill()
        {
            #region Testing Variables
            bool rowsMaximized = true; // used for testing, tells us if the rows or columns were maximized
            double time; //used for testing, tells us how long the processing took
            #endregion

            #region Variables
            Size parentSize = new Size { Height = brdRectangles.ActualHeight, Width = brdRectangles.ActualWidth };

            //Readjust the size of the parent to take into account the margin
            parentSize.Height -= (brdRectangles.Margin.Bottom + brdRectangles.Margin.Top);
            parentSize.Width -= (brdRectangles.Margin.Left + brdRectangles.Margin.Right);

            double parentAspectRatio = parentSize.Width / parentSize.Height; // the aspect ratio of the parent

            int numRectangles = UpdateRectangles();// the current number of children

            //get the aspect ratio from the text box
            float desiredAspectRatio = float.Parse(txtAspectRatio.Text);
            #endregion

            // Use the stopwatch to find out how long it takes to find the optimal size
            // only needed for testing
            Stopwatch stopwatch = new Stopwatch();

            stopwatch.Start(); // only used for testing purposes

            Size newSize = ComputeSize(desiredAspectRatio, numRectangles, parentSize, out rowsMaximized);

            stopwatch.Stop();
            time = stopwatch.Elapsed.TotalMilliseconds;

            txtStatus.Text = String.Format("{0:0} W by {1:0}\n H computed in {2} ms,\n {3:0.00}% of area was used", newSize.Width, newSize.Height, stopwatch.Elapsed.TotalMilliseconds, (newSize.Width * newSize.Height * numRectangles * 100 / (parentSize.Width * parentSize.Height)));
            txtMaximized.Text = String.Format("{0} were maximized", rowsMaximized ? "Rows" : "Columns");

            // set all the children to have the right size
            wpParentContainer.ItemHeight = newSize.Height;
            wpParentContainer.ItemWidth = newSize.Width; 
        }

        /*
         * UpdateRectangles:
         *      Gets the current number of children and makes sure the parent rectangle contains that many rectangles
         * 
         * inputs:
         *      none
         *      
         * outputs:
         *      int - the number of children
         *      
         */
        private int UpdateRectangles()
        {
            //get the new number of rectangles
            int numRectangles = Int32.Parse(txtRectangles.Text);
            int currentChildren = wpParentContainer.Children.Count; // the current value

            //update the number of rectangles
            if (numRectangles < wpParentContainer.Children.Count)
            {
                //too many children
                for (int i = 0; i < currentChildren - numRectangles; i++)
                    wpParentContainer.Children.RemoveAt(0);
            }
            else if (numRectangles > wpParentContainer.Children.Count)
            {
                //not enough children
                Random rand = new Random();
                //add new rectangles using borders
                for (int i = 0; i < numRectangles - currentChildren; i++)
                {
                    Border border = new Border();

                    border.BorderBrush = new SolidColorBrush(Colors.Black);
                    border.BorderThickness = new Thickness(2);

                    //get random colors for fun.
                    Color color = new Color();
                    color.A = 255;
                    color.R = (byte)rand.Next(256);
                    color.G = (byte)rand.Next(256);
                    color.B = (byte)rand.Next(256);
                    border.Background = new SolidColorBrush(color);

                    wpParentContainer.Children.Add(border);
                }
            }
            return numRectangles;
        }

        /*
         * ComputeSize:
         *      Will compute the optimal size of children rectangles while maintaining aspect ratio based upon the desired aspect ratio, the number of children rectangles, and the size of the parent.
         * 
         * inputs:
         *      double DesiredAspectRatio - the desired aspect ratio of the children rectangles
         *      int NumRectangles - the number of children rectangles to be sized
         *      Size ParentSize - the width and height of the parent rectangle
         *      bool RowsMaximized - not used as an input, see output
         *      
         * outputs:
         *      Size - the size of the children rectangle
         *      bool RowsMaximized - True => the rows were maximized in order to find the optimal size
         *                      False -> the columns were maximized in order to find the optimal size
         * 
         * Online Source:
         *      http://www.codeproject.com/Articles/217640/Tile-Scaling-for-Maximum-Area-Coverage-Based-Upon
         *      
         */
        private Size ComputeSize(double DesiredAspectRatio, int NumRectangles, Size ParentSize , out bool RowsMaximized)
        {
            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 newSize = new Size(); // used to hold the new size of the children

            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
            rectangleSize.Width = DesiredAspectRatio;
            rectangleSize.Height = 1;

            // estimate of the number of columns using 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
                RowsMaximized = false;//used for testing

                // 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;
                    RowsMaximized = true;

                    // 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;
                        RowsMaximized = false;

                        // 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;
                            RowsMaximized = true;
                        }
                    }

                    // if we have a lot of added items occasionally 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;
                        RowsMaximized = false;

                        // if the columns are over their bounds, then maximize by the rows instead
                        if (newHeight * Math.Ceiling(NumRectangles / currentCols) > ParentSize.Height)
                        {
                            newHeight = ParentSize.Height / currentRows;
                            newWidth = newHeight * DesiredAspectRatio;
                            RowsMaximized = true;
                        }
                    }

                    // 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;
                RowsMaximized = true;
            }

            //Yay! Finished.
            return newSize;
        }

        private void btnUpdateRectangles_Click(object sender, RoutedEventArgs e)
        {

            Refill();
        }

        private void wpParentContainer_SizeChanged_1(object sender, SizeChangedEventArgs e)
        {
            Refill();
        }

    }
}