c# - 从列表中删除相似的矩形

Question

我有一个包含几千个矩形的列表。我试图通过删除位置在其他项目 x 像素范围内的项目来减小列表的大小。

到目前为止，我最好的尝试是:

list = list.GroupBy(x => x.Location).Select(x => x.First()).ToList();

但这只会删除完全匹配项。我很想删除所有合理相似的内容。想法？

谢谢!

Answer 1

尝试(尽我所能)遵循@EricLippert 的明智建议，并首先考虑数据结构。

WLOG，假设Location包含 Windows.System.Point .我们创建了几个方便的扩展来帮助我们以后:

public static class PointExt {
    public static double Distance(this Point p1, Point p2) => (p1-p2).Length;
    public static Point PointZero = new Point(0, 0);
}

现在我们可以定义我们的 Rectangle类型(针对此问题进行了简化):

public class Rectangle {
    public string Site;
    public Point Loc;

    public Rectangle() { }

    public Rectangle(string site, Point loc) {
        Site = site;
        Loc = loc;
    }
}

注:Site只是为了帮助测试。

现在我们要创建的是 Rectangle 组都是彼此接近的。我选择将 close 定义为距离该组(的 Location s)中心 5 个单位以内的含义，该组是通过对当前组的成员求平均值得到的。

所以我们可以创建一个RectangleGroup帮助我们定义这个类的类:

public class RectangleGroup : IEnumerable<Rectangle> {
    List<Rectangle> members;
    Point center;

    public RectangleGroup() {
        members = new List<Rectangle>();
    }

    public RectangleGroup Add(Rectangle r) {
        members.Add(r);
        center = new Point(members.Average(m => m.Loc.X), members.Average(m => m.Loc.Y));
        return this;
    }

    public bool BelongsToGroup(Rectangle r) => center.Distance(r.Loc) <= 5;

    public Rectangle Middle() => members.OrderBy(m => m.Loc.Distance(center)).First();

    public IEnumerator<Rectangle> GetEnumerator() => members.GetEnumerator();
    IEnumerator IEnumerable.GetEnumerator() => GetEnumerator();
}

我实现了 IEnumerable在组上，以便可以将 LINQ 与 RectangleGroup 一起使用.

在 RectangleGroup 中使用我们的工具, 我们可以创建一个 RectangleGroups管理 RectangleGroup 集合的类类似于 Lookup .这让我想到了 GroupBy 的(非常)通用版本可以创建将组成员身份委托(delegate)给一个类型的方法，这可能很有用，并且不需要此类。

public class RectangleGroups : IEnumerable<RectangleGroup> {
    List<RectangleGroup> groups;
    public RectangleGroups() {
        init();
    }

    public RectangleGroups(IEnumerable<Rectangle> rs) {
        init();

        foreach (var r in rs.OrderBy(r => r.Loc.Distance(PointExt.PointZero)))
            Add(r);
    }

    private void init() {
        groups = new List<RectangleGroup>();
    }

    public void Add(Rectangle r) {
        var found = false;
        foreach (var g in groups) {
            found = g.BelongsToGroup(r);
            if (found) {
                g.Add(r);
                break;
            }
        }
        if (!found)
            groups.Add(new LocationGroup().Add(r));
    }

    public IEnumerator<LocationGroup> GetEnumerator() => groups.GetEnumerator();
    IEnumerator IEnumerable.GetEnumerator() => GetEnumerator();
}

有了这些可用的类，减少了 List<Rectangle>到每个 Rectangle最接近每个组的中心是微不足道的:

var ans = new RectangleGroups(list).Select(lg => lg.Middle());