問題タブ [line-intersection]

私はこれで私のエラーを見つけることができないので、メソッド intersecLines() のように思えます。これは、2 つの線に 1 つ以上の共通点があるかどうかをチェックして、間違った結果を返します。

私はスネークのようなゲームでこれを使用しています。このメソッドは、この「スネークパス」(パスのポイントで構成される ArrayList として存在する) の最初のポイントと 2 番目のポイントの間の線が交差するかどうかを確認する必要があります。ヘビを構成する他の線の1つと。

パラメータは次のとおりです。 Vector2 first 最初の行のポイント。Vector2 最初の線の 2 番目のポイント。Vector2 2 番目の線の最初のポイント。Vector2 2 番目のラインの 2 番目のポイント。交点に設定される Vector2。

GDX に慣れていない方のために説明すると、GDX は Java でのクロスプラットフォーム開発に使用されるフレームワークであり、ほとんどのメソッドは openGL ES メソッドの実装です。Intersector クラスの API リファレンスは次のとおりです: http://libgdx.badlogicgames.com/nightlies/docs/api/com/badlogic/gdx/math/Intersector.html

同じ平面上にある 2 つの 3D ラインがあります。line1は点 ( ) とその方向ベクトル ( ) で定義され、 は点 ( x1, y1, z1) とその方向ベクトル ( a1, b1, c1)でline2定義されます。次に、両方の線のパラメトリック方程式は次のとおりです。x2, y2, z2a2, b2, c2

両方の方向ベクトルが非ゼロの場合、上記の方程式の右辺を等式化し、3 つのうちのいずれか 2 つから と を解くことで、交差ノードの位置を簡単に見つけることができtますs。ただし、a1 b1 c1 a2 b2 c2すべてがゼロではない可能性があるため、これらの方程式を同じ方法で解くことはできません。私の現在の考えは、この問題をケースバイケースで処理することです。

しかし、全体として非常に多くのケースがあり、実装が面倒になります。この問題に対処する良い方法はありますか? 参照はありますか？どうもありがとう！

多くの線分のすべての交点を見つけるには、O(n^2) 内のすべての可能なペアをチェックして交点を見つけることができます。

より効率的に実行するためにスイープ ライン アプローチを使用する、よく知られた Bentley-Ottmann_algorithmもあります。

すべての交差点を見つけるための他の効率的なアルゴリズムはありますか?

せいぜい、既知およびあまり知られていないアルゴリズムの調査が非常に役立つでしょう。

代数的再構成法の重み行列を見つけたいです。このために、グリッドとの線の交点を見つける必要があります。線との直接線の交点を見つけることができますが、交差した線セグメントのグリッド番号を保存する必要があります。したがって、グリッドの最初の正方形がグリッドと交差しない場合、重み行列の最初の要素にゼロを置くとします。

私が線の交点で試したコードは次のとおりです。

m, hparametersで定義された線があります。y = m*x + hこの線はグリッド (つまり、ピクセル) を横切ります。

グリッドの各正方形(a, b)(つまり、正方形) について、指定された線がこの正方形と交差するかどうか[a, a+1]x[b, b+1]を判断したいと考えています。代数再構成法に不可欠です。

線分のセットがありAB1, AB2, ... ABnます。それぞれに(Ax, Ay), (Bx, By)座標があります。次に、中心座標 (Cx、Cy) と r (半径) を持つ円があります。

問題: どの線分が円の上にあるか (図中)、またはそうでないかをどのように検出できますか? .

私は自分の考えをPythonで定式化しようとしました：

よろしくお願いいたします。

線分(線ではない)、(A1, B1)、(A2, B2)、のセットがあります。(A3, B3)ここでA、Bは線分の終点です。それぞれAに座標Bがあります。(x,y)

質問:コード行に実装された図に示されているように、point Oと の間の最短距離を知る必要があります。私が本当に理解できるコードは、疑似コードまたは Python のいずれかです。line segments

コード:このコードで問題を解決しようとしましたが、残念ながら正しく動作しません。

前もって感謝します。

直線（無限）の間のすべての交点を見つけたいと思います。線分のセットで機能する Bentley-Ottmann アルゴリズムを変更しようとしていますが、無限の直線を適切に表現する方法がわかりません。最初のアイデアは、各線の開始と終了をシミュレートする境界点を決定することでしたが、それは間違った解決策だと思います (「無限」の点を見つける方法は?)。次のアイデアは、方程式を使用して直線を表すことですが、Bentley-Ottmann アルゴリズムを使用できるかどうかはわかりません (線を順序付けてスケジュールにイベントを追加する方法は?)。さらに、(一連の方程式を解きながら) 2 つの線の交点を検出するために、おそらく除算を使用する必要があります。避けたいと思います。

アドバイスをいただけますか？

どうもありがとう