圓碰撞檢測HTML5畫布

我想檢查圓圈是否相互碰撞。圓碰撞檢測HTML5畫布

我知道，如果「距離」是> 1

我怎樣才能做到這一點，我可以通過獲取圓的兩個中心之間的距離，並減去這個距離各圓的半徑，看到這樣做有效地說，但有1000圈？也許我能以某種方式得到最近的20個圈子或類似的東西，並檢查這些？我不知道我會如何開始有效地去做，雖然要麼..

任何想法？

下面是一個例子：

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

來源

2012-07-01 maxhud

你開始計算距離的精確區別之前，你至少可以比較中心V.S.的x/y位置半徑。該信息隱含在圓圈中，只需要一些簡單的比較和加/減法。

這會讓你比較所有圓對之間x/y的簡單距離，並拋棄顯然不是碰撞候選者的任何東西，例如，

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

...如果圓心之間X或Y的距離大於半徑之和，則它們不能相互碰撞。

一旦你消減下來可能對撞機，那麼你就正式確切的笛卡爾距離，這哪裏是「重」乘法/除法東西用武之地。

來源

2012-07-01 00:58:03

考慮保存圈中心的座標在四叉樹中，則只需檢查該圓與該象限或相鄰象限中的其他圓相交。

需要注意的是，您需要確定四叉樹的葉節點具有最小圓的半徑的最小直徑，否則您將不得不檢查相鄰節點的交叉點。

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

如果你的社交圈都好散，然後進行簡單的優化，你可以做的是存儲上排序X或Y軸自己的圈子，那麼你只需要檢查圓圈誰的x或y座標在圓的半徑內。

來源

2012-07-01 00:58:35

效率將會與您正在使用算法的速度有關，例如平方根算法，你計算與距離的速度和你的數據結構將確定的效率內存，除了算法。加速計算的另一種方法是降低距離計算的精度。

如您所說，檢測圓圈是否碰撞的最佳方法是將圓的中心座標和半徑存儲在變量中，並計算在減去半徑時中心之間的距離是否等於0 。

來源

2012-07-01 00:58:57

我強烈推薦Keith Peter的AdvancED ActionScript 3。0 Animation book，你可以在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中很容易實現。

來源

2012-07-02 14:50:37

圓碰撞檢測HTML5畫布

回答

相關問題