如何优化Canvas网格选择算法以解决严重卡顿问题？

核心思路 #

原全网格遍历（100万次循环）完全冗余，当已占用单元格数量远小于总网格数时，通过排序+二分查找可快速缩小检查范围，将时间复杂度从O(N)（N=1e6）降至O(log M + K)（M为已占用单元格数量，K为候选区间长度）。

实现步骤 #

1. 预处理已占用单元格

先将已占用单元格转换为可排序的结构化数据，两种常用方式：

方式一：全局索引排序

给每个单元格生成行优先的唯一索引，将所有已占用单元格的索引存入数组并排序：

// 假设occupiedCells为存储已占用单元格的数组，每个元素格式为{x, y}
const occupiedIndices = occupiedCells.map(cell => cell.y * 1000 + cell.x).sort((a, b) => a - b);

方式二：按行分组存储

将已占用单元格按行号分组，每行内的x坐标排序，该方式更精准，适合选择区域较小的场景：

const occupiedByRow = {};
occupiedCells.forEach(cell => {
    if (!occupiedByRow[cell.y]) occupiedByRow[cell.y] = [];
    occupiedByRow[cell.y].push(cell.x);
});
// 对每行的x坐标数组排序
Object.values(occupiedByRow).forEach(xArr => xArr.sort((a, b) => a - b));

2. 基于二分查找的重叠检测

方案一：全局索引查找

通过二分查找定位选择区域对应的索引范围，再遍历候选单元格做精确校验：

function hasOverlap(x1, y1, x2, y2) {
    const minIdx = y1 * 1000 + x1;
    const maxIdx = y2 * 1000 + x2;

    // 二分查找左边界：第一个 >= minIdx的元素位置
    let left = 0, right = occupiedIndices.length;
    while (left < right) {
        const mid = Math.floor((left + right) / 2);
        occupiedIndices[mid] >= minIdx ? right = mid : left = mid + 1;
    }

    // 二分查找右边界：第一个 > maxIdx的元素位置
    let rightBound = 0;
    right = occupiedIndices.length;
    while (rightBound < right) {
        const mid = Math.floor((rightBound + right) / 2);
        occupiedIndices[mid] > maxIdx ? right = mid : rightBound = mid + 1;
    }

    // 遍历候选区间，检查是否在选择区域内
    for (let i = left; i < rightBound; i++) {
        const idx = occupiedIndices[i];
        const y = Math.floor(idx / 1000);
        const x = idx % 1000;
        if (x >= x1 && x <= x2 && y >= y1 && y <= y2) return true;
    }
    return false;
}

方案二：按行分组查找

直接遍历选择区域覆盖的行，对每行的已占用x坐标做二分查找，效率更高：

function hasOverlapByRow(x1, y1, x2, y2) {
    // 遍历选择区域涉及的所有行
    for (let y = y1; y <= y2; y++) {
        const xArr = occupiedByRow[y];
        if (!xArr || xArr.length === 0) continue;

        // 查找第一个 >= x1的x坐标
        let left = 0, right = xArr.length;
        while (left < right) {
            const mid = Math.floor((left + right) / 2);
            xArr[mid] >= x1 ? right = mid : left = mid + 1;
        }

        // 若找到的x坐标 <= x2，说明存在重叠
        if (left < xArr.length && xArr[left] <= x2) return true;
    }
    return false;
}

注意事项 #

• 当已占用单元格新增/删除时，需同步更新排序后的数组或分组数据，否则查找结果会出错
• 若已占用单元格极少（如<100），二分查找提升不明显，但只要已占用数超过1000，对比全量遍历的性能差距会非常显著
• 选择区域越大，按行分组的方案优势越明显，因其仅遍历选择区域覆盖的行，而非全局

内容的提问来源于stack exchange，提问作者chovy