点を囲む矩形を合わせる

Question

を最小化するために、を試しながら、8個の2D点の周りに矩形を合わせようとしています。

例：

矩形がスケーリング及び回転させてもよいです。しかし、それは四角形を維持する必要があります。

私が最初に取り組んだのは、可能な限り回転を強制し、できるだけ近くに矩形をフィットさせ、覆われた領域を計算することでした。最良の適合は、最も低い面積を有する回転である。

しかし、これは実際には最良の解決策のようには聞こえません。

これを実行する方法はありますか？

Answer 1

そこにそれらの多くは無限にありますが、この基本的な考え方は、実際には非常に効率的なソリューションを生み出すように私は、あなたが「あらゆる可能な回転をしてみてください」によって何を意味するのか分からない：

最初のステップは、計算することです凸包。これが実際にどのくらい保存されるかは、データの分布によって異なりますが、for points picked uniformly from a unit disk, the number of points on the hull is expected to be O(n^1/3)です。 number of ways to do thatがあります

• ポイントがすでにそれらの座標の一つでソートされている場合は、グラハムスキャンアルゴリズムはOで（n）のことを行います。指定された順番のすべてのポイントについて、それを船体の前の2つのポイントに接続し、新しい船体のすべての凹点（唯一の候補は新しいポイントに隣接するもの）を削除します。
• ポイントがソートされていない場合、ギフトラッピングアルゴリズムはO（n * h）で実行される単純なアルゴリズムです。入力の左端から始まる船体の各点について、それが船体の次の点であるかどうかを確認するために、すべての点をチェックします。 hは、船体のポイント数です。
• Chen's algorithm私はO（n log h）のパフォーマンスを約束していますが、それがどのように機能するかについてはまだ詳しく調べていません。
• _{別のsimleのアイデアは、方位角で点をソートして、凹状の点を取り除くことです。しかし、これは最初はO（n + sort）のようにしか見えませんが、実際はそうではありません。この時点で}

、これまでに収集したすべての角度をチェックする（私とオリバーCharlesworthの両方でconjencturedとして、およびのためのエフゲニー・Kluev offered a gist of a proof）で十分です。最後に、Lior Kogan's answerの関連資料を参照してください。

各方向について、境界ボックスは、その間隔内のすべての角度に対して同じ4つの（必ずしも別個ではない）点によって定義される。候補者の指示には、少なくとも1つの任意の選択肢があります。これらの点を見つけることは、軸合わせバウンディングボックスの極値がマージを開始するのと同じ極限であり、連続する区間の極点が同一または連続していることがわかるまで、O（h^2） 。極端な点A,B,C,Dを時計回りに呼び出し、境界ボックスを区切る対応する線をa,b,c,dとしましょう。

だから、数学をしましょう。境界ボックス領域は、|a,c| * |b,d|によって与えられる。しかし、|a,c|は、ベクトル(AC)だけが長方形の方向に投影されます。 uをaおよびcと平行なベクトルとし、vを垂直ベクトルとする。範囲全体でスムーズに変化させましょう。ベクトルの意味では、領域は((AC).v)/|v| * ((BD).u)/|u| = {((AC).v) ((BD).u)}/{|u| |v|}になります。また、u = (1,y)を選択してみましょう。その後、v = (y, -1)。 uが垂直の場合、これは限界と無限大を含むわずかな問題があるので、その場合はuを水平にすることを選択しましょう。数値的な安定性のために、が(1,-1)..(1,1)の外にあるときに90度回転させてみましょう。必要に応じて、領域をデカルト形式に翻訳することは、読者のための練習として残されています。

Answer 2

点の集合の最小面積の矩形がコレクションの凸包ポリゴンのエッジの一つと同一直線上に ["Determining the Minimum-Area Encasing Rectangle for an Arbitrary Closed Curve" [フリーマン、1975 Shapira]

アンO（nlogn）溶液このためであることが示されていますこの問題は、入力が凸包である場合（constructing a convex hullの複雑さはに等しい[アリソン、ノガ、1981]

シンプルでエレガントなO（n）の溶液を"A Linear time algorithm for the minimum area rectangle enclosing a convex polygon"に発表された"On the computation of minimum encasing rectangles and set diameters"の[アーノン、Gieselmann 1983】公開されました入力ポイントのソートの複雑さ）。この解決策は、Shamos, 1978に記載されているRotating calipersメソッドに基づいています。オンラインデモンストレーションはhereです。

Answer 3

この問題を見たときに最初に気になったのは、主成分分析を使用することでした。最小矩形は、エッジが主軸と平行であり、少なくとも4つの点がエッジ（境界点）にあるという2つの条件を満たすものであると推測します。 n次元の拡張が必要です。