Обнаружение столкновения с кругом HTML5 Canvas

Я хочу проверить, сталкиваются ли круги друг с другом.

Я знаю, что могу сделать это, получив расстояние между двумя центрами окружностей и вычтя радиус каждого круга из этого расстояния и посмотрев «расстояние». это & gt; 1.

Как я могу сделать это эффективно, хотя, скажем, 1000 кругов? Может быть, я могу как-то получить ближайшие 20 кругов или что-то в этом роде и проверить их? Я не знаю, как бы я начал делать это эффективно, хотя либо ...

Есть идеи?

Вот пример:

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

Ответы на вопрос(4)

Эффективность будет связана сthe speed of the algorithms you are usingнапример, скорость алгоритма квадратного корня, с которым вы рассчитываете расстояние, иyour data structures Определим эффективность памяти, помимо алгоритмов. Еще один способ ускорить вычисления - снизить точность расчетов расстояний.

Лучший способ определить, сталкиваются ли круги, как вы сказали, - сохранить круги & apos; координаты центра и радиус в переменных и вычислите, равно ли расстояние между центрами 0, когда радиусы вычтены.

Подумайте о сохранении координат кругов & apos; центры в четырехугольном дереве, тогда вам нужно будет только проверить, пересекается ли окружность с другими окружностями в этом квадранте или смежных квадрантах.

Единственное предостережение заключается в том, что вам необходимо убедиться, что листовые узлы четырехугольного дерева имеют минимальный диаметр радиуса вашего наибольшего круга, в противном случае вам придется проверять не только смежные узлы на предмет пересечения.

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

Если ваши круги хорошо рассеяны, то простая оптимизация, которую вы можете сделать, это сохранить круги, отсортированные по оси x или y, тогда вам нужно только проверить по тем кругам, чья координата x или y находится в пределах радиуса круга.

Решение Вопроса

Перед тем, как вы начнете вычислять точные различия в расстояниях, вы можете хотя бы сравнить координаты x / y центров против. радиусы Эта информация неявно доступна в круге и требует лишь простых сравнений и сложений / вычитаний.

Это позволит вам сравнивать простые расстояния в x / y между всеми парами окружностей и отбрасывать любые, которые явно не являются кандидатами на столкновение, например,

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

... если расстояние в X или Y между центрами окружности больше, чем сумма радиусов, то они не могут сталкиваться.

После того, как вы урезали возможные коллайдеры, ТО вы делали формальное точное декартово расстояние, где находится «тяжелый». умножение / деление вещи приходит.

Я очень рекомендую Кита ПитераAdvancED ActionScript 3.0 Animation книга, где вы можете найти конкретную реализацию алгоритма Quadtree в Actionscript.

Вот основные шаги:

First create a two dimensional grid and scatter all the balls randomly across the field.

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();
        }
    }
}

Assign balls to grid cells

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);
    }
}

Check if two balls are colliding in a single cell, then check the balls in adjacent cells. As Charles Ma mentioned the only consideration here the grid cells dimension must be greater or equal to the largest ball diameter.

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
    }
}

Here is how it looks like the main method:

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);
        }
    }
}

NOTE:

Код написан на ActionScript, но может быть легко реализован на Javascript.

Ваш ответ на вопрос