Punkte im Vektor sortieren, um Konturen zu bilden

Question

Ich habe einen Vektor mit n Zeilen mit xy-Koordinaten von Punkten. Diese Punkte bilden eine Kontur eines gegebenen CAD-Modells. Jetzt möchte ich die Kontur des Modells wiederherstellen. Also habe ich versucht, den Punkt mit der Atan2-Funktion zu sortieren. Dies ist der Code, mit dem ich die Punkte sortiere.

std::sort(matrix.begin(), matrix.end(), sort1); 

matrix.erase(std::unique(matrix.begin(), matrix.end(), compare2),matrix.end()); 

matrix.push_back(std::vector<double>(3, 0)); 

Also zuerst sortiere ich die Punkte in der Vektormatrix. Als Vergleichsfunktion verwende ich diesen Code

bool sort1(vector<double> const& s1, vector<double> const& s2) 
{ 
    return atan2(s1[1],s1[0])<atan2(s2[1],s2[0]); 
} 

Nachdem der Vektor sortiert wurde, ich Duplikate löschen Sie einfach die Größe des Vektors zu reduzieren. Der letzte Schritt besteht darin, den ersten Punkt bis zum Ende des Vektors zurückzudrücken, um die Kontur zu schließen. Für Standardmodelle wie einen Würfel oder einen Ball funktioniert das gut, aber für kompliziertere Modelle funktioniert die atan2-Funktion einwandfrei. Dieses Bild zeigt also die unsortierten Punkte.

Wenn ich den Vektor ich diesen conture als Ergebnis erhalten sortieren war

Mein erster Ansatz, um die atan2 Funktion zu überprüfen, aber es funktioniert gut. Das Problem scheint das Ergebnis der atan2-Funktion zu sein. So Diese Liste zeigt die aktuellen Koordinaten und das Ergebnis der atan2 Funktion

x    y  z  atan2 
-5.44283 -1.94995 0 -2.79758 
-5.36969 -1.93228 0 -2.79617 
-5.33637 -1.92454 0 -2.79547 
-13.15  -4.76500 0 -2.79395 
-5.26308 -1.90750 0 -2.79389 
-5.22970 -1.90005 0 -2.7931 
-5.15626 -1.88364 0 -2.79134 

Wie Sie während der x sehen und y-Koordinate der atan2 ändern bleibt im gleichen Bereich wie die anderen Werte. Für mich ist das das Problem, warum meine Konturen nicht stimmen. Muss ich meiner Sortierfunktion etwas hinzufügen, um die richtigen Ergebnisse zu erhalten?

Eine Idee war, die Koordinaten nicht nur nach atan2 zu sortieren, sondern auch nach der Länge des Vektors zwischen dem Punkt, dem niedrigsten atan2 und allen anderen Punkten. Aber hier ist mein Problem. Ich würde zuerst nach atan2 sortieren und dann wieder nach der Länge sortieren. Der zweite Sortiervorgang würde jedoch das Lochergebnis der ersten Sortierfunktion zerstören.

Answer 1

atan2 wird offensichtlich nicht im allgemeinen Fall helfen. Es ist meistens gut für konvexe Figuren. Betrachten Sie ein schmales Rechteck mit (0,0) innen und einem angrenzenden Rechteck und versuchen Sie, ihre Punkte nach atan2 zu sortieren. Haben Sie versucht, einen Punkt in der Menge zu malen und dann nach dem nächsten noch nicht bemalten Punkt als Iterationsschritt zu suchen?

Answer 2

Wenn Sie mit Kurven zu tun sind nur dann würde ich vorschlagen, folgenden Algorithmus zu verwenden:

1. definieren Winkelbereich R
2. Ausgangspunkt nehmen A, markieren Sie es als besucht
3. A Punkt B, als besucht markieren
4. Berechne th e Richtung durch den Vektor gebildet [A, B]
5. Nähe zu B Finden unvisited Punkt C in Winkelbereich R und markieren ihn
6. Go besucht zu Schritt 4 mit B als A und C als B

Dies ist keine ultimative Lösung, aber es sollte in der Lage sein, einfache Kurven und einige Polygone zu finden. Mit einem größeren Winkelbereich R können Sie mehr gekrümmte Linien annähern.