Guten Mittag,
kennt jemand einen einfachen und schnellen Algorithmus für folgendes
Problem?
1
*----------*
2
| |
3
| |
4
*------*--*--*----*
5
| | | |
6
| | | |
7
| | *----*
8
| |
9
*---------*
Ich hab mehrere Rechtecke, von denen ich einen Umriss berechnen will ...
Der soll dann so aussehen (die x):
1
2
xxxxxxxxxxxx
3
x x
4
x x
5
xxxxxxxx--*--*----x
6
x | | x
7
x | | x
8
x xxxxxxxxx
9
x x
10
xxxxxxxxxxx
Die Annahme, die ich mache kann ist, dass die Rechtecke immer rechteckig
sind - d.h. alle Ecken haben 90° Winkel.
Kennt da jemand was einfaches?
Grüße,
Steuerbert
Wenn du mal die Programmiersprache angegeben hättest wäre es sicher
einfacher.
Bitte beachten:
Wichtige Regeln - erst lesen, dann posten!
•Aussagekräftigen Betreff wählen
Du hast dein Problem nicht ausreichend spezifiziert!
Wieso ist z.B. die kleine Lücke in der Mitte um Umriss enthalten? Nach
diesem System könnte man ja auch um alles ingsgesamt ein großes Rechteck
machen.
Falls du ein Algorithmus suchst um aus beliebigen Polygonen die
Schnittmenge zu bilden da hätt ich was!
... Wenn du mal die Programmiersprache angegeben hättest wäre es sicher
einfacher ...
Das ist doch Quark. Er braucht einen Algorithmus, da ist egal, ob Algol,
Basic, Cobol, ..., etc. usw. pp.
Was er möchte ist auch eindeutig beschrieben.
P. S. Interessante Aufgabe.
Volker Zabe schrieb:> Wie liegen die Daten vor? Pixel oder Vektoren?> Welches Format soll des Ergebniss haben?
Sorry, dachte das wären schon genug Informationen ...
Programmiersprache ist eigentlich egal ... Am besten wäre irgendwas
C-ähnliches wie Java, C++ oder C ...
Ich hab eine Liste aus Rechtecke mit zugehörigen Koordinaten.
Quasi sowas wie List<Rectangle> und ein Rectangle hat 4 Koordinaten.
Die Koordinaten sind alles int-Wert.
So ein ähnliches Problem dürfte die Konvexe Hülle einer Punktwolke sein
... Das Problem ist aber, dass ich dann höchstwahrscheinlich Vektoren
bekommen würde, die nicht vertikal oder horizontal sind. Diese müsste
ich dann in 2 Vektoren aufbrechen ... Hmm ... Ist es echt so einfach?
Ein schiefer (3 2) Vektor wird in einen (3 0) und in einen (0 2) Vektor
aufgebrochen ...
> Was er möchte ist auch eindeutig beschrieben.
Trotzdem ist nicht klar, was er wirklich will.
Ich sehe auch nicht, wieso die Lücke in der Mitte eingefaßt soll.
Wenn die Daten als Vektoren vorliegen würde wie folgt vorgehen:
1) Fange an einem Eckean.
2) Berechne den Winkel
3) Gehe zumr nächsten Ecke.
4) Berechne den Winkel.
5) Sind es zwei innere Winkel
nein -> gehe zu 3, bis du einen Ecke weiter bist, wie die Startecke.
ja -> 6)
6) verschiebe die beiden Ecken um die kürzere Seitenstrecke.
7) lösche die die beiden überflüssigen Ecken.
8) gehe zu 3, bis du einen Ecke weiter bist, wie die Startecke.
Steuerbert schrieb:> Die Annahme, die ich mache kann ist, dass die Rechtecke immer rechteckig> sind - d.h. alle Ecken haben 90° Winkel.
Können die Rechtecke gegeneinander verdreht sein?
> Kennt da jemand was einfaches?
Sweep Line Algorithmen wurde schon genannt.
Kannst du bitte noch klären, ob das hier
xxxxxxxxxxxx
x x
x x
xxxxxxxx--*--*----x
x | | x
x | | x
x xxxxxxxxx
x x
xxxxxxxxxxx
ein Zeichenfehler im Forum ist und eigentlich so aussehen sollte
xxxxxxxxxxxx
x x
x x
xxxxxxxx--xxxx----x
x x x x
x x x x
x x xxxxxx
x x
xxxxxxxxxxx
oder ob du das wirklich so haben willst?
Es würde die Sache zumindest vereinfachen, wenn du das tatsächlich so
haben willst.
Du brauchst nur das Polgon von unten beginnend (mit einer Sweep Line)
entlang der Y-Richtung abfahren und in jeder 'Zeile' bestimmen, welches
der minimal bzw. maximal vorkommende X-Wert ist. Dein Ergebnispolygon
bewegt sich dann da dazwischen.
Dazu kommt noch: die minimale bzw. maximale X Koordinate (ich nehm jetzt
keine Verdrehung an), kann sich nur an Stellen ändern, an denen 'etwas
passiert'. Also an Stellen an denen ein anderes Rechteck in die
Sweepline eintritt, an Stellen an denen Kreuzungspunkte sind, an Stellen
an denen ein Rechteck aus der Sweepline austritt.
Dazu sortiert man die Rechtecke in 2 Listen
in der einen sind sie nach minimaler Y Koordinate sortiert
in der anderen nach maximaler.
Der Algorithmus hat deine eine Liste von 'aktiven Rechtecken'.
Wenn dann die Sweep-Line ihren gedachten Scan über die Rechtecke
vollführt, muss man immer nur nachsehen, in welcher Liste man das
nächste Ereignis findet, welches die Liste der aktiven Rechtecke
verändert. Der Rest ist dann nur noch: finde die minimale X-Koordinate
der aktiven Rechtecke, finde die Maximum Koordinate der aktiven
Rechtecke und bring das in Beziehung zu den letzten bekannten
X-Minima/Maxima um daraus den Verlauf der Outline abzuleiten.
Steuerbert schrieb:> So ein ähnliches Problem dürfte die Konvexe Hülle einer Punktwolke sein> ...
man kann das Problem so ähnlich lösen. Ja
> Das Problem ist aber, dass ich dann höchstwahrscheinlich Vektoren> bekommen würde, die nicht vertikal oder horizontal sind.
Die Gefahr besteht.
Man müsste zusätzlich noch jede Kante mit jeder Kante schneiden und die
Kanten an den Schnittpunkten aufbrechen. Denn dieser Punkt hier
xxxxxxxxxxxx
x x
x x
xxxxxxxx--*--*----x
x | | x
x | | x
x xxxxxxxxx
x x\
xxxxxxxxxxx \
\
\
\
ist in deinen Orignaldaten nicht enthalten, kann daher auch nicht als
Punkt einer Richtungsänderung gefunden werden.
Diese müsste
> ich dann in 2 Vektoren aufbrechen ... Hmm ... Ist es echt so einfach?> Ein schiefer (3 2) Vektor wird in einen (3 0) und in einen (0 2) Vektor> aufgebrochen ...
Nein das würde nicht gehen. So einfach ist das dann doch nicht :-)
Zumindest nicht, wenn das Ergebnis "eng an deinen Rechtecken" anliegen
soll. Und wenn nicht, dann ist die ganze Operation trivial :-)
Aber alles in allem ist das ziemlich aufwändig in der Rechnerei. Um von
einm Punkt rauszufinden wie es weiter geht, müsssen viele, viele Winkel
berechnet werden.
Sweep-Scan ist einfacher, wenn auch die Datenorganisation ein wenig
aufwändiger ist. (sind aber nur sortierte Arrays mit einem 'aktiven
Index' zusätzlich, der bei Bedarf weiter gestellt wird)
Karl heinz Buchegger schrieb:> xxxxxxxxxxxx> x x> x x> xxxxxxxx--*--*----x> x | | x> x | | x> x xxxxxxxxx> x x> xxxxxxxxxxx
Das ist kein Zeichenfehler ... ich hab das Beispiel extra so gewählt,
damit man das Problem sieht :-)
Das mit der Sweepline hört sich interessant an!
Steuerbert schrieb:> Das mit der Sweepline hört sich interessant an!
(Ich setze immer noch achsparallele Rechtecke voraus)
Der springende Punkt ist:
Du musst das Ergebnis als 2 Konturen betrachten
eine für links
eine für rechts
die beiden Teilkonturen werden dann am Ende zusammengesetzt, indem sie
oben und unten mit einer Waagrechten verbunden werden.
Mal dir auf ein Blatt Papier ein paar Rechtecke auf und leg einen Zettel
drüber dessen Unterkante parallel zu der Rechteck-X-Achse verläuft.
Und dann schiebst du den Zettel nach oben von dir weg.
Interessant sind immer nur die Punkte, an denen entweder ein Rechteck
unter dem Zettel auftaucht bzw. ein Rechteck mit seiner Oberkante
vollständig vom Zettel freigelegt wurde.
Und dann überlegst du dir, wie dieses Ereignisse deine linke bzw. rechte
Teilkontur beeinflussen und was da alles passieren kann (dann merkt man
auch warum man eine 'Liste der aktiven Rechtecke' benötigt)
Erzeuge die konvexe Hülle (nach der gannten Methode) und dan versuche
das was ich geschrieben habe, um die "Einbuchtungen zu elemenieren:
Beitrag "Re: Algorithmus gesucht"
Volker Zabe schrieb:> Erzeuge die konvexe Hülle (nach der gannten Methode)
Die konvexe Hülle hilft ihm nichts. In einer konvexen Hülle gibt es
keine 'inneren Winkel' mehr. Genau aus dem Grunde ist sie ja konvex.
> und dan versuche> das was ich geschrieben habe, um die "Einbuchtungen zu elemenieren:>> Beitrag "Re: Algorithmus gesucht"
Dazu müsste er erst die boolsche Operation 'Union' auf seine Rechtecke
anwenden, dann würde dein Algorithmus greifen und Einbuchtungen
eliminieren.
Willst du das haben?
Für jede Kante eines Rechtecks: Wenn die Verlängerung der Kante eine
andere Kante schneidet, verlängere sie.
Oder sollen nur horizontale Kanten verlängert werden (in deinem Beispiel
taucht nur das auf)?
Da bin ich bei der Implementierung mittlerweile auf ein Problem gestoßen
... und zwar der Fall, dass die Punkte der Fläche zB zweier Rechtecke
keine gemeinsame x- oder y-Koordinate haben ... z.B.
1
*-----*
2
| |
3
| |
4
*-----*
5
6
*-----*
7
| |
8
| |
9
*-----*
In dem Fall ist mir nicht klar, wie die Kontur, die ich eigentlich haben
möchte, aussehen soll ...
Ich glaub, es ist daher schwierig einen Algorithmus zu verallgemeinern,
der das kann, was ich möchte :(
vlt noch zum Anwendungszweck ... Ein Benutzer kann Rechtecke platzieren
und ich hätte gerne die Fläche des benötigten Platzes gebraucht, wo
Löcher aber vom Platzbedarf eingeschlossen werden, weil die Fläche der
Löcher nicht mehr sinnvoll für weitere Rechtecke genutzt werden können
...
Dabei sollte so eine Konstellation wie oben so gewertet werden, dass sie
mehr Platz braucht, als wenn man die Rechtecke aneinander positioniert
...
Aber so ganz klar ist es mir wohl leider selber nicht ...
Ich glaub, ich würde mit einer simplen Konvexen Hülle besser und
einfacher fahren ...
Steuerbert schrieb:> Ich glaub, es ist daher schwierig einen Algorithmus zu verallgemeinern,> der das kann, was ich möchte :(
Nein das Problem ist:
Steuerbert schrieb:> Aber so ganz klar ist es mir wohl leider selber nicht ...
Wie soll man den einen Algorithmus für ein Problem finden wenn nichtmal
dir klar ist was dabei rauskommen soll?
Steuerbert schrieb:> vlt noch zum Anwendungszweck ...
- Maximale/Minaimale X und Y Koordinaten aller Vierecke bestimmen.
- Das ergibt ein neues Rechteck.
- Fläche bestimmen
Und du weißt wieviel "Platz" die Rechtecke benötigen...
> Löcher aber vom Platzbedarf eingeschlossen werden, weil die> Fläche der Löcher nicht mehr sinnvoll für weitere Rechtecke> genutzt werden können
Ui.
Sowas ist immer schwierig.
Dein Programm müsste dafür in die Zukunft blicken können. Definiere
"sinnvoll".
Auch in deiner ürspünglichen Aufgabenstellung, kann es ja auch
vorkommen, dass dieses 'Loch' sinnvoll genutzt werden kann, wenn nur das
hinzuzufügende Rechteck klein genug ist.
Bei Algorithmen muss man mit Worthülsen wie
"sinnvoll", "am besten", "am optimalsten", ...
immer extrem vorsichtig sein.
Karl heinz Buchegger schrieb:> Auch in deiner ürspünglichen Aufgabenstellung, kann es ja auch> vorkommen, dass dieses 'Loch' sinnvoll genutzt werden kann, wenn nur das> hinzuzufügende Rechteck klein genug ist.
Hmm ... man kann sich das so vorstellen, dass so ein Bereich, der aus
Rechtecken besteht, einem User gehört und ein anderer darf nichts
reinsetzen. Dann ist so ein Loch nicht nutzbar ...
Bei dem obigen Problem könnte es aber möglich sein, dass ein anderer
Benutzer links/rechts davon was anordnen, weil die Rechtecke eigentlich
keinen richtigen Bereich abstecken ... Weiß nur nicht, ob ich das jetzt
erwünscht haben will oder nicht, weil eigentlich sollte alles so nah wie
möglich angeordnet werden und nicht so lose auseinander
Ich glaub ich begnüg mich erstmal mit der konvexen Hülle, die mir den
Bereich eines Users absteckt ...
Steuerbert schrieb:> Karl heinz Buchegger schrieb:>> Auch in deiner ürspünglichen Aufgabenstellung, kann es ja auch>> vorkommen, dass dieses 'Loch' sinnvoll genutzt werden kann, wenn nur das>> hinzuzufügende Rechteck klein genug ist.>> Hmm ... man kann sich das so vorstellen, dass so ein Bereich, der aus> Rechtecken besteht, einem User gehört und ein anderer darf nichts> reinsetzen. Dann ist so ein Loch nicht nutzbar ...
OK.
Daran sollten wir arbeiten.
Gesetz den Fall die Vereinigung von Rechtecken ergibt das hier
+----------------------------------------------------------+
| |
| +----------------------------------------------+ |
| | | |
| | | |
| | +---+
| |
| |
+-------+
Darf dann Benutzer B in die Einbuchtung was reinschieben oder nicht?
Das ist im Grunde dieselbe Situation wie oben, nur dass die Einbuchtung
diesmal breiter ist.
Kombiniere ich jetzt deine letzte Aussage mit dem aus dem
Ursprungsposting gelernten, so komme ich zu dem Schluss:
Das hier
+----------------------------------------------------------+
| |
| +----------------------------------------------+ |
| | | |
| | +--------+ | |
| | | | +---+
| | | |
| | +--------+
+-------+
ist für Benutzer B nicht erlaubt.
Das hier:
+----------------------------------------------------------+
| |
| +----------------------------------------------+ |
| | | |
| | | |
| | +---+
| | +--------+
| | | |
+-------+ | |
+--------+
aber schon.
Als Benutzer deines Programms wäre mir das jetzt nicht sofort
unmittelbar einsichtig, wenn ich nicht weiß, wie das Programm zu dieser
Erkenntnis kommt.
Thread beobachten
Seitenaufteilung abschalten