n個の点の座標を含む長方形の最小の面積を求めたい
DeepLで翻訳しながら読む
点の集合を含む最小面積の矩形
目次
1 はじめに 2
2 包括的探索アルゴリズム 2
3 回転カリパスアルゴリズム 3
3.1 初期矩形の計算 ... ... ... ... ... ... ... ... 5
3.2 矩形の更新 ... ... ... ... ... ... ... ... 7
3.2.1 特徴のあるサポート頂点 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 7
3.2.2 重複するサポート頂点．. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 7
3.2.3 複数のポリゴンエッジが最小角度を達成 ... ... ... ... .... .... 8
3.2.4 一般的な更新ステップ ............................................................................ 10
4 ロバストな実装 11
4.1 正規化の回避 ....................................................................................... 11
4.2 角度の間接的な比較 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 12
4.3 サポート情報の更新 ... ... ... ... ... ... ... 12
4.4 浮動小数点長方形への変換 ............................................................................ 13
1.
有限の2次元点集合が与えられたとき、その点を含む最小面積の矩形を計算したい。
この矩形は軸に沿ったものである必要はなく，一般的には軸に沿ったものでもない
制約
点の最小面積の矩形は、点の凸包によってサポートされることは直感的である。この外皮は凸多角形である。この凸包は凸多角形であり、凸多角形の内部の点は矩形に影響を与えない。
最小面積の境界矩形の辺は、多角形の辺と一致しなければならない
凸多角形が0≦i＜nで反時計回りに並んだ頂点Viを持つとする。
ここまでで思いつく単純なアルゴリズム
凸多角形の辺を繰り返し処理することである。各辺に対して、そのポリゴンの辺と一致する辺を持つ最小の外接長方形を計算する。すべての n 個の矩形から面積が最小となるものを選ぶ。
code:cpp
structRectangle
{
Vector2 < Real > center, axis2; };
RectangleMinAreaRectangleOfHull(Vector2 < Real >const& polygon)
{
RectangleminRect;
minRect.area = maxReal;
for (sizeti0 = polygon.size() = 1, i1 = 0; i1 < polygon.size(); i0 = i1++) {
Vector2 < Real > origin=polygoni0; Vector2 < Real > U0=polygoni1 = origin; Normalize(U0);
Vector2 < Real > U1 == Perp(U0);
Realmin0 = 0, max0 = 0;
Realmax1 = 0;
for (sizetj = 0; j < polygon.size(); ++j) {
Vector2 < Real > D=polygonj = origin; Realdot = Dot(U0, D);
if (dot < min0) min0 = dot; elseif(dot > max0)max0 = dot;
dot = Dot(U1, D);
if (dot > max1) max1 = dot;
}
Realarea = (max0 = min0) * max1;
if (area < minRect.area) {
minRect.center = origin + ((min0 + max0) / 2) * U0 + (max1 / 2) * U1;
minRect.extent0 = (max0 = min0) / 2; minRect.extent1 = max1 / 2; minRect.area = area;
}
}
returnminRect;
}
RectangleMinAreaRectangleOfPoints(std:: vector < Vector2 < Real >>const& points)
{
std:: vector < Vector2 < Real >> polygon;
ComputeConvexHull(points, polygon);
returnMinAreaRectangleOfHull(polygon);
}
ただし計算量は$ O(n^2)
https://gyazo.com/bc47a48798e783b22d20a8d18f5195d5
普通にpythonのコードがあった、こっちの方が読みやすい