2

ポイントがラインパスを横切ったかどうかを確認する必要があるという問題があります.
ラインパスはラインのコレクションです（y = ax + b）。
これに関する既知のアルゴリズムを知っている人はいますか?

だから私はそれを次のように解決しました：私はパスの始点と終点に2点を追加しました。レイアルゴリズムを使用しました。

4

4 に答える 4

1

ポイントがポリゴンの内側にあるか外側にあるかを知るための簡単なアルゴリズムがあります: http://en.wikipedia.org/wiki/Point_in_polygon これは、ポリゴンのいくつかのエッジを無限にプッシュすることにより、ライン パス設定に適応させることができます (実際には、ラインパスを大きなボックスに入れ、ラインの右側（または必要に応じて左側）にあるボックスの部分によって形成される多角形を検討できます）。

于 2013-07-24T14:25:47.590 に答える
0

だから私はそれを次のように解決しました：パスの始点と終点に2点を追加したので、これは多角形になり、90度の2点を固定距離の点に追加しました。レイアルゴリズムを使用しました。

編集：常に90度であるとは限りません。ポイントの開始点と終了点の間の角度に依存します

于 2013-07-25T13:23:57.523 に答える
0

私は2つのアプローチを知っています：

  1. ポリゴン アルゴリズム内の適応点を使用
    • あなたはどちらがどちら側であるかを知る必要があります（交差/非交差側）
    • ラインパッチから交差する側を指すベクトルdirを作成します
    • 平均法線（または始点終点線の法線）にすることができます
    • テストされたポイントからdir方向に光線をキャストします
    • ラインパッチとの交点を数えます
    • 交差が 2 つの線の接続点で正確に発生した場合は、1 回だけカウントします
    • 最後に、カウントがゼロ以外で奇数の場合、ポイントはライン パッチを超えています
    • これは堅牢なエラーが発生しやすいですが、少し遅いです
    • 左の写真を見てください
  2. ライン パッチの形状が複雑すぎない場合は、ワインディング ルール (スカラー ベクトル乗算) を使用します。
    • ライン パッチ ラインは、最初から最後まで一方向でなければなりません!!!
    • ポイントに近いパッチから行を選択します（1〜5で十分です）
    • 理想的には右の写真と同じ高さ
    • もちろん、実際には回転できるので、距離で線を選択します（sqrtする必要はありません）
    • 次のように、選択した行の内積を計算します。
    • ライン P0,P1、点 P -> 内積 = ((P1-P0).(P-P1))
    • 2 つのベクトルの内積( (x0,y0,z0).(x1,y1,z1))=(x0*x1+y0*y1+z0*z1)
    • 結果の極性は、巻き方向 CW/CCW を意味します。
    • ポイントが交差していないよりもすべての巻線が正しい場合
    • ライン パッチの形状が複雑な場合、ポイントが近すぎると問題が発生する可能性があります
    • その場合、同じ「高さ」の行のみをテストするか、方法 1 を使用します。
    • 「高さ」を取得するには、点と線の開始点の間の線方向の距離を計算します
    • ゼロから行のサイズまでの場合はOKです。それ以外の場合は使用しません
    • 線方向への法線ベクトルの内積でも実行できます

ラインパッチクロッシング

于 2013-10-05T08:10:08.143 に答える