可視性ポリゴン

計算幾何学において、障害物に囲まれた平面上の点pの可視ポリゴンまたは可視領域は、 pから見える平面上のすべての点の、境界のない可能性のあるポリゴン領域です。可視ポリゴンは、線分またはポリゴンからの可視性に対して定義することもできます。可視ポリゴンは、ロボット工学、ビデオゲーム、および施設配置問題やアートギャラリー問題などのさまざまな最適化問題で役立ちます。

可視ポリゴンが有界である場合、それは星型のポリゴンです。可視ポリゴンが有界であるのは、その点から発射されるすべての光線が最終的に何らかの障害物で終わる場合です。これは、たとえば、障害物が単純なポリゴンのエッジであり、p がポリゴンの内側にある場合です。後者の場合、可視ポリゴンは線形時間で見つかる可能性があります。^{[1] [2] [3] [4]}

正式には、平面可視ポリゴン問題を次のように定義できます。を 内の障害物 (線分またはポリゴン) の集合とします。を障害物内にない 内の点とします。すると、点可視ポリゴンは内の点の集合であり、内のすべての点について、線分は内のどの障害物とも交差しません。 ${\displaystyle S}$${\displaystyle \mathbb {R} ^{2}}$${\displaystyle p}$${\displaystyle \mathbb {R} ^{2}}$ ${\displaystyle V}$${\displaystyle \mathbb {R} ^{2}}$${\displaystyle q}$${\displaystyle V}$${\displaystyle pq}$${\displaystyle S}$

同様に、セグメント可視ポリゴンまたはエッジ可視ポリゴンは、線分に沿った任意の点から見える部分です。

可視ポリゴンはロボット工学で役立ちます。例えば、ロボットの位置特定では、 LIDARなどのセンサーを使用するロボットは、視認できる障害物を検出しますが、これは可視ポリゴンに似ています。^[5]

これらはビデオゲームでも役立ち、実装するための簡単なアルゴリズムを説明するオンラインチュートリアルが多数あります。^{[6] [7] [8]}

ポイント可視ポリゴンを計算するためのアルゴリズムは数多く提案されています。問題のさまざまなバリエーション（たとえば、さまざまなタイプの障害物）に応じて、アルゴリズムの時間計算量は異なります。

単純なアルゴリズムは理解しやすく実装も簡単ですが、他のアルゴリズムよりもはるかに遅くなる可能性があるため、 最適ではありません。

現実世界では、光る点はあらゆる方向に光を発するため、その点から見える領域を照らします。これは、多くの方向に光線を発射することでシミュレートできます。点が で、障害物の集合が であると仮定します。この場合、疑似コードは次のように表現できます。 ${\displaystyle p}$${\displaystyle S}$

アルゴリズムnaive_bad_algorithm( , )は : =です:${\displaystyle p}$${\displaystyle S}$
    ${\displaystyle V}$${\displaystyle \emptyset}$
     ${\displaystyle \theta =0,​​\cdots ,2\pi }$ // 角度:=
        の光線を各障害物に対して発射します:
              := min( 、この方向の障害物までの距離)${\displaystyle \theta}$
        ${\displaystyle r}$${\displaystyle \infty}$
        ${\displaystyle S}$${\displaystyle r}$${\displaystyle r}$${\displaystyle p}$
        頂点を追加して返す${\displaystyle (\theta,r)}$${\displaystyle V}$
     ${\displaystyle V}$

さて、無限に多くの角度をすべて試すことができれば、結果は正しいものになるでしょう。残念ながら、コンピュータの制限により、すべての方向を実際に試すことは不可能です。近似値を作成するには、たとえば 50 本の光線を均等間隔で投射します。ただし、小さな障害物は 2 本の隣接する光線で完全に見逃される可能性があるため、これは正確なソリューションではありません。さらに、ほぼ同様のソリューションを得るために多くの光線を投射する必要があるため、非常に遅く、出力可視ポリゴンには必要以上に多くの頂点が含まれる可能性があります。

前述のアルゴリズムは、すべての障害物の頂点に光線を照射するだけで十分であるという観察を行うことで、速度と正確さの両方において大幅に改善できます。これは、可視ポリゴンの境界に沿った曲がりや角は、障害物の角 (つまり頂点) によるものである必要があるためです。

アルゴリズムnaive_better_algorithm( , )は := の各障害物に対して:
        の各頂点に対して:${\displaystyle p}$${\displaystyle S}$
    ${\displaystyle V}$${\displaystyle \emptyset}$
    ${\displaystyle b}$${\displaystyle S}$${\displaystyle v}$${\displaystyle b}$// からへ
            の光線を発射します := からへの距離:=に対する の角度、内の各障害物について::
                  = min( 、 からへの距離)${\displaystyle p}$${\displaystyle v}$
            ${\displaystyle r}$${\displaystyle p}$${\displaystyle v}$
            ${\displaystyle \theta}$${\displaystyle v}$${\displaystyle p}$
            ${\displaystyle b'}$${\displaystyle S}$${\displaystyle r}$${\displaystyle r}$${\displaystyle p}$${\displaystyle b'}$
            頂点を追加して返す${\displaystyle (\theta,r)}$${\displaystyle V}$
     ${\displaystyle V}$

上記のアルゴリズムは正しくない可能性があります。Talk のディスカッションを参照してください。

このアルゴリズムの時間計算量は です。これは、アルゴリズムがすべての頂点に光線を発射し、光線の終点を確認するためにすべての障害物との交差を確認する必要があるためです。これはビデオゲームなどの多くの単純なアプリケーションでは十分であり、多くのオンラインチュートリアルでこの方法が教えられています。^[8]ただし、後で説明するように、より高速なアルゴリズムがあります（障害物が単純なポリゴンである場合やポリゴンの穴の数が固定されている場合は、さらに高速なアルゴリズムもあります）。 ${\displaystyle O(n^{2})}$${\displaystyle n}$${\displaystyle O(n)}$${\displaystyle O(n\log n)}$

単純な多角形と点 が与えられた場合、から見える 内の領域を計算するには線形時間アルゴリズムが最適です。このようなアルゴリズムは 1981 年に初めて提案されました。^[2]しかし、これは非常に複雑です。1983 年には、概念的により単純なアルゴリズムが提案されましたが^[3] 、これには小さなエラーがあり、1987 年に修正されました。^[4]${\displaystyle {\mathcal {P}}}$${\displaystyle p}$${\displaystyle {\mathcal {P}}}$${\displaystyle p}$

後者のアルゴリズムについて、ここで簡単に説明します。これは、ポリゴン の境界を歩き回り、頂点を出現順に処理しながら、がスタックの最上部にある頂点のスタックを維持します。スタックは、 から見える、これまでに遭遇した頂点で構成されます。アルゴリズムの実行中に、 の一部を隠してしまう新しい頂点がいくつか遭遇した場合、 の隠れた頂点はスタックからポップされます。アルゴリズムが終了すると、 はすべての可視頂点、つまり目的の可視ポリゴンで構成されます。効率的な実装は 2014 年に公開されました。^[9]${\displaystyle {\mathcal {P}}}$${\displaystyle {\mathcal {S}}=s_{0},s_{1},\cdots ,s_{t}}$${\displaystyle s_{t}}$${\displaystyle p}$${\displaystyle {\mathcal {S}}}$${\displaystyle {\mathcal {S}}}$${\displaystyle {\mathcal {S}}}$

穴と頂点を合わせた多角形内の点については、最悪の場合でもアルゴリズムが最適であることが示されます。このようなアルゴリズムは、最適性の証明とともに 1995 年に提案されました。^[10]しかし、これは Chazelle による線形時間多角形三角測量アルゴリズムに依存しており、非常に複雑です。 ${\displaystyle h}$${\displaystyle n}$${\displaystyle \Theta (n+h\log h)}$

端点以外で交差しない線分の集合の中の点については、最悪の場合でもアルゴリズムが最適であることが示される。これは、可視ポリゴンアルゴリズムは可視ポリゴンの頂点をソートされた順序で出力する必要があるため、ソートの問題は可視ポリゴンの計算に還元できるからである。^[11]${\displaystyle n}$${\displaystyle \Theta (n\log n)}$

任意のポリゴンをセグメントに分解できるため、セグメント間のポイントの可視ポリゴンを計算するアルゴリズムは、他のすべての種類のポリゴン障害物の可視ポリゴンを計算するために使用できることに注意してください。

可視ポリゴンを計算するための分割統治アルゴリズムは1987年に提案されました。[ 12 ^]

可視ポリゴンを計算するための角度スイープ、すなわち回転平面スイープアルゴリズムは、1985年[13]と1986年に提案されました。[ 11 ]^アイデアは^、まずすべてのセグメントの端点を極角でソートし、次にその順序で反復処理することです。反復処理中、イベントラインはヒープとして維持されます。効率的な実装は2014年に公開されました。^[9]

一般的に交差する線分の間の点について、可視ポリゴン問題は線形時間で下側エンベロープ問題に還元できる。ダベンポート・シンツェルの議論によれば、最悪の場合の下側エンベロープには頂点数があり、ここで は逆アッカーマン関数である。時間内で実行される最悪の場合の最適な分割統治アルゴリズムは、1989年にジョン・ハーシュバーガーによって作成された。^[14]${\displaystyle \Theta (n\alpha (n))}$${\displaystyle \alpha (n)}$${\displaystyle \Theta (n\log n)}$

• http://web.informatik.uni-bonn.de/I/GeomLab/VisPolygon/index.html.en (単純なポリゴンの可視性 - アプレット)

• VisiLibity: 平面ポリゴン環境での可視性計算用の無料のオープンソース C++ ライブラリ。
• visibility-polygon-js: 角度スイープ法を使用してセグメント間のポイントの可視ポリゴンを計算するためのパブリック ドメインの Javascript ライブラリ。