使用 linq 查找所有相交矩形对

Question

我有一个矩形列表（xpos、ypos、宽度、高度）：

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

此方法可以判断两个矩形是否相交： Rectangle.IntersectsWith()

我想使用 linq 从列表中获取所有相交矩形对...这可能吗？

Answer 1

是的！

var intersecting = rects
    .SelectMany((x, i) => rects.Skip(i + 1), Tuple.Create)
    .Where(x => x.Item1.IntersectsWith(x.Item2))
    .ToList();

请注意，这是一个 O(n^2) 操作，没有某种形式的加速（例如，为每个 x 和 y 维度保留 Rectangles 的列表，排序，以便您可以在每个维度上执行一次 O(n) 遍）。

就我个人而言，为了清楚起见，我只是坚持使用典型的嵌套循环：

var intersecting = new List<Tuple<Rectangle, Rectangle>>();
for (int i = 0; i != rects.Count; ++i) {
    for (int j = i + 1; j != rects.Count; ++j) {
        if (rects[i].IntersectsWith(rects[j]))
            intersecting.Add(Tuple.Create(rects[i], rects[j]));
    }
}

Answer 2

Cameron 的答案适用于少量矩形。如果您运行遇到较大数字的性能问题，您可以添加一些 space 分区策略以减少要检查的交集候选者的数量，使用 k-d tree or quadtree.

使用 linq 查找所有相交矩形对

Find all pairs of intersecting rectangles with linq

c#

linq

rectangles