c++ - 2次元座標のリスト(ベクトル)から上下の境界を抽出する

Question

私のプログラムには、ポイント (自作の構造に格納された 2 次元の二重座標) を含むベクトルの形式を持つポリゴンが含まれています。ポリゴンを含む最小の正方形をすばやく見つける方法を探しています (つまり、すべてのポイントの最大座標と最小座標を知っています)。

すべてのポイントを解析して最小値と最大値を保存するよりも簡単な方法はありますか?

Answer 1

線形時間よりも値の配列で最小値と最大値を見つけるためのより高速な方法があるかどうかはわかりません。私が考えることができる唯一の「最適化」は、配列を反復している他の機会のいずれかでこれらの値を見つけて（すべてのポイントで入力/関数を実行して）、データの更新をチェックすることです。

Answer 2

説明しているアルゴリズムは簡単です。すべてのポイントを繰り返し処理し、各座標の最小値と最大値を見つけます。これは O(n) アルゴリズムで、n はポイントの数です。

少なくともすべてのポイントを 1 回チェックする必要があるため、これ以上のことはできません。そうしないと、最後のポイントが見つけた正方形の外にある可能性があります。

現在、複雑さはせいぜいO(n)であるため、定数係数を最小限に抑える必要がありますが、その場合はすでにかなり小さくなっています.2つの最大値と2つの最小値を探して、ベクトルを1回ループするだけです.

Answer 3

すべてのポイントを繰り返し処理して最大値と最小値を見つけるか、ポイントを treap に保存するなどの前処理を行うことができます ( http://en.wikipedia.org/wiki/Treap )。すべてのポイントを反復するだけでなく、前処理を行う方法はありません。