Question 49622 in Javascript Question posted in
A very good W3school tutorial can be found here.

How do I make the selection function more efficient? – Javascript

    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>
Tags:

2

Answers


  1. 0

    You can pep this up a lot by redrawing less. Drawing the grid at the beginning of the drawSelection function is unnecessary because the function redraws all the changed cells at the end of it.

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

    Also, because the selection color is partially transparent, the selected squares become opaque during selection. If that’s not intentional, you should use a completely opaque color for the selection. Then you wouldn’t need to redraw the grid in the confirmSelection function either, so the pop up wouldn’t lag as much.

    Login or Signup to reply.
  2. 0

    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.

    Login or Signup to reply.
Please signup or login to give your own answer.

Back To Top
Search