28

それで、

問題

2 点が 2D 平面上で接続されているかどうかを判断するアルゴリズムについて質問があります。私は持っている：

  • 2D ラインの配列。各線は、始点と終点の 2D 点で制限されます。各点は 2 つの要素の単純な配列です。[x,y]つまり、各線は次のようになります。['start'=>[X0, Y0], 'end'=>[X1, Y1]]この線セットに という名前を付けますL。線は互いに属することができます (つまり、1 つの線が別の線の一部である可能性があります)。1 つの点のみで交差できます。つまり、2D 平面上では制限はありません。ただし、線を点にすることはできません。つまり、線の始点と線の終点を等しくすることはできません。
  • 2 点SおよびE、つまり配列[Xs, Ys]および[Xe, Ye]

これで、 からのすべての線Lが平面上に描画されます。次に、SとEも描画され、質問に答える必要があります。L の線が交差することなく、S から E に到達できますか? さらに具体的に言うと、どのアルゴリズムが最適でしょうか? 「到達可能」とは、飛行機に からSへの道があり、そこからEどの線とも交差しないことを意味しLます。

サンプル

ここに画像の説明を入力

-ご覧のとおり、サンプルSでは とEは接続されていません。また、サンプルでは、​​ある行が別の行に完全に属している場合 (灰色と紫の行) と、ある行が別の行に開始/終了を持っている場合 (緑とバラの行) があります。

私のアプローチ

現在、それを行うための非決定論的多項式 (NP) アルゴリズムがあります。その手順は次のとおりです。

  • 線の各ペアの交点をすべて見つけます。
  • 最初のステップの点から新しい線のセットを作成します。2 つの線に 1 つの交点がある場合、4 つの新しい線があり、それぞれの新しい線の始点に交点があります。または、最初の線の始点/終点が 2 番目の線にある場合は 3 つの新しい線になります。または、2 つの新しい線になります。最初の行の開始/終了が 2 番目の行の開始/終了と正確に一致する場合の行。すなわち:

2 回線の 5 つの一般的なケース

したがって、最初のケースは 4 つの新しい行になり、2-4 ケースは 3 つの新しい行に、5 つのケースは 2 つの新しい行になります。(行は[A, B]と[C, D])

  • 次に、2番目のステップからラインステップで、すべてのポリゴンを検​​索しています。ポリゴンは閉じた線のセットです (つまり、領域の閉じた部分を保持します)
  • Sを含むポリゴンのサブセットを決定していますS。これを行うために、私は単純なアルゴリズムを使用しています - ポリゴンのエッジとの交差の数とS外側の平面への線を数えます(奇数の場合Sはポリゴンの内側にあり、偶数の場合は外側にあります)。これはレイキャスティングアルゴリズムです。それから私はそれをしますE
  • Sここで、両方にポリゴンを設定し、E単純に両方のセットを比較しています。それらが等しい場合は、Eから到達でき、到達Sできませんでした-そうでない場合。

なぜこれが NP なのか?

答えは簡単です。3 番目のステップで、2D グラフ内のすべてのループの検索を実行しています。NPの場合、最大/最小ループ長を見つける問題があるため、私のものもそうです(結果のループセットをソートするだけで最大/最小ループ長を取得できるため)。これに関する良い情報はここにあります。

質問

私の現在の解決策はNPであるため、知りたいです-問題に対する私の解決策はやり過ぎでしょうか? つまり、多項式時間になるより単純なソリューションがあるかもしれませんか?

4

5 に答える 5

9

基本的に問題は次のように要約されます:
1) 他の多角形を含まない空間を囲むすべての多角形を決定します。上記の例では、他を含まない 3 つの形状/サイクル/ポリゴンがあります。S を含む四角形、E を含む四角形、およびそれらの 2 つの下の三角形です。
2) S と E がこれらのポリゴンのいずれかの内側/外側の反対側にあるかどうかを判断します。

パート 1 では、グラフを作成する必要があります。

指定した線の交点の配列を作成します。これは N^2 です。各交点がどの 2 本の線から来たかを覚えておいてください。これらの交点がグラフの頂点です。

2 つの頂点が同じ線から出ており、それらの間に他の交点がない場合、これらの頂点は「接続」されています。明らかに、これを決定するために浮動小数点の精度に依存しないでください。

ここで、レイアウト内のポリゴンを見つけたいと考えています。一般に、グラフには指数関数的な数のサイクルが含まれる場合があります。ただし、各エッジは 2 つの「内側」ポリゴンにのみ接する可能性があるため、サイクルの多項式サブセットのみに関心があります。エッジを選択し、ポリゴン内の次のエッジを見つけて、最初のエッジに戻るか、最初のエッジがポリゴンの一部ではないと判断するまで繰り返します。

したがって、エッジ E = (U, V) から来て、ポリゴン内の次のエッジ (同じ頂点 V を共有する) を見つけたいとします。
1) ベクトル T を U - V として
作成します。2) 頂点 V に隣接するエッジ A のセットを作成します。そのセットから E を削除します。
3) セットが空の場合、エッジはポリゴンの一部ではありません。
4) A の各辺 (Q, V) に対して、ベクトル R を Q - V として作成します (Q と V は 2D 平面の点を表すことに注意してください)。
5) R の正規化: 長さで割り、長さ 1 のベクトルを作成します。
6) CrossProductValue(T, R) を決定します。
7) CrossProductValue が最小の A のエッジは、隣接するポリゴンの次のエッジです。CrossProductValue が最大の A のエッジは、他のポリゴンの次のエッジです。

CrossProductChecker(2D T, 2D R) {
  return (T.x*R.y - T.y*R.x); // cross product for 2 dimensions
}

したがって、これを使用してポリゴンを見つけます。外積と正弦波の関係を調べて、これがどのように機能するかを理解してください。

============

すべてのポリゴンが揃ったので、あとは、S が内側で E が外側にあるポリゴンがあるかどうか、またはその逆かどうかを確認するだけです。

これを行う簡単な方法は、S から E に線を引くことです。任意のポリゴン (上からのサイクル) と偶数回交差する場合、それらは両方ともポリゴンの内側または外側にあるので、チェックを続けます。

線が周期と奇数回交差する場合、1 つは多角形の内側にあり、もう 1 つは外側にあるため、パスはないと言えます。

于 2013-09-27T11:29:30.377 に答える
6

2 つの障害物頂点が直接可視である場合、それらを接続するいわゆる「可視性グラフ」を作成できます。このグラフの最短経路 (S と E を追加) は、構成空間内の S と E の間の最短の障害物のない経路になります。可視性グラフに関するアルゴリズムと最適化はよく知られており、広く説明されています。

主な問題は、セグメントの反対側への不適切な交差点 (共有セグメント、交差点としてのエンドポイントなど) に「漏れる」ことがないように、コーナー ケースを処理することです。このような特殊なケースの処理は、アルゴリズム的に難しくはありませんが、忍耐が必要です。

編集：

では、もっと形式的に説明しましょう。すべてのセグメントのエンドポイントを含むグラフG(Ver, Edg)を作成します。直接表示されるすべての頂点のペアが含まれます (セグメントをたどる場合を含む) 。VerSEEdg

于 2013-09-27T11:11:04.823 に答える
2

線分によって形成される平面直線グラフを計算し、S と E が属する面を見つけます。S と E が同じ面に属している場合にのみ、パスが存在します。最初の 2 つのステップは、計算幾何学の標準的な多項式時間アルゴリズムであり、多くの説明と実装が利用可能です。

于 2013-09-27T17:38:13.770 に答える