11

新しい長方形が既存の長方形のセットによって完全に覆われているかどうかを判断するアルゴリズムを探しています。別の言い方をすれば、既存の長方形で覆われた領域に新しい長方形が完全に存在するかということです。

長方形の重なりなどを判断するアルゴリズムはたくさんあるようですが、この正確な問題を解決するものは実際には見つかりません。

長方形は、x、y 座標を使用して表されます。この問題は、地理的マッピングに関連しています。

編集- OP が投稿したコメントから:

長方形は X/Y 軸上に配置されます

4

7 に答える 7

8

長方形が整列している場合、それは簡単です:

長方形 A0 があり、それが (B1, B2, B3...) = B で完全に覆われているかどうかを知りたいとしましょう。

A := (A0)
while P := pop B
  for R in A
    if P fully covers R:
      remove R from A
    else if P and R does overlap:
      remove R from A
      break R in subrentangles S := (S1, S2, S3,...) following the intersections \
                                                     with P edges
      push S into A
if A is empty:
   say B covers A0
else:
   say B does not fully cover A0
于 2010-12-09T10:55:53.713 に答える
3

長方形がすべて同じ角度を持っている場合。次に、次のようにすると、より効率的でプログラミングが簡単になります。

すべての y 座標について、その y 座標をカバーする長方形を決定します (カバーが変化する y 座標に対してのみこれを行う必要があります。つまり、長方形の上限または下限に対応します)。それがわかったら、そのような y 座標ごとに問題を解決します (つまり、すべての x 値が、その Y 座標で「アクティブな」長方形に含まれているかどうかを確認します)。

編集:これは O(n^2 log(n)^2) の複雑さだと思います.2つのソートはすべてあなたがしなければならない大変な作業です.

于 2010-12-09T10:45:33.420 に答える
2

あなたが要求したように、これが私のコードです：

最初の方法は、2つの長方形の「減算」（カバーされていない部分を返す）です。

2番目の方法では、ベースの長方形から長方形のリストを減算します。

あなたの場合、リストには既存の長方形が含まれており、新しい長方形はベースです

完全交叉があるかどうかを確認するには、2番目のメソッドから返されるリストに要素が含まれていてはなりません。

public static List<Rectangle> SubtractRectangles(Rectangle baseRect, Rectangle splitterRect)
    {
        List<Rectangle> newRectaglesList = new List<Rectangle>();

        Rectangle intersection = Rectangle.Intersect(baseRect, splitterRect);
        if (!intersection.IsEmpty)
        {
            Rectangle topRect = new Rectangle(baseRect.Left, baseRect.Top, baseRect.Width, (intersection.Top - baseRect.Top));
            Rectangle bottomRect = new Rectangle(baseRect.Left, intersection.Bottom, baseRect.Width, (baseRect.Bottom - intersection.Bottom));

            if ((topRect != intersection) && (topRect.Height != 0))
            {
                newRectaglesList.Add(topRect);
            }

            if ((bottomRect != intersection) && (bottomRect.Height != 0))
            {
                newRectaglesList.Add(bottomRect);
            }
        }
        else
        {
            newRectaglesList.Add(baseRect);
        }

        return newRectaglesList;
    }

    public static List<Rectangle> SubtractRectangles(Rectangle baseRect, List<Rectangle> splitterRectList)
    {
        List<Rectangle> fragmentsList = new List<Rectangle>();
        fragmentsList.Add(baseRect);

        foreach (Rectangle splitter in splitterRectList)
        {
            List<Rectangle> toAddList = new List<Rectangle>();

            foreach (Rectangle fragment in fragmentsList)
            {
                List<Rectangle> newFragmentsList = SubtractRectangles(fragment, splitter);
                toAddList.AddRange(newFragmentsList);
            }

            if (toAddList.Count != 0)
            {
                fragmentsList.Clear();
                fragmentsList.AddRange(toAddList);
            }
        }

        return fragmentsList;
    }
于 2010-12-09T12:03:43.710 に答える
2

私は過去に似たようなことをしました。アイデアは、新しい長方形を既存の長方形のそれぞれと（1つずつ）比較することでした

交差がある場合はそれ（交差した部分）を破棄し、カバーされていないセグメントを長方形配列に追加します

次に、新しいセグメントと他の既存の（まだチェックされていない）長方形の間の交差を検索します。

交差点を再帰的に破棄し、カバーされていない部分のみを残すアルゴリズムを実行します。

結局、配列に長方形がない場合は、完全にオーバーラップしています

配列にまだいくつかの長方形が残っている場合は、まだいくつかの部分が残っているため、オーバーラップは完全ではありません。

お役に立てれば

これがあなたが探しているものであるならば、私は私のコードを見つけることを試みることができます。C＃だと思います

もう1つのアイデアは、既存のすべての長方形をポリゴンに変換してから、新しい長方形がポリゴン内にあるかどうかを確認することですが、ポリゴンの操作方法を知っている言語（またはフレームワーク）を使用していない場合は、これはお勧めしません。

于 2010-12-09T10:39:22.487 に答える
2

R ツリーが役立つ場合があります。回転した四角形が存在する可能性がある場合は、それらを境界四角形で囲むことができます。

于 2010-12-09T11:03:46.193 に答える
1

これを試して

ソース長方形 : X0、Y0、幅、高さ

// 基本的にエッジを比較します

if(((X0 >= xi) && (X0+幅 <= Xi)) && ((Y0 >= Yi)&&(Y0+高さ <= Yi)) { //長方形を考慮する } else { //破棄 }

于 2010-12-09T11:16:41.603 に答える