javascript - Javascript:优化Sprite和Sprite数组之间的碰撞检测

我有一个画布，用户可以在其上上传并放置自己的图像（支持透明性）。

我的目标是不允许与任何其他现有图像重叠的提交。

为此，我将执行以下操作（伪代码）：

for(let i = 0; i < images.length; i++){
    const existingImage = images[i]
    for(let y = 0; y < existingImage.pixels.length; y++){
        for(let x = 0; x < newImage.pixels.length; x++){
            if(newImage.pixels[x] === existingImage.pixels[y])
              return false;
        }
    }

}

return true

但是，画布的分辨率为1200 x1200。假设仅覆盖了所有可用像素的一半，那么我们将已经覆盖了720.000像素。给定一个提交像300 x 300（保守估计），那么我们最终将720.000现有像素与30.000新像素进行比较，这给了我们大约36.000.000.000迭代次数。在我的笔记本电脑上进行的快速测试最终耗时一分钟，进行了20亿次迭代。 15分钟的一次碰撞检测对我来说是不可接受的。

所以我的问题是，如何在不影响准确性的情况下优化碰撞检测？

最佳答案

首先进行边界框碰撞测试，然后仅在边界框重叠时测试像素。

for ( var existingImage of images ) {
    if ( !(
        existingImage.left > newImage.right ||
        existingImage.right < newImage.left ||
        existingImage.top > newImage.bottom ||
        existingImage.bottom < newImage.top
    )) {
        if ( pixelsOverlap( existingImage, newImage ) ) return false;
    }
}