Как найти пустое место в сетке js?

Question

[RuslanSer]

Есть вот такая вот панель с виджетами. Юзается vue grid layout.
Все виджеты разных размеров.
Количество колонок - 24.
Сверху есть кнопки которые добавляют виджеты.
Из документации предлагается рассчитывать координаты добавляемого виджета так:

x: (this.selectedWidgets.length * 2) % (this.colNum || 12),
y: (this.selectedWidgets.length + (this.colNum || 12)),

Это работает если все добавляемые виджеты одинакового размера, но если разного то не работает и всё располагается очень криво.

И в общем надо формировать виджеты слева направо заполняя пустые места (если виджет туда влезает).

Иначе говоря есть сетка, и нужно как то рассчитать координаты так, чтобы добавляемые виджеты заполняли всю сетку.

Comments

[Сергей Сергей]

это "задача заполнения площади".
https://www.codeproject.com/Articles/210979/Fast-o...

[RuslanSer]

Сергей Сергей, По итогу сделал так чтобы пройтись по всем клеткам сетки и проставить там, занята клетка или нет. И всё вроде получилось:

let x = 0
            let y = 0

            if (this.selectedWidgets.length) {
                let maxRow = 0

                this.selectedWidgets.forEach((selectedWidget) => {
                    if((selectedWidget.y + selectedWidget.h) >= maxRow)
                        maxRow = selectedWidget.y + selectedWidget.h
                })

                maxRow += 50

                let matrix = Array.from({length: maxRow}, () =>
                    Array.from({length: this.colNum}, () => true)
                );

                for (let row = 0; row !== maxRow; row++) {
                    for (let col = 0; col !== this.colNum; col++) {
                        this.selectedWidgets.forEach(selectedWidget => {
                            if ((
                                col >= selectedWidget.x &&
                                col <= selectedWidget.x + selectedWidget.w - 1 &&
                                row >= selectedWidget.y &&
                                row <= selectedWidget.y + selectedWidget.h - 1
                            ))
                                matrix[row][col] = false
                        })
                    }
                }

                let isDefined = false
                for (let row = 0; row !== maxRow; row++) {
                    for (let col = 0; col !== this.colNum; col++) {
                        if (
                            matrix[row][col] &&
                            matrix[row][col + widget.w - 1] &&
                            matrix[row + widget.h][col] &&
                            matrix[row + widget.h][col + widget.w - 1]
                        ) {
                            x = col
                            y = row
                            isDefined = true
                            break
                        }
                    }

                    if (isDefined)
                        break
                }
            }