15

したがって、平方根の計算はあまり効率的ではないようです。そのため、2つの円の間の距離（以下では範囲と呼びます）を見つけるのが最善の方法であるかどうか疑問に思います。

2つの円の間の範囲を見つける

だから通常私はうまくいくでしょう：

a^2 + b^2 = c^2
dy^2 + dx^2 = h^2
dy^2 + dx^2 = (r1 + r2 + range)^2
(dy^2 + dx^2)^0.5 = r1 + r2 + range
range = (dy^2 + dx^2)^0.5 - r1 - r2

衝突の「範囲」が0の場合の状況を探すだけで、平方根を回避しようとするとうまくいきます。

 if ( (r1 + r2 + 0 )^2 > (dy^2 + dx^2) )

しかし、その範囲の距離を計算しようとすると、次のような扱いにくい方程式になってしまいます。

 range(range + 2r1 + 2r2) = dy^2 + dx^2 - (r1^2 + r2^2 + 2r1r2)

どこにも行きません。少なくともここからの範囲でそれを解決する方法がわかりません...

明白な答えは三角法であり、最初にシータを見つけます。

  Tan(theta) = dy/dx
  theta = dy/dx * Tan^-1

次に、hypotemuse Sin（theta）= dy / h h = dy / Sin（theta）を見つけます

最後に、範囲範囲+ r1 + r2 = dy / Sin（theta）範囲= dy / Sin（theta）-r1-r2を計算します

これが私が行ったことであり、次のようなメソッドがあります。

private int findRangeToTarget(ShipEntity ship, CircularEntity target){


    //get the relevant locations
    double shipX = ship.getX();
    double shipY = ship.getY();
    double targetX =  target.getX();
    double targetY =  target.getY();
    int shipRadius = ship.getRadius();
    int targetRadius = target.getRadius();

    //get the difference in locations:
    double dX = shipX - targetX;
    double dY = shipY - targetY;

    // find angle 
    double theta = Math.atan(  ( dY / dX ) );

    // find length of line ship centre - target centre
    double hypotemuse = dY / Math.sin(theta);

    // finally range between ship/target is:
    int range = (int) (hypotemuse - shipRadius - targetRadius);

    return range;

}

だから私の質問は、平方根を見つけるよりも日焼けと罪を使う方が効率的ですか？

コードの一部をリファクタリングして、別のメソッド（解決する必要がある場合）からシータ値を取得できる可能性がありますが、それは行う価値がありますか？

それとも、まったく別の方法がありますか？

当たり前のことを聞いたり、初歩的な間違いをしたりするのなら、すみません。高校の数学を使って何かをしてから久しぶりです...

ヒントやアドバイスは大歓迎です！

****編集****

具体的には、敵/障害物が近づいたり遠ざかったりすることを検出する「スキャナー」デバイスをゲームで作成しようとしています。スキャナーは、オーディオトーンやグラフィカルバーなどを介してこの情報を中継します。したがって、正確な数値は必要ありませんが、理想的には次のことを知りたいと思います。

  1. ターゲットが以前よりも近く/遠くにある
  2. ターゲットAはターゲットB、C、Dよりも近い/遠い...
  3. 0（衝突）および最大範囲（一定の一定）に対してターゲットが船からどれだけ離れているかを表す（線形であるといいのですが？）比率
  4. 一部のターゲットは非常に大きくなります（惑星？）ので、半径を考慮する必要があります

いくつかの巧妙な最適化/近似が可能であることを願っています（dx + dy +（dxの長い方、dy？）が、これらすべての要件では、おそらくそうではありません...

4

4 に答える 4

12

Math.hypotフォームのより速く、より正確な計算を取得するように設計されていますsqrt(x^2 + y^2)。だからこれはただ

return Math.hypot(x1 - x2, y1 - y2) - r1 - r2;

これよりも単純で、高速でもないコードは想像できません。

于 2012-05-19T16:54:58.910 に答える
9

正確な距離が本当に必要な場合は、平方根を避けることはできません。三角関数は、悪くはないにしても、少なくとも平方根計算と同じくらい悪いです。

しかし、おおよその距離だけが必要な場合、または円のさまざまな組み合わせに対して相対距離だけが必要な場合は、間違いなくできることがあります。たとえば、相対距離のみが必要な場合、平方数は平方根と同じより大きい関係を持っていることに注意してください。異なるペアのみを比較している場合は、平方根の手順をスキップすると、同じ答えが得られます。

おおよその距離だけが必要な場合は、それがh長い方の隣接する側にほぼ等しいと考えるかもしれません。この近似値は、2倍以上ずれることはありません。または、三角関数のルックアップテーブルを使用することもできます。これは、任意の平方根のルックアップテーブルよりも実用的です。

于 2012-05-19T14:46:06.573 に答える
1

tan、sineを使用した場合の答えが、sqrt関数を使用した場合と同じであるかどうかを最初に理解するのに疲れました。

public static void main(String[] args) throws Exception {
    // TODO Auto-generated method stub
     double shipX = 5;
        double shipY = 5;
        double targetX =  1;
        double targetY =  1;
        int shipRadius = 2;
        int targetRadius = 1;

        //get the difference in locations:
        double dX = shipX - targetX;
        double dY = shipY - targetY;

        // find angle 
        double theta = Math.toDegrees(Math.atan(  ( dY / dX ) ));

        // find length of line ship centre - target centre
        double hypotemuse = dY / Math.sin(theta);
        System.out.println(hypotemuse);
        // finally range between ship/target is:
        float range = (float) (hypotemuse - shipRadius - targetRadius);
        System.out.println(range);

        hypotemuse = Math.sqrt(Math.pow(dX,2) + Math.pow(dY,2));
        System.out.println(hypotemuse);
        range = (float) (hypotemuse - shipRadius - targetRadius);
        System.out.println(range);
}

私が得た答えは：4.700885452542996でした

1.7008854

5.656854249492381

2.6568542

これで、sqrtの値の方が正しい値との間に違いがあるようです。

  1. パフォーマンスについて話す：コードスニペットを検討してください：

私はパフォーマンスの時間を計算しました-それは次のようになります：

    public static void main(String[] args) throws Exception {
    // TODO Auto-generated method stub
    long lStartTime = new Date().getTime(); //start time
    double shipX = 555;
        double shipY = 555;
        double targetX =  11;
        double targetY =  11;
        int shipRadius = 26;
        int targetRadius = 3;

        //get the difference in locations:
        double dX = shipX - targetX;
        double dY = shipY - targetY;

        // find angle 
        double theta = Math.toDegrees(Math.atan(  ( dY / dX ) ));

        // find length of line ship centre - target centre
        double hypotemuse = dY / Math.sin(theta);
        System.out.println(hypotemuse);
        // finally range between ship/target is:
        float range = (float) (hypotemuse - shipRadius - targetRadius);
        System.out.println(range);


        long lEndTime = new Date().getTime(); //end time

          long difference = lEndTime - lStartTime; //check different

          System.out.println("Elapsed milliseconds: " + difference);
}

回答-639.3204215458475、610.32043、経過ミリ秒：2

そして、sqrt root oneで試してみると：

public static void main(String[] args) throws Exception {
    // TODO Auto-generated method stub
    long lStartTime = new Date().getTime(); //start time
    double shipX = 555;
        double shipY = 555;
        double targetX =  11;
        double targetY =  11;
        int shipRadius = 26;
        int targetRadius = 3;

        //get the difference in locations:
        double dX = shipX - targetX;
        double dY = shipY - targetY;

        // find angle 
        double theta = Math.toDegrees(Math.atan(  ( dY / dX ) ));

        // find length of line ship centre - target centre

       double hypotemuse = Math.sqrt(Math.pow(dX,2) + Math.pow(dY,2));
        System.out.println(hypotemuse);
        float range = (float) (hypotemuse - shipRadius - targetRadius);
        System.out.println(range);

        long lEndTime = new Date().getTime(); //end time

          long difference = lEndTime - lStartTime; //check different

          System.out.println("Elapsed milliseconds: " + difference);
}

回答-769.3321779309637、740.33215、経過ミリ秒：1

ここで、違いを確認すると、2つの答えの違いも非常に大きくなります。

したがって、ゲームをより正確にすると、データはユーザーにとってより楽しくなると思います。

于 2012-05-19T15:53:03.900 に答える
1

「ハード」ジオメトリソフトウェアで通常発生する問題はsqrt、そのパフォーマンスではなく、それに伴う精度の低下です。あなたの場合、sqrt法案にうまく適合します。

それがsqrt本当にパフォーマンスのペナルティをもたらすことがわかった場合（ご存知のとおり、必要な場合にのみ最適化してください）、線形近似を試すことができます。

f(x) ~ f(X0) + f'(x0) * (x - x0)
sqrt(x) ~ sqrt(x0) + 1/(2*sqrt(x0)) * (x - x0)

したがって、のルックアップテーブル（LUT）を計算しsqrt、与えられたx場合、最も近いを使用しx0ます。もちろん、通常のコンピューティングにフォールバックする必要がある場合は、可能な範囲が制限されます。さて、いくつかのコード。

class MyMath{
    private static double[] lut;
    private static final LUT_SIZE = 101;
    static {
        lut = new double[LUT_SIZE];
        for (int i=0; i < LUT_SIZE; i++){
            lut[i] = Math.sqrt(i);
        }
    }
    public static double sqrt(final double x){
        int i = Math.round(x);
        if (i < 0)
            throw new ArithmeticException("Invalid argument for sqrt: x < 0");
        else if (i >= LUT_SIZE)
            return Math.sqrt(x);
        else
            return lut[i] + 1.0/(2*lut[i]) * (x - i);
    }
}

（私はこのコードをテストしていません。エラーを許して修正してください）

また、これをすべて書いた後、おそらくすでにいくつかの近似的で効率的な代替の数学ライブラリがそこにあります。あなたはそれを探すべきですが、それはあなたがパフォーマンスが本当に必要であるとわかった場合に限ります。

于 2012-05-19T16:24:11.240 に答える