3

回転していない、整数 (ピクセル) で整列された m 個の四角形のセットがあり、それぞれが重なる場合と重ならない場合があります。四角形は数千のピクセルをカバーしています。m個の長方形のうちn個でカバーされるすべての領域をカバーする最小サイズのバウンディングボックスを見つける必要があります。

これを行う (汚い) 方法は、すべてのターゲットの領域をカバーするキャンバスをペイントすることです。これは O(mk) で、m は四角形の数、k は四角形あたりのピクセル数です。ただし、k は m よりもはるかに大きいため、より良い解決策があると思います。

これは動的プログラミングの問題のように感じます...しかし、再帰を理解するのに苦労しています。

より良いが、まだ良くない解決策：

すべての長方形の始点と終点を X 方向 O(mlogm) に並べ替え、反復して、n 個以上の長方形を持つ可能性のある x 位置を見つけ、O(m) ループします。n を超える四角形を持つ可能性のある x 位置ごとに、その位置で四角形を取得し、その位置で開始点と終了点を並べ替えます (O(mlogm))。オーバーラップの領域を見つけ、そのように境界を追跡します。全体として、O(m^2logm) です。

4

4 に答える 4

0

これはあなたの質問を定義していますか？境界ボックスの場合=>#rect_label >= n 境界ボックス

于 2014-04-25T06:16:30.140 に答える
0

次のアルゴリズムを提案します。

prepareData();
if (findBorder('left')) {
     foreach (direction in ['top', 'right', 'bottom']) {
         findBorder(direction)
    }
} else noIntersectionExists

prepareData (O(mlogm)): 垂直
方向の境界と水平方向の境界を並べ替え
ます。 結果を次のように 保存します。など

findBorder(left): // 他の方向も同様です 最良の場合 O(n)、最悪の場合 O(2m-n)

arrIntersections = new Array;
//an intersection has a depth (number of rectangles intersected), a top and bottom border and list of rectangles
for(i=0; i < 2*m-n-1; i++){ // or (i = 2*m-1; i > n; i--)
    if(isLeftBorder(arrX[i])){
        addToIntersections(arrX[i].rectangle, direction);
        if(max(intersections.depth) = n) break;
    } else {
        removeFromIntersections(arrX[i].rectangle, direction);
    }
}

addToIntersections(rectangle, direction): // direction=left の説明
最良のケース: O(n)、最悪のケース: O(m)

hasIntersected = false;
foreach(intersection in intersection){
    if(intersect(intersection, rectangle)){
        hasIntersected = true
        intersections[] = {
            depth: intersection.depth,
            bottom: min(intersection.bottom, rectangle.bottom),
            top: max(...)}
        intersection.depth++
        intersection.bottom = max(intersection.bottom, rectangle.bottom)
        intersection.top = max(...)
    }
}
if(!hasIntersected)
    intersections[]={depth:1, bottom:rectangle.bottom, top:rectangle.top}

これにより、O(n^2) と O(m*(mn/2)) の間の全体的な順序が得られます。

私の疑似コードが十分に明確であることを願っています

于 2014-04-25T12:44:15.673 に答える