Guten Tag, liebes Forum! ich hab hier ein ultrakompliziertes Problem, das sicher niemand lösen kann. Vielleicht ist es auch ganz einfach und ich kenn nur die Tricks nicht. Keine Ahnung. Am Einfachsten zu verstehen ist es, wenn ich es so erkläre: Ich hab mehrere Rechtecke, die sich irgendwie überlappen können. Alle Rechtecke sind Transparent mit 50%. Wenn sich jetzt z.B. zwei Rechtecke überlappen, gibt es eine Transparenz von nur noch 25% in der Schnittfläche. Ich suche also einen Algorithmus, der die Fläche mehrerer vereinten Rechtecke in neue disjunkte Rechtecke aufteilt, wobei es am Besten möglichst wenig Rechtecke sein sollten. Ich verwende Java und kann mit Area von java.awt.geom z.B. mehrere Rechtecke vereinen. Aber die Frage ist, wie krieg ich eine solche Area wieder in disjunkte Rechtecke zerlegt? Hätte da zufällig irgendjemand eine Idee, wie es einfach gehen könnte? Bin gespannt! Viele Grüße, Microweich
>> Hätte da zufällig irgendjemand eine Idee, wie es einfach gehen könnte?
Habe erst kürzlich irgendwo gelesen, dass dies sicher niemand lösen
kann!
Martin schrieb: >>> Hätte da zufällig irgendjemand eine Idee, wie es einfach gehen könnte? > > Habe erst kürzlich irgendwo gelesen, dass dies sicher niemand lösen > kann! Dann wär ich auch mit einer guten Lösung zufrieden, anstatt einer optimal. Grüße, Microweich
Microweich schrieb: > Ich suche also einen Algorithmus, der die Fläche mehrerer vereinten > Rechtecke in neue disjunkte Rechtecke aufteilt, wobei es am Besten > möglichst wenig Rechtecke sein sollten. Das ist sicherlich schwierig: Wenn Du zwei passend liegende Rechtecke - davon eins um 45° gedreht - miteinander schneidest, könnte die Schnittmenge ein Dreieck sein. Dieses wiederum mit Rechtecken darzustellen erfordert wohl eine Approximation mit ziemlich vielen Rechtecken. Exakt wird man das nicht hinbekommen. Viele Grüße, Simon
Simon Budig schrieb: > Das ist sicherlich schwierig: Wenn Du zwei passend liegende Rechtecke - > davon eins um 45° gedreht - miteinander schneidest, könnte die > Schnittmenge ein Dreieck sein. Dieses wiederum mit Rechtecken > darzustellen erfordert wohl eine Approximation mit ziemlich vielen > Rechtecken. Exakt wird man das nicht hinbekommen. Aaaah! Tut mir leid! Die Rechtecke sind nicht verdreht. Man muss sich die Rechtecke so vorstellen, wie man sie in Java zum Beispiel mit fillRect(x,y,w,h) zeichnen kann, D.h. sie haben einen Aufhängepunkt (x/y) und spannen eine Fläche mit der Breite w und der Höhe h auf. Sorry, das hatte ich bei meiner Fragestellung nicht bedacht. Hatte das - unverständlicherweise - als selbstverständlich angenommen. Grüße, Microweich
Du kannst dir dann aussuchen welche Strategie du fahren möchtest:
Möglichkeit 1
nicht von vorne herein alle Rechtecke übereinander legen, sondern
* du hast eine Liste von Rechtecken, die dein Ergebnis darstellen
* in diese Liste bringst du nacheinander die noch nicht bearbeiteten
Rechtecke ein, in dem du berechnest wie sich jedes einzelne
Rechteck aus deiner Ergebnisliste durch dieses neue Rechteck
verändert.
* Als Ergebnis erhältst du eine neue Rechteckliste, die dann
Ausgangsbasis dient um das nächste noch nicht bearbeitet Rechteck
einzubringen
Möglichkeit 2:
In Anlehung an einen Polygontriangulierer, schreibst du ähnlichen
Code, der die Zerlegung eines Polygons (welches nur aus waagrechten
und senkrechten Kanten bestehen kann) in Rechtecke ermöglicht.
Du suchst die einen Eckpunkt aus und verfolgst die beiden Kanten bis
zum jeweils nächsten Endpunkt. Die beiden Kanten plus deren jeweiligen
parallelen Kanten bilden ein potentielles Rechteck. Das überprüfst du,
ob es entfernbar ist (ob die beiden parallelen Kanten die restliche
Aussenkontur schneiden oder nicht). Wenn diese Rechteck komplett
innerhalb der Kontur liegt (die Aussenkontur nicht schneidet), dann
ist
es entfernbar und wird geometrisch aus der Aussenkontur entfernt.
Ist es nicht entfernbar, dann nimmst du einfach den nächsten Endpunkt
als potentiellen Kandidaten. Das ganze geht dann so lange, bis durch
das Abspalten von Teilrechtecken nur noch ein Rechteck übrig bleibt.
Microweich schrieb: > Die Rechtecke sind nicht verdreht. Ah, ok. Also achsenparallele Rechtecke. Mit wievielen Rechtecken rechnest Du denn? Bzw. wieviel Aufwand willst Du in die Entwicklung eines Algorithmus stecken? Einen fertigen habe ich nicht parat. Ein naiver Ansatz wäre, je zwei Rechtecke auf Überlappung zu testen und ggf. aufzuteilen. Das wäre dann ein O(n²)-Algorithmus und damit für viele Rechtecke vermutlich recht langsam. Wird das zu langsam kann man die Laufzeit vermutlich auf O(n log n) drücken, wenn man einen Sweep-Algorithmus ( http://de.wikipedia.org/wiki/Sweep_%28Informatik%29 ) (er)findet. Also die Rechtecke z.B. nach x0 zu sortieren und dann von links nach rechts durchmarschieren und dabei zu prüfen, welche Rechtecke gerade "aktiv" sind. Diese dann entsprechend aufteilen. Das ist nur ein Denkanstoß. Ich bin mir sicher, dass man da Literatur dazu finden kann. Viele Grüße, Simon
Microweich schrieb: > Ich verwende Java und kann mit Area von java.awt.geom z.B. mehrere > Rechtecke vereinen. Aber die Frage ist, wie krieg ich eine solche Area > wieder in disjunkte Rechtecke zerlegt? Du kanst dir einen Iterator über die Aussenkante der Area besorgen, das Problem wird eher sein festzustellen wo innen und außen ist, wenn sich die Rechtecke so scheniden das in der Mitte eine "Loch" entsteht. Microweich schrieb: > Ich hab mehrere Rechtecke, die sich irgendwie überlappen können. Alle > Rechtecke sind Transparent mit 50%. Wenn sich jetzt z.B. zwei Rechtecke > überlappen, gibt es eine Transparenz von nur noch 25% in der > Schnittfläche. Irgenwie versteh ich auch nicht ganz was du erreichen willst. Soll die Transparenz immer 50% sein (worauf bezogen eigentlich?) sich die Rechtecke also nie farblich "vermischen"? Oder willst du gerade diese 25% Transparenz haben? Ein kleines Bild vom ist Zustand + beschreibung was der Sollzustand ist würde sicher helfen.
Hallo Zuerst überprüfen, ob sie sich überlappen. Falls nicht --> Ende Falls doch: Man nehme z.B. die linken beiden Kanten der Rechtecke. Die Kante, die am meisten rechts liegt, ist die linke Kante des Überlappungsbereiches. Man nehme die nächste Kante und verfahre sinngemäß. Gruß Joachim
XXX schrieb: > Hallo > > Zuerst überprüfen, ob sie sich überlappen. Falls nicht --> Ende > > Falls doch: > > Man nehme z.B. die linken beiden Kanten der Rechtecke. > Die Kante, die am meisten rechts liegt, ist die linke Kante des > Überlappungsbereiches. > > Man nehme die nächste Kante und verfahre sinngemäß. Man versuche zunächst die Aufgabenstellung zu verstehen
>Man versuche zunächst die Aufgabenstellung zu verstehen
Man stelle erst eine Aufgabe.
Geht es hier um einen Algorithmus oder um java.awt.geom? Da Microweich
sich nicht verständlich machen kann, hat sich das Thema erledigt.
YYY schrieb: >>Man versuche zunächst die Aufgabenstellung zu verstehen > > Man stelle erst eine Aufgabe. > > Geht es hier um einen Algorithmus Es geht hier um eigentlich 2 Algorithmen: Um die boolsche Funktion 'union' und um eine Zerlegung eines (noch nicht einmal allgemeinen) Polygons in bekannte geometrische Grundprimitiva (hier Rechtecke). Da es hier 'nur' um Rechtecke geht, ist das noch nicht einmal besonders kompliziert. Aber: Um so einen Algorithmus zu entwickeln muss man eine eiserne Regel über Bord werfen, die da lautet: Verwende niemals, unter keinen Umständen, auch dann nicht wenn es um dein Leben geht, Papier und Bleistift um dir die Sachlage klar zu machen. So was tut man einfach nicht. Wo kämen wir denn da hin, wenn man anhand von ein paar Skizzen ablesen könnte welche Fälle es gibt, was einen so erwartet, eine Idee entwickeln könnte und die dann auch noch an den Skizzen testen könnte. Pfui, Papier und Bleistift sind megaout, die benutzt man einfach nicht mehr.
Läubi .. schrieb: > Du kanst dir einen Iterator über die Aussenkante der Area besorgen, das > Problem wird eher sein festzustellen wo innen und außen ist, wenn sich > die Rechtecke so scheniden das in der Mitte eine "Loch" entsteht. Genau auf das Problem bin ich auch gestoßen. Machts irgendwie nicht einfacher. > Microweich schrieb: >> Ich hab mehrere Rechtecke, die sich irgendwie überlappen können. Alle >> Rechtecke sind Transparent mit 50%. Wenn sich jetzt z.B. zwei Rechtecke >> überlappen, gibt es eine Transparenz von nur noch 25% in der >> Schnittfläche. > Irgenwie versteh ich auch nicht ganz was du erreichen willst. Soll die > Transparenz immer 50% sein (worauf bezogen eigentlich?) sich die > Rechtecke also nie farblich "vermischen"? Oder willst du gerade diese > 25% Transparenz haben? Ein kleines Bild vom ist Zustand + beschreibung > was der Sollzustand ist würde sicher helfen. Ich hab dutzende (bis max. 500) Rechtecke, die sich überlappen können. Im Prinzip wird jedes Rechteck mit 65%-transparentem weiß gefüllt. Wenn sich Rechtecke aber überlappen, dann überdecken sich transparente Bereiche und die daraus resultierende Transparents ist nicht mehr 65%. Im Grunde will ich nur: Ganz viele Rechtecke, die irgendwelche Positionen und Größen haben, so ausfüllen, dass alles schön gleichmäßig 65% transparent ist. Aber das geht wohl nur, wenn ich die Vereinigungsfläche aller Rechtecke in disjunkte Rechtecke zerlegen kann, die sich beim Zeichnen nicht überlappen. Unterhalt der Rechtecke gibts natürlich noch Grafiken, die quasi über solche Rechtecke "ausgeblendet" werden. Ein weiteres Problem ist, dass es Rechtecke gibt, die nicht ausgeblendet werden sollen, die müssen dann von der Gesamtfläche ausgespart werden. Also, es wird eigentlich nur noch immer komplexer, leider ... Der Sweep-Line-Ansatz sieht vielversprechend aus ... Grüße, Microweich
Microweich schrieb: > Im Grunde will ich nur: Ganz viele Rechtecke, die irgendwelche > Positionen und Größen haben, so ausfüllen, dass alles schön gleichmäßig > 65% transparent ist. > > Aber das geht wohl nur, wenn ich die Vereinigungsfläche aller Rechtecke > in disjunkte Rechtecke zerlegen kann, die sich beim Zeichnen nicht > überlappen. ... oder Du Deinen Ansatz zum Malen änderst. (Ich habe eher Erfahrung mit Cairo, von daher kann ich nicht sagen, ob die äquivalente Methode im Java-API vorhanden ist) In Cairo würde ich machen (Pseudocode):
1 | cairo_save (cr); // Graphics State speichern |
2 | |
3 | for r in rectangles: |
4 | // current path um Rechtecke erweitern |
5 | cairo_rectangle (cr, r.x, r.y, r.w, r.h); |
6 | |
7 | cairo_set_fill_rule (cr, CAIRO_FILL_RULE_WINDING); // fill rule |
8 | cairo_clip (cr); // clipping region auf Pfad einschränken |
9 | cairo_set_source_rgba (cr, 1, 1, 1, 0.65); // transparentes weiß |
10 | cairo_paint (cr); // alles vollmalen. Clip-Region wird beachtet. |
11 | |
12 | cairo_restore (cr); // Graphics State wiederherstellen |
Alternativ könnte man ein zweites Bild malen mit vollflächig weißen
Rechtecken und dann dieses Bild mit 65% Deckkraft über das erste Bild
drübercompositen.
Aber wie gesagt, da kenne ich die Java-APIs zuwenig.
Viele Grüße,
Simon
Karl heinz Buchegger schrieb: > Pfui, Papier und Bleistift sind megaout, die benutzt man einfach nicht > mehr. Wir sind SPARTAAAAAAAA! :-) Viele Grüße, Simon
> ich hab hier ein ultrakompliziertes Problem
Es ist eigentlich recht einfach, ein effektiver Algorithms
existiert sicher schon 25 Jahre, es ist der sweep-line
Alorithmus, der von der Anzahl der Rechtecke und als
Obergrenze einem Logarithmus abhängt in der Art O(n log n).
Im Prinzip macht der folgendes:
Alle x-Eckpunkte (senkrechte Seiten) der Rechtecke werden
nach x sortiert, man geht also von links nach rechts über
alle Senkrechten.
An jeder solcher senkrechten beginnt oder endet ein Rechteck,
man fügt ein neues (oberkante-Unterkante) in eine Liste
ein oder entfernt es aus ihr.
Es entsteht also beim von links nach recht drüberwandeln
eine Liste mit aktuell an dieser Linie befindlichen
Rechteckflächen.
Damit ist es ein leichtes, die sich ergebenden Rechtecke
unterschiedlicher Tönung wieder hinten rausfallen zu lassen.
Der Trick beim Algorithmus ist, daß die beiden Speicherstrukturen
(meist B-Bäume mit doppelt verketteter Liste der Blätter),
der nach x sortieren Ecken und der senkrechten sweep line,
die passenden Pointer auf die realen Rechtecke tragen, damit
die sich ergebene Zusatzinfo ohne weitere Suchoperationen
(wie ihrerseits n log n oder gar n erfolern würden und damit
den Algorithmus zu (n^2) oder schlimmer aufblasen würden)
zur Verfügung stehen.
Der Algorithmus ist sehr schnell und wäre gut geeignet gewesen,
Real Time 3D Szenen rendering a la Doom mit einem Bruchteil der
Handwareanforderungen zu erfüllen, zumindest so lange die Anzahl
der Flächen deutlich kleiner ist als die Anzahl der Pixel, war
aber den Doom-Leuten wohl nicht bekannt.
Also ich habe folgende Idee: 1) Die Rechtecke der Reihe nach abarbeiten (ggf. sortiert) 2) Jedes Rechteck bleibt wie es ist und wird nicht geschnitten 3) Die Union zweier Rechtecke wird als Sohn, bzw. eine Ebene höher abgelegt und mit dr Transparenz versehen, die sich aus den beiden geschnittenen ergibt. Dabei werden auch die Rechtecke höherer Ebenen geschnitten, was wiederum noch höhere Ebenenergebnisse gibt. 4) Als Ergebnis kommt ein Stapel Rechecke heraus, den man durch die Sortierung über Ebenen in der Reihenfolge von oben nach unten oder umgekehrt (je nach Technik) zeichnen kann. Das sollte das Ergebnis bringen ohne den Aufwand des Zerteilens. Wenn doch Zerteilen benötigt wird, so kann nachgeschaltet über die Ebene gearbeitet werden. Ich hoffe das Prinzip ist klar geworden ...
Simon Budig schrieb: > Alternativ könnte man ein zweites Bild malen mit vollflächig weißen > Rechtecken und dann dieses Bild mit 65% Deckkraft über das erste Bild > drübercompositen. öööh ... oooh ... hmmmm ... ist das die Möglichkeit, dass es so einfach ist? Wahrscheinlich werden mich jetzt einige wieder schlagen, weil ich wieder soviele Informationen verschwiegen habe. Ich wollte es nicht unnötig kompliziert machen, wobei mir wohl genau das Gegenteil gelungen ist :-( Zum Rahmen außenrum: Die Rechtecke sollen auf einer Webanwendung gezeichnet werden, die das HTML5-Canvas verwendet. Dort hätte es die Möglichkeit gegeben - zumindest in Firefox, Opera, Safari, Chrome - ein vollflächiges 65% zu malen und dann die Rechtecke auszusparen, die nicht "ausgeblendet" werden sollen. Und zwar mittels clearRect. Für den IE gibt's zwar Emulationsbibliotheken, die VML verwenden, es gibt aber keine Implementierung der clearRect-Methode. Daher dachte ich mir, ich müsste das Server-seitig in Java implementieren. Die Idee von Simon ist gigantisch gut und ich werd das gleich ausprobieren, ob das geht. Rechtecke in weiß zeichnen auf das Canvas und im Prinzip per CSS die opacity auf 65% setzen ... Wenn das geht, bist du mein Held! Eigentlich müsste man es wissen. Alles was zu komplex erscheint geht immer irgendwie einfacher. Ich muss jetzt nur noch hoffen, dass CSS Opacity auf allen Browsern implementiert ist ...
Microweich schrieb: > Rechtecke in weiß zeichnen auf das Canvas und im Prinzip per CSS die > opacity auf 65% setzen ... Wenn das geht, bist du mein Held! Also auf'm Firefox klappt das schonmal ... den IE kann ich erst abends testen. Auf jedenfall ist das schonmal besser, als jeden Ansatz, den ich zuvor hatte. Und ich spiel da schon seit 2 Tagen dran rum :-(
Hmpf. Ich hab dann trotzdem das Problem, dass ich Bereiche löschen müsste und dafür bräuchte ich clearRect, weil man einen Bereich nicht mit transparenter Farbe füllen kann. Ich dreh mich im Kreis. Ich glaub ich bau an der Sweep-Line weiter oder überleg mir ganz was neues.
Microweich schrieb: > Hmpf. Ich hab dann trotzdem das Problem, dass ich Bereiche löschen > müsste und dafür bräuchte ich clearRect, weil man einen Bereich nicht > mit transparenter Farbe füllen kann. Der HTML-Canvas kann auch clipping, ähnlich wie ich das oben in meinem Cairo-beispiel verwenden wollte. Ich habe da mal was vorbereitet: http://www.home.unix-ag.org/simon/files/canvas.html obere Hälfte: Clipping-Bereich aus Rechtecken zusammengesetzt, untere Hälfte: der unerwünschte Überlappungs-Effekt. Tut in Firefox, keine Ahnung wie das in anderen Browsern aussieht. Viele Grüße, Simon
Simon Budig schrieb: > Ich habe da mal was vorbereitet: > http://www.home.unix-ag.org/simon/files/canvas.html > > obere Hälfte: Clipping-Bereich aus Rechtecken zusammengesetzt, untere > Hälfte: der unerwünschte Überlappungs-Effekt. > > Tut in Firefox, keine Ahnung wie das in anderen Browsern aussieht. Hmm ... ctx.clip, geht laut gurgel nicht mit dem IE, weil gwt-canvas oder excanvas.js das nicht unterstützt, aber es scheint auch so zu funktionieren:
1 | ctx.fill (); |
2 | // ctx.clip (); |
3 | // ctx.fillRect (0, 0, 400, 400); |
Das muss ich aber mit dem IE noch testen. Ich wusste nicht, dass die Pfade dann alle vereinigt werden ... Jetzt würde nur noch ein transparentes loch von z.B. 50,50 bis 100,100 fehlen und ich wär im siebten Himmel! Grüße, Microweich
Ah, ich glaub ich weiß, wie es geht ... Man bekommt über die Vereinigung und Subtraktion der Rechtecke unter Java einen Path-Iterator, den ich in moveTo und lineTo übersetzen kann. Das hier z.B. mach ein Rechteck (im uhrzeigersinn) mit Loch (gegen uhrzeigersinn):
1 | ctx.save (); |
2 | ctx.beginPath (); |
3 | |
4 | ctx.moveTo(10,10); |
5 | ctx.lineTo(110,10); |
6 | ctx.lineTo(110,110); |
7 | ctx.lineTo(10,110); |
8 | ctx.lineTo(10,10); |
9 | |
10 | ctx.moveTo(20,20); |
11 | ctx.lineTo(20,50); |
12 | ctx.lineTo(50,50); |
13 | ctx.lineTo(50,20); |
14 | ctx.lineTo(20,20); |
15 | |
16 | ctx.fill (); |
Hoffe das klappt so! Grüße, Microweich
Problem gelöst!!! Simon hat mich auf die richtige Fährte gebracht ... ich erklär's kurz, wie es geht ... Problem war, dass ich eine Anzahl Rechtecke hatte, die sich irgendwie überlagern können und ich wollte alle ausblenden, nur ein paar eben nicht. Die Rechtecke, die mit 65% weiß gefüllt wurden, sollten sich beim überlagern nicht mischen oder so, sondern 65% weiß bleiben. So gehts: Man hat in Java eine Area: Area resultArea = new Area(); dann iteriert man von "unten" nach "oben" durch alle Rechtecke und - addiert ein Rechteck, das transparent werden soll, zur Area mit resultArea.add(...); - oder subtrahiert ein Rechteck, das ausgespart werden soll mit resultArea.sub(...); Dann lässt man sich einen PathIterator geben. Der PathIterator gibt dann quasi zusammen mit x und y Koordinaten die Operation an. Das ist entweder moveTo, lineTo oder close. Das hab ich Serverseitig in einem Servlet gemacht und dann serialisiert und zum Client geschickt und der hat einfach 1:1 ohne Umformung mit moveTo und lineTo in das Canvas gezeichnet und anschließend einen Fill gemacht. voila ... Genau so, wie ich es haben wollte und mit geringem Aufwand :) Danke nochmal für die Hilfe! Grüße, Microweich
Ääh ... und es geht im IE7 im kompatibilitätsmodus genauso ... fast vergessen ;-)
Also in Allegro kann man die Rechtecke mit Transparenz einfach zeichnen (ist auch ne Spieleliberary). http://www.allegro.cc/ http://allegro5.org/
Thread beobachten
Seitenaufteilung abschaltenBitte melde dich an um einen Beitrag zu schreiben. Anmeldung ist kostenlos und dauert nur eine Minute.
Bestehender Account
Schon ein Account bei Google/GoogleMail? Keine Anmeldung erforderlich!
Mit Google-Account einloggen
Mit Google-Account einloggen
Noch kein Account? Hier anmelden.