【C++】与えられた点をすべて含む最小の長方形の座標を求める方法

このチュートリアルでは、与えられた複数の座標点をすべて内部に含む長方形の座標を求めるプログラムについて解説します。

問題の概要

いくつかの座標点が与えられます。私たちのタスクは、次の条件を満たす最小の長方形を見つけることです。

• すべての点が長方形の内部(または境界上)に含まれる
• 長方形の辺は座標軸(X軸・Y軸)に平行である

このような長方形は「バウンディングボックス」とも呼ばれ、各点のX座標・Y座標の最小値と最大値から簡単に求めることができます。

解決のアプローチ

軸に平行な最小の長方形は、以下の4つの値だけで決まります。

• Xmin: すべての点のX座標の最小値
• Xmax: すべての点のX座標の最大値
• Ymin: すべての点のY座標の最小値
• Ymax: すべての点のY座標の最大値

これらを使うと、長方形の4つの頂点は次のように表せます。

• 左下: (Xmin, Ymin)
• 左上: (Xmin, Ymax)
• 右上: (Xmax, Ymax)
• 右下: (Xmax, Ymin)

C++での実装例

#include <bits/stdc++.h>
using namespace std;

// 最小の長方形の座標を計算する関数
void print_rectangle(int X[], int Y[], int n){
    // 各座標の最小値と最大値を求める
    int Xmax = *max_element(X, X + n);
    int Xmin = *min_element(X, X + n);
    int Ymax = *max_element(Y, Y + n);
    int Ymin = *min_element(Y, Y + n);

    // 長方形の4つの頂点を出力
    cout << "{" << Xmin << ", " << Ymin << "}" << endl;
    cout << "{" << Xmin << ", " << Ymax << "}" << endl;
    cout << "{" << Xmax << ", " << Ymax << "}" << endl;
    cout << "{" << Xmax << ", " << Ymin << "}" << endl;
}

int main(){
    int X[] = { 4, 3, 6, 1, -1, 12 };
    int Y[] = { 4, 1, 10, 3, 7, -1 };
    int n = sizeof(X) / sizeof(X[0]);
    print_rectangle(X, Y, n);
    return 0;
}

実行結果

{-1, -1}
{-1, 10}
{12, 10}
{12, -1}

コードの解説

このプログラムでは、標準ライブラリの max_element と min_element を使って、配列内のX座標・Y座標それぞれの最大値と最小値を効率的に取得しています。

入力データの場合、X座標の範囲は -1〜12、Y座標の範囲は -1〜10 となるため、出力される4つの頂点が最小の長方形を構成します。

計算量は点の数を n とすると O(n) であり、非常に効率的なアルゴリズムです。座標変換や衝突判定、データの可視化など、さまざまな場面で応用できる基本的なテクニックなので、ぜひ覚えておきましょう。