問題タブ [line-intersection]

楕円が線または長方形にリンクされているかどうかをJavaに検出させる方法を知りたいのですが、プログラムはリンクされている形状も検出する必要があります。

楕円が描かれ、線も描かれ、長方形が描かれます。Java は、楕円にリンクされているものがあるかどうかを検出する必要があります。ある場合は、リンクされているものを行から見つけます。

図形を描画するコードは次のとおりです。

誰かが私を助けてくれますか？

軸に沿った長方形 R が素敵な四角形 Q と交差するかどうかを効率的にテストするにはどうすればよいでしょうか?

• 良い意味: Q は凸型 (シェブロンではない) であり、自己交差していません (蝶ネクタイでも縮退でもない)。
• ただの二次元。
• はい/いいえ。実際の交差領域は必要ありません。
• 編集: Q と R は、開いていても閉じていてもかまいません。

明らかに、Q の各エッジについて、それが R と交差するかどうかをテストできます。これにより、問題は 次のようになります。.

しかし、R の軸整列性が Liang-Barsky によって Cohen-Sutherland よりも高速になるように利用されているように、Q のプロパティは、Liang-Barsky を複数回実行するよりも高速な何かを取得するために利用される可能性があります。

したがって、多角形と長方形の交差アルゴリズムである Sutherland-Hodgman、Vatti、および Greiner-Hormann はすべて、Q を非凸にするアルゴリズムであり、最適である可能性は低いです。

R の軸整列性を利用していなくても、長方形と長方形の交差部分は有望に見えます。

ブースト ジオメトリを使用して、3D で 2 つの線分の交点を計算しようとしています。

ここにコードがあります：

上記のケースには交差がないことは明らかですが、それでも結果が返されます: ( 1, 0, 6.94593e-310 )

2Dでのみ機能しますか？

Sfml を使用して 2D でゲームを作成しようとしています。そのゲームには、Lightengine と、プレイヤーに見える世界の領域を提供できるコードが必要です。両方の問題が非常にうまく適合するため (実質的には同じです)、両方の問題を一度に解決したいと考えています。私の世界は、オブジェクトのヒットボックスがポリゴンとして表現されるファイルからロードされます。ここで、ポリゴンのリストと、マウスに追従する光線の方向を取得し、これらのポリゴンのいずれかとの最も近い交点を見つけるコードをいくつか書きました。次のステップは、プレーヤーまたはライトの位置からポリゴンのエッジに向かってレイをキャストし、レイを +-0.000001 ラジアンオフセットして可視領域を決定し、ポリゴンとして戻すことです。

ただし、問題は、私のアルゴリズム (ベクトル数学を使用して 2 つの線の間の交差を計算する) が遅すぎることです。私の非常に優れた PC では、300 のエッジと 1 つのレイで 100 fps が得られます。

私は今、オンラインで多くの記事を読みましたが、最善の解決策を見つけることができませんでした. しかし、私が読んだ限りでは、三角形との交点を計算する方がはるかに高速です。

私の質問: マップの読み込み中に一度ポリゴンを三角測量してから、光線と三角形の交差を使用する方が意味のある高速でしょうか、それとも私の問題を解決するために知っているより良い方法はありますか? Volumen 階層の境界についても聞いたことがありますが、それがどれほどの影響を与えるかはわかりません。

2 次元の交差を計算するだけでよいため、私のアルゴリズムが消費する電力には少し驚いています...