問題タブ [line-intersection]

How do I determine whether or not two lines intersect, and if they do, at what x,y point?

3D空間で線と線の交点を見つける方法は？誰かが私に方程式を教えてもらえますか？

ゲームのアルゴリズムを機能させるのに問題があり、ここの誰かが私を助けてくれることを願っています。ほとんどのソリューションは完全なタイルで機能するため、Googleはあまり役に立たなかったようです。

ゲームでは、ユニットはタイル内のさまざまな位置を占めることができます。つまり、左上隅、中央、右下、...タイルの位置（2/3）、つまり（2.2 / 3.1）、（2.5 / 3.5）に配置できます。 ）、（2.8 / 3.9）。

それらが位置（2.2 / 3.1）から（5.7 / 4.1）に移動する場合、パスに障害物があるかどうかを確認する必要があります。

私の現在のアルゴリズムは次のとおりです。

1. （2.2 / 3.1）から
2. 動きの角度を計算します（つまり70度）
3. その方向に0.1ステップ移動します
4. 私がいるタイルを確認してください（floor（pX）/ floor（pY））
5. 2から繰り返す

このアルゴリズムは機能しますが、障害物はタイルの一部ではなく完全なタイルにしかなり得ないため、私にはあまり効率的に見えません（ユニットは衝突しません）。ステップサイズを大きくすると、わずかに交差するだけのタイルを見逃し始めます（つまり、左下隅のみを交差します）。ステップサイズが0.1の場合でも、障害物を見逃す可能性があります。

サブマップ（角のあるすべてのタイル（floor（start.X）/ floor（start.Y））と（ceil（start.X）/ ceil（start.Y））を取得するための解決策を見つけようとしました。すべてのタイルを調べて、交差するかどうかを数学的にチェックします。悲しいことに、このチェックに必要な数学の知識が不足しているようです。

私の最後のアイデアは、タイルの4つの境界線すべてを線として取り、線線交叉を行うことでしたが、それは私の元のアプローチよりも遅いようです。

ヒントはありますか？

ありがとう。

2 本の線が交差しているかどうかを検出するための線交差コードを作成しようとしています。私が持っている形式は、Lo(l subscript O) 行を持つことができる O 個のオブジェクトがあり、各行には 2 つのポイントがあり、各ポイントには ax と y があります。これがレコード形式です。

Code を呼び出して、衝突をテストする 2 つのオブジェクトの各行の組み合わせを反復処理します。

各ラインテストはそのように行われます

しかし、私のコードによれば、すべての行は常に交差します.....したがって、私は間違いを犯しました...私は愚かな方法でこれを行っていますか?

numpy を使用して 2 つの線分の交点を計算するにはどうすればよいですか?

私が持っているコードではsegment1 = ((x1,y1),(x2,y2))、segment2 = ((x1,y1),(x2,y2)). 注記segment1は等しくありませんsegment2。したがって、私のコードでは、勾配と y 切片も計算しています。それを回避できればいいのですが、方法がわかりません。

Python で作成した関数で Cramer の規則を使用してきましたが、これを行うためのより高速な方法を見つけたいと思います。

線分のリストが与えられた場合、交点を見つける最も簡単な方法は、線分のリストをループして、それらが交差しているかどうかを確認し、交差している場合は交点を記録することです。

しかし、このメソッドの実行時間はO(n^2)であり、非常に非効率的です。このプロセスを高速化できる他のアルゴリズムはありますか?

線分の交差の計算には、Bentley-Ottmann アルゴリズムが使用されます。

ただし、すべての線の交点を見つけるのではなく、2 つの線のグループ間の交点を見つけたいと考えています。これは、行グループ内のすべての行についてA、それらの行とグループ内の行との交点を知りたいということですB。

このためにBentley-Ottmann アルゴリズムを拡張できる方法はありますか? 私はすでに既存の Bentley-Ottmann アルゴリズムを ( CGAL のライブラリに) 実装していますが、それを変更するつもりはありません。しかし、私はそれを再利用して拡張する方法を見つけたいと思っています。

編集: 他のアルゴリズム (必ずしも Bentley-Ottmann に基づくとは限りません) は歓迎されます。これらのアルゴリズムが既存のライブラリに既に実装されているとよいでしょう。

このデータセットがあるとしましょう...

var a = [5,6,7]; var b = [9,8,6];

これらの値が（x、y）座標ペアでyにプロットされ、xが配列インデックスであると想像してください。2つの配列が1点で交差したかどうかをどのように判断できますか。

ありがとう。

空間に 2 つの点 L1 と L2 があり、線上の 2 つの点を定義します。

空間に 3 点、P1、P2、P3 が平​​面上に 3 点あります。

これらの入力が与えられた場合、直線が平面と交差する点はどこでしょうか?

Fx。平面方程式 A*x+B*y+C*z+D=0 は次のとおりです。

しかし、残りはどうですか？

次の問題に対するアルゴリズムまたは関連する作業はありますか?

2Dの一連の線分が与えられた場合、線分を(水平または垂直に)移動して交差をなくし、全体的な動きを最小限に抑える方法は? エンドポイントでの交差は許可できます。