8

凸多角形が与えられた場合、その直径を維持しながら (「最大面積」のように) その形状を拡大しようとしています。直径は、ポリゴン内に配置できる最長のセグメントの長さとして定義されます。多角形は凸面なので、すべての頂点のペアをスキャンすることで、この直径を常に見つけることができると思います。

たとえば、正三角形を入力ポリゴンとして指定すると、三角形の直径はエッジの長さになります。これを平滑化すると、画像に示すように 3 つの円セグメントが生成されます前後の平滑化

任意の凸多角形の場合、各多角形の頂点を中心とする最大直径の半径の円の交点を計算するアルゴリズムは非常に非効率的です。これは私が現在使用しているものです（Javaで）。もっと良いものはありますか？アルゴリズムへの疑似コードまたはポインタは高く評価されます。

別の例: 押しつぶされた五角形とそれに対応する直径を維持する最大形状。直径を大きくしないと、この形状の面積を大きくすることはできません (つまり、元の直径よりも長い形状の境界内に直線を引くことができます)。この特定のケースでは、radius = polygon_diameter/2 (ピンク) の単一の円は、radius = polygon_diameter (水色) の複数の大きな円の交点よりも優れているようです。2 番目のイメージは、比較を容易にするために両方の領域を重ね合わせていますが、領域はポリゴンを完全に囲む必要があります。

ここに画像の説明を入力

4

3 に答える 3

3

交差点の計算は見た目よりも単純です。実際に行う必要があるのは、2つの隣接する頂点から等距離にある点を決定することだけです。最終的には2つのポイントになりますが、形状の中心に最も近い方がほぼ確実に正しいポイントになります。凸多角形でも保証されるかもしれませんが、数学的な証明は私の強みではありません。

于 2010-09-14T08:38:02.753 に答える
2

あなたの現在のアルゴリズムは非効率的であるだけでなく、間違っているようにも思えます。現在、直径が 10 を少し超えている長方形(0,0)-(10,0)-(10,1)-(0,1)を考えてみましょう。その半径の円を隅々まで交差させると、直径が 16 をはるかに超える非常に大きなレンズ型のものになります。動作しません。

新しい頂点の 1 つを囲む直径サイズの円でシェイプを再度交差させることで、余分な直径を修正できますが、使用する頂点の選択は任意です。どちらを選択しても、結果として得られる「肥大化した三角形」の形状は、長方形の外接円よりも小さく見えます。私の場合、その外接円が最適なソリューションになると思いますが、その一般性を維持しながら、そのソリューションを見つけるような方法でアルゴリズムを変更する簡単な方法がわかりません。

これは単なる直感ですが、入力ポリゴンと要件によって、目的の出力が一意に定義されるとは思えません。この効果の例はまだありませんが、複数の「滑らかな」形状が存在する入力ポリゴンが存在する可能性があり、それらはすべて同じ面積と同じ直径を持ちますが、それでも互いに合同ではありません。この実存的な問題についてさらに議論するために、これを数学スタック交換に持ち込む価値があるかもしれません。

于 2012-07-16T11:14:44.830 に答える
1

この質問はMath Overflowで既に出題されており、難しい問題である可能性が高いと結論付けられました。このような形はユニークなのか、といった基本的な疑問まで答えられていません。

したがって、正確な解決策はありませんが、うまくいけば、これがあなたに近づくか、少なくともいくつかのアイデアを与えるでしょう.

バックグラウンド

簡単にするために、一般性を失うことなく、最初のポリゴンの直径が 1 であると仮定できます。

ディスク ポリゴンに対するブラシュケ-ルベーグの定理の一般化について(M. Bezdek、2009 年) は、多くの有用な概念を説明しています。関連するものは次のとおりです。

  • ディスクポリゴンは、非公式に、エッジが曲率1の円弧に置き換えられた「太い」ポリゴンを形成する凸セットです。
  • 結果として得られる形状の直径が最大で 1 になるように、点の集合Dに追加できる点の集合は、 D の二重円盤多角形D *と呼ばれます。
  • 双対D**の双対はDの紡錘凸包と呼ばれます: これはDを含む最小の円盤多角形です。

多角形で作業​​する代わりに、ディスク ポリゴンで作業するだけで十分です。結果を変更することなく、元の多角形をそのスピンドル凸包でいつでも置き換えることができます。

Dの直径が 1 の場合、D ⊆ D*となり、D の幅が 1である場合に限り、D = D *となります。解Sは幅 1 で一定になります (これはもちろん十分ではありません)。したがって、 D ⊆ S ⊆ D*の場合にのみD ⊆ Sとなります。特に、Sを近似するには、 Sの十分に大きな円盤多角形サブセットDを見つけるだけで済みます。ある点がSに属している、または属していないことを示すので、これは非常に強力です。は、 Sの上限と下限の両方に変換されます (したがって、その領域)。

理論上の問題

理想的には、効率的なアルゴリズムを見つけるには、次の質問に答えることが役立ちます。

  • グローバルに最適な形状、つまり解は、必然的に一意ですか?
  • 局所的に最適な形状は必ず一意ですか?
  • 多角形の等直径​​包は、必ず直径 1 の円ですか、それとも幅 1 のルーロー多角形ですか?
  • もしそうなら、ルーロー多角形の頂点は、元の多角形の頂点から始まる有限個の単位半径の円の交点から派生したものですか?
  • 元の多角形の頂点の数の関数として、ルーロー多角形の頂点の数に制限はありますか?

ディスク ポリゴンの領域に関する質問は難しい場合があります。ディスクを押し離す - 平面におけるクネーザー-ポールセン予想(K. Bezdek、R. Connelly、2001) で解決された問題は、ディスクの交差領域に関する単純な質問でした。長い間未解決のままだった平面で。

実用的な（？）アプローチ

グローバル検索:多角形のスピンドル凸包から開始し、各ノードがD ⊆ X ⊆ D*を満たすすべての固定幅X
のセットを分割するディスク ポリゴンが増加する無限検索ツリーを遅延構築します。D* \ DのxがXに属しているかどうか。左の枝はD ∪ { x } の紡錘凸包です。右の分岐は、すべてのD* ∩ { y : x ∉ [ y , z ]z in D }。

xの選択が非常に不十分でない限り(たとえば、 D* \ Dの境界で)、そのツリーのすべての無限パスは一定幅の曲線に収束するはずです。

アイデアは、ある程度幅優先の方法でツリーを探索することです。xが賢明な方法で選択された場合、これまでに見つかったDの最大面積よりもD*の面積が小さいすべての枝を破棄できることを願っています。そのような枝は解を含むことができないためです。次に、ツリーを深く進むにつれて、問題の解決策のセットに収束するディスク ポリゴンのセットが得られます。

xのヒューリスティックには次のようなものがあります: D* \ Dの内側にできるだけ近い点を取る、ランダムな点を取る、など。ある程度の深さ優先検索を組み込んで、ツリーの枝全体をより早く破棄できる解の領域の下限をより正確にすることも興味深いかもしれません。

ローカル検索:
一定幅のディスク ポリゴン (ルーロー ポリゴン) のみを使用して、わずかな偏差の影響を調べることもできます。しかし、検索スペースはかなり大きいため、その方法は明確ではありません。

于 2012-07-20T04:57:04.473 に答える