0

我有一个重叠矩形的列表。我需要找到一个列表列表，其中返回所有重叠的矩形。例如，在一个包含 7 个矩形的列表中，如果 4 个矩形重叠并且其余部分是分开的，那么列表的列表应该如下所示：

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

我知道我必须执行命中测试。我正在寻找创建链的算法或示例。

谢谢

我已经尝试过这段代码：有时它可以工作，有时它会抛出 index out of bound 有点异常。

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

Written quicly from scratch before you posted your own code. You have a rectangleList, and want to group them by overlap groups.

You use this groupRectangles function

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 回答
0

Rectangle.IntersectsWith这是使用和 Linq 的延迟执行的另一种方法：

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));

也许不是最易读的方式，而是最短的方式之一:)

编辑：这是一个演示（没有 System.Drawing 和 Rectangles 的单声道很难）：

http://ideone.com/eOCMN

于 2012-09-04T09:51:51.600 回答
0

对于每个矩形，必须检查所有较早的矩形组。例如，如果 A 和 C 重叠，B 和 C 重叠，但 A 和 B 不重叠。如果算法接收到 A、B、C，它将首先将 A 放入一个列表中，然后将 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 回答