Как сделать функцию выбора более эффективной?

    const canvas = document.getElementById('myCanvas');
        const ctx = canvas.getContext('2d');
        const overlay = document.getElementById('overlay');
        const fileInput = document.getElementById('fileInput');
        const titleInput = document.getElementById('titleInput');
        const urlInput = document.getElementById('urlInput');
        const submitBtn = document.getElementById('submitBtn');
        const cancelBtn = document.getElementById('cancelBtn');
        const gridSize = 1000;
        const cellSize = 20;
        const gridColor = 'rgba(0,0,0,0.2)';
        const selectionColor = 'rgba(0, 0, 255, 0.5)';
        let mouseDown = false;
        let startCell = null;
        let endCell = null;
        const occupiedCells = new Set();
        let tempSelection = null;

        function drawGrid() {
            ctx.clearRect(0, 0, canvas.width, canvas.height);
            ctx.strokeStyle = gridColor;
            for (let i = 0; i <= gridSize; i++) {
                for (let j = 0; j <= gridSize; j++) {
                    ctx.strokeRect(i * cellSize, j * cellSize, cellSize, cellSize);
                }
            }
        }

        function getCellCoordinates(x, y) {
            return {
                x: Math.floor(x / cellSize),
                y: Math.floor(y / cellSize)
            };
        }

        function isCellOccupied(cell) {
            return occupiedCells.has(`${cell.x},${cell.y}`);
        }

        function isSelectionOverlapping(xMin, xMax, yMin, yMax) {
            for (let x = xMin; x <= xMax; x++) {
                for (let y = yMin; y <= yMax; y++) {
                    const currentCell = { x, y };
                    if (isCellOccupied(currentCell)) {
                        return true;
                    }
                }
            }
            return false;
        }

        function drawSelection() {
            if (!startCell || !endCell) return;

            drawGrid();
            occupiedCells.forEach(cell => {
                const [x, y] = cell.split(',');
                ctx.fillStyle = selectionColor;
                ctx.fillRect(x * cellSize, y * cellSize, cellSize, cellSize);
            });

            let xMin = Math.min(startCell.x, endCell.x);
            let xMax = Math.max(startCell.x, endCell.x);
            let yMin = Math.min(startCell.y, endCell.y);
            let yMax = Math.max(startCell.y, endCell.y);

            while (isSelectionOverlapping(xMin, xMax, yMin, yMax)) {
                if (endCell.x > startCell.x) {
                    xMax--;
                } else if (endCell.x < startCell.x) {
                    xMin++;
                }
                if (endCell.y > startCell.y) {
                    yMax--;
                } else if (endCell.y < startCell.y) {
                    yMin++;
                }
            }

            tempSelection = { xMin, xMax, yMin, yMax };

            ctx.fillStyle = selectionColor;
            for (let x = xMin; x <= xMax; x++) {
                for (let y = yMin; y <= yMax; y++) {
                    ctx.fillRect(x * cellSize, y * cellSize, cellSize, cellSize);
                }
            }

            ctx.fillStyle = '#000';
            ctx.fillText(`${(xMax - xMin + 1) * cellSize}x${(yMax - yMin + 1) * cellSize}`, endCell.x * cellSize, endCell.y * cellSize);
        }

        function confirmSelection() {
            const { xMin, xMax, yMin, yMax } = tempSelection;

            for (let x = xMin; x <= xMax; x++) {
                for (let y = yMin; y <= yMax; y++) {
                    const currentCell = { x, y };
                    occupiedCells.add(`${currentCell.x},${currentCell.y}`);
                }
            }

            drawGrid();
            occupiedCells.forEach(cell => {
                const [x, y] = cell.split(',');
                ctx.fillStyle = selectionColor;
                ctx.fillRect(x * cellSize, y * cellSize, cellSize, cellSize);
            });
        }

        canvas.addEventListener('mousedown', (e) => {
            mouseDown = true;
            startCell = getCellCoordinates(e.offsetX, e.offsetY);
        });

        canvas.addEventListener('mousemove', (e) => {
            if (!mouseDown) return;
            endCell = getCellCoordinates(e.offsetX, e.offsetY);
            drawSelection();
        });

        canvas.addEventListener('mouseup', (e) => {
            if (!mouseDown) return;
            mouseDown = false;
            endCell = getCellCoordinates(e.offsetX, e.offsetY);
            if (!isSelectionOverlapping(tempSelection.xMin, tempSelection.xMax, tempSelection.yMin, tempSelection.yMax)) {
                confirmSelection();
            }
            startCell = null;
            endCell = null;
            overlay.style.display = 'block';
        });

        canvas.addEventListener('mouseleave', (e) => {
            if (!mouseDown) return;
            mouseDown = false;
            startCell = null;
            endCell = null;
        });

        submitBtn.addEventListener('click', () => {
            // Handle form submission here
            overlay.style.display = 'none';
            fileInput.value = '';
            titleInput.value = '';
            urlInput.value = '';
        });

        cancelBtn.addEventListener('click', () => {
            overlay.style.display = 'none';
            fileInput.value = '';
            titleInput.value = '';
            urlInput.value = '';
        });

        drawGrid();

        canvas {
            border: 1px solid rgba(0,0,0,.2);
        }

        #overlay {
            display: none;
            position: fixed;
            left: 0;
            top: 0;
            width: 100%;
            height: 100%;
            background-color: rgba(0, 0, 0, 0.5);
            z-index: 2;
        }

        #form-container {
            display: flex;
            justify-content: center;
            align-items: center;
            height: 100%;
        }

        #upload-form {
            background-color: white;
            padding: 20px;
            border-radius: 5px;
        }

<!DOCTYPE html>
<html lang = "en">

<head>
    <meta charset = "UTF-8">
    <meta name = "viewport" content = "width=device-width, initial-scale=1.0">
    <title>1000x1000 Grid with Non-overlapping Selectable Boxes and File Upload</title>
    <style>
    </style>
</head>

<body>
    <canvas id = "myCanvas" width = "1000" height = "1000"></canvas>
    <div id = "overlay">
        <div id = "form-container">
            <form id = "upload-form">
                <div>
                    <label for = "fileInput">Upload File:</label>
                    <input type = "file" id = "fileInput">
                </div>
                <div>
                    <label for = "titleInput">Title:</label>
                    <input type = "text" id = "titleInput">
                </div>
                <div>
                    <label for = "urlInput">URL:</label>
                    <input type = "text" id = "urlInput">
                </div>
                <button type = "button" id = "submitBtn">Submit</button>
                <button type = "button" id = "cancelBtn">Cancel</button>
            </form>
        </div>
    </div>

</body>

</html>

Этот алгоритм выбора имеет огромное отставание. Мне сказали, что бинарный поиск для поиска занятых ячеек будет быстрее, но я не знаю, как это сделать.

Он просматривает каждую ячейку сетки, что неэффективно.

<!DOCTYPE html>
<html lang = "en">

<head>
    <meta charset = "UTF-8">
    <meta name = "viewport" content = "width=device-width, initial-scale=1.0">
    <title>1000x1000 Grid with Non-overlapping Selectable Boxes and File Upload</title>
    <style>
        canvas {
            border: 1px solid rgba(0,0,0,.2);
        }

        #overlay {
            display: none;
            position: fixed;
            left: 0;
            top: 0;
            width: 100%;
            height: 100%;
            background-color: rgba(0, 0, 0, 0.5);
            z-index: 2;
        }

        #form-container {
            display: flex;
            justify-content: center;
            align-items: center;
            height: 100%;
        }

        #upload-form {
            background-color: white;
            padding: 20px;
            border-radius: 5px;
        }
    </style>
</head>

<body>
    <canvas id = "myCanvas" width = "1000" height = "1000"></canvas>
    <div id = "overlay">
        <div id = "form-container">
            <form id = "upload-form">
                <div>
                    <label for = "fileInput">Upload File:</label>
                    <input type = "file" id = "fileInput">
                </div>
                <div>
                    <label for = "titleInput">Title:</label>
                    <input type = "text" id = "titleInput">
                </div>
                <div>
                    <label for = "urlInput">URL:</label>
                    <input type = "text" id = "urlInput">
                </div>
                <button type = "button" id = "submitBtn">Submit</button>
                <button type = "button" id = "cancelBtn">Cancel</button>
            </form>
        </div>
    </div>
    <script>
        const canvas = document.getElementById('myCanvas');
        const ctx = canvas.getContext('2d');
        const overlay = document.getElementById('overlay');
        const fileInput = document.getElementById('fileInput');
        const titleInput = document.getElementById('titleInput');
        const urlInput = document.getElementById('urlInput');
        const submitBtn = document.getElementById('submitBtn');
        const cancelBtn = document.getElementById('cancelBtn');
        const gridSize = 1000;
        const cellSize = 20;
        const gridColor = 'rgba(0,0,0,0.2)';
        const selectionColor = 'rgba(0, 0, 255, 0.5)';
        let mouseDown = false;
        let startCell = null;
        let endCell = null;
        const occupiedCells = new Set();
        let tempSelection = null;

        function drawGrid() {
            ctx.clearRect(0, 0, canvas.width, canvas.height);
            ctx.strokeStyle = gridColor;
            for (let i = 0; i <= gridSize; i++) {
                for (let j = 0; j <= gridSize; j++) {
                    ctx.strokeRect(i * cellSize, j * cellSize, cellSize, cellSize);
                }
            }
        }

        function getCellCoordinates(x, y) {
            return {
                x: Math.floor(x / cellSize),
                y: Math.floor(y / cellSize)
            };
        }

        function isCellOccupied(cell) {
            return occupiedCells.has(`${cell.x},${cell.y}`);
        }

        function isSelectionOverlapping(xMin, xMax, yMin, yMax) {
            for (let x = xMin; x <= xMax; x++) {
                for (let y = yMin; y <= yMax; y++) {
                    const currentCell = { x, y };
                    if (isCellOccupied(currentCell)) {
                        return true;
                    }
                }
            }
            return false;
        }

        function drawSelection() {
            if (!startCell || !endCell) return;

            drawGrid();
            occupiedCells.forEach(cell => {
                const [x, y] = cell.split(',');
                ctx.fillStyle = selectionColor;
                ctx.fillRect(x * cellSize, y * cellSize, cellSize, cellSize);
            });

            let xMin = Math.min(startCell.x, endCell.x);
            let xMax = Math.max(startCell.x, endCell.x);
            let yMin = Math.min(startCell.y, endCell.y);
            let yMax = Math.max(startCell.y, endCell.y);

            while (isSelectionOverlapping(xMin, xMax, yMin, yMax)) {
                if (endCell.x > startCell.x) {
                    xMax--;
                } else if (endCell.x < startCell.x) {
                    xMin++;
                }
                if (endCell.y > startCell.y) {
                    yMax--;
                } else if (endCell.y < startCell.y) {
                    yMin++;
                }
            }

            tempSelection = { xMin, xMax, yMin, yMax };

            ctx.fillStyle = selectionColor;
            for (let x = xMin; x <= xMax; x++) {
                for (let y = yMin; y <= yMax; y++) {
                    ctx.fillRect(x * cellSize, y * cellSize, cellSize, cellSize);
                }
            }

            ctx.fillStyle = '#000';
            ctx.fillText(`${(xMax - xMin + 1) * cellSize}x${(yMax - yMin + 1) * cellSize}`, endCell.x * cellSize, endCell.y * cellSize);
        }

        function confirmSelection() {
            const { xMin, xMax, yMin, yMax } = tempSelection;

            for (let x = xMin; x <= xMax; x++) {
                for (let y = yMin; y <= yMax; y++) {
                    const currentCell = { x, y };
                    occupiedCells.add(`${currentCell.x},${currentCell.y}`);
                }
            }

            drawGrid();
            occupiedCells.forEach(cell => {
                const [x, y] = cell.split(',');
                ctx.fillStyle = selectionColor;
                ctx.fillRect(x * cellSize, y * cellSize, cellSize, cellSize);
            });
        }

        canvas.addEventListener('mousedown', (e) => {
            mouseDown = true;
            startCell = getCellCoordinates(e.offsetX, e.offsetY);
        });

        canvas.addEventListener('mousemove', (e) => {
            if (!mouseDown) return;
            endCell = getCellCoordinates(e.offsetX, e.offsetY);
            drawSelection();
        });

        canvas.addEventListener('mouseup', (e) => {
            if (!mouseDown) return;
            mouseDown = false;
            endCell = getCellCoordinates(e.offsetX, e.offsetY);
            if (!isSelectionOverlapping(tempSelection.xMin, tempSelection.xMax, tempSelection.yMin, tempSelection.yMax)) {
                confirmSelection();
            }
            startCell = null;
            endCell = null;
            overlay.style.display = 'block';
        });

        canvas.addEventListener('mouseleave', (e) => {
            if (!mouseDown) return;
            mouseDown = false;
            startCell = null;
            endCell = null;
        });

        submitBtn.addEventListener('click', () => {
            // Handle form submission here
            overlay.style.display = 'none';
            fileInput.value = '';
            titleInput.value = '';
            urlInput.value = '';
        });

        cancelBtn.addEventListener('click', () => {
            overlay.style.display = 'none';
            fileInput.value = '';
            titleInput.value = '';
            urlInput.value = '';
        });

        drawGrid();
    </script>
</body>

</html>