回転した四角形の中にない点を見つける

Question

私は速く（パフォーマンスに大きく制約されている）アルゴリズムを探しています。この点が円の中のすべての矩形の外にある円の中の点を見つけます（これらの長方形は回転することができます）。 あるいは、円Aの中心が円Bの内側にあり、円Aが線分のセットと交差しない円Aを見つけることができます。

私が思いつくことができる唯一の解決策は、ポイントのサンプルをループして、それぞれの矩形をループすることです。しかし、私のスペースは連続しているので、それはかなりの痛みです。私は基本的に交差しない単一の点に満足していますが、そのような点が存在しない場合があります。後者の場合、私は理想的には交差点の量が最も少ない点を見つけるか、そのような点が存在しないという答えを見つけることができます。

これをO（n^2）未満のもので達成できるアルゴリズムを知っている人はいますか？良い候補点を特定するのに役立つものはどれも素晴らしいだろう。

状況の典型的な例は次のとおりです。 大きな矩形があり、小さな円があり、そこには点（青色で示されています）があります。多くの長方形が円の外に完全に落ちるのはよくあることですが、円が完全に覆われていることも共通しています。矩形に使用される傾向のある長さと幅の小さなセットがあります。

Answer 1

が長方形が配置されているかに応じて、サブのn^2に来るかもしれないという考え：

が明示的に可能な範囲を計算します。

これを表すデータ構造体は、重なり合わないサブ領域のリストであり、三角形（サークルに近似する場合）または「かさばる三角形」（いずれかの辺を円のセグメントにすることができます） 。

円（またはそれを表す三角形のセット）から三角形を始めて、四角形を連続して引きます。これを行うには、実行可能領域の各サブ領域を交差させて、おそらく空の新しいサブ領域の集合を作成します。

実行可能なサブ領域の数が任意の時点で小さくなる可能性がある場合、これが機能する方法です。矩形とサブ領域のペアを処理するとO（1）の上限があるため、手で波打つO（nm）となるm個のサブ領域があると想定すると、これは恐らく、最悪の場合（多くの不連続な四角形が円に完全に含まれていると言う）、O（n^2）よりもずっと悪いかもしれませんが、典型的な場合（大きな四角形、小さな円） tは非常に高くなり、それは「ほぼO（n）」になります。

実行可能領域はリンクリストにすることができます。ここでは、最後にサブ領域を追加して最初から削除するため、アクセスは一定の時間になる可能性があります。

サブ領域（存在する場合）は凸で重複しないため、実行可能領域が計算されると、その内部の点を得ることは簡単になります。