2

（白い）長方形とそのスペースを占める（黒い）長方形のセットによって制限される2Dスペースを考えると、空の（白い）スペースに何らかのインデックスを付ける方法を探しています。その目的のために、空間内の任意のポイント（「黒い」長方形に属さないポイント）に対して、結果として得られる白い長方形のセットに最大の空の長方形が存在するように、（白い）長方形のセットを作成したいと思います。

ありがとう

4

2 に答える 2

1

グリッド (つまり画像) または連続した 2D 空間にいますか? 私の答えは、各点が整数座標を持つ場合です。それ以外の場合は、私の答えで近似値を得ることができます。

あなたの質問を正しく理解できれば、次の 2 つのことが必要です。

  1. すべての最大の空の四角形 (つまり、黒点を含めずにどの方向にも拡張できない、白点のみが配置された四角形) のリスト (「最大の空の四角形」、または文献では MER とも呼ばれます)。
  2. 各ポイントについて、そのポイントを含む最大の空の四角形を示す四角形ポインターの 2D 配列。他のデータ構造も可能ですが、選択は主にターゲット アプリケーションの要件に依存するため、それらについては説明しません。

リストを計算するために、アルゴリズム O(N) を使用できます。ここで、N は白黒画像のピクセルの量です。http://www.ulg.ac.be/telecom/rectanglesで、そのようなアルゴリズムを説明している論文と、いくつかの (最適化されていない) C++ ソース コードを見つけることができます。実際には、非常に高速です。

ピンターの 2D 配列を計算するには、すべての最大の空の四角形のリストをトラバースし、それぞれについて、含まれるすべてのピクセルのポインターを (必要に応じて) 更新する必要があります。最大で N 個の空の長方形があり (prof については、http://www.ulg.ac.be/telecom/rectanglesにリンクされている論文を参照)、各長方形には最大で N 個のピクセルが含まれているため、このステップは最悪の場合です。ケース O(N^2)。このステップのコストを削減できるかどうかはわかりません。

于 2013-07-09T14:06:42.497 に答える