Mehrere Rechtecke ergeben ein Rechteck - oder nicht?
-
Okay, danke. die Möglichkeit mit der rekursiven Vorgehensweise leuchtet mir ein. Ist natürlich irgendwie nicht wirklich hübsch, aber was soll's.
Vielen Dank für Eure Hilfe!
-
atlastraeger schrieb:
die Möglichkeit mit der rekursiven Vorgehensweise leuchtet mir ein.
Mir nicht. Was hat das damit zu tun, ob man den Algorithmus rekursiv oder iterativ aufbaut?
Noch eine Idee, wenn es wirklich zu viele Rechtecke sind. Teile das Gesamtrechteck in einzelne Teile (am besten wieder Rechtecke) auf, in denen nicht zu viele Rechtecke sind, und überprüfe jeden Abschnitt einzeln. Es gibt dann Rechtecke, die in mehreren Abschnitten sind, daher etwas mehr Aufwand.
Bye, TGGC (Der Held lebt!)
-
rekursiv ist die lösung viel schöner..
du kannst auch z.b. nen binärenbaum iterativ durchlaufen, aber rekursiv ist es viel schöner :>
-
Jetzt hab ich noch 'ne Idee, die ist vieeel besser! Du sortierst alle Rechtecke nach x1 und x2 (d.h. sie sind dann alle zweimal in der Liste L1 drin). Jetzt beginnst du mit dem ersten Element der Liste und speicherst den Abschnitt "y1 bis y2" in einer Liste L2. Du gehst jetzt Schritt für Schritt die Liste L1 durch, wobei jeder Eintrag ja den Beginn oder das Ende eines Rechtecks markiert. Ist das der Anfang eines Rechtecks, so fügst du den neuen y1-y2 Abschnitt in L2 ein. Ist es aber das Ende, so entfernst du den Abschnitt aus L2 und überprüfst, ob die verbleibenden Abschnitte das entfernte "y1 bis y2" komplett überdecken. Dies ist das Originalproblem, aber in 1D (und natürlich mit weniger Rechtecken/Abschnitten bzw. Intervallen). Das kannst du wieder mit den schon vorgeschlagenen Ideen lösen. Ist einmal der Abschnitt nicht komplett überdeckt, so ist dort ein Loch. Die Annahme, das alles überdeckt wird, ist dann widerlegt.
Noch ein paar Bemerkungen. Rechtecke, die einen leeren Schnitt mit dem Gesamtrechteck haben, dürfen nicht in L1 sein. Wenn in L1 mehrmals das gleiche x auftaucht, so müssen hier die Rechteckanfänge vor den Rechteckenden stehen. In L1 muss der Anfang des "Gesamtrechtecks" als Ende eines normalen Rechtecks eingefügt werden, damit auch dort schon alles überprüft wird. Das Ende des Gesamtrechtecks muss als Anfang in L1 eingefügt werden, nachdem Sortieren wird dies und alles dahinter aber alles gelöscht (alternativ bricht der Algorithmus ab, wenn er dort ankommt). Wird L2 als balancierter Suchbaum organisiert und nach y1 (oder y2) geordnet, so dauert Einfügen, Suchen und Löschen nur O(log n).
@durito: Ja, ich hab Langeweile!
Bye, TGGC (Der Held lebt!)
-
life schrieb:
rekursiv ist die lösung viel schöner..
du kannst auch z.b. nen binärenbaum iterativ durchlaufen, aber rekursiv ist es viel schöner :>Ist klar, du weisst nicht genau, wie 'ne funktionierende Lsösung ausschaut, aber rekursiv ist sie viel schöner...
Bye, TGGC (Der Held lebt!)
-
doch weiß ich und eine mögliche (wenn auch langsame) Lösung hab ich in meinem post beschrieben. Nur weil ich kein quellcode oder pseudocode poste, heißt das nicht, dass mein posting keine lösung enthält. Also trau dich und lies meinen post ruhig durch
-
a) Du hoffst, das es passt.
b) Ohne Hinweis hättest du deinen ersten grundsätzlichen Fehler übersehen.
c) Du sagst, man könnte in "überschneidungsrechtecke nach überschneidungen" suchen. Aber wie genau, das sagst du nicht.
d) Du hast hier als einziger Code geliefert.Ich denke du hast nur eine wage Vorstellung, wie es eventuell gehen könnte. Von da aus kann man sicher noch nicht auf Implementierungsdetails schliessen.
Bye, TGGC (Der Held lebt!)
-
a) ich bin mir ziemlich sicher dass es richtig ist
b) nein
c) na genauso, nur dass man jetzt die überschneidungsrechtecke als ausgangsbasis nimmt statt die "normalen" rechtecke daher das ganze auch rekursiv...
d) ja
-
life schrieb:
a) ich bin mir ziemlich sicher dass es richtig ist
a) Bravo,. Sollte man vielleicht ausprobieren. Viele Ideen sehen auf dem papier gut aus, aber leider nur dort.
b)
-
a) der algorithmus ist eh so langsam, dass er völlig unbrauchbar ist, aber funktionieren würde er.. (oder fällt dir ein grund ein, warum er nicht funktionieren sollte?)
b) den "fehler" hatte ich schon bemerkt, bevor ich auf "absenden" geklickt hatte. Da aber trotzdem die Möglichkeit besteht, dass er nützlich ist (z.b. wenn sich nur max 2 rechtecke gegenseitig überlappen können), habe ich ihn gepostet 
