Search code examples
javascriptbinary-tree

How do I make the selection function more efficient?

    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>

There's a huge lag with this selection algorithm. I've been told a binary search to find occupied cells would be quicker, but I don't know how to do that.

It looks at every cell on the grid, which isn't efficient.

<!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>
Solution

  • The main delay is caused by a mistake you made in drawGrid. The loop variable is going from 0 to 999, but you don't have that many lines to draw. Instead of multiplying that value with 20, you should step by 20:

    So change that loop to:

        for (let i = 0; i <= gridSize; i+=cellSize) { // step
        for (let j = 0; j <= gridSize; j+=cellSize) {
            ctx.strokeRect(i, j, cellSize, cellSize); // no multiplication
        }
    }

    There is another problem that when the user start the drag from within a rectangle, you get into an infinite loop. This is easy to avoid: just ignore a mousedown event when it occurs on a rectangle:

        canvas.addEventListener('mousedown', (e) => {
        startCell = getCellCoordinates(e.offsetX, e.offsetY);
        mouseDown = !isCellOccupied(startCell); // Must ensure not in rectangle
    });

    Here is the snippet with those changes (I removed the overlay/form):

    const canvas = document.getElementById('myCanvas');
const ctx = canvas.getContext('2d');

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+=cellSize) { // step
        for (let j = 0; j <= gridSize; j+=cellSize) {
            //ctx.strokeRect(i * cellSize, j * cellSize, cellSize, cellSize);
            ctx.strokeRect(i, j, 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) => {
    startCell = getCellCoordinates(e.offsetX, e.offsetY);
    mouseDown = !isCellOccupied(startCell); // Must ensure not in rectangle
});

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

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

drawGrid();
    <canvas id="myCanvas" width="1000" height="1000"></canvas>

    NB: You might want to improve on the algorithm to make a rectangle "fit" when the mouse moves over another rectangle. The further the mouse moves over another rectangle, the smaller the new rectangle becomes. I find this a bit counter-intuitive.