Graham scan



  • Hallo Forum,

    Mein aktuelles Projekt ist die Umsetzung des Graham scan Algorithmus, die Sortierung der Einzelpunkte nach dem Winkel funktioniert soweit, wobei die Punkte dabei in eine doppelt verkettete Liste eingetragen werden. Das löschen der nicht konvexen Eckpunkte funktioniert allerdings nicht Ordnungsgemäß und frage deshalb hier ob jemand den Fehler in meiner Implementierung finden könnte.

    Definition der Listeneinträge:

    template <class Datentyp> struct Dpointer //definiert die pointerbasierte suchliste
    {
           Dpointer* nächster;
           Dpointer* letzter;
    
           unsigned int refid;
           Datentyp x;
           Datentyp y;
           Datentyp abstand;
           Datentyp winkel;
    
           Dpointer()
           {
                   letzter = 0;
                   nächster = 0;
    
                   refid = 0;
                   x = 0;
                   y = 0;
                   abstand = 0;
                   winkel = 0;
           }
    
    };
    

    Dementsprechend befindet sich nach der Sortierung diese Belegungssituation in der verketteten Liste wieder:

    erstes Element[pivot]->nächster[kleinster winkel rel pivot]->nächster[zweitkleinster rel pivot...]->usw

    um nun aus dieser liste die konvexe Hülle zu erhalten durchlaufe ich diese Liste und verändere nebenbei einen array in das die konvexe Hülle eingetragen werden soll[indices die die punkte der konvexen Hülle adressieren] (wird direkt zurückgegeben)

    //Dpoint = sortierte Liste (erster Listeneintrag)
    //Anzahl = Anzahl der sich in der Liste befindlichen Punkte
    					unsigned int* returnindices = new unsigned int[anzahl + 1]; //zurückzugeben
    					Datentyp* konvexpunkte = new Datentyp[anzahl * 2]; //punktearray in das die konvexe Hülle ausgebildet werden soll 
    
    					unsigned int* pointerint = returnindices + 2;//erster unbeschriebener index
    					Datentyp* konvexpointer = konvexpunkte + 4; //erster unbeschriebener Punkt in der konvexen Hülle
    
    					Datentyp* iterierer = konvexpunkte;
    					Datentyp* iterierer2 = konvexpunkte + 2;		
    					Dpointer<Datentyp>* iterierer3 = Dpoint->nächster->nächster;
    					//definiert ein Punkttripel über das die zugehörigkeit zur konvexen Hülle bestimmt wird
    
    					#pragma region Daten aus der Liste in ein array umschichten
    
    					returnindices[0] = Dpoint->refid;
    					returnindices[1] = Dpoint->nächster->refid;
    
    					konvexpunkte[0] = Dpoint->x;
    					konvexpunkte[1] = Dpoint->y;
    					konvexpunkte[2] = Dpoint->nächster->x;
    					konvexpunkte[3] = Dpoint->nächster->y;
    
    					#if 1
    					unsigned int sucher = 2; //durchlaufene Punkte
    					while (sucher != anzahl)
    					{			
    
    						while ((*iterierer2 - *iterierer) * (iterierer3->y - *(iterierer + 1)) - (iterierer3->x - *iterierer) * (*(iterierer2 + 1) - *(iterierer + 1)) >= 0) //letzte einträge solange löschen bis eine konvexe ecke gefundne wird
    						{
    							//pointer versetzen (zu löschende Ecken werden später überschrieben)
    							pointerint--;
    							konvexpointer -= 2;
    							//die Vektoren A und B (das ende des konvex-Stacks folgt früher)
    							iterierer2 -= 2;
    							iterierer -= 2;
    						}
    						//punktid eintragen
    						*pointerint = iterierer3->refid;
    						pointerint++;
    						//punkte eintragen
    						*konvexpointer = iterierer3->x;
    						konvexpointer++;
    						*konvexpointer = iterierer3->y;
    						konvexpointer++;
    
    						//nächsten punkt verarbeiten
    						iterierer += 2;
    						iterierer2 += 2;
    						iterierer3 = iterierer3->nächster;			
    						sucher++;
    
    					}
                               *pointerint = Dpoint->refid;//vom letzten Eintrag wieder zum ersten (Polygon schliesen)
    

    über Hilfe wäre ich wirklich dankbar ich stehe nämlich schon seit 2 Wochen auf dem Schlauch.

    PS: Könnte auch sein das der Algorithmus an sich schon von der Quelle aus nicht funktionsfähig ist was ich aber eigentlich ausschliesen würde (hier die Quelle( PDF)

    http://www.google.de/url?sa=t&rct=j&q=&esrc=s&source=web&cd=3&ved=0CDYQFjAC&url=http%3A%2F%2Fwwwisg.cs.uni-magdeburg.de%2Fag%2Flehre%2FWS0304%2FThICV%2Fslides%2Fgraham.pdf&ei=uEORUP78PI3NswbH84CIBw&usg=AFQjCNEQnrl4wc3tH2ru9coZGrzhlT0CBw&sig2=AxblcKkz9gvTTXDqgbp8HQ&cad=rja)



  • Warum programmierst du dir eine verkettete Liste selbst?



  • Weil es mich interessiert hat und ich mir dachte das Insertionsort (Ich weiß das geht noch schneller aber war erstmal einfacher zu implementieren) mit einer verketteten Liste bei größeren Datenmenegen effizienter ist, da keine Elemente im Array hin und her kopiert werden müssen. Außerdem geht es mir nicht darum das man sich die Arbeit auch von einer Api abnehmen lassen könnte, ich versuche möglichst viel selber zu implementieren.


  • Mod

    c++neuling2 schrieb:

    und ich mir dachte das Insertionsort (Ich weiß das geht noch schneller aber war erstmal einfacher zu implementieren) mit einer verketteten Liste bei größeren Datenmenegen effizienter ist, da keine Elemente im Array hin und her kopiert werden müssen.

    Daher hat std::list auch eine eigene sort-Methode 🙂 .

    'Tschuldigung, aber für mehr Hilfe als dumme Bemerkungen habe ich gerade keine Zeit.



  • ok gut, vergesst die doppelt verkettete Liste und achtet nur auf den Algorithmus im zweiten Codeblock. 😉 Is halt so wie es ist ich mach mir gerne mehr Arbeit als nötig.

    PS: abgesehen davon hab ichs nachgeprüft die Liste liegt letztendlich korrekt vor.



  • Durch die Verwendung anstaendiger Datenstrukturen wie beispielsweise eines Stacks wird der ganze Algorithmus uebersichtlicher. Herzstueck dabei ist eine Funktion left_of, sie gibt an, ob ein Punkt links von zwei weiteren Punkten liegt. Hast du diese bereits?


Log in to reply