1

2つの同心円の間にあるポリゴンの最小辺数を見つけるアルゴリズムを設計するにはどうすればよいですか？

これに似ています：

サークル

4

3 に答える 3

3

最初に最も単純なケースについて考えてください。内側の円は微視的に小さいです。内側の円の半径がゼロでない限り、辺の最小数は3です。

ポリゴンが4辺を必要とし始めるのはいつですか？円に内接する正三角形を描きます。内側の円の半径が三角形の辺の中心点に達すると、ポリゴンは4つの辺を必要とし始めます。

N辺の正多角形を外側の円に内接する場合、余弦定理を使用して、各辺の中点から円の中心までの距離を計算できます。

distance_to_midpoint = cos ( 360 / (N * 2) ) * radius_of_outer_circle

（説明：問題の側の円の中心点を使用して等辺三角形を作成する場合、半径は360 / Nの角度になります。三角形を側の中点で半分に分割して、ハイポテヌスの直角三角形を形成します。外側の円の半径に等しい場合は、コサインルールを使用します）

ここdistance_to_midpointで、内側の円の半径以上である必要があるため、次のように解きNます。

radius_of_inner_circle = cos(360 / (N * 2)) * radius_of_outer_circle
cos(360 / (N*2)) = radius_of_inner_circle / radius_of_outer_circle
360 / (N*2) = acos(radius_i / radius_o)
N = 180 / (acos(radius_i / radius_o))

（私はこの数学を再確認していません、そしてそれは本当に遅いです）。

于 2012-11-12T06:44:43.567 に答える
1

多角形の外接円の半径である多角形の半径を。で表しRます。内接円の半径は

r = R*Cos[180°/n]

これを解きn、否定的な結果をもたらす偽の解を排除すると、次のようになります。

n = 180°/ArcCos[r/R]

の整数値を取得するには、少しいじる必要がありnます。それはあなたに任せます。

于 2012-11-12T06:46:34.647 に答える
0
  1. 内側の円に接線を描き、A、Bをマークします-接線と外側の円の交点。
  2. 点Bから内側の円に接線（異なる）を描き、外側の円Cとの交点をマークします。
  3. 新しい接線が最初の接線ABと交差するまで、手順（2）を繰り返します。

このアルゴリズムにより、各ステップで最大の放射状セクションを確実にカバーできるため、結果のポリゴンの辺の数を最小限に抑えることができます。

辺の数だけを知りたい場合は、外側の円の同じ点から来る内側の円の2つの接線の間の角度を見つけて、360度全体を構成するそのような角度の数を計算するだけで十分です（残り）-コメントで提案された@cheekenのように

于 2012-11-12T06:33:40.757 に答える