如何在图像中合并一组矩形的最佳方法？

Question

这不是一个作业问题 :)

我有一组散布在图像上的矩形。我想将每个相交矩形组合并（创建联合）。如果一个矩形不与其相邻矩形相交，则保持不变。

问题在于，合并后的矩形可以与以前未考虑的矩形相交；合并后的矩形也可以与新合并的矩形相交。我想捕捉这些情况。

因此，在我的想法中，它需要是迭代的（尝试将每个矩形与集合中的每个其他矩形进行比较）和递归的（再次尝试将每个合并的矩形与集合进行比较，包括合并的矩形）。

我该如何做？ 我正在使用Java，但这更多是算法问题而不是面向语言的问题。

谢谢！

编辑：添加相关代码以更好地说明我现在处理方式的差劲之处。

public static List<BinaryRegion> mergeRegions(List<BinaryRegion> regions)
{
    List<BinaryRegion> merged = new ArrayList<BinaryRegion>();
    geoModel = new GeometryFactory();

    Polygon polys[] = new Polygon[regions.size()];
    for (int i = 0; i < regions.size(); i++)
    {
        Polygon p = convertRectangleToPolygon(regions.get(i)
                .getBoundingBox());
        polys[i] = p;
    }

    System.out.println("Converted " + regions.size() + " polys");

    for (int i = 0; i < regions.size(); i++)
    {
        System.out.println("Sending in poly " + i);
        ArrayList<Polygon> result = mergePoly(polys[i], polys);
        System.out.println("After run, size=" + result.size());
    }
    return merged;

}

private static ArrayList<Polygon> mergePoly(Polygon p, Polygon[] polys)
{
    ArrayList<Polygon> merges = new ArrayList<Polygon>();

    for (int i = 0; i < polys.length; i++)
    {
        if (p.equals(polys[i]))
            System.out.println("found the exact match at " + i);
        else if (p.intersects(polys[i]))
        {
            System.out.println("Found intersection at " + i);
            System.out.println("Other poly is area "+polys[i].getArea());
            Polygon u = (Polygon) p.union(polys[i]);
            System.out.println("Merge size="+u.getArea());
            merges.add(u);
        }
        else
            merges.add(polys[i]);
    }
    return merges;
}

- Mike O'Malley

---

这很明显不是一个作业问题 :) - Sergey Kalinichenko

你有多少个矩形？十个？一百个？一百万个？... - Sergey Kalinichenko

“创建联合”是指“创建一个覆盖两个相交矩形的矩形”，还是“创建一个看起来像两个相交矩形几何上的联合”的形状？ - Sergey Kalinichenko

几千个矩形。创建一个覆盖两个相交矩形的矩形；基本上是这两个矩形的边界框。 - Mike O'Malley

如果有一些API或包可以为我完成这个任务，我非常乐意使用它。只是想把它做好。 - Mike O'Malley

Answer 1

不确定这种嵌套迭代方法是否真的是正确的方式（特别是因为我不知道您在调用mergePoly之后如何处理合并的区域）。与将一个多边形与所有其他多边形进行比较不同，为什么不保留中间步骤并重新运行合并，直到没有更多的相交？大致如下：

private static ArrayList<Polygon> mergePoly(Polygon[] polys)
{
    List<Polygon> polygons = new ArrayList<Polygon>(Arrays.asList(polys));
    boolean foundIntersection = false;
    do
    {
        foundIntersection = false;
        for (int i = 0; i < polygons.size(); i++)
        {
            Polygon current = polygons.get(i);
            for (int j = i + 1; j < polygons.size(); j++)
            {
                if (current.intersects(polygons.get(j)))
                {
                    foundIntersection = true;
                    current = (Polygon)current.union(polygons.remove(j--));
                    System.out.println("Merge size="+u.getArea());
                }
            }
            polygons.set(i, current);
        }
    } while(foundIntersection);
    return polygons;
}

我已经有一段时间没有使用Java了，但逻辑还是很清晰的。你需要执行两次多边形迭代。外部迭代是“当前”多边形，你会将所有内部多边形合并到它上面（在沿途删除它们）。每次外部迭代后，你只需要设置该索引处的元素为（可能）合并的多边形，并继续进行下一个多边形的迭代。你需要一直做这个操作，直到没有更多的合并。请记住，这是一种非常天真的实现，你最好将其分解成“半个”，并合并这些较小的子集（考虑归并排序）。

- SPFiredrake

Answer 2

你可以使用扫描线算法来找到矩形（ 例子1， 例子2）的交点，同时使用并查集算法来有效地合并矩形集合。

- MBo