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;
}
Hmm。数学が行く限り、それはかなり良いように見えます。より速く、terserそれのJava側を作成する方法についていくつかのマイナーなポイント：
if (foo) { return true; } else { return false; }?ちょうどreturn foo;！その後、改良版、：
private static boolean isCollision(Point2D.Double p1, double r1, Point2D.Double p2, double r2)
{
final double a = r1 + r2;
final double dx = p1.x - p2.x;
final double dy = p1.y - p2.y;
return a * a > (dx * dx + dy * dy);
}
（あなたのコードは完全に浮いベースである場合、あなたはPoint2D.Floatとfloat Sと同じことを行うことができます。）
境界矩形が重複しない場合は、早期終了も考慮する必要があります。これが実際に実装する価値があるかどうかは、実際に重複する円と四角形の数に一部依存します。 –
私はそれについて考えてきました。私の腸の感覚（私がもう少し時間があるときに検証する）は、分岐を持つことが、浮動小数点の乗算をもう少し行う必要があるよりも、CPUの方が時間がかかるということです。 – Zarkonnen
フロートにキャストしないほうが速いことは理解していますが、ダブルスの代わりに浮動小数点を使った方が効率的でしょうか？ –
重複または交差ですか？
交差する場合は、円が互いに交差して交差しない場合を忘れないでください。
重複している場合は、さらに最適化する方法は実際にはわかりません。距離の平方根を避けるために距離の二乗を使って、点の距離を半径の合計と比較しています。トリムする脂肪が残っているようには思われません。
それはdoesnのコードを高速化したいが、私は好むだろう：
return a > (dx*dx + dy*dy);
あなたは本当に可能なPoint2D implementatiに？あなたがする必要がない場合は、仮想コールが保存されます：
private static boolean isCollisionFloat (Point2D.Float p1, float r1, Point2D.Float p2, float r2)
{
final float r = r1+r2;
final float dx = p1.x - p2.x;
final float dy = p1.y - p2.y;
return (r*r) > (dx*dx) + (dy*dy);
}
testing 1000x1000 points: Doing nothing took 6 ms Doing isCollision passing Point2D.Float took 128 ms Doing isCollision passing Point2D.Double took 127 ms Doing isCollisionFloat took 71 ms Doing isCollisionDouble took 72 ms
をあなたは、むしろ両方のケータリングよりも、どちらか一方を選択することができます。
perf質問の問題は、実際にはサポートされていない意見と同じ回答を投稿したときのエフェクトを測定する必要があることです。
アルゴリズムを最適化するには、各円の四角形の境界を計算し、それらが重なっているかどうかを確認します。重複しない場合はfalseを返します。これにより、矩形の境界が重複していない（つまり、互いに接近していない）サークルの乗算が回避されます。矩形境界計算の加算/減算は乗算よりも安価です。
これは、Java 2Dが使用するパターンです。 Shape.getBounds()
私は境界計算が失われると思いますしかし、賞金のほとんどは、。しかし、なぜそれを試して結果を投稿しないのですか？ –
あなたの場合は関連するかどうかわかりませんが、あなたのサークルと他の多くのサークルとの重複をチェックしたい場合は、四角でサークルを整理しようとすることができます（http://en.wikipedia.org/wiki/Quadtreeを参照）、クワッドツリーのツリールックアップ（あなたの円の境界の矩形に基づく）を行います。
2つの中心間の距離が1未満で0より大きい場合、解決策のいずれも適切な結果をもたらすとは思わない。 –