drawing - 辺の長さを知っている任意の凸形状を描く

Question

値のリストがあります。これは、任意の凸形状 (ポリゴン) の辺の長さです。この形を描くにはどうしたらよいでしょうか？このタスクに役立つアルゴリズムは何ですか?

たとえば、2、5、2、3 というリストがあります。図面は次のようになります。

ここに画像の説明を入力

score 2 · Accepted Answer

これには、比較的単純な (多少数学が重い場合)O(N log N) to O(N^2) (depending on implementation)再帰的な幾何学/三角法ベースのソリューションがあります。

ステップ 2 では、三角形の小さい 2 つのエッジが大きいエッジよりも長いことを確認する必要があります。

ステップ3は、三角形を2つの三角形に変えることで実行できます。

入力と出力には、次を使用します: 入力: エッジのリスト出力: 内角のリスト。

頂点output[a]の内角ものエッジの前後のいずれかinput[a]です。

適切なリファレンスはここにあります。

方法 #1 gif は、その多くの頂点の三角形を示しています。
方法 #2 gif、P は、手順 2 でブレークが発生する可能性がある場所の例です。
方法 #4 gif、ここで P は #3 のように移動したと見なすことができます。この場合、線の長さは縮尺どおりではなく、実際には不明であることに注意してください。a1との頂点の位置だけa2が変わることに注意してください。a1との前後で頂点の内角が変化しa2ます。この場合、a1,a2,a3,an,p.

内角の決定について。三角法および/またはジオメトリを使用します。三角形の 3 辺が与えられた場合、角度を決定することができます。2 つの側面と 1 つの角度 (または 1 つの角度と 2 つの側面) があれば、欠落している側面と角度を特定できます。

もちろん、三角形を形成できるようにエッジをどこで壊すかについて注意する必要があるかもしれません.

score 1 · Accepted Answer

エッジのチェーンは、最長のエッジが他のすべてのエッジの長さの合計よりも長くない場合に閉じることができます。

あなたの例では、最長のエッジは 5 で、2+2+3=7 より長くはありません。長さ 5 のエッジを長さ 8 のエッジで置き換えると、4 つのセグメントは凸多角形に近づくことができません。3 つ以上のエッジがある場合は常に、結果の凸多角形は一意に決定されません。その形状には柔軟性があります。

証明へのポインタについては、上記の参考文献を参照してください。

2 に答える 2