mikrocontroller.net

Forum: PC-Programmierung Algorithmus gesucht


Autor: Steuerbert (Gast)
Datum:

Bewertung
0 lesenswert
nicht lesenswert
Guten Mittag,

kennt jemand einen einfachen und schnellen Algorithmus für folgendes 
Problem?

         *----------*
         |          |
         |          |
  *------*--*--*----*
  |         |  |    |
  |         |  |    |
  |         |  *----*
  |         |
  *---------*


Ich hab mehrere Rechtecke, von denen ich einen Umriss berechnen will ... 
Der soll dann so aussehen (die x):
         
         xxxxxxxxxxxx
         x          x
         x          x
  xxxxxxxx--*--*----x
  x         |  |    x
  x         |  |    x
  x         xxxxxxxxx
  x         x
  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

Autor: Läubi .. (laeubi) Benutzerseite
Datum:

Bewertung
0 lesenswert
nicht lesenswert
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

Autor: Volker Zabe (vza)
Datum:

Bewertung
0 lesenswert
nicht lesenswert
Wie liegen die Daten vor? Pixel oder Vektoren?
Welches Format soll des Ergebniss haben?

Autor: Stefan (Gast)
Datum:

Bewertung
0 lesenswert
nicht lesenswert
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!

Autor: Martin (Gast)
Datum:

Bewertung
0 lesenswert
nicht lesenswert
... 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.

Autor: Steuerbert (Gast)
Datum:

Bewertung
0 lesenswert
nicht lesenswert
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 ...

Autor: D. I. (Gast)
Datum:

Bewertung
0 lesenswert
nicht lesenswert
Sweep-Line Verfahren ist der gesucht Algorithmus.

Kann heute Abend auch Code dazu liefern, der genau das tut

Autor: Klaus Wachtler (mfgkw)
Datum:

Bewertung
0 lesenswert
nicht lesenswert
> 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.

Autor: Volker Zabe (vza)
Datum:

Bewertung
0 lesenswert
nicht lesenswert
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.

Autor: D. I. (Gast)
Datum:

Bewertung
0 lesenswert
nicht lesenswert

Autor: Android (Gast)
Datum:

Bewertung
0 lesenswert
nicht lesenswert
Also die obere Zeichnung passt nicht zur unteren. Oben sind 3 Rechtecke 
aufgemalt deren Umriss nicht dem unten aufgemalten entspricht.

Autor: Karl Heinz (kbuchegg) (Moderator)
Datum:

Bewertung
0 lesenswert
nicht lesenswert
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.

Autor: Karl Heinz (kbuchegg) (Moderator)
Datum:

Bewertung
0 lesenswert
nicht lesenswert
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)

Autor: Steuerbert (Gast)
Datum:

Bewertung
0 lesenswert
nicht lesenswert
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!

Autor: Karl Heinz (kbuchegg) (Moderator)
Datum:

Bewertung
0 lesenswert
nicht lesenswert
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)

Autor: Volker Zabe (vza)
Datum:

Bewertung
0 lesenswert
nicht lesenswert
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"

Autor: Läubi .. (laeubi) Benutzerseite
Datum:

Bewertung
0 lesenswert
nicht lesenswert
Steuerbert schrieb:
> Programmiersprache ist eigentlich egal ...
Ja... eigentlich...
> Am besten wäre irgendwas
> C-ähnliches wie Java, C++ oder C ...
//TODO: Initialisieren....
    Rectangle2D rect1 = null;
    Rectangle2D rect2 = null;
    Rectangle2D rect3 = null;

    Area a1 = new Area(rect1);
    Area a2 = new Area(rect2);
    Area a3 = new Area(rect3);

    a1.add(a2);
    a1.add(a3);

    PathIterator iterator = a1.getPathIterator(null);
    while (!iterator.isDone()) {
      double[] coords = new double[6];
      int type = iterator.currentSegment(coords);
      System.out.println(type + " " + Arrays.toString(coords));
      iterator.next();
    }
Ist ein Algorithmus der das Problem in Java löst...

Autor: Karl Heinz (kbuchegg) (Moderator)
Datum:

Bewertung
0 lesenswert
nicht lesenswert
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.

Autor: Arc Net (arc)
Datum:

Bewertung
0 lesenswert
nicht lesenswert
Mal wieder Algorithmen die Spaß machen.
Stichwort: Konturproblem
Zwei Lösungen: Der optimale sehr komplexe Plane-Sweep/Sweep-Line-Ansatz 
oder ein Divide&Conquer-Ansatz bei dem im ersten Schritt die 
Streifenmenge d.h. die Vereinigung der Rechtecke berechnet wird und aus 
dieser Darstellung die Kontur bestimmt wird.

http://books.google.com/books?id=uXKyuK0jVJsC&pg=P...
Datenstrukturen und Algorithmen, Ralf Hartmut Güting, Stefan Dieker, 
Teubner Verlag, ISBN: 3519221217

Autor: sebastians (Gast)
Datum:

Bewertung
0 lesenswert
nicht lesenswert
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)?

Autor: Steuerbert (Gast)
Datum:

Bewertung
0 lesenswert
nicht lesenswert
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.

    *-----*
    |     |
    |     |
    *-----*

              *-----*
              |     |
              |     |
              *-----*

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 ...

Autor: Läubi .. (laeubi) Benutzerseite
Datum:

Bewertung
0 lesenswert
nicht lesenswert
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...

Autor: Karl Heinz (kbuchegg) (Moderator)
Datum:

Bewertung
0 lesenswert
nicht lesenswert
> 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.

Autor: Steuerbert (Gast)
Datum:

Bewertung
0 lesenswert
nicht lesenswert
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 ...

Autor: Karl Heinz (kbuchegg) (Moderator)
Datum:

Bewertung
0 lesenswert
nicht lesenswert
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.

Antwort schreiben

Die Angabe einer E-Mail-Adresse ist freiwillig. Wenn Sie automatisch per E-Mail über Antworten auf Ihren Beitrag informiert werden möchten, melden Sie sich bitte an.

Wichtige Regeln - erst lesen, dann posten!

  • Groß- und Kleinschreibung verwenden
  • Längeren Sourcecode nicht im Text einfügen, sondern als Dateianhang

Formatierung (mehr Informationen...)

  • [c]C-Code[/c]
  • [avrasm]AVR-Assembler-Code[/avrasm]
  • [code]Code in anderen Sprachen, ASCII-Zeichnungen[/code]
  • [math]Formel in LaTeX-Syntax[/math]
  • [[Titel]] - Link zu Artikel
  • Verweis auf anderen Beitrag einfügen: Rechtsklick auf Beitragstitel,
    "Adresse kopieren", und in den Text einfügen




Bild automatisch verkleinern, falls nötig
Bitte das JPG-Format nur für Fotos und Scans verwenden!
Zeichnungen und Screenshots im PNG- oder
GIF-Format hochladen. Siehe Bildformate.
Hinweis: der ursprüngliche Beitrag ist mehr als 6 Monate alt.
Bitte hier nur auf die ursprüngliche Frage antworten,
für neue Fragen einen neuen Beitrag erstellen.

Mit dem Abschicken bestätigst du, die Nutzungsbedingungen anzuerkennen.