algorithm - 平面上の点を見つける方法

Question

r=1 の既知の円がいくつかあります (下の図では、4 つの円が C1 から C4 と呼ばれています)。円内ではなく (0,0) に最も近い点を見つけたい。これには多項式アルゴリズムがありますか?

Answer 1

これは完全にすぐに使用できる回答ではありませんが、従うべき下書きにすぎません (次回試したことをお知らせください)。

1. (0,0) が円で覆われていない場合、答えは (0,0) になります。

2. (0,0) が 1 つ以上の円で覆われている場合:

   (1) これらの円上の最も近い点 (円の中心を (0,0) に接続して延長することで計算できます) で、どの円にも覆われていないものを候補にする必要があります。

   (2) どの円にも覆われていないこれらの円のすべての交点が候補となる必要があります。

   (3) (0,0) が 1 つ以上の円の中心である場合、これらの円が他の円によって完全に覆われているかどうかを確認します。そうでない場合は、他の円によってカバーされていないこれらの円上の点のいずれかを候補に追加します。

3. 候補の中から最小のものを見つけます。

Answer 2

原点に最も近いポイントは、次のいずれかになります。

• 2 つの円の交点

• 円と、この円の中心と原点を結ぶ直線との交点

• どの円の内側にもない場合は原点そのもの

• この円の中心が原点にある場合、円上の無限の点

それらの点をすべてチェックし、この点が円の内側にないという条件で、それらの中で最も近い点を見つけます。

複雑さO（n ^ 3）が得られます。

Answer 3

円内の各点について、点 (0,0) からの長さを見つけてから、円内にない近傍の最小値を見つけることができます。

Answer 4

目的の点は、原点を中心とし、いくつかの入力円 Cn 内に最大に内接するすべての円の和集合の境界上にあります。

アルゴリズム：

O_i を中心とする半径 r_i の各入力円 C_i (O_i は原点から d_i、Oi_1^2 + Oi_2^2 = d_i^2) で、内接半径 u_i = r_i - d_i を計算し、それらの最大値を見つけます。原点から u_max 離れた点が解です

実際のポイントを見つけるには、いくつかの i について u_i = u_max とします。次に、必要なポイントは - O_i * u_i / d_i です。d_i = 0 の場合、原点から r_i 離れた任意の点が機能します。