Edgebreaker Algorithmus

[Maradatscha]

Ich versuche mich gerade an der dekompression mit dem edgebreaker. Dazu habe ich mir den String aus der übung c5_2_ex5_t_sol.pdf genommen und versuche ihn zu dekomprimieren. Das klappt auch ganz gut bis zu der Stelle an der Knoten nummer 14 erzeugt wurde. Daraufhin folgt im string ein R. Man muss also eigentlich einen neuen Randknoten hinzufügen. Im Ursprungsnetz ist knoten 14 mit knoten 15 verbunden. Woher bekomme ich diese Information?

Der string sieht folgendermassen aus (in Klammern ist die Stelle an der es kracht):
CCRRCSCRCRRRLRERRCRCRRC(R)RLLLE

Auf der Website der Autoren findet man, dass man zusätzlich zum string noch die anzahl der inzidenten Dreiecke zu dem ersten Knoten speichert. Was man damit anfaengt weiss ich aber nicht. (http://www.gvu.gatech.edu/~jarek/edgebr ... ormat.html)

Habe ich was grundsätzliches vergessen?

[MatthiasBein]

Hi,

der Rand des Netzes ist bei der Dekompression bekannt. Das ist der erste Schritt (Foliensatz 10, Folie 27). Man weiß also wieviele Randknoten es gibt und es ist klar, dass die Vertices aufsteigend sortiert den Rand bilden. Bei den inneren Vertices muß man aufpassen, wann sie wie erstellt wurden, also die Schälung des Netzes im Kopf behalten, um die Verbindungen korrekt auszuführen. Nur als Randbemerkung, dein Problem ist ja ein anderes.

Eigentlich passiert bei Dreieck 25 CCRRCSCRCRRRLRERRCRCRRC(R)RLLLE das gleiche wie bei Dreieck 3 CC(R)RCSCRCRRRLRERRCRCRRCRRLLLE.

Dreieck 25:
aktuelle Gate ist Kante 21 -> 14
R Operation: gegenüberliegender Knoten ist Nachfolger vom Gate, also Vertex 15

Dreieck 3:
aktuelle Gate ist Kante 18 -> 1
R Operation: gegenüberliegender Knoten ist Nachfolger vom Gate, also Vertex 2

Die Anzahl der inzidenten Dreiecke werden auch nicht in jedem Format gespeichert und ist für die Dekompression mit dem String auch unwichtig.

Hoffe das konnte helfen.
Gruß Matthias

[Maradatscha]

Danke!