Two-Dimensional Bin Packing Under Multiple Constraints — Code Analysis for Finding the Optimal Layout of Cairo Ramen Shop (Part 1)

Introduction

This code is implemented in C#. Before starting the code analysis, let's first post the data we'll be using:

In Cairo Ramen Shop, the positive x-axis points left and the positive y-axis points down. To make our calculations easier, we can rotate the values 180° clockwise into the coordinate system we're familiar with, and then just rotate them back after processing. The entrance position here is relative to the cell at the store's bottom-left corner (that is, the direction closest to the origin). For example:

Relative to the bottom-left cell, this store's entrance is 1 cell to the left and 4 cells up, so the entrance position is (1, 4).

It's easy to calculate that there are a total of arrangements, and our task is to find the optimal solution among them! Quite a daunting task, isn't it?

Store Class: Store

Properties

In addition to id, width, height, and entrance position, the Store class also needs to record its own position. For convenience, we use the coordinates of the bottom-left cell as the store's position; for ease of calculation, we also store the rectangle obtained by expanding the store by one row and one column.

/// <summary>
/// 拉面店ID
/// </summary>
public int id; 

/// <summary>
/// 拉面店左下角坐标
/// </summary>
public Point point; 

/// <summary>
/// 拉面店高度
/// </summary>
public int height; 

/// <summary>
/// 拉面店宽度
/// </summary>
public int width; 

/// <summary>
/// 拉面店门的位置
/// </summary>
public Point door; 

/// <summary>
/// 拉面店覆盖区域
/// </summary>
public Rectangle area;

Methods

1. Checking Whether Stores Overlap

This is the method corresponding to constraint 2. When arranging stores with the BL algorithm, we need to check whether the expanded stores overlap; after placing the expanded stores, we also need to check whether the unexpanded stores overlap. Therefore, we need to write multiple member functions to check these separately.

/// <summary>
/// 判断自己与另一个拉面店（扩大后的）是否会重叠
/// </summary>
/// <param name="box">另一个拉面店</param>
/// <returns>若重叠则返回false，不重叠则返回true</returns>
public bool overlap(Store box)
{
    if ((point.X + area.Width-1 < box.point.X || point.X > box.point.X + box.area.Width-1) ||
        (point.Y + area.Height-1 < box.point.Y || point.Y > box.point.Y + box.area.Height-1))
    {
        return true;
    }
    return false;
}

/// <summary>
/// 判断自己与另一个拉面店是否会重叠
/// </summary>
/// <param name="box">另一个拉面店</param>
/// <returns>若重叠则返回false，不重叠则返回true</returns>
public bool overlap_pro(Store box)
{
    if ((point.X + width-1 < box.point.X || point.X > box.point.X + box.width-1) ||
        (point.Y + height-1 < box.point.Y || point.Y > box.point.Y + box.height-1))
    {
        return true;
    }
    return false;
}

/// <summary>
/// 判断本店与其他所有店是否有重叠
/// </summary>
/// <param name="ans">其他所有店</param>
/// <returns>有一个重叠就返回false，全部不重叠返回true</returns>
public bool if_available(List<Store> ans)
{
    bool flag = true;
    for (int i = 0; i < ans.Count; i++)
    {
        if (!overlap(ans[i]))
        {
            flag = false;
            break;
        }
    }

    return flag;
}

2. Deep Copy

In C#, custom classes are passed by reference by default when used as parameters, but some later functions need pass-by-value when processing (this will be explained in detail later), so we need to write a deep copy function.

/// <summary>
/// 深复制
/// </summary>
/// <returns>本店深复制后得到的新店</returns>
public Store Clone()
{
    Store ans = new Store(id, new Point(point.X, point.Y), width, height, new Point(door.X, door.Y));
    return ans;
}

3. Rotation

A member function corresponding to constraint 7.

/// <summary>
/// 旋转
/// </summary>
public void rotate()
{
    int t = height;
    height = width;
    width = t;
    door = new Point(door.Y, door.X);
    area = new Rectangle(new Point(0, 0), new Size(width + 1, height + 1));
}

4. The BL Algorithm and Its Improvement

The first step in implementing the BL algorithm is to place the store at the top-right boundary, so we need to check whether that top-right boundary position can fit the store and whether it would overlap with other stores. If it can be placed, we can start playing “Tetris.” For the BL algorithm, the store needs to determine how many cells it can move down and how many cells it can move left; for the improved BL algorithm, moving down and moving left can be combined into a single action.

/// <summary>
/// 判断本店能否在当前位置填充
/// </summary>
/// <param name="W">当前位置横坐标</param>
/// <param name="H">当前位置纵坐标</param>
/// <param name="ans">已填充的拉面店</param>
/// <returns>可以填充返回true，不能填充返回false</returns>
public bool set(int W, int H, List<Store> ans)
{
    point.X = W - area.Width;
    point.Y = H - area.Height;
    return if_available(ans);
}
/// <summary>
/// 向下移动
/// </summary>
/// <param name="store">当前已填充的拉面店</param>
/// <returns>可以移动的最大步数</returns>
public int go_down(List<Store> store)
{
    int move = 0;
    for (int i = 0; i < store.Count; i++)
    {
        if (area.Width + point.X > store[i].point.X && point.X < store[i].area.Width + store[i].point.X &&
            point.Y >= store[i].point.Y + store[i].area.Height)
        {
            int l = store[i].point.Y + store[i].area.Height;
            if (move < l)
            {
                move = l;
            }
        }
    }

    move = point.Y - move;
    point.Y -= move;
    return move;
}

/// <summary>
/// 向左移动
/// </summary>
/// <param name="store">当前已填充的拉面店</param>
/// <returns>可以移动的最大步数</returns>
public int go_left(List<Store> store)
{
    int move = 0;
    for (int i = 0; i < store.Count; i++)
    {
        if (area.Height + point.Y > store[i].point.Y && point.Y < store[i].area.Height + store[i].point.Y &&
            point.X >= store[i].point.X + store[i].area.Width)
        {
            int l = store[i].point.X + store[i].area.Width;
            if (move < l)
            {
                move = l;
            }
        }
    }

    move = point.X - move;
    point.X -= move;
    return move;
}

/// <summary>
/// BL算法加强版
/// </summary>
/// <param name="store">当前已填充的拉面店</param>
/// <returns>可以移动的最大步数</returns>
public Point BL_plus_move(List<Store> store)
{
    int down = 0;
    int left = 0;
    for (int i = 0; i < store.Count; i++)
    {
        if (point.X + area.Width > store[i].point.X && point.X < store[i].point.X + store[i].area.Width &&
            point.Y >= store[i].point.Y + store[i].area.Height)
        {
            int l = store[i].point.Y + store[i].area.Height;
            if (down < l)
            {
                down = l;
                left = store[i].point.X;
            }
        }
    }

    down = point.Y - down;
    point.Y -= down;
    int move = 0;
    for (int i = 0; i < store.Count; i++)
    {
        if (point.Y + area.Height > store[i].point.Y && point.Y < store[i].point.Y + store[i].area.Height &&
            point.X >= store[i].point.X + store[i].area.Width)
        {
            int l = store[i].point.X + store[i].area.Width;
            if (move < l)
            {
                move = l;
            }
        }
    }

    left = Math.Min(point.X + area.Width - left, point.X - move);
    point.X -= left;
    return new Point(down, left);
}

At this point, a simple Store class is basically implemented. Next comes the implementation of the Individual class.