Dies ist keine Hausaufgabenfrage:)
Ich habe eine Reihe von Rechtecken, die über ein Bild verstreut sind. 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 besteht darin, 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 muss es meiner Ansicht nach iterativ sein (versuche jedes gegen jedes andere rect im Satz) und rekursiv (versuch jedes verschmolzene rect gegen das Set erneut, einschließlich der verschmolzenen rekte).
Wie kann ich darüber gehen? Ich arbeite in Java, aber das ist eher eine algorithmische als eine sprachorientierte Frage.
Danke!
Bearbeiten: Es wurde relevanter Code hinzugefügt, um die schlechte Art, in der ich es jetzt behandle, besser zu veranschaulichen.
%Vor% Ich bin mir nicht ganz sicher, ob dieser verschachtelte iterative Ansatz wirklich der richtige Weg ist (vor allem, weil ich nicht sehe, wie genau Sie nach dem Aufruf von mergePoly mit den zusammengeführten Regionen umgehen). Statt mit jeweils einem Polygon im Vergleich zu allen anderen Polygonen zu arbeiten, sollten Sie Zwischenschritte durchführen und die Zusammenführung wiederholen, bis keine Überschneidungen mehr vorhanden sind. Etwas in der Art von:
Es ist eine Weile her, seit ich mit Java gearbeitet habe, aber die Logik ist ziemlich selbsterklärend. Sie führen zwei Iterationen der Polygone durch. Die äußere Iteration ist Ihr "aktuelles" Polygon, mit dem Sie alle inneren Polygone zusammenführen werden (indem Sie sie aus der Sammlung entfernen, während Sie fortfahren). Nach jeder äußeren Iteration setzen Sie das Element auf diesen Index mit dem (möglicherweise) zusammengeführten Polygon und fahren mit dem nächsten Polygon in der Reihe fort. Du wirst das so lange machen, bis du keine Zusammenführungen mehr hast. Denken Sie daran, dass dies eine fürchterlich naive Implementierung ist, und Sie sollten besser in "Hälften" abbrechen und diese kleineren Teilmengen zusammenführen (denken Sie an Mergesort).
Sie können den Sweep-Line-Algorithmus verwenden, um Schnittpunkte von Rechtecken zu finden ( example1 ) , example2 ) und u nion-find-Algorithmus um Gruppen von Rechtecken effektiv zusammenzuführen.
Tags und Links algorithm image-processing geometry