Javascript: оптимизировать обнаружение столкновений между спрайтом и массивом спрайтов

Question

У меня есть холст, на котором пользователи могут загружать и размещать свои собственные изображения (с поддержкой прозрачности).

Моя цель - не допускать представления, которые перекрывают любые другие существующие изображения.

Длядля этого я бы сделал следующее (псевдокод):

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 x 1200. Допустим, покрыта только половина всех доступных пикселей, тогда у нас будет 720.000 пикселей, которые уже покрыты,Учитывая, что размер представления равен 300 x 300 (приблизительная оценка), мы сравниваем 720 000 существующих пикселей с 30 000 новых пикселей, что дает нам 36 000 000 000 итераций.Быстрый тест на моем ноутбуке занял минуту за 2 миллиарда итераций.15 минут на одно обнаружение столкновения для меня было бы неприемлемым.

Итак, мой вопрос: как я могу оптимизировать обнаружение столкновений без ущерба для точности?

Answer 1

Сначала выполните проверку столкновения ограничивающего прямоугольника, затем проверяйте пиксели, только если ограничивающие прямоугольники перекрываются.

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