Как разделить квадрат на N одинаковых прямоугольников и получить их маски?

Question

Как разделить квадрат на N одинаковых прямоугольников и получить их маски?

Рейтинг: 0Ответов: 2Опубликовано: 13.07.2023

У меня есть ширина квадрата и количество итоговых зон, на сколько нужно разделить этот квадрат. Каким алгоритмом можно найти маски каждой из зон?

Выделил несколько фактов в этой задаче:

Если есть ширина, то известно, сколько всего клеточек в квадрате
Если есть общее количество клеток и количество итоговых зон, то известно, сколько клеточек в каждой зоне

Но что это дает?

Вот пара примеров:

Ширина - 4
Количество зон - 2

 0123
0AAAA
1AAAA
2BBBB
3BBBB

Ответ: [
   [[0, 0, 0, 0],
    [0, 0, 0, 0],
    [1, 1, 1, 1],
    [1, 1, 1, 1]],

   [[1, 1, 1, 1],
    [1, 1, 1, 1],
    [0, 0, 0, 0],
    [0, 0, 0, 0]]
]

Если зоны получатся такими, то так тоже подойдет, просто ответ будет немного другим:

 0123
0AABB
1AABB
2AABB
3AABB

Ширина - 6
Количество зон - 9

 012345
0AABBCC
1AABBCC
2DDEEFF
3DDEEFF
4GGHHII
5GGHHII

Ответ: [
   [[1, 1, 0, 0, 0, 0],
    [1, 1, 0, 0, 0, 0],
    [0, 0, 0, 0, 0, 0],
    [0, 0, 0, 0, 0, 0],
    [0, 0, 0, 0, 0, 0],
    [0, 0, 0, 0, 0, 0],

   [[0, 0, 1, 1, 0, 0],
    [0, 0, 1, 1, 0, 0],
    [0, 0, 0, 0, 0, 0],
    [0, 0, 0, 0, 0, 0],
    [0, 0, 0, 0, 0, 0],
    [0, 0, 0, 0, 0, 0],

    ...
]

В первом случае можно было бы идти двойным циклом по порядку и как только бы собралось нежное количество клеточек, то можно было бы к следующей зоне переходить. Но что делать со вторым случаем? Там так сделать будет нельзя, потому что возьмется только 4 первых клеток в первом ряду.

c# математика алгоритм

Источник: Stack Overflow на русском

Answer 1

▲ 2Принят

Вам придётся разложить длину стороны квадрата L на множители

L = w * C
L = h * R

C и R - это количество столбцов и строк, w и h - ширина и высота прямоугольничков зон.

При обходе в двойном цикле номер зоны (из которого можно получить букву при необходимости) из координат вычисляется так:

z = (y/h)*C + (x/w)

Деление целочисленное (в шарпе обычное деление целочисленных переменных)

Answer 2

▲ 0

Вот такой сервис получился благодаря MBo.

public class MasksService : ISectorsService
{
    private readonly int _size;
    
    public MasksService(int size)
    {
        _size = size;
    }
    
    public List<bool[,]> GetMasks(int n)
    {
        var (columns, rows) = GetColumnsAndRowsAmounts(n);
        var globalMask = GetGlobalMask(columns, rows);
        return BuildMasks(globalMask);
    }
   
    private List<bool[,]> BuildMasks(int[,] globalMask)
    {
        var result = new Dictionary<int, bool[,]>();
        for (var x = 0; x < _size; x++)
        for (var y = 0; y < _size; y++)
        {
            result.TryAdd(globalMask[x, y], new bool[_size, _size]);
            result[globalMask[x, y]][x, y] = true;
        }
        return result.Values.ToList();
    }
   
    private int[,] GetGlobalMask(int columns, int rows)
    {
        var result = new int[_size, _size];
        var areaWidth = _size / columns;
        var areaHeight = _size / rows;
        for (var x = 0; x < _size; x++)
        for (var y = 0; y < _size; y++)
        {
            result[x, y] = (y / areaHeight) * rows + (x / areaWidth);
        }
        return result;
    }
   
    private static (int columns, int rows) GetColumnsAndRowsAmounts(int n)
    {
        var groups = new List<(int columns, int rows)>();
        var sqrtN = Math.Sqrt(n);
        for (var i = 1; i <= sqrtN; i++)
        {
            if (n % i == 0)
            {
                groups.Add((i, n / i));
            }
        }
        return groups.OrderBy(x => Math.Abs(x.columns + x.rows - sqrtN )).First();
    }
}

Но последняя строка в GetColumnsAndRowsAmounts еще под вопросом.

Как разделить квадрат на N одинаковых прямоугольников и получить их маски?

Ответы