14

私はいくつかの解決策を見つけましたが、それらはあまりにも厄介です。

4

4 に答える 4

8

はい。セットCのチェビシェフ中心x*は、Cの内側にある最大のボールの中心です。[Boyd、p。416] Cが凸集合の場合、この問題は凸最適化問題です。

さらに良いことに、Cが多面体の場合、この問題は線形計画法になります。

m側の多面体Cが一次不等式のセットによって定義されていると仮定します：ai ^ T x <= bi、for i in {1、2、...、m}。次に問題は

maximize  R
such that ai^T x + R||a|| <= bi,  i in {1, 2, ..., m}
          R >= 0

ここで、最小化の変数はとでRありx、||a||はのユークリッドノルムですa。

于 2010-10-31T03:32:18.607 に答える
6

要約：それは些細なことではありません。したがって、乱雑にならない可能性はほとんどありません。しかし、あなたが役に立つと思うかもしれないいくつかの講義スライドがあります。

ソース： http ：//www.eggheadcafe.com/software/aspnet/30304481/finding-the-maximum-inscribed-circle-in-c.aspx

あなたの問題は些細なことではなく、箱から出してすぐにこれを行うC＃コードはありません。あなたはあなた自身を書かなければならないでしょう。私はこの問題に興味をそそられ、いくつかの調査を行ったので、ここに役立つかもしれないいくつかの手がかりがあります。

まず、mathforum.orgの「平易な英語」での回答は次のとおりです。

http://mathforum.org/library/drmath/view/67030.html

答えは、プロセスをより効率的にするための方法論としてボロノイ図を参照しています。ボロノイ図を研究しているときに、「最大の空の円」問題（同じ問題、別の名前）に関連して、私はこの有益な論文に出くわしました。

http://www.cosy.sbg.ac.at/~held/teaching/compgeo/slides/vd_slides.pdf

これは、オーストリアのザルツベルク大学の計算幾何学教授であるMartinHeldによって書かれました。ヘルド博士の著作をさらに調査すると、いくつかの優れた記事が得られました。

http://www.cosy.sbg.ac.at/~held/projects/vroni/vroni.html http://www.cosy.sbg.ac.at/~held/projects/triang/triang.html

Vornoiダイアグラムをさらに調査すると、次のサイトが得られました。

http://www.voronoi.com/

このサイトには、多くの情報、さまざまな言語のコード、および他のリソースへのリンクがあります。

最後に、米国国立標準技術研究所（US）の数学および計算科学部門へのURL、あらゆる種類の数学に関する豊富な情報とリンクを次に示します。

http://math.nist.gov/mcsd/

--HTH、

Kevin Spencer Microsoft MVP

于 2010-10-17T14:40:29.307 に答える
6

おそらく、これらの「あまりにも厄介な」ソリューションはあなたが実際に探しているものであり、より単純なものはありませんか？

数値解析を使用する、単純ですが、潜在的に不正確な解決策を提案できます。弾力性のあるボールがあり、半径0から始めて膨らませるとします。その中心があなたが探している中心にない場合、それは移動します。なぜなら、壁はそれが他のどこにも移動できないポイントに到達するまで、適切な方向にそれを「押す」からです。凸多角形の場合、ボールは最終的に最大半径のポイントに移動すると思います。

サークルインフレのプロセスをエミュレートするプログラムを作成できます。任意の点から始めて、壁に達するまで円を「膨らませ」ます。膨らませ続けると、すでに遭遇している壁に近づかない方向の1つに移動します。あなたはそれが現在いる中心を通って壁に平行な線を引くことによってそれが動くことができる可能な方法を決定することができます。

この例では、ボールは緑色でマークされた方向の1つに移動します。


（ソース：coldattic.info）

次に、ボールをこれらの方向の1つに少し動かし（角度の二等分線に沿って動かすのが良い選択かもしれません）、この手順を繰り返します。新しい半径が現在の半径よりも小さい場合は、後退して移動するペースを遅くします。ペースをたとえば1インチ未満にする必要がある場合は、1インチの精度で中心を見つけます（画面に描画する場合は、0.5ピクセルの精度）。十分だと思います）。

不正確な解決策で十分であれば、これは十分に単純だと思います。

于 2010-10-17T14:53:13.900 に答える
2

最大の内接円（私はそれがユニークだと思います）は、接線方向にいくつかの面と交差し、他の面と交差しない可能性があります。最大の内接円が交差する場合は顔を「関連性がある」と呼び、そうでない場合は「関連性がない」と呼びましょう。

凸多角形が実際に三角形である場合、角度の二等分線を交差させることにより、三角形の内心を計算することで問題を解決できます。これは些細なことのように思えるかもしれませんが、凸多角形が複雑な場合でも、内接円は常に少なくとも3つの面に接しているため（証明？は幾何学的に明白に見えます）、その中心は3つの関連する面の中心として計算できます。 （元のポリゴンに外接する三角形を作成するために外側に拡張されます）。ここでは、そのような2つの面が平行ではないと仮定します。2つが平行である場合、2つの平行線の「二等分線」を、それらの間の3番目の平行線を意味すると解釈する必要があります。

これはすぐにかなりひどいアルゴリズムを示唆します。面のすべてのn-choose-3サブセットを検討し、上記のようにすべての三角形の内心を見つけ、元のポリゴンに含まれているかどうか各円をテストします。合法的なものの中で最大化します。しかし、これはnの立方であり、はるかにうまくいくことができます。

ただし、代わりに、前もって無関係な面を特定することもできます。面が内接円に接している場合、その面とその端点に2つの二等分線で囲まれた点の領域があり、円の中心が存在する必要があります。その三角形の領域の最も遠い先端に中心がある円でさえ「合法」（ポリゴンに完全に含まれている）である場合、面自体は無関係であり、削除できます。それに触れる2つの面は、それらが出会うようにそれを超えて延長する必要があります。

この意味で無関係な面を繰り返し削除することで、ポリゴンを三角形またはおそらく台形に縮小できるはずです。その時点で問題は簡単に解決され、その解決策は元のポリゴン内に残ります。

于 2010-10-18T15:53:51.083 に答える