Click here to Skip to main content
Click here to Skip to main content
Add your own
alternative version

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

, 21 Sep 2012 CPOL
This is an algorithm for maximizing coverage of a rectangular area with scaling tile children.
scalingtiles-noexe.zip
ScalingTiles
ScalingTiles.suo
ScalingTiles.v11.suo
ScalingTiles
bin
Debug
ScalingTiles.vshost.exe.manifest
Release
ScalingTiles.vshost.exe.manifest
obj
x86
Debug
GenerateResource.read.1.tlog
GenerateResource.write.1.tlog
Release
Properties
Settings.settings
ScalingTiles.zip
ScalingTiles.suo
ScalingTiles.v11.suo
ScalingTiles.vshost.exe.manifest
ScalingTiles.vshost.exe.manifest
GenerateResource.read.1.tlog
GenerateResource.write.1.tlog
Settings.settings
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();
        }

    }
}

By viewing downloads associated with this article you agree to the Terms of Service and the article's licence.

If a file you wish to view isn't highlighted, and is a text file (not binary), please let us know and we'll add colourisation support for it.

License

This article, along with any associated source code and files, is licensed under The Code Project Open License (CPOL)

Share

About the Author

ShawnPavel

United States United States
No Biography provided

| Advertise | Privacy | Terms of Use | Mobile
Web02 | 2.8.141220.1 | Last Updated 21 Sep 2012
Article Copyright 2011 by ShawnPavel
Everything else Copyright © CodeProject, 1999-2014
Layout: fixed | fluid