Найти все прямоугольники, которые вписываются в сетку

Question

Я работаю над алгоритмами и ищу лучшее решение для поиска всех мест в гирде, где я могу добавить прямоугольник.

Я написал простой тест:

test('Based on layout elements getting highlighting positions where we can drop element', () => {
    const layoutElements = [
        {
            row: 3,
            column: 2,
            width: 2,
            height: 1,
        },
        {
            row: 3,
            column: 4,
            width: 1,
            height: 3,
        },
        {
            row: 4,
            column: 1,
            width: 1,
            height: 2,
        },
    ];

    const highlightingPositions = getHighlightingLayoutDropPositions({
        draggedElWidth: 2,
        draggedElHeight: 2,
        layoutWidth: 4,
        layoutHeight: 5,
        layoutElements
    });

    expect(highlightingPositions.length).toEqual(12);
});

Визуализация будетбыть:

Решение грубой силы должно было бы пройти через каждую ячейку и проверить диапазон N x M, где N |М - размер перетаскиваемого элемента.У кого-нибудь есть лучший способ сделать это?Любой пример?

Answer 1

В соответствии с моим предыдущим комментарием к вопросу, используя алгоритм из моего второго ответа в Реализация Bin Packing Js с использованием поворота блока для наилучшего соответствия , вы можете подать все пустые блоки в кучу, а затем запустить unionAll для получения доступных прямоугольных областей ячейки. (Обратите внимание, что координаты x1 / y1 таковы (x1 - x0) и (y1 - y0) представляют размер определяемой ячейки / блока). Используя визуализацию в вопросе в качестве примера данных, заполните кучу всеми доступными ячейками и затем вызовите 'unionAll` ...

x = new Packer(4,5);
x.heap = [{x0:1, y0:1, x1:2, y1:2},  // All are w:1, h:1
          {x0:2, y0:1, x1:3, y1:2},
          {x0:3, y0:1, x1:4, y1:2},
          {x0:4, y0:1, x1:5, y1:2},
          {x0:1, y0:2, x1:2, y1:3},
          {x0:2, y0:2, x1:3, y1:3},
          {x0:3, y0:2, x1:4, y1:3},
          {x0:4, y0:2, x1:5, y1:3},

          {x0:1, y0:3, x1:2, y1:4},

          {x0:2, y0:4, x1:3, y1:5},
          {x0:2, y0:5, x1:3, y1:6},
          {x0:3, y0:4, x1:4, y1:5},
          {x0:3, y0:5, x1:4, y1:6}]

x.unionAll();
console.log(x);

... что приводит к уменьшению кучи до ...

heap: Array(3)
0: {x0: 1, y0: 1, x1: 5, y1: 3}  // w:4, h:2
1: {x0: 1, y0: 1, x1: 2, y1: 4}  // w:1, h:3
2: {x0: 2, y0: 4, x1: 4, y1: 6}  // w:2, h:2

... представляет доступные блоки ячеек. Обратите внимание, что куча [0] и куча [1] перекрываются, поскольку алгоритм просто находит самые большие доступные прямоугольные области для использования.

Затем, если вы планируете помещать элементы в свою сетку, и вам нужно знать, какие ячейки остались, вы можете использовать метод adjustHeap для пересчета доступного пространства. Допустим, вы добавили прямоугольник размером 2 горизонтальных ячейки, начиная со столбца 3, строки 2. Продолжая сверху ...

x.adjustHeap({x0:3, y0:2, x1:5, y1:3});  // w:2, h:1
console.log(x);

.. приводит к куче ...

heap: Array(4)
0: {x0: 1, y0: 1, x1: 2, y1: 4}  // w:1, h:3
1: {x0: 2, y0: 4, x1: 4, y1: 6}  // w:2, h:2
2: {x0: 1, y0: 1, x1: 5, y1: 2}  // w:4, h:1
3: {x0: 1, y0: 1, x1: 3, y1: 3}  // w:2, h:2

Опять же, обратите внимание на перекрытие получающихся прямоугольников, так как эта функция упрощает поиск прямоугольной области нужного размера.

Несколько заметок:

• В вашем случае требуются не все функции из Packer.
• Я не заинтересован в том, как выстроен интерфейс Packer, но, как правило, оставил его как есть в пользу вопроса 2D Bin Packer. Если бы я использовал это в одном из моих проектов, я бы преобразовал его в класс.
• Прорабатывая ваш пример, я обнаружил, что смотрю в глаза, глядя на x0,y0,x1,y1 средство определения клеток. Возможно, вам будет проще, если вы переработаете алгоритм, чтобы использовать x,y (начало блока ячеек) и w,h (ширина и высота блока ячеек).