CODEWITHSUNDEEP
javascriptalgorithmmath
yerpy
yerpy

Reputation: 1446

Find all rectangles that fit in grid system

I am working on algorithms and looking for best solution for finding all places in gird where I can add rectangle.

I've written simple test:

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);
});

The visualisation would be:

enter image description here

The brute force solution would be to loop through every cell and check the range of N x M where N | M is size of the dragged element. Does any one have better way to do it ? Any example ?

Upvotes: 2

Views: 903

Answers (1)

Trentium
Trentium

Reputation: 3719

Per my earlier comment to the question, using the algorithm in my second answer at Bin Packing Js implementation using box rotation for best fit , you can feed all the empty blocks to the heap, and then run unionAll to obtain the available rectangular cell block regions. (Note that the x1 / y1 coordinates are such (x1 - x0) and (y1 - y0) represent the size of the cell/block being defined). Using the visualization in the question as example data, populate the heap with all the single cells that are available, and then call '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);

...which results in the heap being reduced to...

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

...representing the cell blocks that are available. Notice that heap[0] and heap[1] overlap, as the algorithm is simply finding the largest available rectangular regions for use.

Then, if you're planning to drop elements into your grid, and you need to know what cells are left over, you can use the adjustHeap method to recalculate the available space. Let's say you add a rectangle the size of 2 horizontal cells starting at column 3 row 2. Continuing from above...

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

..results in the heap of...

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

Again, note the overlap of the resulting rectangles, as this feature is to simplify seeking a rectangular region of the desired size.

A few notes:

  • Not all the functions from Packer are required in your case.
  • I'm not keen on the way the Packer interface is laid out, but generally left it as is for the benefit of the 2D Bin Packer question. If I were using this in one of my projects, I would convert it to a class.
  • In working through your example, I found myself going cross eyed looking at the x0,y0,x1,y1 means of defining the cells. You might find it easier if you reworked the algorithm to make use of x,y (the origin of the cell block) and w,h (the width and height of the cell block).

Upvotes: 1

Related Questions