15

2 つの円が重なっているかどうかを計算するメソッドを作成しようとしています。私は次のことを思いつきましたが、さらに最適化できる方法があるかどうか知りたいだけです。

private static boolean isCollision(Point2D p1, float r1, Point2D p2, float r2)
{
    float a,dx, dy;
    a = (r1+r2) * (r1+r2);
    dx = (float) (p1.getX() - p2.getX());
    dy = (float) (p1.getY() - p2.getY());

    if (a > (dx*dx) + (dy*dy))
    {
        return true;
    }
    return false;
}
4

6 に答える 6

9

重なったり交差したり？

交差する場合は、円が互いに内側にあるために交差しない場合があることを忘れないでください。

重複している場合、さらに最適化する方法がわかりません。ポイント距離を半径の合計と比較し、距離の二乗を使用して平方根をとらないようにします。削る脂肪はないようです。

于 2009-03-30T13:35:29.733 に答える
3

あなたの場合に関連するかどうかはわかりませんが、円と他の多くの円 (数千の円としましょう) との重複を確認したい場合は、円を四分木で整理してみてください ( http: //en.wikipedia.org/wiki/Quadtree ) を実行し、クワッド ツリーで (円の境界四角形に基づいて) ツリー ルックアップを実行します。

于 2010-02-14T11:32:42.167 に答える
2

各円の長方形の境界を計算し、それらが重なるかどうかを確認することで、アルゴリズムをさらに最適化できます。重複しない場合は、false を返します。これにより、長方形の境界が重なっていない (つまり、互いに近くにない) 円の乗算が回避されます。矩形境界計算の加算/減算は、乗算より安価です。

これは、Java 2D が使用するパターンです。Shape.getBounds()を参照してください。

于 2009-03-30T19:57:42.917 に答える