时间戳

首页 > 解决方案 > 查找适合网格系统的所有矩形

javascript - 查找适合网格系统的所有矩形

问题描述

我正在研究算法并寻找最佳解决方案来查找网格中可以添加矩形的所有位置。

我写了简单的测试：

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 | M 是被拖动元素的大小。有没有人有更好的方法呢？有什么例子吗？

标签： javascriptalgorithmmath

解决方案

根据我之前对该问题的评论，使用我在Bin Packing Js implementation using box rotation for best fit的第二个答案中的算法，您可以将所有空块提供给堆，然后运行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

...表示可用的单元块。请注意 heap[0] 和 heap[1] 重叠，因为该算法只是寻找最大的可用矩形区域以供使用。

然后，如果您打算将元素放入网格中，并且需要知道剩余的单元格，则可以使用该adjustHeap方法重新计算可用空间。假设您从第 3 列第 2 行开始添加一个大小为 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（单元块的宽度和高度），您可能会发现它更容易。

推荐阅读