Dies ist keine Hausaufgabe :)Was ist der beste Weg, um eine Reihe von Rechtecken in einem Bild zusammenzuführen?
Ich habe eine Reihe von Rechtecken über ein Bild verstreut. Ich möchte jede Gruppe von durchschnittenen Rechtecken zusammenführen (eine Vereinigung erstellen). Wenn ein Rechteck seine Nachbarn nicht schneidet, bleibt es unberührt.
Das Problem ist, dass gemischte Rechtecke Rechtecke überschneiden können, die zuvor nicht berücksichtigt wurden; Zusammengefügte Rechtecke können auch neu zusammengefügte Rechtecke schneiden. Ich möchte diese Fälle fangen.
Also, in meinen Gedanken, muss es iterativ sein (versuchen Sie jedes Rect gegen jedes andere Rect in der Menge) und rekursiv (versuchen Sie jedes verschmolzen Rect gegen das Set wieder, einschließlich fusionierte Rect).
Wie kann ich darüber gehen? Ich arbeite in Java, aber das ist eher eine algorithmische Frage als eine sprachorientierte Frage.
Danke!
Bearbeiten: hinzugefügt relevanten Code, um besser zu veranschaulichen, die schlechte Art, in der ich es jetzt handle.
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;
}
Es ist offensichtlich, dass dies keine Hausaufgabe ist :) – dasblinkenlight
Wie viele Rechtecke hast du? Zehn? Hunderte? Millionen? .. – dasblinkenlight
Mit "Erstellen einer Union" meinst du "ein Rechteck erstellen, das beide sich überschneidenden Rechtecken umfasst" oder "eine Form erstellen, die wie eine geometrische Vereinigung der beiden sich überschneidenden Rechtecke aussieht"? – dasblinkenlight