与えられたすべての点を囲む最小半径の円を見つけるにはどうすればよいですか?

Question

飛行機上に約 1000 個の奇妙な点があると仮定します。

次に、私ができると思うのは、円の半径にまったく影響を与えない点を破棄することです。 通過するポイント 凸包 通らない [いずれかの使用 いくつかのアルゴリズム]。これにより、重要な点が残ります。

さて、ここからはその最小半径円を求めるにはどうすればよいでしょうか？

円に対してどのようにできるかを理解したら、これを楕円に対して一般化しようとしています。

「公開ソースコード」へのリンクは、省略記号を変更できるようにするのに役立ちます。

Answer 1

1 つのオプションは、 CGAL 計算幾何アルゴリズム ライブラリ. 。これはオープンソースですが、規模も大きいため、おそらく最大の問題は、干し草の山から針を見つけることだと思います。

もちろん (これは Martin への謝罪の意味もありますが)、Google を使用すると、より焦点を絞ったオプションを簡単に見つけることができます。Prolog を気にしなければ、リストされている 2 番目の項目は試してみたところ問題ないようで、結果の最初のページには少なくとも 1 つの C サンプルと 1 つの Javascript がありました。そして、もはや Google にその単語を知らないと主張することはほとんどできません。

Answer 2

これは最小囲み円問題として知られており (Google 検索でなぜ何も表示されなかったのか不思議です)、議論されました。 ここ, ここ, ここ, 、その他多くの場所で。