22

凸多角形と数 N が与えられた場合、最小の多角形を見つけるにはどうすればよいですか?

  1. 元のポリゴンのすべてのポイントが含まれます
  2. 正確に N 個のコーナー ポイントを持つ

たとえば、一連の点があり、それらの凸包 (緑) を計算するとします。今、すべての点 (赤) を含む最小の四角形を見つけたい

最小の四角形 ここに画像の説明を入力

4 つの角を持つ他の多角形は、より大きくなるか、すべての点を含むことができないことが容易にわかります。しかし、一般的なケースでこのポリゴンを見つけるにはどうすればよいでしょうか?

編集：

最小のポリゴンとは、最小の領域をカバーするポリゴンを意味しますが、最小の円周が異なる結果をもたらすかどうかはわかりません.

残念ながら、回答の1つで「エッジの削除」アプローチでは機能しないように見える2つのサンプル写真を追加しました

背景情報:

目標は、画像認識で形状を正確に決定することです。たとえば、立方体の写真を撮ります。2D 写真のボックス内のすべての点は、6 角の凸多角形に含まれます。ただし、現実世界の形状には完全な角がなく、カメラによって多少のぼかしが加えられるため、このポリゴンのエッジは丸くなります。質問から添付の画像を参照してください凸点から角を取得します

ぼやけた角

4

2 に答える 2

17

質問で「最小」の概念を定義する必要があります。あなたの定義がどうであれ、この問題は計算幾何学の文献でよく研究されてきました。キーとなる検索フレーズは、k-gon を囲む最小限のものです。

  • Micchell et al.: "Minimum-Perimeter Enclosing k-gon" 2006 ( CiteSeer リンク)
  • Aggarwal et al.: "Minimum Area Circumscribing Polygons" 1985 ( CiteSeer リンク)
  • O'Rourke et al.: "最小の内包三角形を見つけるための最適なアルゴリズム" 1986 年、アルゴリズム( ACM リンク)

一般的なアルゴリズムは単純ではありません (最小面積の三角形または長方形のアルゴリズムは単純ですが)。目標によっては、「最小」という数学的概念を放棄し、ヒューリスティックに向かう必要がある場合があります。

于 2012-07-22T18:20:25.333 に答える
0 
While number of edges > N do
  remove the shortest edge by replacing its endpoints 
  with the intersection point of the adjacent edges
于 2012-07-22T17:31:30.303 に答える