問題タブ [line-segment]

光線があります。光線が当たる最も近い線分を見つける必要があります。最初に線分をソートすると O(log n) 時間でこれを行うことができると思いますが、それらをソートする方法を思い出せません...ある種のツリーが最適に機能すると思いますが、どうすればソートできますか始点と終点の両方でそれらを？可能であれば、このデータ構造への高速挿入も希望します。

1 つの光線と 1 つの線分のコードはたくさんありますが、1 つの線と多数の線分のコードが必要です...どの用語を検索すればよいかわかりません。

適切な記事へのリンクは有効です。C++ コードはさらに優れています。ありがとう！:)

PS: 線分は、実際には自己交差しないポリゴンのエッジであり、反時計回りの順序で並べ替えられています...しかし、別の方法で並べ替えると、いくつかの利点があると思いますか?

これはすべて2Dです。

よく考えてみると、これが可能かどうかは完全にはわかりません。ある種の空間分割が役立つかもしれませんが、そうでなければ、任意の光線と比較できるように線を並べ替える方法が思いつきません。

点と線分の間の最短距離を見つけるための基本的な関数が必要です。好きな言語でソリューションを自由に書いてください。私はそれを私が使用しているものに翻訳することができます（Javascript）。

編集：私の線分は2つの端点によって定義されています。したがって、私の線分は2つの点とABで定義されます。この線分と点の間の距離を見つけようとしています。私の幾何学のスキルは錆びているので、私が見た例は紛らわしいです、認めて申し訳ありません。A (x1,y1)B (x2,y2)C (x3,y3)

上記の ASCII アートには、正確に重なる線分を持つ 4 つのポリゴン (P1、P2、P3、P4) があります。たとえば、ポリゴン P2 (ノード n3、10、9、12、15、14、13、8、7、6、および 2 間の線分によって形成される) と P1 (n1、2、5、および 6) は、 n2 と n6 の間の線分。

正確に重なっている線分を見つける最速の方法は何ですか?

これは、レイ (および/またはライン セグメントやエッジなど) と、レイ トレーシング操作を実行している/実行していないソフトウェア レンダリング 3D エンジンにおけるそれらの場所に関する大きな一般化された質問です。私は基本を学んでいますが、このことについてあまり知らないことを最初に認めたので、親切にしてください. :)

光線の代わりにパラメータ化された線が使用されないのはなぜだろうか (または??)。インターネット上のいくつかの cpp ファイルを見回したところ、いくつかのリソースで Ray.cpp オブジェクトが定義されていることがわかりました。1 つは頂点とベクトル、もう 1 つはポイントとベクトルを使用しています。法線またはベクトルのみで無限線を定義し、その線に沿って交点を定義して、その無限線のサブセットとして線分を作成できると確信しています。この方法で行を実装している現在のエンジンはありますか、それとももっと良い方法がありますか?

さらに複雑さ (または単純さ?) を追加するために、ウィキペディアは、ベクトル空間では、線分の端点はしばしばベクトルであり、特に u -> u + v であると述べています。すでに定義された無限の線と交差していますが、これの実装を見つけることができず、これを 3D エンジンに適用するときの私の考えの有効性について疑問に思います。Flash 3D エンジン、Papervision を見ると、さらに複雑になります。 Ray クラスを調べたところ、パラメーターとして 6 つの個別の数値を取り、それらを 2 つの異なる Number3D (Papervision の Vector に相当するもの) のデータ型として返します?!?

これらの低レベルの部分を実際の定義に従って実装する正しい方法を実際に使用するものの実装を見ることに非常に興味があります。

通常の式を使用して 2 つの 2D セグメント間の交差を計算する場合、つまりここで、結果を整数に丸めると、非対称の結果が得られます。

つまり、丸め誤差が原因で、intersection(A,B)!=intersection(B,A).

最善の解決策は、フロートを使用し続け、結果を特定の精度まで比較することです。ただし、交差を計算した後、結果を整数に丸める必要があり、浮動小数点数で作業を続けることができません。

これまでの私の最善の解決策は、平面内のセグメントに完全な順序を使用し、intersection常に小さいセグメントと大きいセグメントを比較する必要があることでした。

より良い方法はありますか？何か不足していますか？

いくつかの調査の結果、 2DゲームでLiang-Barskyラインクリッピングアルゴリズムを使用することにしました。Googleは、このアルゴリズムのVB.NET実装を提供していませんでしたが、C/++の実装はたくさん提供していました。したがって、私はC ++の知識があるので、 Skytopiaで見つかったものをVB.Netに移植することにしました。残念ながら、以下では機能しません。

私は次のようなクラス/メソッドを使用しています：

ただし、CollideRayメソッドは3番目のエッジ反復（エッジ= 3）、r <t0で失敗するため、関数はfalseを返します。

私は元気で本当に困惑しているので、誰かが私のCollideRay関数の問題を見つけて、この動作を引き起こす可能性があるかどうか疑問に思っています。

前もって感謝します。

一連の x、y 座標点で定義された非直線があります。画面上でこれらの点の間に直接直線を引くことができましたが、問題はありませんでした。残念ながら、同じ長さのセグメントで線を引く必要があります。

これは、3 つの点を持つ非直線を複数の等距離点の配列に分割する必要がある方法の例です。(最後の赤い点は無視してください。これは、線が均等に分割されていない場合の結果であり、終点でもあります)

「つなぎ目」の赤い線に注目してください。ベクトル AB と BC が角度を成す線 A->B->C があるとします。基本的に、線は点 B で曲がります。

点 A と点 B の間の線分を区切ることは、点までは問題ありません。しかし、AB がセグメントの長さで均等に分割されない場合、何か特別なことをする必要があります。残りの長さを三角形の 1 辺と見なす必要があります。一定のセグメント長は、BC セグメント (上の赤い線) に接続する三角形のもう 1 つの辺です。点 B からこの交点までの長さを知る必要があります。この情報を使用して、BC の線分の計算を続行できます。

これが私が解決しようとしている三角形です(以下、この図に表示されている変数を参照します) ここまでで、コサインの法則を使用して問題を分解しました。c ² = a ² + b ² - 2ab * Cos( y )

問題は、私がすでに c を知っていることです。それはセグメントの長さです。a を解く必要があります (y を計算できます)。

私は多項式を書くところまで行きましたが、今は行き詰まっています: a ² + b ² - 2ab * Cos( y ) - c ² = 0

または Ax ² + Bx + C (A = 1、B = -2b * Cos( y )、C = b ² - c ²、x = a)

これは正しいアプローチですか？次に何をすればいいですか？これを Actionscript で実装する必要があります。

編集:まあ、私は二次式を使用する必要があります。だから私は今得ます：

a = b * Cos( y ) +/- SqrRoot(c ² - b ² * Sin( y ) ² )

これをどのようにコードに入れるか...

現時点では、画像内のエッジを検出しており、ハフ変換を使用してエッジから線分を抽出することを計画しています。セグメントを取得したら、2 つのセグメントが交差するコーナーを見つけることを計画しています。角から長方形を検出できるアルゴリズムはありますか? 4 つの角が検出されたとします。長方形に 4 つの直角があることを知って、4 つの角が構成する長方形の辺の相対的な長さを取得することは可能ですか?

これを行う理由は、四角形で囲まれたテクスチャを抽出し、画面上で平らな四角形として描画できるようにするためです。

編集：これまでの回答に感謝します。少し誤解されていると思うので、問題をより明確に説明する必要があると思います。私は実際に歪んだ長方形を平らな長方形に変換しようとしています。私はいくつかの aforge 記事を読み、この機能を見ました: link。四隅だけで四角形の辺の比率がわかるのかな？

C# または Java での既存の Bentley-Ottmann アルゴリズム実装/ライブラリはありますか?