最小外接矩形

一、最小外接矩形法

最小外接矩形法是指找到一個矩形能夠完全包裹住所有給定點，且這個矩形的面積最小。這個矩形就是最小外接矩形。

解決最小外接矩形的問題可以用旋轉卡殼演算法，步驟如下：

1. 找到凸包。
2. 找到凸包上相鄰兩點。
3. 以這兩點為直徑的圓，可以覆蓋所有的點。
4. 讓圓旋轉，在過凸包上的點的時候，記錄圓的面積和長軸長度的最小值。
5. 繼續旋轉，直到回到起始位置，得到最小外接矩形的面積和長軸長度。

二、最小外接矩形 Matlab

在Matlab中實現最小外接矩形，可以用以下代碼實現：

% 一列表示一組數據，n * 2 的數組
% X(:, 1) 表示所有點的x坐標，X(:, 2) 表示所有點的y坐標
X = [...]; 
k = convhull(X); % 求凸包
k(end) = []; % 去掉最後一個點
Q_ = X(k, :); % 凸包上的點
Q = unique(Q_, 'rows'); % 去重
Q(end + 1, :) = Q(1, :); % 閉合凸包
index = 1;
min_area = inf;

for i = 1:size(Q, 1)-1
   for j = i+1:size(Q, 1)-1
      % i, j 是長軸的兩個端點
      % 計算矩形
      rect = [Q(i, 1:2); Q(j, 1:2); Q(j, 1), Q(i, 2); Q(i, 1), Q(j, 2)];
      % 計算矩形面積
      area = polyarea(rect(:, 1), rect(:, 2));
      if area < min_area
         min_area = area;
         index = [i, j];
      end
   end
end

% 顯示結果
rectangle = [Q(index(1), 1:2); Q(index(2), 1:2); Q(index(2), 1), Q(index(1), 2); Q(index(1), 1), Q(index(2), 2)];
plot(X(:,1), X(:,2), 'k.', Q(:,1), Q(:,2), 'r+', rectangle(:,1), rectangle(:,2), 'g', 'LineWidth', 2)
axis equal

三、最小外接矩形公式

最小外接矩形的長軸與短軸可以通過計算點集的協方差矩陣求解。設點集為 $S=\{(x_1,y_1), (x_2,y_2), …, (x_n,y_n)\}$，其中平均值為 $(\bar{x}, \bar{y})$，則：

% 計算點集的協方差矩陣
Sxx = sum((X(:,1) - mean(X(:,1))).^2);
Syy = sum((X(:,2) - mean(X(:,2))).^2);
Sxy = sum((X(:,1) - mean(X(:,1))).*(X(:,2) - mean(X(:,2))));  
COV = [Sxx, Sxy; Sxy, Syy] ./ (size(X,1)-1);

% 計算協方差矩陣的特徵值和特徵向量
[E, LAMBDA] = eig(COV);   

% 特徵向量方向即為矩形的長軸和短軸的方向，特徵值的根即為長軸和短軸的長度
rect_long = sqrt(max(LAMBDA(:)));  
rect_short = sqrt(min(LAMBDA(:)));  

四、四邊形的最小外接矩形怎麼求

對於任意四邊形，可以通過將其轉換為點集後求解最小外接矩形的方法來求解。

步驟如下：

1. 將四邊形轉化為點集。
2. 按照上面的演算法求解點集的最小外接矩形。
3. 將最小外接矩形轉化為四邊形。

五、最小外接矩形演算法

最小外接矩形演算法有兩種，分別是旋轉卡殼演算法和協方差矩陣演算法。旋轉卡殼演算法適用於點集和凸包，而協方差矩陣演算法適用於任意二維形狀。

六、最小外接矩形C++直接法

在C++中實現最小外接矩形可以用以下代碼實現：

// 輸入點集 nn 和每個點的坐標對應的下標 id，返回最小外接矩形面積
double MinRectangle(int nn, Point* p, int* id) {
    int l = 1, r = 2, p1, p2, p3;
    double area = 1e20, w, h, dx, dy, ta;

    // 以所有點的最小矩形為初值
    // 求出最上面的和最下面的點
    for (int i = 1; i <= nn; i++) {
        if (p[i].x = p[r].x) r = i;
    }

    // 初始化矩形長軸
    dx = p[r].x - p[l].x; dy = p[r].y - p[l].y;

    // 開始旋轉，每次旋轉一條邊，記錄面積最小值
    p1 = l, p2 = r;
    for (int i = 1; i <= nn; i++) {
        if ((ta = Cross(p[p2]-p[p1], p[id[i]]-p[p1])) < 0) continue;

        while ((ta = Cross(p[p2]-p[p1], p[id[i]]-p[p1]))  nn ? 1 : (p2+1)];
        }

        // 重新計算長軸並記錄最小值
        if (ta != 0) {
            w = fabs(dy * (p[id[i]].x-p[p1].x) / ta);
            h = fabs(dx * (p[id[i]].y-p[p1].y) / ta);
        } else {
            w = Distance(p[p1], p[id[i]]);
            h = 0;
        }

        if (w * h < area) {
            area = w * h;
        }
    }
    return area;
}

七、最小外接矩形英文

最小外接矩形的英文是Minimum bounding rectangle。

八、ArcGis最小外接矩形

ArcGis是一個常用的地理信息系統軟體，它提供了對最小外接矩形的支持。使用ArcGis，可以將最小外接矩形作為工具使用。

九、最小外接矩形實驗報告

在實驗中，我們可以使用點集來驗證最小外接矩形演算法的正確性。首先，我們可以隨機生成若干個二維點，然後利用演算法計算出最小外接矩形，並將其顯示在圖像上。然後我們可以手動調整幾個點的位置，觀察最小外接矩形是否隨之變化，以此來驗證演算法的正確性。

十、最小外接矩形是什麼

最小外接矩形是指一個矩形能夠完全包裹住所有給定點，且這個矩形的面積最小。它在計算幾何、圖形處理等領域有著廣泛的應用。