問題タブ [line-intersection]

編集: サンプル ファイルの Git リポジトリ https://github.com/tpubben/lineIntersect

複数のセグメントで構成される 1 つの連続した線と交差する交差する線のセットに基づいて、x、y 座標で線の交点を計算しようとしています。

連続線は、次のようにタプルのリストで表されます。各セグメントは、前のセグメントの終点の x/y 座標で始まります。

交差する線は同じ方法で表されますが、それぞれが個別の線です (共有点はありません)。

連続線 (lineA) を反復処理し、どの交差する線が lineA のどのセグメントと交差するかを確認しようとしています。

線の交点がどのように見えるかの例の画像は次のとおりです。

これまでのところ、私は次のことを試しました：

どちらかの側からの 2 つの線形ポリフィットから作成された結合されたフィット ラインを取得しようとしています (交差する必要があります)。フィット ラインの画像は次のとおりです。

下の図に示すように、2 つのフィット (青) 線を交差させて結合フィット ラインを生成しようとしています。

クレストはどこにでも発生する可能性があるため、中心にあるとは想定できません。

最初のプロットを作成するコードは次のとおりです。

水平または垂直のN 個の線分があります。次に、交差点の総数と、線分ごとの交差点の総数を調べる必要があります。Nは100000まで上げることができます。すべてのペアの行をチェックしてみました。答えは正しいですが、それにかかる時間を短縮する必要があります。

これが私のコードです:

誰かがこのプログラムの時間の複雑さを軽減するのを手伝ってくれますか?

N本の線 (水平または垂直)が与えられた場合、これらの線分の合計交点と、線ごとの交点を見つける必要があります。私のコードは次のとおりです。

次の入力の場合:

出力:

今、私は次のことを行う方法を理解できません:

1.両方の線分の終点が交わるとき、交点があってはなりません。(3,0) は正しくありませんが、1 つの終点が他の線分上にある可能性があります。私の条件による有効な交点は次のとおりです。

2. 1 行あたりの交点数を計算したい。つまり、目的の出力は次のようになります。

すなわち

コードのこれら2つの間違いを修正するのを手伝ってくれる人はいますか?

学校の数学の知識をブラッシュアップしたいので、簡単な 2D ゲームエンジンを書いています。おそらく多くの人がすでに同様の質問に答えていることは知っていますが（このトピックに関する多くの質問と回答を読みました）、私の方法が機能しない理由を管理できません. この例では、カメラと、カメラの方向に応じて方向を変える 2 つの光線がある「部屋」を見ることができます。これらの光線は、カメラの視野の左右の境界を表し、カメラの前の壁と交差する必要があります。問題は、カメラが移動および回転するとき ("UP"、"DOWN"、"LEFT"、"RIGHT" を使用)、時々光線が消える、つまり交差関数が失敗することです。誰かが解決策を見つけるのを手伝ってくれますか? コードの関連部分は次のとおりです。

編集:コードの無関係な部分を切り取ろうとしました。統合は私の資質の 1 つではありません。より読みやすくなることを願っています。

配列の 1 つが並べ替えられているのに対し、配列の 2 つのセット間の交差の合計量を見つけることができるアルゴリズムを見つける必要があります。

例として、これら 2 つの配列があり、対応する数値に向かって直線を引きます。

これら 2 つの配列により、合計7 つの交差が得られます。

この問題を解決するために、どのようなアルゴリズムが存在しますか?

検索ボタンを使用しましたが、この問題を解決するものは見つかりませんでした。

ありがとう

3D 空間のどこかに線と三角形があります。つまり、三角形には 3 つの点 (それぞれ [x,y,z]) があり、線には 2 つの点 (これも [x,y,z]) があります。

できれば C++ を使用して、線が三角形を横切るかどうかを判断する方法を見つける必要があります。三角形に平行で、共通点が複数ある線は、「交差しない」と見なされます。

すでにいくつかのコードを作成しましたが、機能しません。視覚的な表現が明確に交差点を示している場合でも、常に false になります。

そして、これが inside() の定義です