基于Sweep Line算法实现矩形低重叠随机分布的技术咨询

核心逻辑通俗拆解 #

你不用纠结“扫描线”这个术语的复杂定义，核心就是把画布上所有空白区域拆成规整的矩形块——这些块是100%安全的可放置区域，新矩形只从这些块里选位置放，从根源上避免重叠。

打个比方：就像你在一张白纸上贴便利贴，每贴一张，剩下的空白不会是碎渣状，而是被便利贴分割成几个完整的矩形空白区，下次贴新便利贴就从这些空白区里挑，肯定不会贴到已有便利贴上。扫描线的作用就是帮你高效维护、更新这些空白矩形块。

具体实现步骤 #

• 初始化：把整个画布作为第一个可放置矩形块，比如{x:0, y:0, width:画布宽, height:画布高}
• 选块放矩形：先过滤出能放下目标矩形的空白块，随机挑一个；再在这个块内随机选位置（保证目标矩形完全嵌在块里）
• 更新空白块：放完新矩形后，把原来的空白块拆成最多4个新的空白区（上下左右四个方向的剩余空间），替换掉原来的块
• 重复操作：直到放完所有矩形，或者没有足够大的空白块为止

伪代码实现 #

// 定义矩形结构：x/y为左上角坐标，width/height为尺寸
struct Rect {
    x: number,
    y: number,
    width: number,
    height: number
}

// 初始化可放置空白区域列表
availableRects = [new Rect(0, 0, canvasWidth, canvasHeight)]

function placeRandomRect(targetWidth, targetHeight):
    // 筛选出能放下目标矩形的空白块
    validBlocks = availableRects.filter(block => block.width >= targetWidth && block.height >= targetHeight)
    if validBlocks.length === 0:
        return null // 无足够空间
    
    // 随机选一个可用空白块
    selectedBlock = validBlocks[Math.floor(Math.random() * validBlocks.length)]
    
    // 在块内随机确定放置位置（确保矩形完全在块内）
    posX = selectedBlock.x + Math.floor(Math.random() * (selectedBlock.width - targetWidth + 1))
    posY = selectedBlock.y + Math.floor(Math.random() * (selectedBlock.height - targetHeight + 1))
    newRect = new Rect(posX, posY, targetWidth, targetHeight)
    
    // 拆分原空白块为新的空白区域
    newAvailable = []
    // 上方剩余空白
    if posY > selectedBlock.y:
        newAvailable.push(new Rect(
            selectedBlock.x,
            selectedBlock.y,
            selectedBlock.width,
            posY - selectedBlock.y
        ))
    // 下方剩余空白
    if posY + targetHeight < selectedBlock.y + selectedBlock.height:
        newAvailable.push(new Rect(
            selectedBlock.x,
            posY + targetHeight,
            selectedBlock.width,
            selectedBlock.y + selectedBlock.height - (posY + targetHeight)
        ))
    // 左侧剩余空白（仅在新矩形上下边界之间的部分）
    if posX > selectedBlock.x:
        newAvailable.push(new Rect(
            selectedBlock.x,
            posY,
            posX - selectedBlock.x,
            targetHeight
        ))
    // 右侧剩余空白（仅在新矩形上下边界之间的部分）
    if posX + targetWidth < selectedBlock.x + selectedBlock.width:
        newAvailable.push(new Rect(
            posX + targetWidth,
            posY,
            selectedBlock.x + selectedBlock.width - (posX + targetWidth),
            targetHeight
        ))
    
    // 更新可放置区域：移除已用块，加入新拆分的空白块
    availableRects = availableRects.filter(block => block !== selectedBlock).concat(newAvailable)
    
    return newRect

为什么这不是暴力算法？ #

暴力算法是每次随机选位置后，和所有已放矩形逐一检测重叠，复杂度是O(n²)（n为已放矩形数）。而这个方法从根源上避免了重叠检测——新矩形只在已确认的空白块里放置，每次仅操作空白块列表，拆分和筛选的复杂度远低于暴力检测，效率提升明显。

实用优化技巧 #

• 给空白块加权重：优先选择面积大的块放置，避免小矩形过早占满大空间
• 允许少量重叠：如果业务允许，可放宽validBlocks的筛选条件，允许目标矩形与块边缘有一定比例的重叠
• 清理极小块：定期移除面积小于阈值的空白块，减少列表长度提升效率

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