Schweres Problem beim Sortieren von Paaren.

Atlanx

Atlanx

Mitglied
Einordnung: Algorithmusproblem unter Verwendung von c++
(Da ich hier keinen Unterbereich fuer Algorithmen gefunden habe und ich in c++ programmiere, hab ich das mal hier reingestellt.)

Hallo, ich habe hier ein interessantes Problem beim Einsortieren von Paaren, die der Ordnung A < B unterliegen.

Es geht darum Polygonflaechen, zur Vereinfachung nehmen wir einfach mal Kreise, so in eine Liste einzusortieren, dass die Ordnung gewahrt bleibt.

Das heisst, am Schluss soll eine Liste L* herauskommen, in der am Anfang das Polygon steht, dass zuerst gezeichnet werden soll und am Ende das Polygon, dass zuletzt gezeichnet werden soll, so dass weiter hinten liegende Polygone nicht andere Polygone im Vordergrund ueberdecken.

Als Ausgangsmaterial habe ich eine unsortierte Liste, in der jeweils Paare gespeichert sind mit der Ordnung A < B , was bedeuted, dass B weiter hinten liegt und somit zuerst gezeichnet werden muss.

[Siehe Anhang Bild 1]

Beispiel der Ausgangsliste: L = AD, CD, BC, CA, EB, FE, FD
Eine Loesung: S = FEBCAD

Hat jemand einen Vorschlag(z.B. Sortieralgorithmen, Baumalgorithmen), wie ich da am besten rangehen soll, um das moeglichst schnell zu sortiern. (One-Pass waere halt schoen)

-------------------------------------

Meine erste Loesung sieht so aus, funktioniert aber nur, wenn die Struktur einen echten Baum ergibt, also keine Elemente mit mehr als 2 Aesten verbunden sind, wie das im dargestellten Fall der Fall ist.

Folgendes funktioniert also mit einer 4 elementigen Liste L = AD, CD, BC, CA

Algorithmus:
Liste S = NULL;
for j == 1 to k
{
if Aj element von S & Bj nicht element von S dann fuege Bj direkt hinter Aj in die Liste ein
if Aj nicht element von S & Bj element von S dann fuege Aj direkt vor Bj in die Liste ein
if Aj element von S & Bj element von S UND wenn sie in der falschen Ordnung sind,
dann loesche Element Bj aus der Liste S und ersetze Aj durch das Paar Aj,Bj
}

Ablauf:

L = AD, CD, BC, CA

1. AD > S = AD
2. CD > S = SCD
3. BC > S = ABCD
4. CA > S = C ist in der Liste und A, aber in der falschen Reihenfolge
>>> A loeschen und C durch das Paar CA ersetzen
S = BCAD

Fertig, und Ordnung stimmt. Aber wie gesagt geht das nur mit echten Baumstrukturen.

Irgendwelche Vorschlaege oder Denkanstoesse?

Vielen Dank.
 

Anhänge

Hallo,
noch verstehe ich die Sache mit den Paaren nicht: Was für eine Bedeutung hat zum Beispiel ein Paar "AB"?

[EDIT]: Gerade ist mir das Brett vom Kopf gefallen. Also ein Paar ist offenbar die Information, dass sich zwei Flächen überdecken.

Ein Algorithmus ist wahrscheinlich recht einfach.
Es gibt in der Paarliste mindestens 1 Fläche, die niemals rechter Teil des Paares ist.
Finde diese, zeichne diese und lösche anschließend alle Paare, die diese Fläche enthalten.
Dann das ganze solange wiederholen, bis die Paarliste leer ist.

Ich habs jetzt nicht ausprobiert. Aber vielleicht bringt der Denkanstoß ja etwas.

Grüße
Onkel Schuppig
 
Zuletzt bearbeitet:
[EDIT]: Gerade ist mir das Brett vom Kopf gefallen. Also ein Paar ist offenbar die Information, dass sich zwei Flächen überdecken.

Ja, genau. Ein Paar AD bedeuted z.B, dass A von D überdeckt wird.

Ein Algorithmus ist wahrscheinlich recht einfach.
Es gibt in der Paarliste mindestens 1 Fläche, die niemals rechter Teil des Paares ist.
Finde diese, zeichne diese und lösche anschließend alle Paare, die diese Fläche enthalten.
Dann das ganze solange wiederholen, bis die Paarliste leer ist.

Hört sich cool an :-) Danke für den anderen Blickwinkel, genau sowas hab ich jetzt gebraucht. Mir gefällt die Idee.
Allerdings glaub ich nicht, dass ich sie wirklich verwenden kann, weil ich dabei immer und immer wieder durch die Liste laufen muss, zum Vergleich. Aber muss erstmal darüber nachdenken,

Ich habs jetzt nicht ausprobiert. Aber vielleicht bringt der Denkanstoß ja etwas.

Grüße

Nochmal danke :)
 
Hmm, wenn es um Schnelligkeit geht:
Statt in der Liste ständig herumzulöschen, sollte man sie lieber unverändert lassen und stattdessen Marker für die bereits verarbeiteten Flächen setzen.
Ist ja alles Integer-Arithmetik. Müsste rattenschnell sein.

Grüße
OS
 
Ok, ich hab ein Problem in dieser Lösung gefunden:

Was ist, wenn wir diesen Fall haben:

B liegt unter A und A liegt unter D, dann sieht die Liste unter Umständen so aus:
L = BA, BD

Wenn ich jetzt B zeichne und wegwerfe und dann alle wegwerfe, in denen B vorkommt, also BD, dann kann ich weder A noch D zeichnen.
 
Was ja konstant ist: Die Anzahl zu zeichnender Flächen. Zunächst mal zeichnen wir B und markieren B als "gezeichnet". Die leere Paar-Liste (oder die "voll markierte" Paarliste) sagt uns nur, dass keine weiteren Berechnungen zum Thema "Reihenfolge" mehr anstehen.
Ganz zum Schluß geht man die komplette Liste der Flächen durch und zeichnet alle, die noch nicht gezeichnet wurden. Die Reihenfolge von A und D ist ja dann egal.
Also wäre BAD und BDA eine Lösung.
 
OK. Nach dem Algorithmus kommt ja heraus, dass B zuerst gezeichnet werden muss.
Danach sind alle Paare gelöscht.

Im letzten Schritt sind dann noch alle restlichen Flächen zu zeichnen. Für diese ist aber die Reihenfolge dann egal.

PS: Kann man nachts gut über so etwas Schwieriges nachdenken? ;)
 
Onkel Schuppig hat gesagt.:
Ganz zum Schluß geht man die komplette Liste der Flächen durch und zeichnet alle, die noch nicht gezeichnet wurden. Die Reihenfolge von A und D ist ja dann egal.
Also wäre BAD und BDA eine Lösung.
Zum Vergrößern anklicken....

Warum ist die Reihenfolge von A und D egal?

Wenn ich zuerst D zeichne, und dann A, dann liegt A ueber D und das ist nicht richtig.
A muss immer unter D liegen.

Erklaer mir das doch bitte mal Schritt fuer Schritt, wie du dir das vorstellst.
 
Ich beziehe mich hier auf L=(B,A), (B,D).
Es gibt kein Paar (A,D). Ergo gibt es keine Überdeckung von A und D, deshalb darf die Reihenfolge von A und D doch frei gewählt werden, nachdem B gezeichnet ist.
 
Um antworten zu können musst du eingeloggt sein.

Neue Beiträge

Zurück