2D軸上にN個の接続線のセットがあれば、Xの最小境界矩形を決定するアルゴリズムを探しています。一連の線の境界線の矩形を見つけるにはどうすればよいですか？
例えば、私は10行が与えられているとしますが、私は最大3つの（潜在的に交差する）長方形でそれらを束縛したいとします。したがって、ラインのうち8つが密接にクラスタリングされている場合は、1つの矩形を使用し、他の2つは、互いに近接しているので、第2の矩形またはおそらくは第3の矩形を使用することがあります。
ありがとうございました。
実際に行がパスである場合、各矩形がパスの連続部分をカバーするという要件を嫌うことはないでしょう。この場合、時間O（n r）で実行される動的プログラムがあります.nはセグメント数、rは長方形の数です。
エントリC（i、j）がセグメント1、...、iをj個の長方形でカバーするコストを表すテーブルを計算する。再発は、iについて、であり、J> 0、
C（0、0）= 0
C（iは0）=∞
i「はC（i、j）は=分かけ< I
O（nr）個のエントリがあり、それぞれが時間内に計算されます（O（n-1）、O（n-1）に）。最後に、例えば、各エントリについて最良のi 'を記憶することによって、矩形の最適な集合を復元する。
一般的なケースでは、単純で最適なアルゴリズムはわかりません。 「唯一の」O（n ）の矩形があり、その辺のそれぞれにセグメントの端点が含まれているので、この問題を一般化集合カバーのインスタンスとして定式化したいと思うでしょう。
申し訳ありませんが、私は最小限に抑えたいものを得られませんでした：長方形の数？長方形の集約領域？他に何か？ – Miquel
集約領域。混乱させて申し訳ありません。 – glutz
余分な情報をありがとう。しかし、私はそれを考えていますが、より多くの制限が必要な場合や、各点の周りに極小の矩形を作成するだけでよい場合は、 – Miquel