不規則な形状のポリゴンの包含確率

私は2つの図形を持っています.1つはサークル、Aはサークル、もう1つは不規則に形作られたポリゴンBです.Aは常にBより大きい領域を持ちます。これらのポリゴンは両方とも領域S内にあります。

私の仕事は、無作為抽出のサンプルでポリゴンBの包含確率を計算することです。包含はポリゴンBが完全に円A(円)の内側にあると定義されます。

私の仮定は、ポリゴンBの包含確率は、ポリゴンBを囲むことができるようにサークルAが置かれる領域に等しい別のポリゴンCの領域であり、ポリゴンBをSの総面積で割ったものです。

この仮定が正しければ、ポリゴンCを計算することは計算上集中的に見える。

ポリゴンCを見つける効率的な方法はありますか?

ベストアンサー

まず注目すべきは、$ B $の頂点のすべてが$ A $の内側にある場合に限り、$ n $ – 頂点ポリゴン$ B $がサークル$
A $の内側にあることです。 (1)

だからあなたの問題に対する解は、ちょうど$ n $任意の交差する円の領域であり、それぞれの半径は$ r $で頂点は$ B
$です。 (最終的な確率を得るために$ S $で割ります)。この問題に関する興味深いブログがあります。ここには、あなたのユースケースに十分なヒューリスティックな解決策が含まれています。

理論的な観点から、最も遠い点のボロノイ図は、
a>は私たちに良い出発点を与えます。最も遠い点のボロノイ図のセルの中の点$ p $を見てみましょう。 $ p $を中心とする円A
$に$ B $が含まれているかどうかを知りたい。上記により、$ B $のすべての頂点が$ p $の距離$ r
$内にある場合にのみ、これが発生します。今、最も遠いボロノイ図のセルの内部にあるので、$ p $がその最も遠い点の距離$ r
$以内にあるかどうかをテストすることができます。

特に、与えられたVoronoiセル内で必要とする領域は、そのボロノイセルと半径$ r
$の単一円との交点である。これは、セルの辺の数が時間的に直線的に容易に計算することができる。最も遠い点のボロノイ図は$
O(n)$個の辺を持つ$ O(n)$個のセルを持つので、合計$ O(n)$時間かかる。

次に、合計実行時間は、最も遠い点のボロノイ図を計算する時間によって支配されます。これは$ O(n log
n)$です。同様の戦略では、同じ時間内に明示的な領域$ C $が得られます。

(1):「唯一の」方向が明白です。 “if”方向を見るために、まず$ B $の頂点が$ A
$の内側にある場合にconvexityによって、$ B
$のすべての辺も同じでなければならないことに注意してください。同じ議論は、2つの頂点または辺の間の線上になければならないので、$ B
$のすべての内部点に及ぶ。

返信を残す

メールアドレスが公開されることはありません。 * が付いている欄は必須項目です