Замощение плоскости произвольными прямоугольниками

Question

У меня есть множество прямоугольных кусков(1-1, 2-1, 1-2, 2-2 и т.д.). Нужно их всех положить так, чтобы прямоугольную область, которую они занимают имела наименьшую площадь. Например у нас есть 1 кусок 1 на 1 и 1 2 на 1. Итого мы должны как то их скомпоновать на плоскости при наименьшей площади образуемого обрамляющего прямоугольника: прямоугольник получился 3 на 1, в начале на координате 0:0 стоит первый кусок, а на 1:0 второй.

Есть ли уже готовые алгоритмы такого замощения или придется думать самому? Если о применении, то это нужно для генерации общей текстуры из нескольких текстур

Answer 1

что то получилось

static class Programm
{
    public static void Main(string[] args)
    {
        Random random = new Random();
        const int count = 15;
        var texs = new Texture[count];

        string views = "#!/+=.&^%$@()|5";


        while (true)
        {
            Console.Clear();
            var symb = 0;

            for (int i = 0; i < count; i++)
            {
                texs[i] = new Texture(random.Next(1, 4), random.Next(1, 5), views[symb++]);
            }

            TextureAsm asembler = new TextureAsm(texs.ToList());
            asembler.PlaceTextures();
            Thread.Sleep(1000);
        }
    }
    }

    public struct TextureUnit(int x, int y, char view)
    {
    public int X = x, Y = y;

    public char View = view;

    public static TextureUnit operator +(TextureUnit tu1, (int xMove, int yMove) move)
    {
        return new TextureUnit { X = tu1.X + move.xMove, Y = tu1.Y + move.yMove, View = tu1.View };
    }

    public override string ToString()
    {
        return $"{X}x{Y} ({View})";
    }

    public override bool Equals(object obj)
    {
        if (obj is not TextureUnit)
            return false;
        var local = (TextureUnit)obj;
        return local.X == X && local.Y == Y;
    }
    }

    public class Texture
    {
    public int X, Y, XSize, YSize;

    private List<TextureUnit> zeroUnits = new();

    public List<TextureUnit> MovedUnits;

    public Texture(int xSize, int ySize, char view)
    {
        XSize = xSize;
        YSize = ySize;
        for (int i = 0; i < XSize; i++)
        {
            for (int j = 0; j < YSize; j++)
            {
                zeroUnits.Add(new TextureUnit(i, j, view));
            }
        }

        MovedUnits = zeroUnits;
    }

    public List<TextureUnit> GetUnits()
    {
        MovedUnits = zeroUnits.Select(i => i + (X, Y)).ToList();
        return MovedUnits;
    }

    public int Square() => XSize * YSize;

    public override int GetHashCode()
    {
        return 15;
    }

    public override string ToString()
    {
        return $"{XSize}x{YSize} > {X} \u2193 {Y}";
    }
    }

    public class TextureAsm
    {
    public List<Texture> Textures;

    public TextureAsm(List<Texture> textures)
    {
        Textures = textures;
    }

    public double PlaceTextures()
    {
        List<TextureUnit> outTexture = new List<TextureUnit>();
        var sorted = Textures.OrderBy(i => i.Square()).Reverse().ToList();


        foreach (var texture in sorted)
        {
            (int x, int y) currentSize = GetOutSize(outTexture);
            (int x, int y) selectedPos = (0, 0);
            int maxSq = int.MaxValue;

            void trySet(int i, int j)
            {
                var tempTexture = new List<TextureUnit>(outTexture);
                texture.X = i;
                texture.Y = j;
                var moved = texture.GetUnits();
                bool next = false;
                foreach (var unit in moved)
                {
                    if (tempTexture.Contains(unit))
                    {
                        next = true;
                        break;
                    }
                }

                if (next)
                    return;

                tempTexture.AddRange(moved);
                var curSize = GetOutSize(tempTexture);
                if (curSize.x * curSize.y >= maxSq)
                    return;
                maxSq = curSize.x * curSize.y;
                selectedPos = (i, j);
            }

            if (outTexture.Count != 0)
            {
                if (currentSize.x > currentSize.y)
                    for (int i = 0; i < currentSize.x + 1; i++)
                    {
                        for (int j = 0; j < currentSize.y + 1; j++)
                        {
                            trySet(i, j);
                        }
                    }
                else
                    for (int j = 0; j < currentSize.y + 1; j++)
                    {
                        for (int i = 0; i < currentSize.x + 1; i++)
                        {
                            trySet(i, j);
                        }
                    }
            }


            texture.X = selectedPos.x;
            texture.Y = selectedPos.y;

            outTexture.AddRange(texture.GetUnits());
            DrawSet(outTexture);
        }

        (int x, int y) finalSize = GetOutSize(outTexture);

        Console.SetCursorPosition(0, finalSize.y + 1);
        Console.WriteLine(finalSize);
        Console.WriteLine(outTexture.Count);
        Console.WriteLine($"{Math.Round(outTexture.Count / (double)(finalSize.y * finalSize.x) * 100, 2)} %");
        return outTexture.Count / (double)(finalSize.y * finalSize.x) * 100;
    }

    (int x, int y) GetOutSize(List<TextureUnit> outTexture)
    {
        (int x, int y) res = (0, 0);
        foreach (var unit in outTexture)
        {
            if (res.x < unit.X)
                res.x = unit.X;
            if (res.y < unit.Y)
                res.y = unit.Y;
        }

        return (res.x + 1, res.y + 1);
    }

    static void DrawSet(List<TextureUnit> set)
    {
        var cursor = Console.GetCursorPosition();
        foreach (var unit in set)
        {
            Console.SetCursorPosition(unit.X, unit.Y);
            Console.Write(unit.View);
        }

        Console.SetCursorPosition(cursor.Left, cursor.Top);
    }
}

в итоге +- оптимальностью получается 93-94%

БЛОГ НА HUSL

Замощение плоскости произвольными прямоугольниками

Ответы (1 шт):