三角形と正方形が交差しているかどうかをテストするにはどうすればよいですか?
長方形ではなく正方形であることがわかっている場合、これを最適化する方法はありますか? また、正方形は軸が揃っているので、パフォーマンスがさらに向上するはずですか?
それとも、正方形を三角形に分割し、三角形と三角形の交差チェックを 2 回行う必要がありますか?
編集：明確にするために：これらの2つの形状が何らかの形で互いに重なっているかどうかを確認しようとしています. したがって、三角形は正方形の内側にある可能性があり、正方形は三角形の内側にある可能性があり、その場合も true を返す必要があります。
これは、古典的な衝突検出の問題です。次の条件のいずれかに該当する場合、形状は交差します。
最初の 2 つの条件は、一方の形状がもう一方の形状に完全に含まれている可能性をカバーしています (この場合、エッジは交差しません)。
いくつかの最適化が可能です。
形状の外接円を計算します。2 つの形状の中心点間の距離が外接円の半径の合計よりも大きい場合、衝突を除外できます。長方形に外接する円の中心点は、対角線の中点であることに注意してください。三角形の外接円の中心点は、任意の 2 つのエッジの垂直二等分線の交点を見つけることによって取得できます。三角形を完全に含む円の悲観的な推定値を見つける 2 つの方法は、(1) 円の直径として最も長い辺を使用すること、および (2) ( mintx、minty )、( mintx、maxty ) の角を持つ外接する四角形を作成することです。 ( maxtx、maxty) および ( maxtx , minty ) ここで、 maxtxは三角形の角の最大 X 座標、mintxは三角形の角の最小 X 座標などです。
四角形の頂点の 1 つが原点に配置され、四角形の底辺が正の X 軸に沿うように、形状を移動および回転できます。これにより、三角形の頂点が四角形に含まれているかどうかを簡単に確認できます。
平行移動、回転、および線の交差は非常によく理解されている問題であり、ここで適切なコードを見つけるのに問題はないはずです。
ヒント：
概念的には、回転は簡単です。各ポイントについて、極座標に変換し、回転角度を加算または減算してから、デカルト座標に変換し直します。極座標との変換は計算コストが高いため、次の式を使用して回転を行うことができます。
Xrot = X * cos(シータ) - Y * sin(シータ)
Yrot = X * sin(シータ) + Y * cos(シータ)
長方形の一辺を取ることで角度シータを見つけることができます。
シータ = atan2(デルタ X、デルタ Y)
三角形の頂点を取り、各エッジの線の方程式を作成して、一貫した順序 (三角形の周りを時計回りまたは反時計回り) で三角形の各エッジに対して長方形 (または正方形) を比較します。
長方形が三角形のいずれかのエッジの外側に完全にある場合、交差しません。
三角形に対して長方形のエッジで再度テストします。
四隅すべてをテストするのではなく、どの角が三角形の内側にある可能性が最も高いかを判断し、その角だけをテストできるため、四角形が軸に沿って配置されていることを知ることで、パフォーマンスが向上する可能性があります。
それが勝つかどうかは、実装に依存します。実際に最適な座標を計算するよりも、やみくもに 4 つの座標をチェックする方が速い場合があります。
長方形が軸に揃えられている場合、線の方程式は x または y に対する単純なテストであるため、長方形に対して三角形をチェックするのは簡単です。
これは分離軸テストの一般化された形式です。つまり、2 つのオブジェクトを分離する線または平面を見つけて、それらが交差できないことを証明します。より高いパフォーマンスが必要な場合は、すべてを試すのではなく、2 つのオブジェクトの最も近いフィーチャを見つけて、使用するのに最も適した線/面を見つけ出すことができます。