13

与えられた：

  • （X、Y）座標。これは、車両の位置です。
  • ポリラインの頂点である（X、Y）の配列。ポリラインは直線セグメントのみで構成され、円弧は含まれないことに注意してください。

私が欲しいもの：

  • 車両がポリラインの左側にあるか右側にあるか（またはもちろん上部にあるか）を計算します。

私のアプローチ：

  • すべての線分を反復処理し、各線分までの距離を計算します。次に、最も近いセグメントに対して、単純な左左テストを実行します（たとえばここで説明します）。

考えられる問題：

  • 3つのポイントが90度よりも小さい角度を形成する場合（画像のブローに示されているように）、より複雑なシナリオが発生します。以下に示すように、車両が赤いセグメントにある場合、最も近いセグメントは2つのいずれかになります。ただし、左のテストでは、最初のセグメントが最も近いセグメントとして選択された場合は右になり、それ以外の場合は左になります。車両がポリラインから離れているという正しい結果が得られるはずであることが簡単にわかります（少なくとも、私は願っています） 。

エラーシナリオ

私の質問：

  • どうすればエレガントに、しかしほとんど効率的にこの特定の状況に対処できますか？

これまでの私の修正：

  • 両方のセグメントについて、頂点点から開始して、そのセグメント上の点を計算します。
  • ユークリッド距離を使用して、車両から両方のポイントまでの距離を計算します
  • 計算されたポイントが最も近いセグメントを保持します。

私はこの修正にあまり満足していません。はるかにエレガントな解決策が欠けているように感じ、私の修正はかなり「ハッキー」に感じます。ただし、効率はリアルタイムの組み込みシステムで使用されるため、重要です。

既存のコードベースはC++であるため、特定の言語で記述したい場合は、C++が私の好みです。ありがとう！

[編集]外向きの法線を計算するよりも線分をたどる方が簡単だと思うので、修正を垂直点から平行点 に変更しました。

4

4 に答える 4

1

無限大=Mとします。ここで、Mは十分に大きいです。すべてが正方形[-M、M] x [-M、M]にあると見なし、正方形をポリラインで分割すると、2つのポリゴンが作成されます。次に、車が特定のポリゴン内にあるかどうかを確認することは、角度を使用して非常に簡単に行うことができます。

最初の点と最後の点の座標にMが含まれていると思います。ポリゴンを作成するには、次のポイントのいくつかを追加する必要がある場合があります：（-M、-M）、（M、-M）、（M、M）、および（-M、M）。

ポリラインの左側にポリゴンができたら、角度OĈPを合計します。ここで、Oは固定点、Cは車、Pはポリゴンの点です。合計が0の場合、車はポリゴンの外側にあり、そうでない場合は内側にあります。

于 2012-05-14T13:13:29.170 に答える
1

このトピックは長い間非アクティブであったため、私はそれが死んでいると信じています。しかし、私には解決策があります。

ただし、左のテストでは、最初のセグメントが最も近いセグメントとして選択された場合は右になり、それ以外の場合は左になります。

少しあいまいな言葉を使用しました。セグメントを使用してポリラインの線分について説明し、象限を使用してそれらで区切られた領域について説明します。したがって、あなたの場合、一方のセグメントの右側ともう一方のセグメントの左側にあるように見える赤い象限があります。

左側のテストでセグメントごとに異なる回答が得られる場合は、セグメント自体でテストをやり直す必要があります。あなたの場合、あなたは持っているでしょう：

  • 象限は最初のセグメントの右側にあります
  • 象限は2番目のセグメントの左側にあります

両方のセグメントは象限がどこにあるかについて意見が一致しないため、さらに2つの曖昧性解消テストを実行します。

  • 2番目のセグメントは最初のセグメントの右側にあります
  • 最初のセグメントは2番目のセグメントの右側にあります

これにより、2番目のセグメントが最初のセグメントと象限の間にあると結論付けることができます。これら2つのセグメントはそれぞれ2番目のセグメントの異なる側にあるためです。したがって、2番目のセグメントは最初のセグメントよりも象限に「近い」ので、左右のテストに対する答えを正しいものとして使用する必要があります。

（2つの曖昧性解消テストのうち1つだけで実行できるとほぼ確信しています。わかりやすくするために、両方を入れました）

完全を期すために：このソリューションは、最初から使用していたのと同じ方法（テストの左側）を使用し、指定されたすべての条件を満たしているため、効率と優雅さの要求も考慮していると思います。それはエレガントで、効率的で、問題を処理します。

于 2014-04-16T07:28:45.920 に答える
0

簡単なアイデア：ポリラインの最後と最初の頂点を接続して、ポリゴンになることは可能でしょうか？次に、単純な内側/外側のチェックを実行して、車両がラインの左/右にあるかどうかを判断できます（これはもちろんポリゴンの方向によって異なります）。

ただし、この方法では、最後の頂点と最初の頂点を接続した後も、ポリゴンがまだ自己交差していないことを前提としています。

于 2012-05-14T12:57:20.517 に答える
0

これは、計算幾何学からの標準的な種類の問題です。ポイント（x0、y0）が特定のサーフェス（ポリライン）の左側にあるかどうかをテストするため、テストするセグメントをその高さで特定する必要があります。これを行う簡単な方法の1つは、各セグメントの下位ポイントのツリーを構築し、そのツリーでテストポイントの先行ポイントを検索することです。そのセグメントを取得したら、左側のテストを直接実行できます。両方のエンドポイントの左側、または適切な側のそれらの間にある場合は、trueを返します。

ここでは、ポリラインの垂直方向の範囲がクエリポイントを見つける場所よりも大きく、線が垂直方向に重ならないことを保証していると想定しています。後者の仮定はかなり貧弱かもしれません。

OPのコメントに応じた拡張：

質問の角度の例は、最初の仮定と矛盾することに注意してください。ポリラインは検索ポイントの高さに達していません。

私の方法を概念化する1つの方法は、セグメントを垂直方向に並べ替えてから、ポイントが下の端点より上で上の端点より下になるまで、ポイントのy座標をセグメントと比較することです。次に、セグメントの端点を使用して、指定されたyでのx切片を計算します。ポイントのx座標が低い場合は左側にあり、x座標が大きい場合は右側にあります。

実際の実装でこの説明を改善する方法は2つあり、そのうちの1つについて説明しました。

  1. バランスの取れた検索ツリーを使用して、並べ替えられたリストを反復処理する代わりに、適切なセグメントを見つけてO(n)、O(log n)
  2. 検索ポイントを通るポリラインと水平線y=y0の交点を見つけることとして、検索を再概念化します。次に、交差のx値を検索ポイントと比較します。
于 2012-05-14T13:14:14.843 に答える