0

重なり合う長方形のリストがあります。重複するすべての長方形が返されるリストのリストを見つける必要があります。たとえば、7 つの長方形のリストで、4 つの長方形が重なり、残りが分離している場合、リストのリストは次のようになります。

[0]: r1, r2, r3, r4
[1]: r5
[2]: r6
[3]: r7

ヒットテストを実行する必要があることはわかっています。チェーンを作成するアルゴリズムまたは例を探しています。

ありがとう

私はこのコードを試しました:時々それは動作しますが、時々、インデックスがバインドされていない例外をスローします。

while (rects.Count != 0)
            {
                listOfRects.Add(joinRectangles(rects, new List<Rectangle>(), rects[rects.Count - 1]));
            }

        private List<Rectangle> joinRectangles(List<Rectangle> rects, List<Rectangle> tempRects, Rectangle curRect)
        {
            for (int j = rects.Count; j-- > 0; )
            {
                if (hitTest(curRect, rects[j]) == true)
                {
                    if (tempRects.Contains(rects[j]) == false)
                    {
                        tempRects.Add(rects[j]);
                        curRect = rects[j];
                        rects.Remove(rects[j]);

                        j--;

                        joinRectangles(rects, tempRects, curRect);
                    }
                }


            }


            return tempRects;
        }

これらの座標を指定すると、次のような 4 つのリストのリストを取得する必要があります。

    [0]: 1 rectangle
    [1]: 3 rectangles
    [2]: 1 rectangle
    [3]: 1 rectangle


<?xml version="1.0" encoding="utf-16"?>
<rectangles>
  <rectangle>
    <X1>50.833333344375</X1>
    <Y1>100</Y1>
    <X2>53.833333344375</X2>
    <Y2>127.00000004975</Y2>
  </rectangle>
  <rectangle>
    <X1>136.500000033125</X1>
    <Y1>100</Y1>
    <X2>139.516666655625</X2>
    <Y2>127.00000004975</Y2>
  </rectangle>
  <rectangle>
    <X1>50.833333344375</X1>
    <Y1>130.647222172472</Y1>
    <X2>53.833333344375</X2>
    <Y2>157.647222222222</Y2>
  </rectangle>
  <rectangle>
    <X1>136.500000033125</X1>
    <Y1>130.647222172472</Y1>
    <X2>139.516666655625</X2>
    <Y2>157.647222222222</Y2>
  </rectangle>
  <rectangle>
    <X1>136.500000033125</X1>
    <Y1>100</Y1>
    <X2>139.516666655625</X2>
    <Y2>157.3333333830833</Y2>
  </rectangle>
  <rectangle>
    <X1>179.3333333775</X1>
    <Y1>100</Y1>
    <X2>182.3333333775</X2>
    <Y2>157.3333333830833</Y2>
  </rectangle>
</rectangles>
4

3 に答える 3

0

Rectangle.IntersectsWithLinq の遅延実行を使用した別のアプローチを次に示します。

var intersectingRectangles = new List<List<Rectangle>>();
var alreadyChecked = new HashSet<Rectangle>();
var toCheck = rectangles.Except(alreadyChecked);
while (alreadyChecked.Count != rectangles.Count)
{
    var intersections = toCheck.Where(r => r.IntersectsWith(toCheck.ElementAt(0)))
                               .ToList();
    intersectingRectangles.Add(intersections);
    foreach (var r in intersections)
        alreadyChecked.Add(r);
}
intersectingRectangles.Sort((rl1, rl2) => (-1) * rl1.Count.CompareTo(rl2.Count));

おそらく最も読みやすい方法ではありませんが、最短の方法の1つです:)

編集：これがデモです（System.DrawingとRectanglesのないモノでは難しい）：

http://ideone.com/eOCMN

于 2012-09-04T09:51:51.600 に答える
0

各長方形について、以前のすべての長方形のグループをチェックする必要があります。たとえば、A と C が重複していて、B と C が重複していて、A と B が重複していない場合などです。アルゴリズムが A、B、C を受け取ると、最初に A を 1 つのリストに入れ、次に B を別のリストに入れます。しかし、C が来ると、A を含むリストと B を含むリストの両方を、C を含む新しいリストにマージする必要があります (これは、他の回答が見逃しているようです)。

public static List<List<Rectangle>> SortOverlap(Rectangle[] rectangles)
{
    var result = new List<List<Rectangle>>();
    for (int i = 0; i < rectangles.Length; i++) 
    {
        var newList = new List<Rectangle>();
        newList.Add(rectangles[i]);
        for (int j = 0; j < result.Count; j++) 
        {
            if(result[j].Any(r => r.Overlap(newList[0])))
            {
                newList.AddRange(result[j]);
                result[j] = null;
            }
        }
        result.Add(newList);
        result.RemoveAll(list => list == null);
    }
    return result;
}

編集：オーバーラップチェックは実装がかなり簡単なので、そのチェックだけに System.Drawing などを使用する必要はありません...

public class Rectangle {
    ....
    public bool Overlap(Rectangle other)
    {
        return !(this.MinX >= other.MaxX || this.MaxX <= other.MinX ||
                 this.MinY >= other.MaxY || this.MaxY <= other.MinY);
    }
}
于 2012-09-04T18:44:10.227 に答える
0

独自のコードを投稿する前に、最初からすばやく作成します。あなたはrectangleListを持っていて、それらをオーバーラップグループでグループ化したいと考えています。

この groupRectangles 関数を使用します

public List<List<Rectangle>> groupRectangles(List<Rectangle> rectangleList) {

List<List<Rectangle>> groupOverlappedRectangles = new List<List<Rectangle>>();

foreach (Rectangle r : rectangleList) {
    bool overLap = false;
    foreach (List<Rectangle> liste : groupOverlappedRectangles) {
        if (overlapsRectangleList(r,liste))
        {
                liste.add(r);
            overLap = true;
            break;
        }
    }
    if (!overLap) {
        List<Rectangle> newOverlapList = new List<Rectangle>();
        newOverlapList.add(r);
        groupOverlappedRectangles.add(newOverlapList);
    }
}
return groupOverlappedRectangles;
}

public bool overlapsRectangleList(Rectangle r, List<Rectangle> listeOver)
{
    foreach (Rectangle rOver : listeOver) {
        if (r.IntersectsWith(rOver)) {
            return true;
    }
    }
    return false;
}
于 2012-09-04T09:42:08.140 に答える