51

私の状況

  • 入力: 長方形のセット
  • 各 rect は、次のように 4 つの double で構成されます: (x0,y0,x1,y1)
  • それらはどの角度でも「回転」していません。すべて、画面に対して「上下」および「左右」に移動する「通常の」長方形です。
  • それらはランダムに配置されています - それらは端で接触している、重なり合っている、または接触していない可能性があります
  • 数百の長方形があります
  • これはC#で実装されています

私は見つける必要があります

  • それらのオーバーラップによって形成される領域 - 複数の長方形が「カバー」するキャンバス内のすべての領域 (たとえば、2 つの長方形の場合、それは交点になります)
  • オーバーラップのジオメトリは必要ありません。面積だけです (例: 4 平方インチ)
  • オーバーラップは複数回カウントされるべきではありません。たとえば、同じサイズと位置を持つ 3 つの四角形が重なり合っているとします。この領域は (3 回ではなく) 1 回カウントする必要があります。

例

  • 下の画像には、A、B、C の 3 つの長方形が含まれています。
  • A と B が重なっている (破線で示されている)
  • B と C の重なり (破線で示す)
  • 私が探しているのは、ダッシュが表示されている領域です

-

AAAAAAAAAAAAAAAAAAAAAAAAAAAAAA
AAAAAAAAAAAAAAAAAAAAAAAAAAAAAA
AAAAAAAAAAAAAAAAAAAAAAAAAAAAAA
AAAAAAAAAAAAAAAAAAAAAAAAAAAAAA
AAAAAAAAAAAAAAAAAAAAAAAAAAAAAA
AAAAAAAAAAAAAAAAAAAAAAAAAAAAAA
AAAAAAAAAAAAAAAAAAAAAAAAAAAAAA
AAAAAAAAAAAAAAAAAAAAAAAAAAAAAA
AAAAAAAAAAAAAAAA--------------BBB
AAAAAAAAAAAAAAAA--------------BBB
AAAAAAAAAAAAAAAA--------------BBB
AAAAAAAAAAAAAAAA--------------BBB
                BBBBBBBBBBBBBBBBB
                BBBBBBBBBBBBBBBBB
                BBBBBBBBBBBBBBBBB
                BBBBBB-----------CCCCCCCC
                BBBBBB-----------CCCCCCCC
                BBBBBB-----------CCCCCCCC
                      CCCCCCCCCCCCCCCCCCC
                      CCCCCCCCCCCCCCCCCCC
                      CCCCCCCCCCCCCCCCCCC
                      CCCCCCCCCCCCCCCCCCC
4

16 に答える 16

62

この領域を計算する効率的な方法は、スイープ アルゴリズムを使用することです。長方形 U の結合を通る垂直線 L(x) をスイープすると仮定します。

  • まず最初に、イベント キュー Q を作成する必要があります。これは、この場合、四角形のすべての x 座標 (左と右) の順序付きリストです。
  • スイープ中は、L(x) と U の交点の全長を示す 1D データ構造を維持する必要があります。重要なことは、この長さが Q の 2 つの連続するイベント q と q' の間で一定であることです。 、もし l(q) が U と交差する L(q+) (つまり、q のすぐ右側にある L) の全長を表す場合、イベント q と q' の間で L によって掃引される領域は、正確に l(q)*(q' -q)。
  • これらすべてのスイープ領域を合計して合計を取得する必要があります。

1 次元の問題を解決する必要があります。(垂直) セグメントの結合を動的に計算する 1D 構造が必要です。動的とは、新しいセグメントを追加したり、削除したりすることを意味します。

この崩壊する範囲の質問に対する回答で、静的な方法でそれを行う方法について詳しく説明しました（実際には1Dスイープです）。したがって、単純なものが必要な場合は、それを直接適用できます (各イベントの和集合を再計算することにより)。より効率的なものが必要な場合は、少し調整する必要があります。

  • セグメント S 1 ...S nの和集合が互いに素なセグメント D 1 ...D kで構成されていることがわかっていると仮定します。S n+1の追加は非常に簡単です。S n+1の両端を D 1 ...D kの両端に配置するだけです。
  • セグメント S 1 ...S nの和集合がばらばらのセグメント D 1 ...D kで構成されていることがわかっていると仮定すると、セグメント S iを削除することは (S iが D jに含まれていると仮定して)、セグメントの和集合を再計算することを意味します。jは、S iを除く(静的アルゴリズムを使用) で構成されていました。

これが動的アルゴリズムです。D 1 ...D kを表すためにログ時間ロケーション クエリでソートされたセットを使用すると仮定すると、これはおそらく最も効率的な、特殊化されていない方法です。

于 2008-10-28T23:20:01.027 に答える
14

解決策の 1 つは、キャンバスにプロットすることです。半透明の色を使用して各長方形を描画します。.NET ランタイムは、最適化されたネイティブ コードで、またはハードウェア アクセラレータを使用して描画を行います。

次に、ピクセルを読み戻す必要があります。各ピクセルは背景色ですか、長方形の色ですか、それとも別の色ですか? 別の色になる唯一の方法は、2 つ以上の長方形が重なった場合です...

これがチートすぎる場合は、別の回答者が行ったように quad-tree 、またはr-treeをお勧めします。

于 2008-10-28T19:49:17.287 に答える
11

最も簡単な解決策

import numpy as np

A = np.zeros((100, 100))
B = np.zeros((100, 100))

A[rect1.top : rect1.bottom,  rect1.left : rect1.right] = 1
B[rect2.top : rect2.bottom,  rect2.left : rect2.right] = 1

area_of_union     = np.sum((A + B) > 0)
area_of_intersect = np.sum((A + B) > 1)

この例では、キャンバスのサイズである 2 つのゼロ マトリックスを作成します。四角形ごとに、これらのマトリックスの 1 つを、四角形がスペースを占有するマトリックスで埋めます。次に、行列を合計します。今sum(A+B > 0)は結合sum(A+B > 1)の領域であり、重複の領域です。この例は、複数の長方形に簡単に一般化できます。

于 2014-08-18T01:44:07.153 に答える
10

これは、TopCoder SRM 160 Div 2 で使用した簡単で汚いコードです。

t = 上
b = 下
l = 左
r = 右

public class Rect
{
    public int t, b, l, r;

    public Rect(int _l, int _b, int _r, int _t)
    {
        t = _t;
        b = _b;
        l = _l;
        r = _r;
    }   

    public bool Intersects(Rect R)
    {
        return !(l > R.r || R.l > r || R.b > t || b > R.t);
    }

    public Rect Intersection(Rect R)
    {
        if(!this.Intersects(R))
            return new Rect(0,0,0,0);
        int [] horiz = {l, r, R.l, R.r};
        Array.Sort(horiz);
        int [] vert = {b, t, R.b, R.t};
        Array.Sort(vert);

        return new Rect(horiz[1], vert[1], horiz[2], vert[2]);
    } 

    public int Area()
    {
        return (t - b)*(r-l);
    }

    public override string ToString()
    {
        return l + " " + b + " " + r + " " + t;
    }
}
于 2008-10-28T20:14:48.920 に答える
6

これは私の頭の上からそれがうまくいくように聞こえるものです：

  1. 次のように、2 つのキーと四角形 + ブール値のリストを使用して辞書を作成します。

    Dictionary< Double、List< KeyValuePair< Rectangle、Boolean>>> 四角形;

  2. セット内の各四角形について、x0 と x1 の値に対応するリストを見つけ、そのリストに四角形を追加します。x0 の場合は true、x1 の場合は false のブール値を指定します。このようにして、各長方形が x 方向に入る (true) または出る (false) すべての x 座標の完全なリストが得られます。

  3. そのディクショナリからすべてのキー (すべての個別の x 座標) を取得し、並べ替えて、順番にループし、現在の x 値と次の x 値の両方を取得できることを確認します (両方が必要です)。 ）。これにより、長方形の個々のストリップが得られます

  4. 現在見ている四角形のセットを維持します。これは最初は空です。ポイント3で繰り返し処理するx値ごとに、長方形が真の値で登録されている場合はセットに追加し、そうでない場合は削除します。
  5. ストリップの場合、長方形を y 座標で並べ替えます
  6. 重なり合う距離を数えながら、ストリップ内の長方形をループします（これを効率的に行う方法はまだわかりません）
  7. ストリップの幅と重なり合う距離の高さの積を計算して、面積を取得します

例、5 つの長方形、a から e までを重ねて描画:

aaaaaaaaaaaaaaaa          bbbbbbbbbbbbbbbbb
aaaaaaaaaaaaaaaa          bbbbbbbbbbbbbbbbb
aaaaaaaaaaaaaaaa          bbbbbbbbbbbbbbbbb
aaaaaaaaaaaaaaaa          bbbbbbbbbbbbbbbbb
aaaaaaaadddddddddddddddddddddddddddddbbbbbb
aaaaaaaadddddddddddddddddddddddddddddbbbbbb
        ddddddddddddddddddddddddddddd
        ddddddddddddddddddddddddddddd
        ddddddddddddddeeeeeeeeeeeeeeeeee
        ddddddddddddddeeeeeeeeeeeeeeeeee
        ddddddddddddddeeeeeeeeeeeeeeeeee
ccccccccddddddddddddddeeeeeeeeeeeeeeeeee
ccccccccddddddddddddddeeeeeeeeeeeeeeeeee
cccccccccccc          eeeeeeeeeeeeeeeeee
cccccccccccc          eeeeeeeeeeeeeeeeee
cccccccccccc
cccccccccccc

x座標のリストは次のとおりです。

v       v  v   v      v   v         v  v  v   
|aaaaaaa|aa|aaaa      |   bbbbbbbbbb|bb|bbb
|aaaaaaa|aa|aaaa      |   bbbbbbbbbb|bb|bbb
|aaaaaaa|aa|aaaa      |   bbbbbbbbbb|bb|bbb
|aaaaaaa|aa|aaaa      |   bbbbbbbbbb|bb|bbb
|aaaaaaaddd|dddddddddd|ddddddddddddddbb|bbb
|aaaaaaaddd|dddddddddd|ddddddddddddddbb|bbb
|       ddd|dddddddddd|dddddddddddddd  |
|       ddd|dddddddddd|dddddddddddddd  |
|       ddd|ddddddddddeeeeeeeeeeeeeeeeee
|       ddd|ddddddddddeeeeeeeeeeeeeeeeee
|       ddd|ddddddddddeeeeeeeeeeeeeeeeee
ccccccccddd|ddddddddddeeeeeeeeeeeeeeeeee
ccccccccddd|ddddddddddeeeeeeeeeeeeeeeeee
cccccccccccc          eeeeeeeeeeeeeeeeee
cccccccccccc          eeeeeeeeeeeeeeeeee
cccccccccccc
cccccccccccc

リストは次のようになります (各 v には、0 から始まる座標が単純に与えられます):

0: +a, +c
1: +d
2: -c
3: -a
4: +e
5: +b
6: -d
7: -e
8: -b

したがって、各ストリップは次のようになります (上から下に並べ替えられた四角形):

0-1: a, c
1-2: a, d, c
2-3: a, d
3-4: d
4-5: d, e
5-6: b, d, e
6-7: b, e
7-8: b

各ストリップのオーバーラップは次のようになります。

0-1: none
1-2: a/d, d/c
2-3: a/d
3-4: none
4-5: d/e
5-6: b/d, d/e
6-7: none
7-8: none

上下チェックのソート + エンター/リーブ アルゴリズムのバリエーションも同様に実行可能であると思います。

  1. ストリップで現在分析している長方形を上から下に並べ替えます。同じ上座標を持つ長方形については、下座標でも並べ替えます
  2. y座標を反復処理し、長方形に入るとセットに追加し、長方形を離れるとセットから削除します
  3. セットに複数の長方形がある場合は常に、重複があります（現在見ている同じ上/下座標を持つすべての長方形を確実に追加/削除する場合、複数の重なり合う長方形は問題になりません

上記の 1-2 ストリップの場合、次のように繰り返します。

0. empty set, zero sum
1. enter a, add a to set (1 rectangle in set)
2. enter d, add d to set (>1 rectangles in set = overlap, store this y-coordinate)
3. leave a, remove a from set (now back from >1 rectangles in set, add to sum: y - stored_y
4. enter c, add c to set (>1 rectangles in set = overlap, store this y-coordinate)
5. leave d, remove d from set (now back from >1 rectangles in set, add to sum: y - stored_y)
6. multiply sum with width of strip to get overlapping areas

ここでも実際のセットを実際に維持する必要はありません。内部にある長方形の数だけです。これが1から2になるたびにyを保存し、2から1になるたびに現在のyを計算します- y を格納し、この差を合計します。

これが理解できることを願っています。私が言ったように、これは私の頭の上から外れており、まったくテストされていません。

于 2008-10-28T22:14:59.990 に答える
3

エリアスイープアルゴリズム用に書いたコードは次のとおりです。

#include <iostream>
#include <vector>

using namespace std;


class Rectangle {
public:
    int x[2], y[2];

    Rectangle(int x1, int y1, int x2, int y2) {
        x[0] = x1;
        y[0] = y1;
        x[1] = x2;
        y[1] = y2; 
    };
    void print(void) {
        cout << "Rect: " << x[0] << " " << y[0] << " " << x[1] << " " << y[1] << " " <<endl;
    };
};

// return the iterator of rec in list
vector<Rectangle *>::iterator bin_search(vector<Rectangle *> &list, int begin, int end, Rectangle *rec) {
    cout << begin << " " <<end <<endl;
    int mid = (begin+end)/2;
    if (list[mid]->y[0] == rec->y[0]) {
        if (list[mid]->y[1] == rec->y[1])
            return list.begin() + mid;
        else if (list[mid]->y[1] < rec->y[1]) {
            if (mid == end)
                return list.begin() + mid+1;
            return bin_search(list,mid+1,mid,rec);
        }
        else {
            if (mid == begin)
                return list.begin()+mid;
            return bin_search(list,begin,mid-1,rec);
        }
    }
    else if (list[mid]->y[0] < rec->y[0]) {
        if (mid == end) {
            return list.begin() + mid+1;
        }
        return bin_search(list, mid+1, end, rec);
    }
    else {
        if (mid == begin) {
            return list.begin() + mid;
        }
        return bin_search(list, begin, mid-1, rec);
    }
}

// add rect to rects
void add_rec(Rectangle *rect, vector<Rectangle *> &rects) {
    if (rects.size() == 0) {
        rects.push_back(rect);
    }
    else {
        vector<Rectangle *>::iterator it = bin_search(rects, 0, rects.size()-1, rect);
        rects.insert(it, rect);
    }
}

// remove rec from rets
void remove_rec(Rectangle *rect, vector<Rectangle *> &rects) {
    vector<Rectangle *>::iterator it = bin_search(rects, 0, rects.size()-1, rect);
    rects.erase(it);
}

// calculate the total vertical length covered by rectangles in the active set
int vert_dist(vector<Rectangle *> as) {
    int n = as.size();

    int totallength = 0;
    int start, end;

    int i = 0;
    while (i < n) {
        start = as[i]->y[0];
        end = as[i]->y[1];
        while (i < n && as[i]->y[0] <= end) {
            if (as[i]->y[1] > end) {
                end = as[i]->y[1];
            }
            i++;
        }
        totallength += end-start;
    }
    return totallength;
}

bool mycomp1(Rectangle* a, Rectangle* b) {
    return (a->x[0] < b->x[0]);
}

bool mycomp2(Rectangle* a, Rectangle* b) {
    return (a->x[1] < b->x[1]);
}

int findarea(vector<Rectangle *> rects) {
    vector<Rectangle *> start = rects;
    vector<Rectangle *> end = rects;
    sort(start.begin(), start.end(), mycomp1);
    sort(end.begin(), end.end(), mycomp2);

    // active set
    vector<Rectangle *> as;

    int n = rects.size();

    int totalarea = 0;
    int current = start[0]->x[0];
    int next;
    int i = 0, j = 0;
    // big loop
    while (j < n) {
        cout << "loop---------------"<<endl;
        // add all recs that start at current
        while (i < n && start[i]->x[0] == current) {
            cout << "add" <<endl;
            // add start[i] to AS
            add_rec(start[i], as);
            cout << "after" <<endl;
            i++;
        }
        // remove all recs that end at current
        while (j < n && end[j]->x[1] == current) {
            cout << "remove" <<endl;
            // remove end[j] from AS
            remove_rec(end[j], as);
            cout << "after" <<endl;
            j++;
        }

        // find next event x
        if (i < n && j < n) {
            if (start[i]->x[0] <= end[j]->x[1]) {
                next = start[i]->x[0];
            }
            else {
                next = end[j]->x[1];
            }
        }
        else if (j < n) {
            next = end[j]->x[1];
        }

        // distance to next event
        int horiz = next - current;
        cout << "horiz: " << horiz <<endl;

        // figure out vertical dist
        int vert = vert_dist(as);
        cout << "vert: " << vert <<endl;

        totalarea += vert * horiz;

        current = next;
    }
    return totalarea;
}

int main() {
    vector<Rectangle *> rects;
    rects.push_back(new Rectangle(0,0,1,1));

    rects.push_back(new Rectangle(1,0,2,3));

    rects.push_back(new Rectangle(0,0,3,3));

    rects.push_back(new Rectangle(1,0,5,1));

    cout << findarea(rects) <<endl;
}
于 2010-04-13T04:44:52.520 に答える
3

例を使用します。

   1 2 3 4 5 6

1 +---+---+
   | | | |   
2 + A +---+---+
   | | | | ビ |
3 + + +---+---+
   | | | | | | | | | |
4 +---+---+---+---+ +
               | | | |
5 + C +
               | | | |
6 +---+---+

1) すべての x 座標 (左と右の両方) をリストに収集し、並べ替えて重複を削除します

1 3 4 5 6

2) すべての y 座標 (上と下の両方) をリストに収集し、並べ替えて重複を削除します。

1 2 3 4 6

3) 一意の x 座標間のギャップ数 * 一意の y 座標間のギャップ数で 2D 配列を作成します。

4*4

4) すべての長方形をこのグリッドにペイントし、発生する各セルのカウントを増やします。

   1 3 4 5 6

1 +---+
   | | 1 | 0 0 0
2 +---+---+---+
   | | 1 | 1 | 1 | 0
3 +---+---+---+---+
   | | 1 | 1 | 2 | 1 |
4 +---+---+---+---+
     0 0 | 1 | 1 |
6 +---+---+

5) カウントが 1 より大きいグリッド内のセルの面積の合計がオーバーラップの面積です。まばらなユースケースで効率を高めるために、セルを 1 から 2 に移動するたびに、長方形をペイントするときに、実際には現在の領域の合計を維持できます。

問題では、四角形は 4 つの double であると説明されています。通常、倍精度浮動小数点数には丸め誤差が含まれており、計算されたオーバーラップ領域に誤差が入り込む可能性があります。有効な座標が有限の点にある場合は、整数表現の使用を検討してください。

私の他の答えのようにハードウェアアクセラレータを使用するPSは、解像度が許容できる場合、それほどみすぼらしい考えではありません。また、上で概説したアプローチよりもはるかに少ないコードで簡単に実装できます。コース用の馬。

于 2008-11-18T09:41:51.817 に答える
2

各長方形を小さな長方形に分割すると、この問題をかなり単純化できます。すべての長方形の X 座標と Y 座標をすべて収集すると、これらが分割点になります。長方形が線と交差する場合は、2 つに分割します。完了すると、0% または 100% 重複する長方形のリストができます。それらを並べ替えると、同一のものを簡単に見つけることができます。

于 2008-10-28T22:15:33.920 に答える
0

このタイプの衝突検出は、AABB (Axis Aligned Bounding Boxes) と呼ばれることが多く、 Google 検索の出発点として適しています。

于 2008-10-28T22:09:39.313 に答える
0

スイープアルゴリズムとは異なる解決策を見つけました。

長方形はすべて長方形に配置されているため、長方形の水平線と垂直線は長方形の不規則なグリッドを形成します。このグリッドに長方形を「ペイント」できます。つまり、グリッドのどのフィールドに入力するかを決定できます。グリッド線は指定された長方形の境界から形成されるため、このグリッドのフィールドは常に完全に空であるか、完全に長方形で埋められます。

私はJavaで問題を解決しなければならなかったので、ここに私の解決策があります: http://pastebin.com/03mss8yf

この関数は、長方形が占める完全な面積を計算します。「重複」部分だけに関心がある場合は、70 行目と 72 行目の間でコード ブロックを拡張する必要があります。70 行目から 72 行目までのコードは、次のようなブロックに置き換える必要があります。

GridLocation gl = new GridLocation(curX, curY);
if(usedLocations.contains(gl) && usedLocations2.add(gl)) {
  ret += width*height;
} else {
  usedLocations.add(gl);
}

ここでの変数 usedLocations2 は、usedLocations と同じ型です。同じ場所に建設されます。

私は複雑さの計算にあまり詳しくありません。そのため、2 つのソリューション (スイープまたはグリッド ソリューション) のどちらがパフォーマンス/スケーリングに優れているかわかりません。

于 2013-12-27T12:37:42.077 に答える
0

長方形がまばらになる場合 (ほとんど交差しない場合) は、再帰的な次元クラスタリングを検討する価値があるかもしれません。それ以外の場合は、四分木が適しているようです (他のポスターで言及されているように.

これは、コンピューター ゲームの衝突検出における一般的な問題であるため、解決方法を提案するリソースが不足することはありません。

これは、 RCDを要約した素敵なブログ投稿です。

これは、適切なさまざまな衝突検出アルゴリズムをまとめた Dr.Dobbs の記事です。

于 2008-10-28T21:49:44.097 に答える
0

x軸とy軸でオーバーラップを見つけて、それらを掛けることができます。

int LineOverlap(int line1a, line1b, line2a, line2b) 
{
  // assume line1a <= line1b and line2a <= line2b
  if (line1a < line2a) 
  {
    if (line1b > line2b)
      return line2b-line2a;
    else if (line1b > line2a)
      return line1b-line2a;
    else 
      return 0;
  }
  else if (line2a < line1b)
    return line2b-line1a;
  else 
    return 0;
}


int RectangleOverlap(Rect rectA, rectB) 
{
  return LineOverlap(rectA.x1, rectA.x2, rectB.x1, rectB.x2) *
    LineOverlap(rectA.y1, rectA.y2, rectB.y1, rectB.y2);
}
于 2008-10-28T19:12:41.620 に答える