javascript - 优化对象重叠检测 (Javascript)

Question

问题

我正在编写一个程序，其中涉及计算一个移动物体与另一个物体重叠的像素数。我必须每秒多次返回该值，因此程序必须高效。我想出的例子似乎并非如此。

<小时/>

示例

让我们缩小一分钟，假设我们有一个 3*3 像素的对象和一个 3*2 像素的对象

a b c
d e f   j k l
g h i   m n o

每个字母代表每个对象的一个​​单独像素。 3*3 对象位于左侧，3*2 对象位于右侧，x 值比较大对象大 4。它们不重叠。

<小时/>

代码

目前，我通过一个简单的函数返回重叠像素的数量，该函数检查对象一中的每个像素与对象二中的每个像素是否重叠:

var a = {
    width: 3,
    height: 3,
    x: 0,
    y: 0
}

var b = {
    width: 3,
    height: 2,
    x: 4,
    y: 0
}

function overlappingPixels(object_1, object_2) {
    var overlapping = 0;
    for (var w_1 = 0; w_1 < object_1.width; w_1++) {
        for (var h_1 = 0; h_1 < object_1.height; h_1++) {
            for (var w_2 = 0; w_2 < object_1.width; w_2++) {
                for (var h_2 = 0; h_2 < object_1.height; h_2++) {
                    if (w_1 + object_1.x == w_2 + object_2.x && h_1 + object_1.y == h_2 + + object_2.y) {
                        overlapping++;
                    }
                }
            }
        }
    }
    return overlapping;
}

overlappingPixels(a, b); 返回 0，因为两个对象没有重叠像素。

<小时/>

回顾

回顾一下，我构建了一个函数，用于比较对象一的每个像素与对象二的每个像素是否有重叠。这似乎效率非常低，我很好奇如果需要非常快速地对移动对象执行此计算，是否有更快的选择。随着对象大小的增加，函数的速度会迅速下降。无论如何，我都会对较大的对象执行此计算，因此这并不理想。

谢谢!

Answer 1

有一种简单有效的方法来检查两个矩形是否发生碰撞。

var rect1 = {x: 5, y: 5, width: 50, height: 50}
var rect2 = {x: 20, y: 10, width: 10, height: 10}

if (rect1.x < rect2.x + rect2.width &&
   rect1.x + rect1.width > rect2.x &&
   rect1.y < rect2.y + rect2.height &&
   rect1.height + rect1.y > rect2.y) {
    // collision detected!
}

参见MDN 2D object collision detection

<小时/>

一旦您确定存在碰撞，获得重叠的大小也很容易。只需获取它们重叠处的高度和宽度，然后将它们相乘即可得到面积。请参阅代码片段中的 calculateCollisionLength 函数，了解如何在不逐像素遍历的情况下计算重叠。

const calculateCollisionLength = (point1, point2, length1, length2) => {
    const pointb1 = point1 + length1;
    const pointb2 = point2 + length2;
    const diff1 = Math.abs(point1 - point2);
    const diff2 = Math.abs(pointb1 - pointb2);
    return (length1 + length2 - diff1 - diff2) / 2;
}
function checkCollusion(rect1, rect2) {
    if (rect1.x < rect2.x + rect2.width &&
        rect1.x + rect1.width > rect2.x &&
        rect1.y < rect2.y + rect2.height &&
        rect1.height + rect1.y > rect2.y) {
        // collision detected!

        const collision = { xLength: 0, yLength: 0 };

        collision.xLength = calculateCollisionLength(rect1.x, rect2.x, rect1.width, rect2.width);
        collision.yLength = calculateCollisionLength(rect1.y, rect2.y, rect1.height, rect2.height);

        return collision.xLength * collision.yLength;
    }
    else return null;
}

var rect1 = { x: 5, y: 5, width: 50, height: 50 }
var rect2 = { x: 20, y: 10, width: 10, height: 10 }
console.log(checkCollusion(rect1, rect2))