这不是作业题:)
我有一组散布在图像上的矩形。我想合并(创建一个并集)每组相交的矩形。如果矩形不与其相邻矩形相交,则它保持不变。
问题是合并后的矩形可以与之前未考虑的矩形相交;合并的矩形也可以与新合并的矩形相交。我想捕获那些案例。
因此,在我看来,它需要迭代(针对集合中的每个其他矩形尝试每个矩形)和递归(针对集合再次尝试每个合并的矩形,包括合并的矩形)。
我该怎么做?我在 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;
}
最佳答案
不完全确定这种嵌套迭代方法是否真的可行(特别是因为我看不到您在调用 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 以来已经有一段时间了,但是逻辑是不言自明的。您执行多边形的两次迭代。外部迭代是您的“当前”多边形,您将合并所有内部多边形(在进行时将它们从集合中移除)。在每次外部迭代之后,您只需使用(可能)合并的多边形设置该索引处的元素,然后移动到系列中的下一个多边形。您将继续这样做,直到不再合并为止。请记住,这是一个非常幼稚的实现,您最好将其分成“两半”并合并这些较小的子集(想想合并排序)。
关于algorithm - 合并图像中的一组矩形的最佳方法是什么?,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/12284025/