如何对数百个 canvas 圈进行高效 overlap/collision 检测？
how to do performant overlap/collision detection for hundreds of canvas circles?
我在 canvas 上画了 100 个不同大小的圆，它们不能重叠。这些圆圈也会从右到左动画化（当它们离开屏幕时会回到 canvas 的右边缘），并且还会有一些垂直的 "bob"，这也不能与任何其他圆圈重叠。
以下是我目前正在尝试的，这似乎会锁定浏览器。我遍历圆圈集合并执行 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 class（入口点）：
这个 class 是 "stage"，它构建气泡对象，然后将它们添加到 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);
}
气泡class:
这是代表绘制到屏幕上的数据的 class。我们需要确保 none 这些对象相互重叠。
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++;
}
}
这看起来像是一个简单的错误。您初始化一个圈子列表。然后，对于列表中的每个圆圈，您计算列表中有多少个圆圈与它重叠。如果您发现重叠，请移动圆圈并重试。
但是每个圈子都会在列表中找到自己，发现自己重叠了。你移动它，同样的事情发生。这是一个永无止境的无限循环。
您需要让每个圆圈寻找与其重叠的 圆圈。
从算法上讲，您可以使用四叉树等巧妙的数据结构来改进这种重叠检测。这将使您立即找到所有圆心在您的圆的小方框内的圆，并让您以这种方式找到重叠部分。
但是，如果性能有问题，则无需那么努力。取而代之的是按 x 坐标对圆圈进行排序，绘制垂直带，例如，相隔 5 个，然后将每个圆圈放入它相交的所有带中。现在对于每个圆圈，您可以只搜索它相交的所有波段。
提高效率的下一步是按 y 坐标对每个波段进行排序，这样您就可以在该波段中进行二进制搜索，以找到与波段相交的所有圆圈，这些圆圈的距离足够近，可能与您的圆圈相交。但是这些波段通常应该接近空，所以这不是一个胜利。
如果仅在创建整个列表后才暂存气泡（尽管您也可以通过以随机顺序从现有列表暂存来模拟随机出现），为什么不通过创建随机间距来完全避免碰撞检测？
可能还有更有趣、更有机的程序，但一种简单的方法是按排队顺序细分 space，保持当前框大小的随机截止以考虑不同的半径。像这样：
Describe the space as a tuple consisting of a middle point and a top left point.
(middle,top_left)
Choose a random point on the top border of the box:
-----x-----------
Choose one random point on the left border of the box and one on the right:
-----x-----------
| | |
| | |
x----- |
| | |
| |----------x
| | |
-----------------
You now have four new middle and top left points, easily calculated.
Add the four new tuples to the queue and remove the tuple
representing the parent box. Customize the function to get appropriately
sized results.
我们最终得到一个元组列表，这些元组代表不同大小的非重叠框，具有给定的中间点。剩下的就是随机挑选一些盒子（列表可以散列以避免碰撞）并在其中放置气泡。 （这假设同一水平 space 中的气泡以相同的速度移动。）
类似这样的东西（可能需要一些调整）：
var MIN_WIDTH = MIN_HEIGHT = 20;
function f(top_left,bottom_right){
var w = bottom_right.x - top_left.x - 2 * MIN_WIDTH,
h = bottom_right.y - top_left.y - 2 * MIN_HEIGHT,
random_top = top_left.x + MIN_WIDTH
+ Math.ceil(Math.random() * w),
random_left = top_left.y + MIN_HEIGHT
+ Math.ceil(Math.random() * h),
random_right = top_left.y + MIN_HEIGHT
+ Math.ceil(Math.random() * h);
var rectangle_1 = [top_left
,{x: random_top, y: random_left}],
rectangle_2 = [{x: top_left.x, y: random_left}
,{x: random_top, y: bottom_right.y}],
rectangle_3 = [{x: random_top, y: top_left.y}
,{x: bottom_right.x, y: random_right}],
rectangle_4 = [{x: random_top, y: random_right}
,bottom_right];
return [rectangle_1, rectangle_2, rectangle_3, rectangle_4];
}
console.log(JSON.stringify(f({x: 0, y: 0}, {x: 200, y: 200})))
第一次将整个 canvas 尺寸送入 f。然后将四个结果矩形中的每一个都输入 f，这样每个矩形都会再次细分，依此类推。在递归中添加一个随机停止点，这样一些矩形就会比其他矩形大（因为它们不会被细分）。将气泡放在矩形 space 内。它们不会碰撞，但由此产生的排列可能会缺少一种更有机的感觉 - 也许可以通过随机 "nudging" 它们稍微调整一下。
我在 canvas 上画了 100 个不同大小的圆，它们不能重叠。这些圆圈也会从右到左动画化（当它们离开屏幕时会回到 canvas 的右边缘），并且还会有一些垂直的 "bob"，这也不能与任何其他圆圈重叠。
以下是我目前正在尝试的，这似乎会锁定浏览器。我遍历圆圈集合并执行 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 class（入口点）： 这个 class 是 "stage"，它构建气泡对象，然后将它们添加到 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);
}
气泡class: 这是代表绘制到屏幕上的数据的 class。我们需要确保 none 这些对象相互重叠。
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++;
}
}
这看起来像是一个简单的错误。您初始化一个圈子列表。然后，对于列表中的每个圆圈，您计算列表中有多少个圆圈与它重叠。如果您发现重叠，请移动圆圈并重试。
但是每个圈子都会在列表中找到自己，发现自己重叠了。你移动它，同样的事情发生。这是一个永无止境的无限循环。
您需要让每个圆圈寻找与其重叠的 圆圈。
从算法上讲，您可以使用四叉树等巧妙的数据结构来改进这种重叠检测。这将使您立即找到所有圆心在您的圆的小方框内的圆，并让您以这种方式找到重叠部分。
但是，如果性能有问题，则无需那么努力。取而代之的是按 x 坐标对圆圈进行排序，绘制垂直带，例如，相隔 5 个，然后将每个圆圈放入它相交的所有带中。现在对于每个圆圈，您可以只搜索它相交的所有波段。
提高效率的下一步是按 y 坐标对每个波段进行排序，这样您就可以在该波段中进行二进制搜索，以找到与波段相交的所有圆圈，这些圆圈的距离足够近，可能与您的圆圈相交。但是这些波段通常应该接近空，所以这不是一个胜利。
如果仅在创建整个列表后才暂存气泡（尽管您也可以通过以随机顺序从现有列表暂存来模拟随机出现），为什么不通过创建随机间距来完全避免碰撞检测？
可能还有更有趣、更有机的程序，但一种简单的方法是按排队顺序细分 space，保持当前框大小的随机截止以考虑不同的半径。像这样：
Describe the space as a tuple consisting of a middle point and a top left point.
(middle,top_left)
Choose a random point on the top border of the box:
-----x-----------
Choose one random point on the left border of the box and one on the right:
-----x-----------
| | |
| | |
x----- |
| | |
| |----------x
| | |
-----------------
You now have four new middle and top left points, easily calculated.
Add the four new tuples to the queue and remove the tuple
representing the parent box. Customize the function to get appropriately
sized results.
我们最终得到一个元组列表，这些元组代表不同大小的非重叠框，具有给定的中间点。剩下的就是随机挑选一些盒子（列表可以散列以避免碰撞）并在其中放置气泡。 （这假设同一水平 space 中的气泡以相同的速度移动。）
类似这样的东西（可能需要一些调整）：
var MIN_WIDTH = MIN_HEIGHT = 20;
function f(top_left,bottom_right){
var w = bottom_right.x - top_left.x - 2 * MIN_WIDTH,
h = bottom_right.y - top_left.y - 2 * MIN_HEIGHT,
random_top = top_left.x + MIN_WIDTH
+ Math.ceil(Math.random() * w),
random_left = top_left.y + MIN_HEIGHT
+ Math.ceil(Math.random() * h),
random_right = top_left.y + MIN_HEIGHT
+ Math.ceil(Math.random() * h);
var rectangle_1 = [top_left
,{x: random_top, y: random_left}],
rectangle_2 = [{x: top_left.x, y: random_left}
,{x: random_top, y: bottom_right.y}],
rectangle_3 = [{x: random_top, y: top_left.y}
,{x: bottom_right.x, y: random_right}],
rectangle_4 = [{x: random_top, y: random_right}
,bottom_right];
return [rectangle_1, rectangle_2, rectangle_3, rectangle_4];
}
console.log(JSON.stringify(f({x: 0, y: 0}, {x: 200, y: 200})))
第一次将整个 canvas 尺寸送入 f。然后将四个结果矩形中的每一个都输入 f，这样每个矩形都会再次细分，依此类推。在递归中添加一个随机停止点，这样一些矩形就会比其他矩形大（因为它们不会被细分）。将气泡放在矩形 space 内。它们不会碰撞，但由此产生的排列可能会缺少一种更有机的感觉 - 也许可以通过随机 "nudging" 它们稍微调整一下。