Sortieren/Verketten/Anordnen nach 2 Kriterien?

[Marco]

Hi,
ich habe Linien, die zusammen die Begrenzung ein Polygon ergeben. Diese Linien habe ich mit Anfangs- und Endpunkt erfasst.
Da ich damit einen path in SVG zeichnen will, benötige ich aber nur die Eckpunkte in der richtigen Reihenfolge.
D.h. ich muss die Linien so ordnen, dass auf den Endpunkt einer Linie immer der Beginn einer neuen folgt.
Wie kann ich das erreichen? Ich habe es bisher so versucht, dass ich die Punktepaare jeder Linie in einen Hash gepackt habe (key:Anfangspunkte, value:Endpunkte - z.B.: key:"35,70" value:"80,45").

Meine Idee ist, von einem erstbesten Punkt (key) auszugehen und von da aus, mit dessen value zu der nächsten Linie zu "springen" - deren key-Wert ist ja = dem value-Wert des Vorgängers.
Der key-Wert soll dabei immer an ein Array gehängt werden und der bearbeitete Eintrag im Hash gelöscht werden.
Wenn das klappen würde, wäre der Hash am Ende leer und das Array wäre mit den Eckpunkten des Polygons in der richtigen Reihenfolge gefüllt.

Soweit die Idee. An der Ausführung scheiter ich i.A. und hab fast das Gefühl, ich hätte mich verrannt. Googlen hilft auch nicht, da ich nicht weiß, welche Suchbegriffe da passen. (Sortieren ist es ja nicht nur)

Kann mir mal jemand auf die Sprünge helfen?

MfG
Marco.

P.S. Bin mir ja nicht mal sicher, in welchen Themenbereich das hier gehört. ;-)

[Matti Maekitalo]

use Mosche;

Meine Idee ist, von einem erstbesten Punkt (key) auszugehen und von da aus, mit dessen value zu der nächsten Linie zu "springen" - deren key-Wert ist ja = dem value-Wert des Vorgängers.
Der key-Wert soll dabei immer an ein Array gehängt werden und der bearbeitete Eintrag im Hash gelöscht werden.
Wenn das klappen würde, wäre der Hash am Ende leer und das Array wäre mit den Eckpunkten des Polygons in der richtigen Reihenfolge gefüllt.

Das hört sich prinzipiell nicht falsch an. Poste mal deinen bisherigen Code, damit man da drüberschauen kann.

Vielleicht hast du aber auch eine Möglichkeit, in der Produktionsversin deines Programmes die Eckpunkte zu speichern, anstatt jedesmal diese Umformungen durchzuführen.

use Tschoe qw(Matti);

[Marco]

Das hört sich prinzipiell nicht falsch an. Poste mal deinen bisherigen Code, damit man da drüberschauen kann.

Tja, wenn der Frust tief sitzt, schreibt man einfach sein Problem auf und belästigt andere Leute damit. Und schon schafft man selbst wieder einen Schritt... ;-) Ich hab mich noch einmal in die Sache verbissen und eine (Vor-)Lösung gefunden. Da sind die Schnipsel auch schon:

#$ecken{$punkta} = $punktb;
while ( ($pa,$pe) = each %ecken ) { #Array mit keys des Hashes füllen um über das Array iterieren zu können.
    push @startpunkte, $pa;
}

for (@startpunkte) {
    print "M";               #Path starten
    do {
        $p_a=$_;
        print "$_ ";         #Punkte ausgeben
        $_ = $ecken{$_};     #Eckentausch
        delete $ecken{$p_a}; #bearbeitete Eckpunkte löschen
 #Array löschen und neu füllen mit dem nun kleineren Hash
 #(sonst werden die in @startpunkte noch folgenden Arrayelemente
 #einmal mit ausgegeben, obwohl kein zugehöriger Endpunkt im Hash mehr ist.
        @startpunkte='';
        while ( ($pa,$pe) = each %ecken ) {
        push @startpunkte, $pa;
    }
    } while defined;
    print "Z ";              #Path schließen

So. Ich sag gleich mal vorneweg, dass ich KEIN Programierer bin, sondern ein autodidaktischer try-and-error-Masochist mit Lama-Buch ;-) Also vereiß meinen Stil nicht so hart. Ich leide so schon genug. ;-)

Vielleicht hast du aber auch eine Möglichkeit, in der Produktionsversin deines Programmes die Eckpunkte zu speichern, anstatt jedesmal diese Umformungen durchzuführen.

Geht vorerst leider nicht. Die Eckpunkte werden erstmal serverseitig generiert um unnützen Traffic zu vermeiden. Ausserdem müsste ich sonst den ganzen Kram in Javascript vom Client machen lassen. Erstens hab ich aber gerade mal Grundkenntnisse in Javascript, zweitens weiß ich nicht, wie dann die Geschwindigkeit des Bildaufbaus wäre und drittens ist noch nicht vollkommen geklärt, ob ein Client immer die gesamten Daten bekommen soll/darf.

(Ich habe auch mal probeweise die fragliche Grafik aus den Einzel-Polygonen aufgebaut (14400 Stück mindestens)... Mit nem PIII-600 dauert es über eine Minute...)

MfG
Marco.

P.S. Aus den Eckpunkten im fraglichen Hash entsteht meist nicht nur ein Polygon/Path, sondern mehrere sind möglich. (wie z.B. lauter Inseln auf einer Meereskarte)

[Erwin]

Harte Nuss ;-)

try this:

use strict;

hier stehen die Linien

my %draw = (
 "10,10","20,10",
 "20,10","20,20",
 "20,20","10,20",
 "10,20","5,15",
 "5,15","10,10",
);

my $start = "20,20";
print "$start \n";
ab($start);

Rekursion

sub ab{
 my $key = shift;
 my $k;
 foreach $k( keys %draw ){
  if( $draw{$key} eq $k ){
   print "$k \n";
   delete $draw{$key};
   ab($k);
  }
 }
}

Erwin