Optimal Rectangle Packing

Keywords: Xamarin.Forms, Animation, async/await, Task, TranslateTo, RotateTo, Anchor, 2D Rectangle Packing, Optimization, Near-Fit Decreasing Height, Fast-Fit Decreasing Height, Best-Fit Decreasing Height, NFDH, FFDH, BFDH, Bottom-Left method, Simulated Annealing

---

I tried 2D Rectangle Packing problem, and additionally developed animations of blocks moving. I have learned Xamarin animations such as TranslateTo and RotateTo, async and await, as well as 2D Packing algorithms.

A screen shot of the iOS Simulator just after launching the App.

MainPage.xaml

<?xml version="1.0" encoding="utf-8"?>
<ContentPage xmlns="http://xamarin.com/schemas/2014/forms" 
             xmlns:x="http://schemas.microsoft.com/winfx/2009/xaml" 
             xmlns:local="clr-namespace:OptPacking" 
             x:Class="OptPacking.MainPage">

    <Grid RowSpacing="0">
        <Grid.RowDefinitions>
            <RowDefinition Height="Auto"/>
            <RowDefinition Height="Auto"/>
            <RowDefinition Height="*" />
            <RowDefinition Height="Auto"/>
        </Grid.RowDefinitions>

        <!-- Title -->
        <StackLayout Grid.Row="0" BackgroundColor="Gray" 
                     Padding="0,0,0,1" HeightRequest="50">
            <StackLayout BackgroundColor="White" HeightRequest="50">
                <Label Text="OptPacking Demo" 
                       Grid.Row="0" VerticalOptions="EndAndExpand"/>
            </StackLayout>
        </StackLayout>

        <!-- Buttons to control this App -->
        <StackLayout Grid.Row="1" Orientation="Horizontal">
            <Button x:Name="OperateSystemButton"
                    Text="Crane" Clicked="OperateSystem"
                    WidthRequest="60" HeightRequest="25"
                    BorderWidth="1" Margin="3,3,0,3"/>
            <Button x:Name="ChangePackingButton"
                    Text="BL" Clicked="ChangePacking"
                    WidthRequest="60" HeightRequest="25"
                    BorderWidth="1" Margin="-3,3,0,3"/>            
            <Button x:Name="LocalSearchButton"
                    Text="LclSrch" Clicked="LocalSearch"
                    WidthRequest="60" HeightRequest="25"
                    BorderWidth="1" Margin="-3,3,0,3"/>
            <Button x:Name="SetBlockToContainerButton"
                    Text="SetBlck" Clicked="SetBlockToContainer"
                    WidthRequest="60" HeightRequest="25"
                    BorderWidth="1" Margin="-3,3,0,3"/>
            <!--
            <Button x:Name="Init"
                    Text="Init" Clicked="ReInitSystem"
                    WidthRequest="60" HeightRequest="25"
                    BorderWidth="1" Margin="-3,3,0,3"/>
            -->
            <Label x:Name="StatusLabel" Text="System Ready" FontSize="14"
                   HorizontalOptions="EndAndExpand" VerticalOptions="Center"/>
        </StackLayout>

        <!-- Main Area -->
        <StackLayout Grid.Row="2" BackgroundColor="Gray" Padding="0,1,0,1" 
                     VerticalOptions="FillAndExpand">
            <AbsoluteLayout x:Name="Board" SizeChanged="GetBoardSize"
                            BackgroundColor="DimGray" VerticalOptions="FillAndExpand">

                <!-- Container -->
                <StackLayout x:Name="ContainerBox"
                             TranslationX="10" TranslationY="250" 
                             WidthRequest="200" HeightRequest="250"
                             BackgroundColor="White"/>
                
                <!-- Block Conveyor -->
                <ContentView x:Name="Conveyor" WidthRequest="300" HeightRequest="100"
                             TranslationX="250" TranslationY="100">
                    <ContentView.Content>
                        <AbsoluteLayout x:Name="ConveyorAbsLayout" WidthRequest="200" HeightRequest="150"
                                        BackgroundColor="Transparent">
                            <BoxView x:Name="ConveyorBoard" WidthRequest="200" HeightRequest="20"
                                     TranslationX="0"  BackgroundColor="LightBlue" />
                        </AbsoluteLayout>                        
                    </ContentView.Content>
                </ContentView>


                <!-- Crane Belt -->
                <StackLayout BackgroundColor="Yellow"
                             TranslationX="105" TranslationY="48"
                             WidthRequest="200" HeightRequest="2" />
                <StackLayout BackgroundColor="Yellow"
                             TranslationX="105" TranslationY="98"
                             WidthRequest="200" HeightRequest="2" />
                
                <!-- Crane Gear -->
                <Label Text="○" FontSize="70" TextColor="Yellow"
                       TranslationX="77" TranslationY="32"/>
                <Label Text="○" FontSize="70" TextColor="Yellow"
                       TranslationX="277" TranslationY="32"/>
                
                <!-- Indicator -->
                <StackLayout TranslationX="215" TranslationY="300" 
                             WidthRequest="155" HeightRequest="200"
                             BackgroundColor="Teal">
                    <Label Text="Created Blocks:"
                           FontSize="14" TextColor="White"/>
                    <Label x:Name="Label4" 
                           FontSize="14" TextColor="White"/>
                    <Label x:Name="Label5" Margin="0,-5,0,0"
                           FontSize="14" TextColor="White"/>
                    <Label Text="  CTR area: 50,000" Margin="0,-5,0,0"
                           FontSize="14" TextColor="White"/>
                    <Label Text="                         [pixel^2]" Margin="0,-10,0,0"
                           FontSize="12" TextColor="White"/>
                    <Label Text="Packed Blocks:" Margin="0,20,0,0"
                           FontSize="14" TextColor="White"/>
                    <Label x:Name="Label6"
                           FontSize="14" TextColor="White"/>
                    <Label x:Name="Label7" Margin="0,-5,0,0"
                           FontSize="14" TextColor="White"/>
                    <Label x:Name="Label8" Margin="0,-5,0,0"
                           FontSize="14" TextColor="White"/>
                </StackLayout>
                                
            </AbsoluteLayout>
        </StackLayout>


        <!-- Monitor some variables for Debug -->
        <StackLayout x:Name="Debug" Grid.Row="3" Orientation="Horizontal">
            <StackLayout>
                <Label x:Name="Label1" FontSize="14" Text=" "/>
                <Label x:Name="Label2" FontSize="14" Text=" "/>
                <Label x:Name="Label3" FontSize="14" Text=" "/>
            </StackLayout>
        </StackLayout>
        
    </Grid>
    
</ContentPage>

The source code is also here.

Designed the screen layout with four rows and one column Grid as usual.  From the upper row, App title, some Buttons to control the App, main area displaying the blocks and something, and the bottom area is to show some variables for debugging. In the main area, the light-blue object is the conveyor carrying the blocks from right to left, the yellow objects are the crane system picking up the blocks on the conveyor and carrying them to the right side. The conveyor moves up and down according to the block height so that the cranes can pick up the blocks. When the blocks picked up by the cranes arrives at the left end, they are released from the crane and fall down to the Container. You can see these animations in the movie that link are shown later.

Block.cs

//#define BoxDisplay

using System;
using System.Threading.Tasks;
using System.Collections.Generic;
using Xamarin.Forms;

namespace OptPacking
{
    public partial class MainPage : ContentPage
    {        
        List<Block> Blocks = new List<Block>();
        int NumBlocks = 0;  // The Number of Blocks
        int MaxSize = 50;   // Maximum Block Size
        int MinSize = 10;   // Minimum Block Size
        double Vb = 0.1;    // Block Velocity

        Random rnd = new Random();

        bool ServeBlock = false;

        // Block Class
        class Block
        {
            private ContentView body = new ContentView()
            {                
                BackgroundColor = Color.Transparent,
                Padding = 1,
                Content = new Label
                {
                    WidthRequest = 100,
                    HeightRequest = 100,
                    BackgroundColor = Color.Aqua,
                    HorizontalTextAlignment = TextAlignment.Center,
                    VerticalTextAlignment = TextAlignment.Center,
                    HorizontalOptions = LayoutOptions.Center,
                    VerticalOptions = LayoutOptions.Center
                }
            };
            public ContentView Body { get { return this.body; } }
            public int No { get; set; }
            public string Name
            {
                get { return ((Label)Body.Content).Text; }
                set { ((Label)Body.Content).Text = value; }
            }
            public double X
            {
                get { return Body.TranslationX; }
                set { Body.TranslationX = value; }
            }
            public double Y
            {
                get { return Body.TranslationY; }
                set { Body.TranslationY = value; }
            }
            public double W
            {
                get { return Body.WidthRequest; }
                set { Body.WidthRequest = value; }
            }
            public double H
            {
                get { return Body.HeightRequest; }
                set { Body.HeightRequest = value; }
            }
            public double Area
            {
                get { return W * H; }
            }

            private double r;
            private double angle()
            {
                r = r % 360;
                if (r > 180) r -= 360;
                if (r < -180) r += 360;
                return r;
            }
            public double R
            {
                get { return this.angle(); }
                set { this.r = value; }
            }

            // Anchor value in Rotating Anchor Coordinate
            public double AnchorX { get; set; }            
            public double AnchorY { get; set; }

            // Bottom-Left position of blocks
            public double Xg { get; set; }
            public double Yg { get; set; }
            
            public bool Start { get; set; }
        }


        // Create and Initialize new Blocks
        void InitBlocks()
        {
            List<ContentView> contentViews = new List<ContentView>();
            List<BoxView> boxViews = new List<BoxView>();

            // Create Blocks with random size
            for (int i = 0; i < 100; i++)
            {
                double w = rnd.Next(MinSize, MaxSize);
                double h = rnd.Next(MinSize, MaxSize);
                Block block = new Block()
                {
                    No = i + 1,
                    Name = (i + 1).ToString(),
                    W = w,
                    H = h,
                    X = i * 150 + 200,
                    Y = MaxSize - h,                    
                };
                if(block.W < 20 || block.H < 15) // Small Font for Small Blocks
                {
                    Label label = (Label)block.Body.Content;
                    label.FontSize = 10;                    
                }
                
                // If total blocks area becomes larger than the initial Container size,
                // stop blocks creation
                if (Area + block.Area > ContainerWidth * ContainerHeight)
                {
                    NumBlocks = i;
                    break;
                }

                Area += block.Area;

                ConveyorAbsLayout.Children.Add(block.Body);
                Blocks.Add(block);


            }
            
            Label4.Text = string.Format("  # {0} [blocks]", NumBlocks);
            Label5.Text = string.Format("  tot. area: {0:#,0}", Area);
            Label6.Text = " max height: 0 pixel";
            Label7.Text = " pack ratio: 0 %";
        }


        // Serve each Block from the Conveyor to the Container
        async Task OperateBlock(Block block)
        {
            // Slide Blocks to the left on the Conveyor, 
            // and Wait Ready at the position 100 of the Conveyor
            await block.Body.TranslateTo(100, MaxSize - block.H, (uint)((block.X - 100) / Vc));            

            // A Crane approaches the Conveyor (ServeBlock = false -> true), 
            // Start the Blocks Serving
            ServeBlock = false;
            Device.StartTimer(
                TimeSpan.FromMilliseconds(1), () => {
                    if (ServeBlock)
                    {
                        block.Start = true;
                        MoveBlock(block);                        
                    }
                    
                    return !block.Start;    // true : Next Timer Start
                                            // false: Timer Stop
                }
            );
        }


        async Task MoveBlock(Block block)
        {
            // Crane Pick Up Position
            //   - Crane Position on Board:     300
            //   - Conveyor TranslationX on Board: 250
            double x = 50.0 - block.W / 2.0 + CraneWidth / 2.0;

            ServeBlock = false; // Initialize ServeBlock for the next Block

            // Move the Block to the Crane Pick Up Position, 
            // and simultaneously move the Conveyor up and down so that 
            // the Block can be lifted up by the Crane
            await Task.WhenAll(
                block.Body.TranslateTo(x, MaxSize - block.H, (uint)(100.0 / Vc)),
                Conveyor.TranslateTo(250, 150 - (MaxSize - block.H), (uint)(100.0 / Vc))
            );

            // Move the blcok from the Conveyor to the Board
            ConveyorAbsLayout.Children.Remove(block.Body);
            block.X = 250 + x;
            block.Y = 150;
            Board.Children.Add(block.Body);

            // The Block parallelly move to the left with the Crane
            await block.Body.TranslateTo(50 + x, 150, (uint)(200.0 / Vc));

            // The Block is released and falls to the Container
            await FallTo(block, block.Xg, block.Yg - block.H);

            
            if (block.No == NumBlocks)  // All Blocks has been served
            {
                OperateSystemButton.Text = "Change";
                StatusLabel.Text = "All Blocks Served1";
                CraneStart = false; // Stop the Cranes
            }
        }


        // The Block falls with rotating to the Container
        async Task FallTo(Block block, double x, double y, uint length = 0)
        {
            // Create a new Trajectory and the Block falls along it
            double rndx, rndy;
            int n = rnd.Next(2, 4);
            for (int i = 0; i < n; i++)
            {
                rndx = block.X + rnd.Next(50, 100);
                rndy = block.Y + rnd.Next(50, 100);
                await RotateToXY(block, rndx, rndy, length: length);
            }
            
            // In the final rotating, the Block Label keeps Upright
            await RotateToXY(block, x, y, true, length: length);

            // Reset Block Rotation
            block.AnchorX = 0; block.AnchorY = 0;
            block.Body.Rotation = 0;
            block.Body.Content.Rotation = 0;
            block.Body.BackgroundColor = Color.White;

            // Update maximum height of the packed blocks
            if (Y0 - y > BestHeight) BestHeight = Y0 - y;

            // If the packed blocks are full, expand the Container            
            if (BestHeight > ContainerHeight) ExpandContainer(BestHeight);

            Area += block.Area;
            PackRatio = Area / (ContainerWidth * ContainerHeight) * 100;            
            Label6.Text = string.Format(" max height: {0} pixel", BestHeight);
            Label7.Text = string.Format(" pack ratio: {0:0.0} %", PackRatio);
        }

        
        // Move Block to the position (x, y) with rotating
        async Task RotateToXY(Block block, double x, double y, 
                                bool upright = false, uint length = 0)
        {
            double x0 = block.X;        double y0 = block.Y;
            double dx = x - x0;         double dy = y - y0;
            double xc = x0 + dx / 2;    double yc = y0 + dy / 2;

            if (Math.Abs(dy) < 0.000001) dy = 0.001;
            double a = dx / dy;

            double xa;
            double phi = Math.PI * block.R / 180.0;
            if (Math.Abs(block.R - 90.0) < 0.000001) xa = x0;
            else if (Math.Abs(block.R + 90.0) < 0.000001) xa = x0;
            else xa = (a * xc + yc + Math.Tan(phi) * x0 - y0) / (Math.Tan(phi) + a);

            double ya = -a * (xa - xc) + yc;
            double l = Math.Sqrt(Math.Pow(xa - x0, 2) + Math.Pow(ya - y0, 2));

#if BoxDisplay  // Display Start, End and Anchor position for debug
            BoxView box1 = new BoxView() {
                TranslationX = xa,  TranslationY = ya,
                WidthRequest = l,   HeightRequest = 2,
                AnchorX = 0,        AnchorY = 0,
                Rotation = Math.Atan2(y0 - ya, x0 - xa) / Math.PI * 180.0,
                BackgroundColor = Color.Yellow
            };
            BoxView box2 = new BoxView() {
                TranslationX = xa,  TranslationY = ya,
                WidthRequest = l,   HeightRequest = 2,
                AnchorX = 0,        AnchorY = 0,
                Rotation = Math.Atan2(y - ya, x - xa) / Math.PI * 180.0,
                BackgroundColor = Color.Yellow
            };
            BoxView box3 = new BoxView() {
                TranslationX = x,   TranslationY = y,
                WidthRequest = 5,   HeightRequest = 5,
                BackgroundColor = Color.Red
            };

            Board.Children.Add(box1);
            Board.Children.Add(box2);
            Board.Children.Add(box3);
#endif

            if (xa - x0 > 0 && Math.Cos(phi) < 0) l *= -1;
            if (xa - x0 < 0 && Math.Cos(phi) > 0) l *= -1;
            double anchorx = l / block.W;

            double thetad = Math.PI - (Math.Atan2(dy, dx) - phi);
            double theta = (Math.PI - 2 * thetad) / Math.PI * 180.0;
            theta = theta % 360.0;
            if (theta > 180) theta -= 360;
            if (theta < -180) theta += 360;
            
            block.AnchorX = anchorx;
            block.AnchorY = 0;
            block.Body.Content.AnchorX = 0;
            block.Body.Content.AnchorY = 0;

            if (length == 0)
                length = (uint)(Math.Abs(Math.PI * theta / 180.0 * l) / 314.0 * 50 / Vb);

            double rotation;
            if (upright) rotation = -(block.R + theta);
            else rotation = 0;

            await Task.WhenAll(
                Rotate(block, theta, length),                
                block.Body.Content.RotateTo(rotation, length)
            );
        }
        

        // Rotate Block
        async Task Rotate(Block block, double rotation, uint length)
        {
            block.Body.AnchorX = block.AnchorX;
            block.Body.AnchorY = block.AnchorY;
            block.Body.Content.AnchorX = 0;
            block.Body.Content.AnchorY = 0;

            double theta0 = Math.Atan2(block.Body.AnchorY * block.H, block.Body.AnchorX * block.W);
            double theta = Math.PI * (rotation / 180.0);
            double phi = Math.PI * block.R / 180.0;
            double l = Math.Sqrt(Math.Pow(block.Body.AnchorX * block.W, 2)
                                 + Math.Pow(block.Body.AnchorY * block.H, 2));
            double dx = l * (Math.Cos(theta0 + phi) - Math.Cos(theta0));
            double dy = l * (Math.Sin(theta0 + phi) - Math.Sin(theta0));

            block.X += dx; block.Y += dy;
            await Task.WhenAll(
                block.Body.RelRotateTo(rotation, length),
                block.Body.Content.RotateTo(0, length)
            );
            block.X -= dx; block.Y -= dy;

            block.Body.AnchorX = 0;
            block.Body.AnchorY = 0;
            block.X += l * (Math.Cos(theta0 + phi) - Math.Cos(theta + theta0 + phi));
            block.Y += l * (Math.Sin(theta0 + phi) - Math.Sin(theta + theta0 + phi));

            block.R += rotation;
        }

    }
}

Block properties are defined in class "Block." "InitBlocks" method created random sized Blocks that make the Container almost full and set them on the Conveyor. "OperateBlock" and the following methods create animations of the Blocks that are carried from the Conveyor to the Cranes and packed into the Container. The Blocks are controlled synchronously with the Cranes, the Conveyor, and the other Blocks. "FallTo" and the following methods are animations for the blocks that are released from the Cranes and packed into the Container. The blocks are randomly rotated while falling into the Container.

Crane.cs

using System.Threading.Tasks;
using System.Collections.Generic;
using Xamarin.Forms;

namespace OptPacking
{
    public partial class MainPage : ContentPage
    {
        bool CraneStart = false;    // Start trigger for the cranes

        int NumCranes = 5;          // The Number of Cranes
        int NumSections = 6;        // The Number of Sections
        double Vc = 0.1;            // Average Velocity of Cranes
        double CraneWidth = 10.0;   // Crane width

        // Crane class
        class Crane
        {
            private ContentView body = new ContentView()
            {
                WidthRequest = 10,
                HeightRequest = 50,
                TranslationX = 300,
                TranslationY = 0,
                AnchorX = 0.5,
                AnchorY = 1.5,                
                Content = new AbsoluteLayout
                {
                    WidthRequest = 10,
                    HeightRequest = 200,
                    BackgroundColor = Color.Yellow
                }
            };
            public ContentView Body { get { return this.body; } }
            public int Section { get; set; }
            public Crane Ahead { get; set; }
        }
        List<Crane> Cranes = new List<Crane>();

        BoxView Gear1 = new BoxView
        {
            WidthRequest = 3,   HeightRequest = 40,
            TranslationX = 105, TranslationY = 54,
            AnchorX = 0.5,      AnchorY = 0.5,
            BackgroundColor = Color.Yellow
        };
        BoxView Gear2 = new BoxView
        {
            WidthRequest = 3,   HeightRequest = 40,
            TranslationX = 305, TranslationY = 54,
            AnchorX = 0.5,      AnchorY = 0.5,
            BackgroundColor = Color.Yellow
        };


        // Create and Initialize Cranes
        void InitCranes()
        {
            CraneStart = false;

            for (int i = 0; i < NumCranes; i++)
            {
                Crane crane = new Crane();
                Cranes.Add(crane);
                Board.Children.Add(crane.Body);
            }

            foreach(Crane crane in Cranes)
            {
                int index = Cranes.IndexOf(crane);

                if (index == 0) crane.Ahead = Cranes[NumCranes - 1];
                else crane.Ahead = Cranes[index - 1];
            }


            Cranes[0].Section = 5;

            Cranes[1].Body.TranslationX = 200;
            Cranes[1].Section = 4;

            Cranes[2].Body.TranslationX = 100;
            Cranes[2].Section = 3;

            Cranes[3].Body.TranslationX = 100;
            Cranes[3].Body.Rotation = 180;
            Cranes[3].Section = 2;

            Cranes[4].Body.TranslationX = 200;
            Cranes[4].Body.Rotation = 180;
            Cranes[4].Section = 1;

            Board.Children.Add(Gear1);
            Board.Children.Add(Gear2);
        }


        // Operate each Crane
        async Task OperateCrane(Crane crane)
        {
            CraneStart = true;

            while(CraneStart)
            {
                for (int i = 0; i < NumSections; i++)
                {                    
                    while (true)
                    {
                        bool MoveNextSection = (crane.Ahead.Section != crane.Section + 1);
                        if (crane.Section == NumCranes)
                            MoveNextSection = ((crane.Ahead.Section != 0) && (crane.Ahead.Section != NumCranes));

                        if (MoveNextSection) break;
                    }

                    crane.Section++;
                    if (crane.Section > NumCranes)
                    {
                        ServeBlock = true;
                        crane.Section = 0;                        
                    }

                    await MoveCrane(crane);

                }
            }
        }


        // Move each Crane in each Section
        async Task MoveCrane(Crane crane)
        {            
            switch (crane.Section)
            {
                case 0:
                case 3:                    
                    await crane.Body.RelRotateTo(180, (uint)(100.0 / Vc));
                    break;

                case 1:
                case 4:                    
                    await crane.Body.TranslateTo(200, 0, (uint)(100.0 / Vc));
                    break;

                case 2:                    
                    await crane.Body.TranslateTo(100, 0, (uint)(100.0 / Vc));
                    break;

                case 5:                    
                    await crane.Body.TranslateTo(300, 0, (uint)(100.0 / Vc));
                    break;
            }
        }


        // Rotate the Crane Gears
        async Task RotateGear()
        {
            while (CraneStart)
            {
                await Task.WhenAll(
                    Gear1.RelRotateTo(360, 2000),
                    Gear2.RelRotateTo(360, 2000)
                );
            }
        }


    }
}

The Crane system are composed of some crane arms, belt (programmed in MainPage.xaml), and two gears which rotate the belt. Those properties are defined in class "Crane." "InitCranes" method created Crane arms. "OperateCrane" and its following methods control the system. The "ServeBlock" bool variable in "OperateCrane" method is for the synchronization between the Cranes and the Blocks.

Packing.cs

using System;
using System.Linq;
using System.Collections.Generic;
using System.Threading.Tasks;
using Xamarin.Forms;

namespace OptPacking
{
    public partial class MainPage : ContentPage
    {
        double Area = 0.0;          // Total Area of the Packed Blocks
        double BestHeight = 0.0;    // The Lowest Height in the Local Search
        double PackRatio = 0.0;     // Filling rate of the Packed Blocks
        int Iteration = 3000;
        double maxTemp = 5.0;
        double minTemp = 0.5;

        // No-Fit Polygon class for Bottom-Left algorithm
        class NFP
        {
            public double X { get; set; }
            public double Y { get; set; }
            public double W { get; set; }
            public double H { get; set; }
        }
        List<NFP> NFPs = new List<NFP>();

        List<Block> PackedBlocks = new List<Block>();   // Packed Blocks Lists
        List<Block> BestBlocks = new List<Block>();     // Best Packed Blocks in Local Search

        // Level class for 'X'FDH algorithms
        class Level
        {
            public double X { get; set; }
            public double Y { get; set; }
            public double H { get; set; }
            public double ResidualX { get { return X0 + ContainerWidth - X; } }
            public double NextY { get { return Y - H; } }
        }
        List<Level> Levels = new List<Level>();



        // X-Fit Decreasing Height algorityms
        double XFDH(string x, ref List<Block> blocks)
        {
            blocks = SortBlocks(Blocks, "height");
            Levels.Clear();

            Level PackLevel = new Level()
            {
                X = X0,
                Y = Y0,
                H = blocks[0].H
            };
            Levels.Add(PackLevel);
            double height = PackLevel.H;

            foreach (Block block in blocks)
            {
                bool Packed = false;
                block.Body.Content.BackgroundColor = Color.Aqua;

                switch (x)
                {
                    case "NFDH":    // Near-Fit Decreaseing Height
                        if (block.W < PackLevel.ResidualX) Packed = true;
                        break;

                    case "FFDH":    // Fast-Fit Decreasing Height
                        foreach (Level level in Levels)
                            if (block.W < level.ResidualX)
                            {
                                Packed = true;
                                PackLevel = level;
                                break;
                            }
                        break;

                    case "BFDH":    // Best-Fit Decreasing Height　
                        List<Level> SortedLevels
                            = new List<Level>(Levels.OrderBy(n => n.ResidualX));
                        foreach (Level level in SortedLevels)
                            if (block.W < level.ResidualX)
                            {
                                Packed = true;
                                PackLevel = level;
                                break;
                            }
                        break;
                }


                // if the block can not be packed in the last level, 
                // create a new level
                if (!Packed)
                {
                    PackLevel = new Level()
                    {
                        X = X0,
                        Y = Levels.Last().NextY,
                        H = block.H
                    };
                    Levels.Add(PackLevel);
                    height += PackLevel.H;
                }

                block.Xg = PackLevel.X;
                block.Yg = PackLevel.Y;

                // Shift the next block position
                PackLevel.X += block.W;

                // If the block is packed at the left end, 
                // the Level heigh is equal to its block height
                if (block.Xg < X0 + 1.0) PackLevel.H = block.H;
            }

            return height;

        }



        // Bottom-Left algorithm
        double BottomLeft(ref List<Block> blocks, string sort = "none")
        {
            int x = 0; int y = 0;
            bool FindBL = true;
            double height = 0;

            if (sort != "none") blocks = SortBlocks(blocks, sort);

            PackedBlocks.Clear();

            foreach (Block block in blocks)
            {
                // Make NFPs of all PackedBlocks
                NFPs.Clear();
                foreach (Block packedblock in PackedBlocks)
                {
                    NFP nfp = new NFP
                    {
                        X = packedblock.Xg - block.W,
                        Y = packedblock.Yg - packedblock.H,
                        W = packedblock.W + block.W,
                        H = packedblock.H + block.H
                    };
                    NFPs.Add(nfp);
                }


                // Scan the Container to find the Bottom-Left Point
                for (y = (int)Y0; y > 0; y--)
                {
                    for (x = (int)X0; x < (int)(X0 + ContainerWidth - block.W); x++)
                    {
                        FindBL = true;
                        foreach (NFP nfp in NFPs)
                        {
                            // Scanning point (x, y) is in any NFP, or not?
                            if (x > nfp.X && x < nfp.X + nfp.W
                             && y > nfp.Y && y < nfp.Y + nfp.H)
                            {
                                FindBL = false;
                                x = (int)(nfp.X + nfp.W);   // Skip to the right end of this NFP
                                break;
                            }
                        }
                        // if (x,y) is not in any NFPs, the point is BL.
                        if (FindBL) break;
                    }
                    if (FindBL) break;
                }

                block.Xg = (double)x;
                block.Yg = (double)y;

                if (Y0 - (block.Yg - block.H) > height)
                    height = Y0 - (block.Yg - block.H);

                PackedBlocks.Add(block);
            }

            return height;
        }



        // Local Searach to find the best packed solution
        async void LocalSearch(object sender, EventArgs e)
        {
            int i = 1;
            BestHeight = 500.0;
            List<Block> blocks = new List<Block>(SortBlocks(Blocks, "Area"));

            while (i < Iteration)
            {
                await SimulatedAnnealing(blocks, i);
                
                await MoveAllBlocks(BestBlocks);
                Label8.Text = string.Format(" iterations: # {0}", i + 1);

                i += i;
                Label2.Text += i.ToString() + " ";
            }
            Label8.Text = string.Format(" iterations: # {0}END", i + 1);

        }


        // Simulated Annealing method for Local Search
        async Task SimulatedAnnealing(List<Block> blocks, int iteration)
        {
            List<Block> NeighbourBlocks = new List<Block>();
            int i = 0;
            int j = 0; int k = 0;
            double height = 0;
            double heightNeighbour = 0;
            double p = 0;
            double t = 0;

            // Local Search Loop
            for (i = iteration; i < iteration*2; i++)
            {
                int index1 = rnd.Next(NumBlocks - 1);
                int index2 = rnd.Next(NumBlocks - 1);

                NeighbourBlocks = new List<Block>(blocks);
                /*
                // Create a neighbouring blocks of the current blocks by
                //    moving a randomly chosen blocks to randomly chosen position
                Block dummy = NeighbourBlocks[index1];
                NeighbourBlocks.Remove(NeighbourBlocks[index1]);
                NeighbourBlocks.Insert(index2, dummy);
                */
                // Create a neighbouring blocks of the current blocks
                //    by exchanging randomly chosen two blocks
                Block dummy1 = NeighbourBlocks[index1];
                Block dummy2 = NeighbourBlocks[index2];
                NeighbourBlocks.Remove(NeighbourBlocks[index1]);
                NeighbourBlocks.Insert(index1, dummy2);
                NeighbourBlocks.Remove(NeighbourBlocks[index2]);
                NeighbourBlocks.Insert(index2, dummy1);


                // Calculate the energy of the neighbouring and the original blocks
                heightNeighbour = BottomLeft(ref NeighbourBlocks);
                height          = BottomLeft(ref blocks);

                if (height > heightNeighbour)
                {
                    blocks = new List<Block>(NeighbourBlocks);
                    if (BestHeight > heightNeighbour)
                    {
                        BestHeight = heightNeighbour;
                        Label3.Text += BestHeight.ToString() + " ";
                        BestBlocks = new List<Block>(NeighbourBlocks);                        
                    }
                    j++;
                }
                else// if(heightNeighbour - height < 20.0)
                {
                    // Calculate Acceptance Probability for Simulated Annealing
                    t = maxTemp * Math.Pow(minTemp / maxTemp, (double)i / (double)Iteration);
                    p = Math.Exp((height - heightNeighbour) / t);
                    if (rnd.NextDouble() < p)
                    {
                        blocks = new List<Block>(NeighbourBlocks);
                        k++;
                    }
                }
            }


            await Task.Delay(1);
            Label1.Text = string.Format("Iteration: {0}   Temperature:  {1:0.00}", i, t);
            //Label2.Text = string.Format("Find Better Sol: # {0}   Acceptance Prob: # {1}", j, k);
            
        }


        // Move All Blocks to the better solution
        async Task MoveAllBlocks(List<Block> blocks)
        {
            double height = BottomLeft(ref blocks);

            var tasks = new List<Task>();
            foreach (Block block in blocks)
                tasks.Add(block.Body.TranslateTo(block.Xg, block.Yg - block.H, 700));            

            await Task.WhenAll(tasks);

            // Fit the Container size to the Packed Blocks            
            PackRatio = ExpandContainer(height);
            Label6.Text = string.Format(" max height: {0} pixel", height);
            Label7.Text = string.Format(" pack ratio: {0:0.0} %", PackRatio);
        }



        // Sort the Blocks in some orders
        List<Block> SortBlocks(List<Block> blocks, string order)
        //                                       string order, bool rename = true)
        {

            switch(order)
            {
                // Sort the blocks in their Height order
                case "height":
                case "Height":
                    blocks = new List<Block>(blocks.OrderByDescending(n => n.H));
                    break;

                // Sort the blocks in their Area order
                case "area":
                case "Area":
                    blocks = new List<Block>(blocks.OrderByDescending(n => n.Area));
                    break;

                // Sort the blocks in their Height order
                case "width":
                case "Width":
                    blocks = new List<Block>(blocks.OrderByDescending(n => n.W));
                    break;

                // Sort the blocks in their X-position
                case "x":
                case "X":
                    blocks = new List<Block>(blocks.OrderByDescending(n => n.X));
                    break;

                // Sort the blocks in their Y-position
                case "-y":
                case "-Y":
                    blocks = new List<Block>(blocks.OrderBy(n => n.Y));
                    break;

                // Sort the blocks in their Height order
                case "original":
                case "Original":
                    blocks = new List<Block>(blocks.OrderByDescending(n => n.No));
                    break;

            }


            foreach (Block block in blocks)
            {
                int index = blocks.IndexOf(block);
                block.No = index + 1;
                block.Name = block.No.ToString();
                if (OperateSystemButton.Text != "Change")
                    block.X = index * 150 + 150;
            }

            return blocks;
        }


        // Expand the Container when the Packed Blocks are full
        double ExpandContainer(double height)
        {
            ContainerHeight = height;
            ContainerBox.TranslationY = Y0 - height;
            ContainerBox.HeightRequest = height;

            return Area / (ContainerWidth * ContainerHeight) * 100;
        }


    }
}

Bottom-Left method and Near, Fast, Best-Fit Decreasing Height algorithms has been programmed. A local search algorithm are also developed in the "LocalSearch" and "SimulatedAnnealing" methods. The "MoveAllBlocks" method show the process of the packing optimization.

MainPage.xaml.cs

using System;
using Xamarin.Forms;

namespace OptPacking
{
    public partial class MainPage : ContentPage
    {
        // Container Position and Size
        static double X0 = 10;
        static double Y0 = 500;
        static double ContainerWidth = 200;
        static double ContainerHeight = 250;
        //static double ContainerHeight = 60;

        public MainPage()
        {
            InitializeComponent();
            InitSystem();
        }


        // Get "Console" size properly and set some variables
        void GetBoardSize(object sender, EventArgs args)
        {
            //Label1.Text = string.Format("Board Size = ( {0}, {1} )",
            //                            Board.Width, Board.Height);
        }
        

        // Initialize All of Blocks, Cranes, and Conveyor
        void InitSystem()
        {
            InitBlocks();
            InitCranes();

            ContainerBox.TranslationY = Y0 - ContainerHeight;
            ContainerBox.HeightRequest = ContainerHeight;
            ConveyorBoard.TranslationY = MaxSize;
            OperateSystemButton.Text = "Crane";

            // Calculate Block Packing Position (default: Bottom-Left)            
            BestHeight = BottomLeft(ref Blocks, "Area");
        }


        // Operate All of the System
        async void OperateSystem(object sender, EventArgs e)
        {
            Button button = (Button)sender;

            switch (button.Text)
            {
                case "Crane":
                    foreach (Crane crane in Cranes)
                        OperateCrane(crane);
                    RotateGear();
                    StatusLabel.Text = "Crane Operated";
                    button.Text = "Block";
                    break;

                case "Block":
                    Area = 0;
                    BestHeight = 0;
                    foreach (Block block in Blocks)
                        OperateBlock(block);
                    StatusLabel.Text = "Serving Blocks";
                    break;

                case "Change":
                    break;
            }
        }


        // Change Packing Algorithm
        void ChangePacking(object sender, EventArgs e)
        {
            Button button = (Button)sender;
            double height = 0;

            switch (button.Text)
            {
                case "NFDH":    // Near-Fit Decreasing Height
                    height = XFDH("FFDH", ref Blocks);                    
                    button.Text = "FFDH";
                    break;

                case "FFDH":    // Fast-Fit Decreasing Height
                    height = XFDH("BFDH", ref Blocks);                    
                    button.Text = "BFDH";
                    break;

                case "BFDH":    // Best-Fit Decreasing Height
                    PackedBlocks.Clear();
                    height = BottomLeft(ref Blocks, "Area");
                    button.Text = "BL";
                    break;

                case "BL":      // Bottom-Left
                    height = XFDH("NFDH", ref Blocks);                    
                    button.Text = "NFDH";
                    break;
            }

            // The Mode after all blocks has been served
            if (OperateSystemButton.Text == "Change")
            {
                foreach (Block block in Blocks)
                    block.Body.TranslateTo(block.Xg, block.Yg - block.H, 1000);

                // Fit the Container size to the Packed Blocks            
                PackRatio = ExpandContainer(height);
                Label6.Text = string.Format(" max height: {0} pixel", BestHeight);
                Label7.Text = string.Format(" pack ratio: {0:0.0} %", PackRatio);
            }
        }


        // Set all the Blocks to the Container quickly (without Crane Operation)
        void SetBlockToContainer(object sender, EventArgs e)
        {
            Area = 0;
            foreach (Block block in Blocks)
            {
                ConveyorAbsLayout.Children.Remove(block.Body);
                Board.Children.Add(block.Body);
                block.Body.TranslationX = block.Xg;
                block.Body.TranslationY = block.Yg - block.H;
                block.Body.BackgroundColor = Color.White;
                Area += block.Area;
            }

            // Fit the Container size to the Packed Blocks            
            PackRatio = ExpandContainer(BestHeight);
            Label6.Text = string.Format(" max height: {0} pixel", BestHeight);
            Label7.Text = string.Format(" pack ratio: {0:0.0} %", PackRatio);

            OperateSystemButton.Text = "Change";
            StatusLabel.Text = "All Blocks Served1";
        }

    }   // End of public partial class MainPage
}       // End of namespace OptPacking

After "InitSystem" method initializes the Blocks, the Cranes, the Container, and the Conveyor, this App are waiting use operation. Push the Crane button starts the Crane system, and push the same button (The button title is changed to "Block") makes the Blocks operation. The "ChangePacking" button is to change the packing algorithm. The final method, "SetBlockToContainer", is to skip all animations and quickly pack all the Blocks into the Container.


A movie showing this App running.  You can get the original movie file from here (in "movie" folder).

The screenshot below is the final packing result. The packed ratio is around 90% or so, because the local search algorithm were not well tuned. Other local search algorithms and better tuning will be needed for better result, but it will be posted next time.