4

我想检查圆圈是否相互碰撞。

我知道我可以通过获取两个圆心之间的距离并从该距离中减去每个圆的半径并查看“距离”是否大于 1 来做到这一点。

我怎样才能有效地做到这一点，虽然有 1000 个圈子？也许我可以以某种方式获得最近的 20 个圆圈或类似的东西并检查这些？我也不知道我将如何开始有效地解决这个问题。

有任何想法吗？

这是一个例子：

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

4

4 回答 4

6

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

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

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

...如果圆心之间的 X 或 Y 距离大于半径之和，则它们不会发生碰撞。

一旦你减少了可能的对撞机，那么你就可以进行正式的精确笛卡尔距离，这就是“重”乘法/除法的地方。

于 2012-07-01T00:58:03.763 回答
2

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

需要注意的是，您需要确保四叉树的叶节点具有最大圆半径的最小直径，否则您将不得不检查的不仅仅是相邻节点的交叉点。

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

如果你的圆圈很分散，那么你可以做的一个简单的优化是将你的圆圈存储在 x 或 y 轴上，然后你只需要检查 x 或 y 坐标在圆圈半径内的圆圈。

于 2012-07-01T00:58:35.093 回答
0

效率将与您使用的算法的速度有关，例如计算距离的平方根算法的速度，除了算法之外，您的数据结构将决定内存的效率。加快计算速度的另一种方法是降低距离计算的精度。

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

于 2012-07-01T00:58:57.300 回答
0

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

以下是基本步骤：

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

    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-02T14:50:37.160 回答