2

角度間隔（ラジアン）があります[0,2π）

  • たとえば、間隔[（2π）/ 3、（3π）/ 4]、[π/ 2、π]など。
  • ただし、間隔[（3π）/ 2、π/3]もあります。

私はほとんどの間隔で配置されている角度を見つける必要があります。C ++でそれを見つけるための最良の方法は何ですか？角度間隔をどのように表すことができますか？

4

4 に答える 4

4

この問題を解決するために、単純なスイープラインアルゴリズムを実装できます。

区間ごとに、区間の開始と終了をベクトルに追加します。このベクトルを並べ替えてから、繰り返します。2π境界を越える区間がある場合は、それを2つの区間に分割します。これらは両方とも（0、2π）の内側にあります。

リストを反復処理するときは、現在のポイントで重複している反復回数と、これまでに見た中で最高の角度（およびその角度で重複していた間隔）を追跡します。終わりに達すると、最適な角度がわかります。

複数の角度が必要な場合は、このアプローチを簡単に適応させて、単一の角度ではなく、最大のオーバーラップを持つ間隔を記憶することができます。

于 2012-11-09T16:50:06.133 に答える
1

私の解決策には、間隔の開始とそれと重なる間隔の数のペアのリストが含まれます。

     1        2       3       2              1
|---------|--------|-----|---------------|------|

|------------------|
          |--------------|
                   |---------------------|
                   |----------------------------|

したがって、すべての開始点と終了点を並べ替え、リストをトラバースして、新しい間隔ごとに重複する間隔の数を割り当てます（開始点の場合は増加し、そうでない場合は減少します）。次に、オーバーラップカウントから最大値を取得します。

于 2012-11-09T16:52:05.930 に答える
1

[0,2π]のパーティションを間隔カバレッジに対応する範囲に維持し、各範囲をカウントします。まず、どの区間も0（または2π）を超えないという条件下でアルゴリズムがどのように機能するかを次に示します。間隔も次のように正規化されると想定されます。間隔が0で終了する場合、2πで終了するように変更されます。2πから始まる場合は、0から始まるように変更されます。

  1. 単一の範囲[0、2π]とカウント0で初期化された（範囲、カウント）ペアのリストを作成します（リストは範囲の開始順に並べられます。リスト内の範囲は、それらの範囲でのみ重複します。エンドポイントであり、常に[0,2π]をカバーします）。
  2. 以下に説明するように各間隔を処理します
  3. リストをスキャンして、カウントが最も高い（範囲、カウント）ペアを探します。関係を任意に解決します。範囲内の任意の角度を返します。

間隔を処理するにはi：

  1. 最初の（範囲、カウント）ペア（それを呼び出す）を見つけますs（i.start >= s.range.startつまり、範囲にが含まれますi.start）。（i.startが1つの範囲の終わりである場合、それは別の範囲の開始になることに注意してください。これにより、開始となるペアが選択されます。）
  2. の最後の（範囲、カウント）ペアeを見つけますi.end <= e.range.end。（i.endが1つの範囲の開始である場合、それは別の範囲の終了になることに注意してください。これにより、それが終了であるペアが選択されます。）
  3. i.start > s.range.start（が）i.rangeの内部で始まる場合、2つの（範囲、カウント）ペアとsに分割します。リスト内でとを（この順序で）置き換えます。ss1 = ([s.range.start, i.start], s.count)s2 = ([i.start, s.range.end], s.count)ss1s2
  4. の場合、分割を行うためにを使用して、前の手順と並行してi.end < e.range.end置き換えます。ei.end
  5. （またはステップ3で分割された場合）からs（またはステップ4で分割された場合）までの各ペアについて、カウントに1を加算します。s2see1e

特定の角度を含む実際の間隔の数を追跡する必要がない場合は、それが最大であるだけで、0（または2π）を超える間隔の簿記が簡単です。間隔の補数を取るだけです（逆）開始と終了）を追加する代わりに、ステップ5のカウントから1を減算します。絶対カウントが必要な場合は、補完トリックを実行してから、リストのすべてのカウントに1を追加します。

上記は、隣接する間隔（[0、π/3]と[π/3、π]、または[2π/ 3、2π]と[0、1]）を正しく処理しません。そのような場合、私が理解しているように、それらが接する角度（π/ 3または0）は、2つの間隔にあるものとして数える必要があります。上記のアルゴリズムは、間隔の開始が範囲の終了点と一致するときに、新しい（範囲、カウント）ペアが問題のペアの後に挿入されるように調整できます。新しいペアは、単一の角度範囲（つまり、range.start == range.end）を持ちます。同様の手順が、間隔の終わりから始まる範囲にも適用されます。これらの調整により、上記のアルゴリズムはすべてのケースを正しく処理できると思います。

于 2012-11-09T18:49:30.073 に答える
0

これを象徴的に行わないと、奇妙なエッジケースに遭遇するだろうと思います。

角度範囲は、2進数の分数として正確に表現できるだけでなく（丸め誤差が発生します）、不合理です。（Pi3.14159265359より大きく3.14159265360より小さい;Pi記号的に角度が/ 2に等しいとどのように言いますか？）

私が見ている最も堅牢な方法は、間隔のすべての組み合わせを順番に取得し、それらの交差を決定し、これらの結合された間隔のどれが最も個々の間隔の交差の結果であるかを確認することです。

これには、1つだけでなく、条件を満たすすべての角度を提供するというボーナスもあります。

于 2012-11-09T16:58:10.440 に答える