圆形碰撞检测 HTML5 画布

Question

我希望检查圆形是否相互碰撞。

我知道可以通过获取两个圆心之间的距离，从该距离中减去每个圆的半径，然后查看“距离”是否> 1来实现此目的。

但是如果有1000个圆，如何高效地执行此操作呢？也许我可以以某种方式获取最近的20个圆形或类似的东西，然后检查这些圆形？但是我不知道如何有效地开始执行这项任务...

你有什么想法吗？

以下是示例：

http://experiments.lionel.me/blocs/

- Max Hudson

Answer 1

在开始计算距离的确切差值之前，您可以至少比较中心点的x / y位置与半径。该信息在圆形中是隐含的，只需要进行一些简单的比较和加法/减法即可。

这将允许您比较所有圆对之间的x / y简单距离，并丢弃任何明显不是碰撞候选的距离，例如：

abs(x2 - x1) > (r2 + r1)
abs(y2 - y1) > (r2 + r1)

如果两个圆心在X轴或Y轴上的距离大于它们半径的和，那么它们就不会碰撞。

一旦你缩小了可能的碰撞对象范围，然后你就可以进行精确的笛卡尔距离计算，这时候就需要用到“重”乘除法运算。

- Marc B

Answer 2

考虑将圆的中心坐标存储在四叉树中，那么您只需要检查该象限或相邻象限中的圆是否与其他圆相交。

唯一的注意点是，您需要确保四叉树的叶子节点具有最小直径，至少要大于您最大圆的半径，否则您将不得不检查更多的非相邻节点以进行相交检查。

http://en.wikipedia.org/wiki/Quadtree

如果您的圆散布得很好，那么您可以进行简单的优化，即按照 x 或 y 轴对圆进行排序存储，然后只需要检查 x 或 y 坐标在圆半径范围内的圆。

- Charles Ma

Answer 3

效率与你所使用的算法速度有关，例如你用来计算距离的平方根算法的速度以及你的数据结构将决定内存的效率，除了算法之外。另一种加速计算的方法是减少距离计算的精度。

检测圆是否碰撞的最佳方法，如你所说，是将圆心坐标和半径存储在变量中，并计算当半径相减时中心点之间的距离是否等于0。

- Alex W

Answer 4

我强烈推荐Keith Peter的《AdvancED ActionScript 3.0 Animation》一书，其中您可以找到Actionscript中Quadtree算法的具体实现。

以下是基本步骤：

• 首先创建一个二维网格，并将所有球随机分散在场地上。

  private function createGrids():void {
      _grids = new Array();
      for (var i:int = 0; i< stage.stageWidth / GRID_SIZE; i++) {
          _grids[i] = new Array();
          for (var j:int = 0; j< stage.stageHeight / GRID_SIZE; j++) {
              _grids[i][j] = new Array();
          }
      }
  }
  

• 将球分配到网格单元格中

  private function assignBallsToGrid():void {
      for (var i:int = 0; i< numBalls; i++) {
          var ball:Ball = Ball(_balls[i]);
          var xpos:int = Math.floor(ball.x / GRID_SIZE);
          var ypos:int = Math.floor(ball.y / GRID_SIZE);
          _grids[xpos][ypos].push(ball);
      }
  }
  

• 检查单个单元格中是否有两个球碰撞，然后检查相邻单元格中的球。正如Charles Ma所提到的，这里唯一需要考虑的是网格单元格的尺寸必须大于或等于最大球直径。

  private function checkOneCell(x1:Number, y1:Number):void {
      var _cell:Array = _grids[x1][y1] as Array;
      for (var i:int = 0; i< _cell.length-1; i++) {
          var ballA:Ball = _cell[i] as Ball;
          for (var j:int = i+1; j< _cell.length; j++) {
              var ballB:Ball = _cell[j] as Ball;
              checkCollision(ballA, ballB);
          }
      }
  }
  
  private function checkTwoCell(x1:Number, y1:Number, x2:Number, y2:Number):void {
      if (x2 < 0) { return } 
      if (x2 >= _grids.length) { return }
      if (y2 >= _grids[x2].length) { return }
  
      var _cell0:Array = _grids[x1][y1] as Array;
      var _cell1:Array = _grids[x2][y2] as Array;
  
      for (var i:int = 0; i< _cell0.length; i++) {
          var ballA:Ball = _cell0[i] as Ball;
          for (var j:int = 0; j< _cell1.length; j++) {
              var ballB:Ball = _cell1[j] as Ball;
              checkCollision(ballA, ballB);
          }
      }
  }
  
  private function checkCollision(ballA:Ball, ballB:Ball):void {
      var dx:Number = ballB.x - ballA.x;
      var dy:Number = ballB.y - ballA.y;
      var dist:Number = Math.sqrt(dx*dx + dy*dy);
      if (dist < ballB.radius + ballA.radius) {
                       // do something
      }
  }
  

• 这是主要方法的样子：

  private function checkBallsCollision():void {
      for (var i:int = 0; i< _grids.length; i++) {
          for (var j:int = 0; j< _grids[i].length; j++) {
              checkOneCell(i, j);
  
              checkTwoCell(i, j, i+1, j);
              checkTwoCell(i, j, i, j+1);
              checkTwoCell(i, j, i-1, j);
              checkTwoCell(i, j, i+1, j+1);
          }
      }
  }
  

注意：

该代码是用Actionscript编写的，但在Javascript中也可以很容易地实现。

- Endre Simo