javascript - 如何对数百个 Canvas 圆进行高性能重叠/碰撞检测？

Question

我正在 Canvas 上绘制 100 个不同大小的圆圈，它们不能重叠。这些圆圈也会从右到左进行动画处理(当它们离开屏幕时会回到 Canvas 的右边缘)，并且还会有一些垂直的“摆动”，它们也不能与任何其他圆圈重叠。

下面是我目前正在尝试的，它似乎正在锁定浏览器。我遍历圆集合并执行 detectOverlap() 函数，将圆集合传递给它。

然后 detectOverlap() 函数循环遍历圆圈，执行以下检查:

detectOverlap: function (bubblesArr) {
    while (true) {
        var hit = 0;
        for (var i=0; i<bubblesArr.length; i++) {
            var circle = bubblesArr[i];
            var dx = this._x - circle._x;
            var dy = this._y - circle._y;
            var rr = this._radius + circle._radius;
            if (dx * dx + dy * dy < rr * rr) {
                hit++;
            }
        }
        if (hit == 0) {
            break; // didn't overlap, break out of while loop
        }
        // if we didn't break then there was an overlap somewhere. calc again.
        this._x = Math.round(Math.random() * this.stage.getWidth());
        this._y = Math.round(Math.random() * this.stage.getHeight());
    }
},

如果 hit == 0，循环中断，我们假设没有重叠。否则，我们随机计算一个新的 X/Y 位置并重新开始该过程。

这似乎效率低下。执行此操作的任何性能提示？

Canvas 类(入口点):这个类是“舞台”，它构建气泡对象，然后将它们添加到 Canvas 。

var $container;
var listData;
var bubbles = [];

function init(l, c) {
    $container = c;
    listData = l;

    // this just draws the canvas. full-width + 500px tall.
    var stage = new Konva.Stage({
      container: $container.selector,
      width: window.innerWidth,
      height: 500
    });

    // this creates the drawing layer where the bubbles will live
    layer = new Konva.Layer();

    // create an instance of the Bubble class for each element in the list.
    for (var i=0; i<listData.length; i++) {
        bubbles[i] = new celebApp.Bubble.Bubble(listData[i], stage);
    }

    /** TODO:::: FIGURE OUT COLLISION DETECTION */
    for (var i=0; i<bubbles.length; i++) {
        bubbles[i].detectOverlap(bubbles);
    }

    // create the Konva representation for our generated objects
    for (var i=0; i<bubbles.length; i++) {
        var b = bubbles[i];
        layer.add(new Konva.Circle({
            x: b._x,
            y: b._y,
            radius: b._radius,
            fill: b._fill,
            stroke: b._stroke,
            strokeWidth: b._strokeWidth,
        }));
    }

    // add the layer to the stage
    stage.add(layer);
}

气泡类:这是代表绘制到屏幕上的数据的类。我们需要确保这些对象中没有一个相互重叠。

var Bubble = function (listData, stage) {
    this.stage = stage;
    this._x = Math.round(Math.random() * stage.getWidth()),
    this._y = Math.round(Math.random() * stage.getHeight()),
    this._radius = Math.round(Math.random() * 80);
    this._fill = 'red';
    this._stroke = 'black';
    this._strokeWidth = 4;
    this._speed = 3;
};
Bubble.prototype = {
    detectOverlap: function (bubblesArr) {
        while (true) {
            var hit = 0;
            for (var i=0; i<bubblesArr.length; i++) {
                var circle = bubblesArr[i];
                var dx = this._x - circle._x;
                var dy = this._y - circle._y;
                var rr = this._radius + circle._radius;
                if (dx * dx + dy * dy < rr * rr) {
                    hit++;
                }
            }
            if (hit == 0) {
                break; // didn't overlap
            }
            this._x = Math.round(Math.random() * this.stage.getWidth());
            this._y = Math.round(Math.random() * this.stage.getHeight());
        }
    },
};

---

编辑:刚刚根据@MarcB 的评论进行了尝试——但是，浏览器似乎仍然锁定。是否造成了性能瓶颈，但 100 个项目都在运行它们自己的 while() 循环？

for (var i=0; i<bubblesArr.length; i++) {
    var circle = bubblesArr[i];
    var combinedRadius = Math.abs(circle._radius + this._radius);
    var distance = Math.abs(this._x - circle._x);
    if (distance <= combinedRadius) {
        hit++;
    }
}

Answer 1

这看起来像是一个简单的错误。您初始化一个圈子列表。然后，对于列表中的每个圆圈，您计算列表中有多少个圆圈与它重叠。如果您发现重叠，请移动圆圈并重试。

但是每个圈子都会在列表中找自己，发现和自己重叠。你移动它，同样的事情发生。这是一个永无止境的无限循环。

您需要让每个圆圈寻找与其重叠的圆圈。

从算法上讲，您可以使用四叉树等巧妙的数据结构来改进这种重叠检测。这将使您立即找到中心在您的圆圈的一个小盒子内的所有圆圈，并让您以这种方式找到重叠部分。

但是，如果性能有问题，则无需那么努力。取而代之的是按 x 坐标对圆圈进行排序，绘制垂直带，例如，相隔 5 个，然后将每个圆圈放入它相交的所有带中。现在对于每个圆圈，您可以只搜索它相交的所有带。

提高效率的下一步是按 y 坐标对每个波段进行排序，这样您就可以在该波段中进行二进制搜索，以找到与波段相交的所有圆圈，这些圆圈的距离足够近，可能与您的圆圈相交。但这些波段通常应该接近空，所以这算不上什么胜利。