java（Android）の2行の衝突検出

Question

非常に簡単な質問。 Javaで描画された線で衝突検出を達成するにはどうすればよいですか？ちょうどライン。四角形、円、画像はありません。

ところで、これらの線は直線ではありません。彼らは、プレイヤーの動きを表す非常に小さな線の数百（彼らは移動するように彼らのGPS座標）を構築されているので、彼らはプレイヤーの動きとしてその場に蛇行する。すべての回線が接続されています。 1行の終点が次の始点などとなります。それはこの点で絶え間ない線です。隙間はありません。

私は線の始点のx、y値を配列に格納してから、この配列を反復してその点が以前に訪問されたかどうかを判断しようとしました。これは、プレイヤーが正確なコインを再び訪問する場合は問題ありませんが、これらの記録されたポイントの中間にいる場合はどうなりますか？

これは問題の背景に役立ちます。しかし、主な問題は私の焦点です。 Javaで行の衝突検出をどのように達成しますか？

Answer 1

私はあなたが正しい方法でそれをやっていることを知っています。私はおそらく座標位置を介して線をハッシュすることを示唆しているので、ラインチェックが少なくなっています。推定されたより大きな直線（より小さい線の平均から作成された）が作成され、その代わりにチェックに使用された場合は、チェックの数を減らすこともできます。

Answer 2

私が正しく理解していれば、あなたの問題は厳密には線の交差点ではなく（ウェブ上で簡単に見つけることができますが）何百もの問題を処理する方法ですか？

多分計算を制限するためにデータの空間構造を考えるべきです。例えば、 "quadtree"を見てください。

すべての座標の部分集合でのみ交差をテストします。

Answer 3

直線と呼ばれるものは、直線セグメントのリストList<Line2D>を呼び出すことができます。 List<Line2D> aとList<Line2D> bがある場合は、aのすべての行とbのすべての行を比較します。私はあなたが2つの直線部分の交差点を見つける方法を見ることができると仮定します - またはLine2Dはさらにdo this for youになります。例：

for(Line2D line1 : a) { 
    for(Line2D line2 : b) { 
     if(a.intersectsLine(b)) { 
     return true; 
     } 
    } 
} 
return false; 

このコードは高速ではありませんが、十分に速いかもしれません。速度が遅すぎる場合は、最適化を検討する必要があります。これはさまざまな方法で行うことができます。クォッド・ツリーまたは1次元でのソートは、2つの明白な単純なステップです。