Ramer-Douglas-Peucker Pfadvereinfachungsalgorithmus
Ich habe nach der Lektüre des Artikels hier einen Pfadvereinfachungsalgorithmus implementiert:
Es hat für mich ziemlich gut funktioniert, um eine optimierte Level-Geometrie für mein Spiel zu generieren. Aber ich benutze es jetzt, um Pfadpfade zu bereinigen und es hat einen seltsamen Randfall, der kläglich versagt.
Hier ist ein Screenshot, der funktioniert - den Pfad vom roten Kreis zum blauen Kreis optimiert. Die schwache grüne Linie ist der a * -Ausgang, und die hellere weißliche Linie ist der optimierte Pfad.
Und hier ist ein Screenshot davon:
Hier ist mein Code. Ich habe den ObjC-Code aus dem Artikel nach c ++
angepasst Hinweis: vec2fvec ist ein std::vector< vec2<float> > und 'real' ist nur ein typedef float.
Ich bin wirklich ratlos, was falsch läuft. Mein spidery Sinn sagt, dass es in den std :: copy Calls ist ... Ich muss in einigen Fällen Müll kopieren.
BEARBEITEN: Ich habe den Algorithmus umgeschrieben, indem ich jegliche Verwendung von Iteratoren und std :: copy und dergleichen weglasse. Es schlägt immer noch genauso fehl.
%Vor%1 Antwort
Ich kann keine Fehler in Ihrem Code finden.
Einige Dinge zu versuchen:
- Fügen Sie einige Debug-Druckanweisungen hinzu, um zu überprüfen, welche
maxDistim Fehlerfall vorliegt. Es sollte wirklich niedrig sein, aber wenn es hoch hinausgeht, dann weißt du, dass es ein Problem mit deinem Entfernungscode für den Linienabschnitt gibt. - Überprüfen Sie, ob der Pfad, den Sie sehen, mit dem Pfad übereinstimmt, den Ihr Algorithmus zurückgibt. Wenn nicht, dann stimmt vielleicht etwas mit der Pfaddarstellung nicht? Vielleicht ein Fehler, wenn der Pfad nur zwei Punkte hat?
- Überprüfen Sie, ob Ihr Eingabepfad dem entspricht, was Sie erwarten, indem Sie alle seine Koordinaten am Anfang des Algorithmus ausdrucken.
Es sollte nicht zu lange dauern, um die Ursache des Problems zu finden, wenn Sie nur ein wenig nachforschen. Nach ein paar Minuten ist das Anschauen von Code ein sehr schlechter Weg zum Debuggen.